Очередная статья про wc

А ghc (вроде-бы) умеет в Cкомпилировать? Весьма вероятно этого будет достаточно.

Очередная статья про wc

1. Для полноты картины в статье конечно не хватает отсылки к не-наивной переносимой реализации (aka "С" наносит ответный удар"), в том числе замера её скорости на вашей машине. На всякий — popcount/Hamming_weight в там нет намеренно ради переносимости.
2. О том что производительность "на SIMDах" будет в пределах memory bandwidth было заявлено примерно сразу. Тем не менее, соглашусь что многим это не очевидно и лучше "показать на пальцах".
3. Вы еще раз поменяли условия/требования (выбросили табуляции и т.п.), чем еще больше понизили градус смысла в этом флешмобе бенчмарков.
   В контрольных цифрах должно быть lines 15000000, words 44774631, chars 1871822210.
4. Другой CPU, другой компилятор, другая ОС. Поэтому недостаёт результатов работы других реализаций в ваших условиях.
5. По информации 0xd34df00d Хаскель быстрее наивной С-реализации (я имею в виду комментарий "Но ведь не обходит. 2 секунды для С против 1.45 для хаскеля"). Если я правильно понимаю, причина в достаточно простой "механике": ghc (хаскель-компилятор) немного раскатывает вот этот цикл (aka loop unrolling). Точнее говоря, не раскатывает, а не полностью сворачивает (aka fold), и такой цикл отрабатывает быстрее. Предлагаю всем самостоятельно оценить насколько это определяющий критерий победы, с учетом того что clang с -march=native заставляет наивный код работать быстрее хаскеля.
   В моём понимании C-цикл под спойлером должен работать "со скоростью хаскеля". Хорошо-бы кто-то проверил (достаточно вставить этот кусок в код по первой ссылке и сравнить скорость с Хаскель-реализацией на одной машине).

Заголовок спойлера

for (size_t i = 0; i < bytes; i += 8) {
    unsigned char c0 = text[i];
    unsigned char c1 = text[i+1];
    unsigned char c2 = text[i+2];
    unsigned char c3 = text[i+3];
    unsigned char c4 = text[i+4];
    unsigned char c5 = text[i+5];
    unsigned char c6 = text[i+6];
    unsigned char c7 = text[i+7];

    result.lines += c0 == '\n';
    result.lines += c1 == '\n';
    result.lines += c2 == '\n';
    result.lines += c3 == '\n';
    result.lines += c4 == '\n';
    result.lines += c5 == '\n';
    result.lines += c6 == '\n';
    result.lines += c7 == '\n';

    _Bool x0 = (c0 != ' ') && (c0 - 9 > 4);
    _Bool x1 = (c1 != ' ') && (c1 - 9 > 4);
    _Bool x2 = (c2 != ' ') && (c2 - 9 > 4);
    _Bool x3 = (c3 != ' ') && (c3 - 9 > 4);
    _Bool x4 = (c4 != ' ') && (c4 - 9 > 4);
    _Bool x5 = (c5 != ' ') && (c5 - 9 > 4);
    _Bool x6 = (c6 != ' ') && (c6 - 9 > 4);
    _Bool x7 = (c7 != ' ') && (c7 - 9 > 4);

    result.words += x0 && !prev;
    result.words += x1 && !x0;
    result.words += x2 && !x1;
    result.words += x3 && !x2;
    result.words += x4 && !x3;
    result.words += x5 && !x4;
    result.words += x6 && !x5;
    result.words += x7 && !x6;
    prev = x7;
  }~~~

<!--</spoiler>-->

Почему базы данных NoSQL — плохое решение для современных приложений

Сова, Глобус, MemSQL

Побеждая C двадцатью строками Haskell: пишем свой wc

"С" наносит ответный удар ;)

Внутри примерно то (или чуть больше), что (теоретически, в моем представлении) делает ghc в ходе оптимизаций перед бэкэндом, но только на C (без налога на абстракцию) и поэтому быстрее. Суть идеи описана в другом ответе.

