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

Всем добрый день.


Недавно на Хабре появилась статья Побеждая C двадцатью строками Haskell: пишем свой wc от @0xd34df00d. Автор, известный своей симпатией к функциональному программированию, реализовал на Хаскеле аналог утилиты wc, и подверг его оптимизации, получив в результате вариант, работающий более чем в 7 раз быстрее стандартной юниксовой утилиты.


Будучи добросовестным "бенчмаркером", 0xd34df00d в конце статьи указал, что его вариант работает с сильно упрощенным ТЗ по сравнению с оригиналом (например, был проигнорирован Unicode), и следовательно его превосходство в производительности ничего по факту не означает. Но ясное дело, что несмотря на это формат статьи породил множество споров в комментариях (да я и сам часто не читаю дальше заголовка, чего греха таить). Под статьей yleo привел результаты тестирования написанного им тривиального решения на C (под упрощенное условие), показав, что даже наивная C-реализация обходит оптимизированный Haskell-вариант. После этого господа принялись кидаться друг в друга какомментариями, в которых придирались к мелким различиям возможностей их вариантов (это исключительно мое личное видение ситуации).


Спустя некоторое время вышла статья товарища chapuza, в которой была представлена реализация упрощенного wc на Elixir, также работающая быстрее, чем стандартная. В комментариях продолжилась дискуссия из первого поста, хотя на мой взгляд былой запал был утрачен.


В данной статье мы не будем пытаться победить один язык/парадигму программирования другим/другой. Думаю, непредвзятому человеку понятно, что C намного гибче в плане ручной оптимизации, чем Haskell и большинство других языков программирования, и поэтому код на C хоть и может быть медленнее чем на Haskell, но также может быть и намного быстрее — все зависит от того, кто этот код пишет. С другой стороны, лично я вижу много пока что не раскрытых возможностей функциональной парадигмы, и не исключаю возможности, что когда-то именно функциональный код будет оптимизироваться настолько круто, что написание подобного аналога на C будет слишком затратным занятием. Но даже если и так, это время еще не пришло.


В то же время, будучи человеком, чью любовь к оптимизации (даже бессмысленной) я оцениваю как фанатическую, я сразу заинтересовался насколько можно оптимизировать тривиальный C-вариант. Этим мы и займемся. Думаю, на волне предыдущих статей это будет интересно, к тому же, сам 0xd34df00d в комментариях к своей статье выразил интерес к подсчету слов с помощью "simd-магии".


Тестовый стенд


Итак, для начала представим условия, в которых мы будем считать слова.


#include <stdint.h>
#include <stdio.h>
#include <malloc.h>
#include <Windows.h>
#include <intrin.h>

using namespace std;

struct stats
{
    uint32_t char_count;
    uint32_t line_count;
    uint32_t word_count;
};

void word_count( unsigned char* const str, uint32_t size, stats& result );

int main( )
{
    FILE* f;
    fopen_s( &f, "input.txt", "rb" );
    fseek( f, 0, SEEK_END );
    long size = ftell( f );
    rewind( f );

    long alloc_size = size + 63 - ( size + 63 ) % 64;
    unsigned char* const data = (unsigned char*)_aligned_malloc( alloc_size, 64 );
    fread( data, 1, size, f );
    fclose( f );

    LARGE_INTEGER fr, t0, t1;
    QueryPerformanceFrequency( &fr );
    QueryPerformanceCounter( &t0 );

    stats result;
    word_count2( data, size, result );

    QueryPerformanceCounter( &t1 );

    _aligned_free( data );

    double const time = (double)( t1.QuadPart - t0.QuadPart ) / (double)fr.QuadPart;
    printf(
        "Words: %d; lines: %d; chars: %d\nElapsed time: %lfms\n",
        result.word_count, result.line_count, result.char_count, time * 1000.0
    );
    system( "pause" );
}

Для начала — да, я буду использовать Windows и Visual Studio. К сожалению, мой уровень владения Linux'ом приближается к нулю, и писать Linux-программы значило бы потратить значительно больше усилий. С другой стороны, мы ведь ни с кем не соревнуемся — так что пусть будет уютная VS.


