Объяснение: почему wc на Haskell оказался «быстрее» аналога на С

Вероятно у меня будет время чтобы добавить результаты от более новых компиляторов из Fedora 31 на чуть более современно процессоре.

Если немного присмотреться к результатам, то легко увидеть что средняя длина слова 1871822210 / 44774631 = 41.8 символов, а строка в среднем состоит из 44774631 / 15000000 = 2.98 слов.

Ничего не хочу сказать, но обычный человекочитаемый текст, на который чаще всего и натравливают wc, сгенерирован не случайным образом, и имеет характеристики, несколько отличные от случайного.

Все результаты и выводы подтвердились для ghc 8.8.3, LLVM-бакендом и на текстах Шекспира.
См под спойлером в конце статьи.

1. Никто не собирался делать это переносимым дальше POSIX и загромождать исходный код. Под "переносимостью" прежде всего подразумевалась отсутствие привязи к x86 (особенно всяческие SIMD).
2. mmap() ничего не меняет, но остался по историческим причинам. Если аккуратно закомментировать, то всё должно работать (хотя я уже не помню проверял или нет).
3. В windows есть CreateFileMapping() и MapViewOfFile(). Поправить элементарно, либо WSL.

Вы что-то совсем не верно поняли, возможно мне стоит переформулировать текст или сместить акценты (но пока лень).

Код сгенерированный ghc в принципе не оптимальный, но показывает хорошие результаты только на сильно смещенных данных. Он особенно хорош если в гигабайтном тексте будет одно слово. Поэтому хаскель-коду буквально сильно повезло с тестовыми данными в первой статье.

Далее, случайные данные с точки зрения ТЗ являются не мусором, а совершенно корректными данными с более естественными статистическими показателями. Данные из /dev/urandom взять было просто удобнее, но если взять любой текст то результат будет примерно аналогичным. Пожалуйста попробуйте и отпишите, если сомневаетесь.

Хаскель должен хорошо с хода читаться людьми, для которых родной язык RtL (иврит, арабский).

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

TL;DR с системной утилитой wc нет смысла соревноваться — лежачего не бьют. Но на самом деле wc учитывает юникодные варианты пробелов и подсчитывает печатную дли строк (с табуляциями и вот это вот всё). Остальное подробности в комментариях к первой статье.

.

Откуда-то взялась лишняя строчка

Вот не менее наивная реализация без каких-либо дополнительных оптимизаций, но она работает корректно и в 3 раза быстрее Вашего варианта (просто за счёт отсутствия ненужных операций вроде преобразования []byte в string или удаления \r?\n из конца строк).

package main

import (
    "bufio"
    "bytes"
    "fmt"
    "log"
    "os"
)

func main() {
    var lines, words, characters int
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(scanLines)
    for scanner.Scan() {
        line := scanner.Bytes()
        characters += len(line)
        words += bytes.Count(line, []byte{' '}) + 1
        if line[len(line)-1] == '\n' {
            lines++
        }
    }
    if err := scanner.Err(); err != nil {
        log.Fatal(err)
    }
    fmt.Printf("%10d %10d %10d\n", lines, words, characters)
}

func scanLines(data []byte, atEOF bool) (advance int, token []byte, err error) {
    if atEOF && len(data) == 0 {
        return 0, nil, nil
    }
    if i := bytes.IndexByte(data, '\n'); i >= 0 {
        return i + 1, data[0 : i+1], nil
    }
    if atEOF {
        return len(data), data, nil
    }
    return 0, nil, nil
}

# Ваш вариант из комментария выше
$ time ./wc.orig /dev/shm/test.txt
  15000001   44774631 1841822210 /dev/shm/test.txt

2.994 real  2.917 user  0.390 sys  11MB RAM

# Мой вариант из кода под спойлером в этом комментарии
$ time ./wc </dev/shm/test.txt
  15000000   44774631 1871822210

0.974 real  0.664 user  0.312 sys  11MB RAM

# Штатная утилита
$ time LANG=C wc </dev/shm/test.txt
  15000000   44774631 1871822210

7.044 real  6.858 user  0.185 sys  11MB RAM

# на Haskell: ghc 8.0.2, -O2
$ time ./haskell_wc /dev/shm/test.txt
(1871822210,44774631,15000000)

2.510 real  2.420 user  0.090 sys  1788MB RAM

# простая на С: gcc 9.2.0, -Ofast
$ time ./naive_wc </dev/shm/test.txt
lines 15000000, words 44774631, chars 1871822210
took 2.517815 seconds

2.519 real  2.433 user  0.085 sys  1782MB RAM

# оптимизированная переносимая на С: gcc 9.2.0, -Ofast
$ time ./ascii_wc </dev/shm/test.txt
lines 15000000, words 44774631, chars 1871822210
took 0.558271 seconds

0.559 real  0.472 user  0.086 sys  1783MB RAM

P.S. У меня i7-2600K, он AVX2 не поддерживает.

Все результаты и выводы подтвердились для ghc 8.8.3, LLVM-бакендом и на текстах Шекспира.
См под спойлером в конце статьи.

AVX, SSE и прочие фигня всё это в данном случае. Есть еще другие способы оптимизации:
1. файл большой => следует читать асинхронно.

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

3. приводить результаты в абсолютных величинах Gb/s и сравнивать с максимальной пропускной способностью в %. Например по отношению к HDD 160Mb/s, SSD 500Mb/s… 4Gb/s, RAM 40-80Gb/s

AVX, SSE и прочие фигня всё это в данном случае. Есть еще другие способы оптимизации:

Ой не говорите, ерундой какой-то занимаемся.

1. файл большой => следует читать асинхронно, пока читает обрабатывать прочитанное. Задача проста: обработать данные до получения следующего блока.

Видимо не в теме этой прорывной технологии. Поэтому просто разместили файл в tmpfs чтобы было меньше букв в коде.

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

Это даст прирост если данные читаются больше одного раза, а в здешнем баловстве это не так. Поэтому хватает prefetch. Более того, в подобных практических задачах всегда выгоднее не засорять кэш данными читаемыми однократно. Т.е. буквально для AVX2 будет выгоднее делать предвыборку вручную в потоковом режиме, обрабатывания данные кэш-линияим (по 64 байта).

1. приводить результаты в абсолютных величинах Gb/s и сравнивать с максимальной пропускной способностью в %. Например по отношению к HDD 160Mb/s, SSD 500Mb/s… 4Gb/s, RAM 40-80Gb/s

В этом есть здравое зерно, но нет рациональности. Поскольку варианты кода сравнивались между собой на одной машине по wall clock, и намеренно без дискового обмена.

В целом — спасибо, посмешили.
Всё-же желательно читать статьи перед тем так блистать в комментариях.