Примерно 20 строк, примерно такие же результаты: wc на Elixir

Работает

Примерно 20 строк, примерно такие же результаты: wc на Elixir

Основная задержка из-за зависимости по данным при подсчете слов, т.е. состояние всегда зависит от текущего и предыдущего символов (пробел или не пробел).
Эту зависимость нужно сузить, позволив максимальному кол-ву операций выполняться параллельно. Сделать это проще всего следуя стратегии map-reduce.

Каждый символ следует рассматривать как вектор, перемещающий состояние счетчика в некотором пространстве. Сложение этих векторов не коммутативно, т.е. результат зависит от порядка. Поэтому следует отображать эти вектора в другое "удобное" пространство, в котором их проекции легко складывать. Затем нужно будет применить результат к состоянию анализатора, т.е. отобразить результат сложения в инкремент счетчика слов.

На `C` это выглядит примерно так

typedef struct {
  uint16_t m[4];
} hyper_t;

static hyper_t sym2hyper[65536];
static uint8_t hyper2value[512];

static void build_hyper(void) { 
  /* подготовительная магия наполнения  sym2hyper и hyper2value */ 
}

static unsigned map(const unsigned char *text, size_t i, size_t n) {
  return sym2hyper[*(uint16_t *)(text + i + n * 2)].m[n];
}

static unsigned reduce(unsigned prev, 
                       unsigned hyper_a, unsigned hyper_b,
                       unsigned hyper_c, unsigned hyper_d) {
  return prev + hyper_a + hyper_b + hyper_c + hyper_d;
}

static unsigned apply(unsigned hyper) {
  result.lines += hyper & 15;
  result.words += hyper2value[hyper >> 4];
  return /* состояние для следующей итерации */ (hyper >> 8) & 16;
}

static unsigned process_chunk(const unsigned char *text,
                              const size_t bytes,
                              unsigned prev) {
  result.chars += bytes;
  for (size_t i = 0; i < bytes; i += 8)
    prev = apply(reduce(prev, 
                        map(text, i, 0), 
                        map(text, i, 1), 
                        map(text, i, 2),
                        map(text, i, 3)));
  return prev;
}

Этот код выдает результат за 0.55 секунды, т.е. примерно вдвое быстрее чем наивная версия авто-векторизованная clang-ом с -march=native. Но пока я не уверен в его полной корректности, ибо нужно доделать "магию" (уже лень, но буду сопротивляться).

Примерно 20 строк, примерно такие же результаты: wc на Elixir

А, вы невнимательно читали статью! -march=native использовалься только для сишного wc (потому что сишный wc собирается emerge'м, а менять флаги ради одного этого теста было лень, тем более, что этот флаг даёт фору сишному коду, а не хаскель-версии).

Вы переоцениваете мои интеллектуальные резервы — просто просмотрел "по-диагонали" ;)
Если серьезно, то я не особо заморачивался с -march=native, а следовал простому сценарию: есть железка, перем от неё максимум, но без дополнительных усилий.

Эта оптимизация ломает наблюдаемое поведение: в итоге код на более ранних CPU запускаться не сможет. Например, на моей основной машине i7 3930k без AVX2, поэтому от wc без AVX2 или AVX512 толку там нет.

Хм, а какая исходная точка для образцового поведения?
Вы сделали сравнение с wc, предлагаю начать с i486 в 89-году.
Тогда ваш код "ломает поведение", ибо не компилируется из-за отсутствия Haskell ;)
И на e2k ваш код тоже "фатально меняет поведение", ибо не компилируется.

В целом, наличие/отсутствие AVX это локальные плюсы/минусы, как и x86_64.
Ведь если вам свет временно отключат, то остальные не должны тоже сидеть в темноте?

В любом случае, первое "изменение поведения" — это переход на только-ASCII, в второе — отказ от подсчета "печатной" длины строк (ведь без модификации кода нельзя получить все что умеет wc).

