Круто :) Я примерно это и имел ввиду под вариантом "16бит табличку" но полного понимания как сделать еще не было. Я делал такое немного для других кейсов.
На оптимизацию wc (включая упомянутые мной кусочки) потратили менее получаса? Не верю, извините.
На wc не уверен, т.к. у него больше опций, а вот на вариант потипу yleo — да, во всяком случае в принципе столько, сколько уйдет у меня на это на си. То что си многословнее, тяжелее подстановки — я не спорю. Но ваш посыл, что напишите идеоматично на си и на хаскеле и получите быстрее хаскель — не верно.
Вот посыл напишите такие мелкие консольные утилиты на языках, которые для этого предназначены, например на перле, а не на си. Времени потратите меньше, а скорость будет возможно даже такая же, как на си. И корректное сравнение с вариантом yleo — вот тогда было бы все корректно в статье.
А coreutils — у него задача предоставить core утилиты на голом железе, с зависимостью только от си компилятора, который можно уместить в 300кб кода на нем же (привет tcc). Но кажется все знают что для текстового процессора не лучший выбор.
А там же нет вызовов рантайма. Вы просто бежите по куску памяти и просто инкреметируете счётчики. Там даже вызовов функций может не быть, если компилятор всё заинлайнил (или если используется прямая проверка на пробельные символы, как в предложенных альтернативных С-вариантах).
В wc есть вызовы glibc, может и не влияет, но надо проверять. Так же ghc стандартные isspace, — поддерживает только latin1 (как я понял), а в glibc — поддерживает локали и надо ходить в tls.
У ghc даже стека в привычном смысле нет, хехе. Вот это как раз сравнивать будет очень сложно.
Вот и я про то, надо глянуть асм, скорее всего -fomit-frame-pointer тоже потребуется для корректного сравнения.
Что си, что хаскель можно попробовать еще ускорить. Можно попробовать 16бит табличку, можно попробовать читать по 4-8 байт и разбираться с прочитанным в регистре (для парсинга http заголовков это помогало, односимвольные слова возможно ухудшит).
Их вообще довольно сложно сравнить, т.к. как я понял ghc работает и с LLVM и без. Про компактность никто не спорит, все замечания были именно про сравнения скорости.
Судя по коду — заморачивались. Ну серьезно, незаморачивающиеся люди не будут учитывать недавние длины строк и писать цикл для поиска конца строки руками из-за того, что memchr на слишком коротких строках тормозит, вызывая его, если последние строки были достаточно короткими.
Заморачивались, но не до такого уровня как приведенный хаскель код. Ну серьезно, yleo же вполне наглядно показал что будет если на си тоже изначально учитывать только asccii. Почему авторы wc так сделали — гадать бесполезно, надо спрашивать у них. Но для бенчмарка с приведенным хаскелем он не подходит и идеоматичность тут вообще непричем.
По поводу -march=native и опций — надо еще учесть, что у gcc по дефолту стоят безопасные вызовы рантайма, чтобы их отключить надо добавить -U_FORTIFY_SOURCE. Так же возможно понадобятся -fno-stack-protector и frame pointer omission, в зависимости как поступает ghc.
В общем корректный бенчмарк да еще разных компиляторов дело сложное, подводных камней тут масса.
Корректно: просто мы бенчмаркаем не только качество конкретного компилятора, но и выразительность языка.
Так чем вариант yleo вам не выразителен? Для си вполне обычный код, если бы вы взяли исходный более сложный счетчик на хаскеле с локалями и писали бы статью написав вот такой урощенный на си — ничего же не поменялось бы.
Уже обсудили в комментариях. Если кратко — wc даже при сишной локали в дефолтной сборке использует mbcs. Там есть фоллбэк MB_CUR_MAX=1, который можно включить на этапе сборки, но даже его включение — это более сложный код, чем предложенный на хаскеле. В комментах приведен си код упрощенный до того же состояния и производительности сравнялись.
В целом это ожидаемо, т.к. 99.99% использвание wc будут без изменения env переменных. А какая локаль будет включена в дистрибутиве? Ну явно не сишная, 99% — utf8, только для каких-то облегченных дистров с musl включится фоллбэк и будет только простые локали поддерживать. Это можно было бы проверить и до написания ститьи.
Там \t все равно в свиче есть, даже если mbcs отключить. Просто надежны на оптимизированность были напрасными. Если бы я делал такой упрощенный ascii only wc на си — я бы делал по-другому.
Ну вообще в кодеках такое сплошь и рядом на си, там где motion compensation и надо его 100500 вариантов. Если вы про то что сишный препроцессор неудобнее для всяких групповых подстановок — то да, все верно. С++, Хаскель и многие другие языки тут могут поудобнее и покомпактнее быть (иногда ценой что подстановка не всегда compile time), но принципиальных сложностей там с этим нет.
Ну я с этим и не спорю, хаскель выглядит куда компактнее.
Про кодогенерацию только не понял, что на си, что на хаскеле же тоже 2 варианта иннер лупа надо будет сделать? Там чистая подстановка mbcs\ascii вариантов функций в один и тот же код плохо ложится т.к. mbrtowc может переводить состояния, потому там fallback отдельно и сделан. В общем суть про n вариантов и причем тут си не уловил.
Да качество вроде нормальное, просто если локаль поддерживать, то никуда не деться от того чтобы ее из tls взять и заглянуть.
То что это вряд ли большая доля это да, я думаю переход на fallback дает куда больше. Но все равно надо проверять, и лишнее из switch тоже удалить, что в хаскель варианте отсутствует. Все же такой inner loop вещь тонкая на любом языке.
Ну точнее ну как достаточно, glibc наверно получит локаль, пойдет в табличку и проверит там флаг. Магически isspace до == ' ' не оптимизируется. Оптимизируется только если на этапе сборки там поддерживается отключение локалей и оптимизация этих функций до ascii.
Да, кажется я ошибся, isprint/isspace уже в glibc, а не gnulib, если их конечно не переопределили на mb_isprint/mb_isspace. Тогда достаточно только чтобы fallback включился.
Проблема в том, что fallback код все равно использует mbcs версии isprint и isspace. Ну тоесть fallback конечно явно быстрее, но чтобы включить оптимизацию до конца — надо оба пересобрать, wc и gnulib.
А MB_CUR_MAX или MB_LEN_MAX от локали автоматом все равно не изменятся, их надо или рередефайнить для wc, или от пересобранного gnulib они сами единичные подтянутся.
MB_LEN_MAX/MB_CUR_MAX это же константа, MB_LEN_MAX=1 — это mbcs отключен при компиляции, от локали никак не зависит. Вот перекомпилить gnulib и wc с MB_LEN_MAX=1 можно попробовать, да.
Отдельного оптимизированного цикла под кейс не вижу, есть только проверка на is_basic без mbrtowc и установка n = 1; wide_char = *p; wide = false;, прогоняя это дальше через универсальный код. При этом is_basic вижу может быть в 2х вариантах:
MBCHAR_INLINE bool
is_basic (char c)
{
return (is_basic_table [(unsigned char) c >> 5] >> ((unsigned char) c & 31))
& 1;
}
#else
MBCHAR_INLINE bool
is_basic (char c)
{
switch (c)
{
case '\t': case '\v': case '\f':
case ' ': case '!': case '"': case '#': case '%':
case '&': case '\'': case '(': case ')': case '*':
case '+': case ',': case '-': case '.': case '/':
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
case ':': case ';': case '<': case '=': case '>':
case '?':
case 'A': case 'B': case 'C': case 'D': case 'E':
case 'F': case 'G': case 'H': case 'I': case 'J':
case 'K': case 'L': case 'M': case 'N': case 'O':
case 'P': case 'Q': case 'R': case 'S': case 'T':
case 'U': case 'V': case 'W': case 'X': case 'Y':
case 'Z':
case '[': case '\\': case ']': case '^': case '_':
case 'a': case 'b': case 'c': case 'd': case 'e':
case 'f': case 'g': case 'h': case 'i': case 'j':
case 'k': case 'l': case 'm': case 'n': case 'o':
case 'p': case 'q': case 'r': case 's': case 't':
case 'u': case 'v': case 'w': case 'x': case 'y':
case 'z': case '{': case '|': case '}': case '~':
return 1;
default:
return 0;
}
}
Круто :) Я примерно это и имел ввиду под вариантом "16бит табличку" но полного понимания как сделать еще не было. Я делал такое немного для других кейсов.
Интересно конечно, с ходу больше не могу придумать как еще можно ускорить.
На wc не уверен, т.к. у него больше опций, а вот на вариант потипу yleo — да, во всяком случае в принципе столько, сколько уйдет у меня на это на си. То что си многословнее, тяжелее подстановки — я не спорю. Но ваш посыл, что напишите идеоматично на си и на хаскеле и получите быстрее хаскель — не верно.
Вот посыл напишите такие мелкие консольные утилиты на языках, которые для этого предназначены, например на перле, а не на си. Времени потратите меньше, а скорость будет возможно даже такая же, как на си. И корректное сравнение с вариантом yleo — вот тогда было бы все корректно в статье.
А coreutils — у него задача предоставить core утилиты на голом железе, с зависимостью только от си компилятора, который можно уместить в 300кб кода на нем же (привет tcc). Но кажется все знают что для текстового процессора не лучший выбор.
В wc есть вызовы glibc, может и не влияет, но надо проверять. Так же ghc стандартные isspace, — поддерживает только latin1 (как я понял), а в glibc — поддерживает локали и надо ходить в tls.
Вот и я про то, надо глянуть асм, скорее всего -fomit-frame-pointer тоже потребуется для корректного сравнения.
Что си, что хаскель можно попробовать еще ускорить. Можно попробовать 16бит табличку, можно попробовать читать по 4-8 байт и разбираться с прочитанным в регистре (для парсинга http заголовков это помогало, односимвольные слова возможно ухудшит).
Их вообще довольно сложно сравнить, т.к. как я понял ghc работает и с LLVM и без. Про компактность никто не спорит, все замечания были именно про сравнения скорости.
Заморачивались, но не до такого уровня как приведенный хаскель код. Ну серьезно, yleo же вполне наглядно показал что будет если на си тоже изначально учитывать только asccii. Почему авторы wc так сделали — гадать бесполезно, надо спрашивать у них. Но для бенчмарка с приведенным хаскелем он не подходит и идеоматичность тут вообще непричем.
По поводу -march=native и опций — надо еще учесть, что у gcc по дефолту стоят безопасные вызовы рантайма, чтобы их отключить надо добавить -U_FORTIFY_SOURCE. Так же возможно понадобятся -fno-stack-protector и frame pointer omission, в зависимости как поступает ghc.
В общем корректный бенчмарк да еще разных компиляторов дело сложное, подводных камней тут масса.
Так чем вариант yleo вам не выразителен? Для си вполне обычный код, если бы вы взяли исходный более сложный счетчик на хаскеле с локалями и писали бы статью написав вот такой урощенный на си — ничего же не поменялось бы.
Да, вы правы. Я думал что это константа, а это оказался вызов функции:
А, да, точно. Еще одино условие для ' ' надо добавить, тогда будет корректно. yleo
Вроде в хаскеле тоже просто проверяется '\n' и ' '. Т.е. в данном случае тз — сделать такой же утил как пример на хаскеле.
Уже обсудили в комментариях. Если кратко — wc даже при сишной локали в дефолтной сборке использует mbcs. Там есть фоллбэк MB_CUR_MAX=1, который можно включить на этапе сборки, но даже его включение — это более сложный код, чем предложенный на хаскеле. В комментах приведен си код упрощенный до того же состояния и производительности сравнялись.
В целом это ожидаемо, т.к. 99.99% использвание wc будут без изменения env переменных. А какая локаль будет включена в дистрибутиве? Ну явно не сишная, 99% — utf8, только для каких-то облегченных дистров с musl включится фоллбэк и будет только простые локали поддерживать. Это можно было бы проверить и до написания ститьи.
Там \t все равно в свиче есть, даже если mbcs отключить. Просто надежны на оптимизированность были напрасными. Если бы я делал такой упрощенный ascii only wc на си — я бы делал по-другому.
Есть интересная табличка бенчмарка скриптовых языков, некоторые с jit: https://github.com/r-lyeh-archived/scriptorium (староватая правда).
Ну вообще в кодеках такое сплошь и рядом на си, там где motion compensation и надо его 100500 вариантов. Если вы про то что сишный препроцессор неудобнее для всяких групповых подстановок — то да, все верно. С++, Хаскель и многие другие языки тут могут поудобнее и покомпактнее быть (иногда ценой что подстановка не всегда compile time), но принципиальных сложностей там с этим нет.
Ну я с этим и не спорю, хаскель выглядит куда компактнее.
Про кодогенерацию только не понял, что на си, что на хаскеле же тоже 2 варианта иннер лупа надо будет сделать? Там чистая подстановка mbcs\ascii вариантов функций в один и тот же код плохо ложится т.к. mbrtowc может переводить состояния, потому там fallback отдельно и сделан. В общем суть про n вариантов и причем тут си не уловил.
Да качество вроде нормальное, просто если локаль поддерживать, то никуда не деться от того чтобы ее из tls взять и заглянуть.
То что это вряд ли большая доля это да, я думаю переход на fallback дает куда больше. Но все равно надо проверять, и лишнее из switch тоже удалить, что в хаскель варианте отсутствует. Все же такой inner loop вещь тонкая на любом языке.
Ну точнее ну как достаточно, glibc наверно получит локаль, пойдет в табличку и проверит там флаг. Магически isspace до
== ' 'не оптимизируется. Оптимизируется только если на этапе сборки там поддерживается отключение локалей и оптимизация этих функций до ascii.Да, кажется я ошибся, isprint/isspace уже в glibc, а не gnulib, если их конечно не переопределили на mb_isprint/mb_isspace. Тогда достаточно только чтобы fallback включился.
Проблема в том, что fallback код все равно использует mbcs версии isprint и isspace. Ну тоесть fallback конечно явно быстрее, но чтобы включить оптимизацию до конца — надо оба пересобрать, wc и gnulib.
А MB_CUR_MAX или MB_LEN_MAX от локали автоматом все равно не изменятся, их надо или рередефайнить для wc, или от пересобранного gnulib они сами единичные подтянутся.
MB_LEN_MAX/MB_CUR_MAX это же константа, MB_LEN_MAX=1 — это mbcs отключен при компиляции, от локали никак не зависит. Вот перекомпилить gnulib и wc с MB_LEN_MAX=1 можно попробовать, да.
Отдельного оптимизированного цикла под кейс не вижу, есть только проверка на is_basic без mbrtowc и установка n = 1; wide_char = *p; wide = false;, прогоняя это дальше через универсальный код. При этом is_basic вижу может быть в 2х вариантах:
Отдельный не-mbcs вариант явно будет быстрее.