Как видите, все максимально просто. Мы считываем файл с диска, предварительно узнав его размер и выделив под него память. Память выделяем выровненную по 64 байта и также дополняем размер аллокации до 64 байт — пригодится для SIMD-инструкций, да и вообще не повредит. Далее вызываем функцию подсчета слов, время выполнения которой трекаем с помощью таймеров высокой точности. (Стоило бы использовать средства стандартной библиотеки, но этот метод мне привычней, к тому же, не приходится сомневаться в его точности.) Далее просто выводим результат обработки и затраченное время в миллисекундах, не забывая освободить память.


Будем считать, что во входном файле не используется Unicode, и что пробельными являются символы код которых меньше либо равен 32. Последнее ограничение можно заменить на более корректное, но тогда результаты возможно будут другими. К тому же, мне кажется что подсчет слов обычно используется на данных, где такое условие будет работать удовлетворительно.


Тестирование проводилось на компьютере с новеньким Ryzen 5 3600 c оперативной памятью 2x8 Gb 3200 MHz. Ах да, входной файл использовался тот же, что и в предыдущих статьях.


Тривиальная реализация


Мой тривиальный вариант следующий:


void word_count( unsigned char* const str, uint32_t size, stats& result )
{
    uint32_t lines = 1;
    uint32_t words = 0;

    bool was_space = false;

    for ( uint32_t i = 0; i < size; ++i )
    {
        unsigned char const c = str[i];
        bool const is_space = c <= ' ';
        lines += ( c == '\n' ) ? 1 : 0;
        words += ( is_space && !was_space ) ? 1 : 0;
        was_space = is_space;
    }

    words += !was_space ? 1 : 0;

    result.char_count = size;
    result.line_count = lines;
    result.word_count = words;
}

По сути он практически ничем не отличается от уже приведенного в комментариях к статье 0xd34df00d. Результаты работы:


Words: 44774640; lines: 15000010; chars: 1871822228
Elapsed time: 1825.704800ms

(SIMD-магия выходит на сцену)


Итак, что мы видим? Видим то, что каждый символ строки по сути обрабатывается независимо (да, есть зависимость от предыдущего символа, но не от результата его обработки). Так почему бы нам не обрабатывать по 16 символов одновременно с помощью SSE-инструкций?


Вариант с SSE:


void word_count_sse( unsigned char* const str, uint32_t size, stats& result )
{
    uint32_t lines = 1;
    uint32_t words = 0;

    bool was_space = false;

    for ( uint32_t i = 0; i < size; i += 16 )
    {
        __m128i const c = _mm_load_si128( (__m128i*)( str + i ) );
        uint32_t is_newline_mask = _mm_movemask_epi8(
            _mm_cmpeq_epi8( c, _mm_set1_epi8( '\n' ) )
        );

        uint32_t is_space_mask = _mm_movemask_epi8(
            _mm_andnot_si128( c, _mm_cmplt_epi8( c, _mm_set1_epi8( ' ' + 1 ) ) )
        );
        uint32_t was_space_mask = ( was_space ? 1 : 0 ) | ( is_space_mask << 1 );

        lines += __popcnt( is_newline_mask );
        words += __popcnt( is_space_mask & ~was_space_mask );
        was_space = is_space_mask & 0x8000;
    }

    words += !was_space ? 1 : 0;

    result.char_count = size;
    result.line_count = lines;
    result.word_count = words;
}

Думаю стоит объяснить что тут происходит. У нас все еще есть флаг was_space, который означает был ли предыдущий символ пробельным. Теперь, поскольку мы обрабатываем 16 символов за раз, этот флаг сохраняет информацию о 15-ом символе из предыдущей партии, так как именно это нам важно для первого символа из текущей.


В цикле мы сначала загружаем данные с помощью интринсика _mm_load_si128 в переменную типа __m128i (в ассемблере она станет 128-битным XMM-регистром).


Далее мы проводим тесты символов на то что они являются пробельными или символами перевода строки. Наша цель — получить 16-битные маски результата, в котором каждый бит отвечает за соответствующий символ в 128-битном регистре. SSE-инструкции сравнения работают только с XMM-регистрами, и для того что бы получить 16-битную маску мы используем интринсик _mm_movemask_epi8. Эта инструкция делает именно то что нам нужно — принимает на вход 128-битную переменную, интерпретирует ее как массив из 16 байт, и выдает 16-битную маску, каждый бит которой копируется из старшего бита соответствующего байта XMM-регистра.