Плюс, не могу не отметить интересный факт: вы почему-то считаете нечестным сравнивать хаскелевскую версию с исходной сишной, которая внутри делает больше вычислений (но имеет такой же наблюдаемый результат), но не считаете нечестным одну из версий собирать с -march=native, что наблюдаемый результат таки меняет.

Нет, уж извините.

Во-первых, кто начал весь этот флеш-моб сравнения теплого с мягким и кликбейтом "в 10 раз"?

Во-вторых, я ни разу не сказал что сравнивать SIMD и не-SIMD версии честно.
Собственно я не смотрел на последствия -march и не знал что clang замутил авто-векторизацию, ибо увиденное соотношения производительности было ожидаемым. Выяснять последствия -march я стал по информации в одного из ваших ответов.

Суть же в том, что тут нет и не может быть рационального сравнения, ибо:

• с одной стороны компилятор haskell со специфической оптимизацией map-конструкций (без этого он бы бесполезен), но с march-лоботомией.
• а с другой стороны наивный C-код, но использующий чуть больше возможностей CPU.

Вы не смотрите рекламу во время разработки? Непорядок

У телеком-операторов есть экзистенциальная мечта перестать быть "просто трубой" для доставки данных, и вот они все пытаются изо-всех-сил. Эта не просто "забастовка водопровода", а буквально стратегия развития бизнеса, воплощающаяся в самые разнообразные формы.

Примерно 20 строк, примерно такие же результаты: wc на Elixir

Что си, что хаскель можно попробовать еще ускорить. Можно попробовать 16бит табличку, можно попробовать читать по 4-8 байт и разбираться с прочитанным в регистре (для парсинга http заголовков это помогало, односимвольные слова возможно ухудшит).

Немного не так. Начало правильное, но не хватает главного. Если интересно, могу объяснить как (на самом деле чисто функциональный подход, т.е. при правильном алгоритме и хорошем хаскель-компиляторе реализации будут работать быстрее и с одинаковой скоростью).

Примерно 20 строк, примерно такие же результаты: wc на Elixir

Вот примерно на дроздофилах я и зарабатываю. Поэтому "прорывными" (именно в кавычках) называю бенчмарки где хаскель оказывается в 10 раз быстрее С. Но чтобы не было недопонимания гляньте дисклаймер в моем первом комментарии ко всему этому флеш-мобу.

Примерно 20 строк, примерно такие же результаты: wc на Elixir

Не о чем жалеть, вы все совершенно точно сформулировали "Ниже вы увидите некоторые трюки, которые я использовал… просто хотел убедиться, что на финише мы не отстанем от победителей на круг.".
Своим комментарием я нисколько не хотел задеть вас или придраться к вашей статье.
Тем не менее, достаточно много "бенчмарков" со странными "прорывными" результатами. Строка "Желающим докопаться до сути..." относится именно к ним.

Примерно 20 строк, примерно такие же результаты: wc на Elixir

Неэквивалентное сравнение из-за -march=native (как вы дальше и пишете). Я считаю, что было бы честно упомянуть, что без этой опции вариант на С медленнее (а хаскель собирается без нее или какого-либо ее эквивалента).

Хм, а где вы увидели какую-либо мою нечестность?

1. В вашей статье было упоминание про Gentoo и сборку -march=native, а также была таблица, в которой в том числе были результаты при использовании LLVM. Поэтому был использован clang и опции -Ofast -march=native, что общепринято для бенчмарков. Эти опции были сразу приведены вместе с первым исходным кодом и результатами.

   
   

2. Потом вы сами собрали и запускали C-версии как без -march=native, так и используя gcc. Получив при этом другие результаты.

   
   

3. Итого: результат наивной С-реализации зависит от компилятора и опций оптимизации/кодогенерации. Что абсолютно ожидаемо, и в точности (как мне кажется) отражено в моем первом комментарии выше.

   
   

Кроме этого, слабость компилятора Haskell в отношении -march=native не должна является поводом отказа от этой оптимизации.

Не в разы, а менее чем в два раза (clang с -march=native на моей машине с вашим исходником отрабатывает за 0.9 секунд, что менее чем в два раза быстрее искомых 1.45).

По-факту результаты получены на разных машинах с разными версиями компиляторов. У меня цифры другие. На машине с AVX512 или на E2K скорость C-реализации будет еще больше.

Примерно 20 строк, примерно такие же результаты: wc на Elixir

С-версии собранные разными компиляторами с разными опциями дают разную скорость.
Хаскель-версии с поддержкой pipe или только с mmap тоже показывают разный результат.
Автор C-реализации утверждает что быстрее всего его C-вариант собранный clang-ом с -march=native.
А у автора хаскель-версии его вариант быстрее чем C-версия без -march=native.
При этом машины разные, с разными CPU.

Каждый может скомпилировать, запустить, увидеть результаты и показать их при желании.
Какие еще пруфы?

Примерно 20 строк, примерно такие же результаты: wc на Elixir

Каких именно подтверждений и каких именно заявлений?

Примерно 20 строк, примерно такие же результаты: wc на Elixir

Похоже флеш-синдром заразен ;)

Тем не менее, в комментариях к "первой" статье есть пара заслуживающих упоминания моментов:

1. Оригинальная утилита wc делает больше чем было реализовано на Хаскеле. Можно думать разное про авторов wc, но оптимизацией скорости они точно не заморачивались и поэтому мерятся с болезным wc джентльменам не к лицу. В целом, как было отмечено, такой "бенчмаркинг" без ТЗ где-то между бредом и жульничеством.
2. Функционально-равнозначная коду на Haskell наивная реализация на C может выдать результат в разы быстрее. Но тут мнения несколько разошлись, в частности:
   
   • Нет единого мнения какой компилятор C и с какими опциями оптимизации/кодогенерации следует использовать. Причина разногласий видимо в том, что clang с опциями -Ofast -march=native выполняет (не идеальную, но все же) авто-векторизацию, и в результате реализация на C оказывается в разы быстрее. А как дела с автовекторизацией у компилятора Хаскеля и какой именно набор инструкций он задействует в общем случае (пока) не ясно.
   • У обоих авторов (реализаций на C и на Хаскеле) быстрее работает собственный вариант, а верификации результатов третьими лицами не было.

Желающим докопаться до сути и составить собственно мнение стоит ознакомиться с топиками на Hacker News (1, 2), где уже звучали обвинения в FUD и во введении в заблуждении относительно скорости в адрес евангелистов Хаскеля и еже с ним.

Побеждая C двадцатью строками Haskell: пишем свой wc

На всякий, в коде есть опечатка.
Вместо r.words += now && prev должно быть r.words += now && !prev т.е. пропущен '!'.

Побеждая C двадцатью строками Haskell: пишем свой wc

Выше был вариант с поправленными не-пробелами (без принципиальных изменений в скорости).
Здесь вариант с поддержкой чтения из pipe и нескольких файлов (включая "-" как синоним stdin).
Чтение из pipe добавляет 1% к времени работы.

naive_wc.c (с пайпами и блекджеком)

#include <errno.h>
#include <fcntl.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <time.h>
#include <unistd.h>

struct {
  size_t chars, words, lines;
} static result;

static _Bool process_chunk(const unsigned char *text, const size_t bytes,
                           _Bool prev) {
  result.chars += bytes;
  for (size_t i = 0; i < bytes; ++i) {
    result.lines += text[i] == '\n';
    _Bool now = text[i] != ' ' && text[i] - 9 > 4;
    result.words += now && !prev;
    prev = now;
  }

  return prev;
}

static int process_fd(int fd) {
  off_t length = lseek(fd, 0, SEEK_END);
  if (length >= 0 && length <= INTPTR_MAX) {
    void *ptr = mmap(NULL, (size_t)length, PROT_READ, MAP_PRIVATE, fd, 0);
    if (ptr == MAP_FAILED) {
      perror("mmap");
      return EXIT_FAILURE;
    }
    process_chunk((const unsigned char *)ptr, (size_t)length, 0);
    munmap(ptr, length);
    return EXIT_SUCCESS;
  }

  if (length < 0 && errno != ESPIPE) {
    perror("leeek");
    return EXIT_FAILURE;
  }

  _Bool state = 0;
  ssize_t chunk;
  for (;;) {
    unsigned char buf[65536];
    chunk = read(fd, buf, sizeof(buf));
    if (chunk < 1)
      break;
    state = process_chunk(buf, chunk, state);
  }

  if (chunk < 0) {
    perror("read");
    return EXIT_FAILURE;
  }
  return EXIT_SUCCESS;
}