Для теста на перевод строки мы просто используем инструкцию _mm_cmpeq_epi8, которая побайтно сравнивает входные параметры и выдает 128-битный результат, каждый байт которого имеет значение 0, если соответствующие входные байты неравны, и 255 в противном случае. На вход мы подаем переменную с обрабатываемыми символами и 128-битную переменную, каждый байт представляет символ перевода строки (для этого используем интринсик _mm_set1_epi8).


С тестом на пробельный символ все немного сложнее. Дело в том, что тест больше/меньше SSE может проводить только над знаковыми целыми числами. Это и делает инструкция _mm_cmplt_epi8 — проверяет, что байты первого аргумента строго меньше байтов второго и возвращает маску аналогично _mm_cmpeq_epi8. Но это значит, что любой символ, код которого равен 128 и выше, такая проверка назовет пробельным. Поэтому мы маскируем подобные символы с помощью инструкции _mm_andnot_si128. Она принимает на вход два 128-битных регистра и возвращает результат побитового "И" второго аргумента и инвертированного первого. Мы передаем текущие символы как первый аргумент и результат _mm_cmplt_epi8 как второй. У символов с кодом больше 128 установлен старший бит, следовательно в результате соответствующие старшие биты будут обнулены — это как раз то, что нам нужно для movemask'а.


Дальше мы уже оперируем с битовыми масками в обычных регистрах. Вычисляем маску was_space_mask, используя is_space_mask и флаг was_space, комбинируем маски так же, как в элементарном варианте и используем __popcnt что бы узнать количество установленных бит, которое аккумулируем в результат. В конце обновляем was_space флаг, устанавливая его в старший бит маски.


Поподробнее узнать об SIMD-инструкциях платформы x86 лучше здесь.


Результаты тестирования:


Words: 44774640; lines: 15000010; chars: 1871822228
Elapsed time: 165.704300ms

В 11 раз быстрее! Неплохой результат.


Еще SIMD-магия


Но, как говорится в известной пословице, между SSE и AVX перерывчик небольшой. Давайте попробуем обрабатывать 32 символа за раз с помощью инструкций AVX/AVX2:


void word_count_avx( unsigned char* const str, uint32_t size, stats& result )
{
    uint32_t lines = 1;
    uint32_t words = 0;

    bool was_space = false;

    for ( uint32_t i = 0; i < size; i += 32 )
    {
        _mm_prefetch( (char*)str + i + 32 * 64, _MM_HINT_NTA );

        __m256i const c = _mm256_load_si256( (__m256i*)( str + i ) );
        uint32_t is_newline_mask = _mm256_movemask_epi8(
            _mm256_cmpeq_epi8( c, _mm256_set1_epi8( '\n' ) )
        );

        uint32_t is_space_mask = _mm256_movemask_epi8(
            _mm256_andnot_si256( c, _mm256_sub_epi8( c, _mm256_set1_epi8( ' ' + 1 ) ) )
        );
        uint32_t was_space_mask = ( was_space ? 1 : 0 ) | ( is_space_mask << 1 );

        lines += __popcnt( is_newline_mask );
        words += __popcnt( is_space_mask & ~was_space_mask );
        was_space = is_space_mask & 0x80000000;
    }

    words += !was_space ? 1 : 0;

    result.char_count = size;
    result.line_count = lines;
    result.word_count = words;
}

Как видно, по сравнению с SSE-вариантом смысловых изменений нет. Использованы инструкции AVX/AVX2, функционал которых аналогичен тем, что были использованы ранее. Инкремент в цикле теперь не 16, а 32, и маски теперь 32-битные.


Результат:


Words: 44774640; lines: 15000010; chars: 1871822228
Elapsed time: 109.606000ms

Примерно в полтора раза быстрее.


Prefetch


В подобных ситуациях, когда мы обрабатываем большие объемы памяти, производя не так уж много вычислений, и при этом доступ к памяти последовательный, стоит задуматься о том, что бы использовать интринсик _mm_prefetch. Данная инструкция указывает, что мы хотим в будущем использовать некоторый участок памяти, и что неплохо бы загрузить его в кеш (то, что происходит на самом деле, сильно зависит от модели процессора). Так что сделал небольшую вставку в AVX-вариант:


void word_count2( unsigned char* const str, uint32_t size, stats& result )
{
    // ..............

    for ( uint32_t i = 0; i < size; i += 32 )
    {
        _mm_prefetch( (char*)str + i + 32 * 64, _MM_HINT_NTA );

        // ..............
    }

    // ..............
}