int main(int argc, const char *argv[]) {
  int rc = 42;
  if (argc > 1) {
    for (int i = 1; i < argc; ++i) {
      int fd =
          (strcmp(argv[i], "-") == 0) ? STDIN_FILENO : open(argv[1], O_RDONLY);
      if (fd < 0) {
        perror("open");
        return EXIT_FAILURE;
      }
      rc = process_fd(fd);
      close(fd);
      if (rc != EXIT_SUCCESS)
        break;
    }
  } else
    rc = process_fd(STDIN_FILENO);

  struct timespec ts = {0, 0};
  if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts))
    perror("clock_gettime(CLOCK_PROCESS_CPUTIME_ID)");

  if (rc == EXIT_SUCCESS)
    printf("lines %zu, words %zu, chars %zu\ntook %.6f seconds\n", result.lines,
           result.words, result.chars, ts.tv_nsec * 1e-9 + ts.tv_sec);
  return rc;
}

Побеждая C двадцатью строками Haskell: пишем свой wc

И какую работу она не выполняет?

Штатный wc подсчитывает "печатную длину" строк, но выводит только если попросили опциями. Да, тупо делается лишняя работа, ибо никто не заморачивался.
Тем не менее, при "сравнении скоростей" не корректно сравнивать реализации с и без этой "особенности развития".

Вариант-то отличный, только что там от С остаётся? Аллокация регистров, пожалуй, да и всё?

Ну много что остается (типы данных, циклы).
Тем не менее, разве должна быть какая-то "пятая нога"?

Побеждая C двадцатью строками Haskell: пишем свой wc

Поправил. Отрабатывает за 1.09 секунды, т.е. чуть медленне чем первый вариант. Но на пропорцию с Хаскель-вариантом это примерно не влияет.

naive_wc.c

#include <fcntl.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <time.h>
#include <unistd.h>

typedef struct {
  size_t chars, words, lines;
} wc_result;

static wc_result process(const unsigned char *text, const size_t bytes) {
  wc_result r = {bytes, 0, 0};
  _Bool prev = 0;
  for (size_t i = 0; i < bytes; ++i) {
    r.lines += text[i] == '\n';
    _Bool now = text[i] != ' ' && text[i] - 9 > 4;
    r.words += now && prev;
    prev = now;
  }
  return r;
}

int main(int argc, const char *argv[]) {
  int fd = STDIN_FILENO;
  if (argc > 1) {
    fd = open(argv[1], O_RDONLY);
    if (fd < 0) {
      perror("open");
      return EXIT_FAILURE;
    }
  }

  off_t length = lseek(fd, 0, SEEK_END);
  if (length < 0 || length > INTPTR_MAX)
    return EXIT_FAILURE;

  const void *ptr = mmap(NULL, (size_t)length, PROT_READ, MAP_PRIVATE, fd, 0);
  if (ptr == MAP_FAILED) {
    perror("mmap");
    return EXIT_FAILURE;
  }

  wc_result r = process((const unsigned char *)ptr, (size_t)length);

  struct timespec ts = {0, 0};
  if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts))
    perror("clock_gettime(CLOCK_PROCESS_CPUTIME_ID)");

  printf("lines %zu, words %zu, chars %zu\ntook %.6f seconds\n", r.lines,
         r.words, r.chars, ts.tv_nsec * 1e-9 + ts.tv_sec);
  return EXIT_SUCCESS;
}

Побеждая C двадцатью строками Haskell: пишем свой wc

Ниже C-вариант который отрабатывает в 3-4 раза быстрее, без магии.