Words: 44774640; lines: 15000010; chars: 1871822228
Elapsed time: 73.564900ms

То есть на каждой итерации цикла мы просим загрузить в кеш участок памяти, который будем обрабатывать через 64 итерации. Немного нечестная оптимизация, поскольку параметры я подстроил исключительно под себя; на других платформах на самом деле это может даже снизить производительность.


В этом месте я подумал, что мы уже наверняка почти что упираемся в пропускную способность RAM. И правда — если оставить в цикле только загрузку данных в регистр, цикл отрабатывает примерно за 70ms. Так что смысла оптимизировать дальше скорее всего нет (да и раньше его не было).


Выводы


Итак, в этой статье было показано, как можно действительно быстро считать слова в тексте. Другой вопрос, стоит ли это делать быстро, или лучше все таки делать это правильно на любых входных данных, при том что изначально 1.8 Gb текста обрабатывались за 10 секунд.


В любом случае, надеюсь, статья была интересной, и кто-то сможет почерпнуть для себя что-нибудь новое.


Веселых холиваров!

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 46

    +2

    А ничё, что предыдущие ораторы считали не только слова?


    Это требование убивает правило 32х и заставляет учитывать предыдущий символ, что в арифметике добавляет заметное проседание.


    А то так-то я умею ванлайнер на пейтоне, который посчитает байты за наносекунду.

      +3
      Я отлично понимаю, что джентльменам принято верить на слово, но, может, поделитесь?
        –4

        Зачитали файл в строку, вызвали сайз.

          +7

          И это у вас изначально можно сделать за наносекунду? Вы уверены? А как меряли?

        0
        Ну, показывайте тогда python, можно даже не за нано-, а за микросекунду.
        Очень интересно посмотреть будет.
          –4

          Вызвать системную команду file, распарсить вывод, показать только размер.

            +13

            Вы уверены, что это будет возможно сделать за микросекунду?
            Можно таки увидеть пруф?

          0
          Во-первых, повторюсь, что я ни с кем не соревнуюсь (кроме как со своими предыдущими реализациями).
          Во-вторых, не очень понял суть Вашей претензии. Я посчитал слова/строки/байты, вроде бы это все, разве нет? И что значит я не учитываю предыдущий символ?
          На счет <= ' ' — да, скрупулезная проверка на пробелы посложнее с точки зрения арифметики. Если будет возможность — может быть реализую и ее.
            0

            Скормите вашей реализации вот это:


            Foo
            
                    Bar
              0
              Words: 2; lines: 3; chars: 18
              Elapsed time: 0.000200ms
              ЧЯДНТ?
                0

                Тут не так парсер хабра, но я понял ваши аргументы, и даже согласен с ними.


                Строк так, правда, в любом случае — 4.

                  +1
                  Вы имеете в виду что для перевода строки нужно также проверить на '\r'? Ну это небольшой оверхед.
          0

          кажется мне что надо сделать нормальную стейтмашину, просто пройти ей по входному потоку


          в итоге C должен получиться лучше хацкеля и ко


          а не делали потому что "лень, и так работает, а быстродействие тут нафиг никому не нужно"


          кстати системный wc имхо с багом:


          $ echo -n test > test.txt
          $ wc -l test.txt                                    
          0 test.txt

          начать править wc можно с этого ;)

            –1
            в итоге C должен получиться лучше хацкеля и ко

            Вот почему все в этом так уверены?


            а не делали потому что "лень, и так работает, а быстродействие тут нафиг никому не нужно"

            По коду wc и не скажешь.

              +6
              Вот почему все в этом так уверены?

              потому что Си — это этакий ассемблер.


              нет алгоритма который можно запрограммировать на другом языке и нельзя на Си, но есть множество алгоритмов которые можно запрограммировать на Си и нельзя на куче других языков. Например всякие переключения стека относятся к таким алгоритмам.


              то есть, тот алгоритм, который запрограммировали в статье про другой язык можно переложить на Си и бенчмаркать он будет не хуже. Или скорее всего лучше.

                0

                Вопрос в том, сколько усилий у вас на это уйдет. Некоторые оптимизации вроде того же fusion'а в прочих языках даются нахаляву.

                  0

                  не должно уйти много усилий


                  тут же стейтмашина о менее чем десятке стейтов, ей даже рагель не нужен чтоб её построить.

                0
                По коду wc и не скажешь.

                wc умеет (должна уметь, не знаю как умеет ли или нет) non-8-bit-char локали


                и вот ради этого умения возможно там нагорожено мноооого кода.


                и вроде non-8-bit-char локали до сих пор много где применяются в странах с иероглифами.
                просто потому что легаси ПО много.


                PS: хотя тут я возможно и отстал лет на 10, может они все уже на UTF-8 перешли.
                я на эти локали как раз натыкался где-то в году 2010-м. как сейчас там дело обстоит ХЗ

                  0

                  Там для однобайтовых локалей отдельный цикл.

                    0

                    ну вот — я ж говорю — наворочено.
                    отдельный цикл для того, отдельная фиговина для сего...


                    а если всё выбросить и с нуля написать, то кроме байтовых локалей ничего и не нужно.

                  –3

                  Ох. Как на перемену из третьего класса вышел, прям.


                  Я не уверен, я думаю, что в 2020 все компиляторы в натив сделают примерно одинаково.


                  Все виртуальные машины сделают чуть хуже, но не сильно.


                  Всех, кто так не сможет, надо на свалку.


                  И забавно, что на моей рабочей машине, с 32 ядрами, и идиоматичный си, и идиоматичный хаскель, влетают идиоматичному эрлангу на почти порядок.


                  Потому что в 2020 тут рулит идиоматичность распараллеливания, а не опций компилятора.


                  Убираю линейку с видом победителя, иду на урок.

                    –2

                    Распараллелить искомый код на хаскеле — тоже, в общем, дело 15 минут, из которых вы 10 минут будете думать о стратегии склейки (предлагаю ничего не склеивать и не обмазывается моноидами, а просто поделить файл на N равных кусков с округлением до ближайшего ньюлайна вверх).


                    И тот же хаскель тогда будет в 32 раза (или насколько шина памяти позволит) быстрее.

                      0

                      Поделить файл — это как? Мне мать писала, что хаскель ленив до жути.


                      И в языке, аоторый из коробки готов к распараллеливанию, об этом думать не надо. Я именно об этом.

                        0
                        Поделить файл — это как? Мне мать писала, что хаскель ленив до жути.

                        Ну как, будет что-то вроде


                        main = do
                          [path, read -> parallelism] <- getArgs
                          contents <- mmapFile path
                          let chunks = calcChunks parallelism $ BS.length contents
                          counts <- forConcurrently chunks $ \(start, end) -> wc $ substring start end contents
                          print $ mconcat counts

                        И в языке, аоторый из коробки готов к распараллеливанию, об этом думать не надо. Я именно об этом.

                        Думать о параллелизме надо всегда, по крайней мере, если у вас что-то не выражается обычным map (а тут свёртка).

                          0
                          Думать о параллелизме надо всегда [когда не map]

                          И да, и нет. Да — в смысле, нужно понять, когда эмитнуть синхронизацию (в совсем запутанных случаях). Нет — в смысле вот такого кошмара, как выше, в клиентском коде быть не должно.


                          Сравните с кодом из моего гиста:


                          file
                          |> File.stream!([], @chunk)
                          |> Flow.from_enumerable()
                          |> Flow.partition()
                          |> Flow.reduce(fn -> @acc end, &parse/2)
                          |> Enum.to_list()
                            0

                            Я в другом смысле.


                            Какой размер файла? Какой размер чанков? Какой размер чанка адекватно отдавать одному ядру? Насколько сбалансированной будет работа разных воркеров над разными чанками?


                            Бить на N чанков по числу тредов и тупо запускать по воркеру на каждый? Бить по N * 1000 чанков, и пусть воркеры там друг у друга воруют работу? Что-то ещё умнее?


                            Никакой компилятор за вас это понять не сможет, для этого нужны вы, как знающий больше о решаемой задаче.

                              0

                              А, ну это-то конечно, но тут чуда никто и не ждал.

                        0

                        На 28-29 примерно :)

                    0

                    FSM в наивной реализации будет в разы медленнее показанной наивной реализации на C. Но если продолжить вашу мысль в верном направлении, то получится что-то подобное.

                    –2
                    не хватает обработки других непробельных символов
                      +3
                      Под статьей yleo привел результаты тестирования написанного им тривиального решения на C (под упрощенное условие), показав, что даже наивная C-реализация обходит оптимизированный Haskell-вариант.

                      Но ведь не обходит. 2 секунды для С против 1.45 для хаскеля.


                      А про пробелы вам уже и так написали.

                        0

                        Если не затруднит, то прогоните пожалуйста на вашей машине вариант с развернутым циклом (т.е. с заменой этого цикла на код под спойлером). Хочется нащупать отличие кода из-под ghc от C.

                          0

                          gcc стало чуть лучше (1.95 с), clang стало сильно хуже (3.4 с). -O3, без -march=native.


                          Впрочем, если -marc=native включить из интереса, то на gcc не будет никакого эффекта, а вот clang'у несколько полегчает (до 2.6 с).

                        +1
                        Не хватает определения «wc» в самом начале статьи для тех, кто не в теме
                          +1
                          судя из текста это word count. Но действительно, для непосвященного звучит двояко
                          –1
                          Я прошу прощения, но как у вас обработается символ с кодом 160? Как пробел?
                            0
                            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>-->
                              0
                              Если я правильно понимаю, причина в достаточно простой "механике": ghc (хаскель-компилятор) немного раскатывает вот этот цикл (aka loop unrolling). Точнее говоря, не раскатывает, а не полностью сворачивает (aka fold), и такой цикл отрабатывает быстрее.

                              Конкретно ghc эту оптимизацию делать не умеет. Может, её делает LLVM, но тогда он её должен делать и для clang'а без всяких -march=native.


                              Впрочем, читать ассемблерный код, сгенеренный ghc — то ещё удовольствие. Для бравых духом могу выложить десять метров дизасма.

                                0

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

                                  0

                                  Это ещё один кодогенератор, и там нет части оптимизаций, которые делает LLVM или NCG.


                                  Ну и смотреть в получающийся С я бы тоже не рекомендовал :)


                                  Тем более, что я таки не поленился и попробовал:


                                  Building library for hwc-0.1.0.0..
                                  
                                  on the commandline: warning:
                                      -fvia-C is deprecated: The -fvia-C flag does nothing; it will be removed in a future GHC release
                                  0

                                  Кстати, ассемблерный вывод ghc совсем сухой, без его "технических" комментариев?
                                  Может какой-нибудь ключик есть для аннотации?
                                  Должны быть какие-то средства навигации или "дорожные столбы", чтобы сами разработчики ghc поманили что из чего получилось.

                                    +1
                                    Кстати, ассемблерный вывод ghc совсем сухой, без его "технических" комментариев?

                                    Да.


                                    Должны быть какие-то средства навигации или "дорожные столбы", что сами разработчики ghc поманили что из чего получилось.

                                    Они есть для более высокоуровневых представлений (Core — дешугаренный и простой хаскель, Cmm — одно из IR у NCG). Кстати, гляну, можно ли дампить, что он там для LLVM нагенерил, это должно быть читабельнее, по идее.


                                    Может, оно есть и для нативного кодогенератора, но я так глубоко никогда не лазал, мне обычно другие части компилятора были интересны, которые ближе к тайпчекингу.

                                0
                                Просто ткнулся, не глядя, на первой попавшейся под руку железяке, не самой могучей :) Исходный файл тот же.

                                1)

                                $ time wc test.txt                                                                                                                  
                                  15000000   44774631 1871822210 test.txt
                                
                                real    0m24.825s
                                user    0m24.560s
                                sys     0m0.260s


                                2)

                                $ time cat test.txt | ./wc.pl                                                                                                       44774631
                                
                                real    0m16.171s
                                user    0m15.736s
                                sys     0m1.472s
                                


                                3)

                                #!/usr/bin/perl
                                
                                use Modern::Perl;
                                use utf8::all;
                                use open qw/:std :utf8/;
                                
                                my $words;
                                $words += split /\s+/ while <>;
                                say $words;
                                  0

                                  у меня Perl получался в 4 раза медленнее обычного wc


                                  у Вас похоже не tmpfs

                                    0

                                    Ну и тут мы только слова считаем, арифметики сильно меньше, чем в корректном решении.

                                      0
                                      у Вас похоже не tmpfs


                                      Дык я ж сразу сказал: «на первой попавшейся под руку железяке, не самой могучей» :-)

                                      Хотя, надо проверить.

                                      Что касается перла — тут есть куча нюансов. Один и тот же алгоритм можно и ускорить, и замедлить, от реализации зависит. TIMTOWDY, однако… Ну, это если не влезать в такты, а говорить только о средствах языка :)

                                  Only users with full accounts can post comments. Log in, please.