Комментарии 75

Ну наверное разработчики glibc наворотили это не от доброты душевной, а чтобы соответствовать стандарту, плюс быть совместимыми со старыми приложениями, которые вместо EOF используют -1 и при этом еще и поддерживать локали. И чтобы это все работало на процессорах с разным endianess.
Поэтому, я не совсем понимаю возмущение автора.

В glibc недостает assert-а, который-бы контролировал допустимость аргумента.


У меня даже стойкое дежавю, что лет 10 назад я то-ли субиметл такой патч, то-ли добавлял assert в заголовки на сборочной ферме.

В glibc недостает assert-а, который-бы контролировал допустимость аргумента.
и который:
а) успешно выпиливается в релизной конфигурации
б) если не выпиливается, то кладёт на лопатки branch prediction

Так вы считаете что от assert-ов следует вообще отказаться по обозначенным "причинам"?

Я считаю, что слово «причины» в данном случае не следует брать в кавычки, что в релизном билде ассерты не помогут, и что если кому-то нужна версия isalnum с валидацией параметров, то её всегда можно написать и назвать isalnum_safe.

ну и к слову, а что решит assert? Заменит «segmentation fault» внутри isalnum() на «assertion failure», но только в отладочной сборке?

Заменит непонятное сообщение об ошибке на понятное, чтобы больше не пришлось гадать как это вообще возможно и лезть в потроха glibc.


Да, только в отладочной сборке.

Признаюсь: я не настоящий разработчик на С, я маску на стройке нашел. Как плюсовик, когда стандартная библиотека начинает меня удивлять, я иду на cppreference.com и в третьем предложении документации к функции читаю: «The behavior is undefined if the value of ch is not representable as unsigned char and is not equal to EOF.»

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

Я тоже не настоящий разработчик на Си, и документацию я читать тоже умею. Вот только если код чужой — то может оказаться далеко не сразу очевидно, что нарушено именно это условие. Корректное сообщение об ошибке хотя бы в отладочной сборке надёжнее.

Как только прочёл предложение автора "Переменные last и next имеют тип uint32_t", сразу стало понятно, что проблема — в диапазоне чисел, осталось только пойти на https://en.cppreference.com/w/c/string/byte/isalnum за подтверждением. Минус бы автору за то, что специально до конца не раскрывал значение переменной next.

А ещё статическому анализатору поможет, который распознает assert и радостно сообщит «value out of range». (Но ни cppcheck, ни scan-build из clang-tools-7 в Debian 9 assert не помог увидеть ошибку.)

Хм, но почему простой assert кладёт на лопатки branch prediction? Вроде же наоборот, он должен без проблем им предсказываться...

Я погорячился. Не будет он класть branch prediction на лопатки, т.к. процессор быстро поймет, что этот assert при нормальной работе приложения не срабатывает никогда.

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

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

А вы можете как-то прокомментировать эти тесты? Я не настоящий сварщик и не пишу на Си, но если функция содержит две строки кода и выполняет только базовые операции над целыми числами, а работает на целый порядок медленнее — закрадывается подозрение, что сам тест написан неправильно.

С тестами всё нормально. Все упомянутые "навороты" в glibc, в том числе, для скорости.

Надо ассемблерный код обоих вариантов смотреть. Ощущение, будто в случае с glibc функция заинлайнилась, а в случае с musl — нет, и такое сравнение нельзя назвать корректным.

Реализация glibc избавлена от сравнений и условных переходов, в том числе изначально рассчитана на инлайнинг. Её примерно всегда дешевле заинлайнить чем вызвать, как по объему кода, так и по скорости.


В целом довольно наивно/глупо писать статью со словами "галиматья", "дурацкая херня" и т.п. (это я про автора, а переводчику респект) не понимая и 1/10 причин "зачем и почему" так сделано. А голосование довольно хорошо показывает "среднюю по больнице" квалификацию голосующих.

А голосование довольно хорошо показывает «среднюю по больнице» квалификацию голосующих.
Судя по статьям про стандарт C++ можно и результаты голосования не открывать, так как там дофига комментариев типа «в моём Rust/Go/C#/Java/JavaScript/PHP всё понятно, такой фигни нет, дурачки из комитета/писатели компиляторов только и делают, что UB вводят».
В C/C++ вообще довольно много случаев с UB — я так понимаю, K&R и СтраусТруп сие пооставляли для каких-то неявно-неочевидных оптимизаций — однако, как правило, все равно куча народу стреляет себе в ногу )))

Ну, собственно, потому в glibc и используются макросы вместо функций, что макросы гарантированно инлайнятся...

Не две строки кода, а примерно 3 арифметические операции и 3 сравнения. Сравнения сбивают с толку предсказание переходов в процессоре и производительность падает.

Подозреваю, что glibc-шный метод, со всей его работой с локалями сводится к массиву из 256 элементов, для которых заранее рассчитано, являются ли они «alphanumeric».

Что-то вроде
 static bool g_isAlphanumeric[256] = initAlphanumericOnce();
 bool isalnum(unsigned int c) { return g_isAlphanumeric[c]; }

Массив быстро попадает в кеш процессора, лишние разыменования указателей нивелируются способностью процессора выполнять несколько микроинструкций за такт: никто не мешает процессору тянуть данные из этой таблицы заранее, и никто не мешает в процессе доступа к памяти посчитать что-нибудь заранее на АЛУ. Пока какой-то if() из кода по типу интуитивной реализации isalnum() не обдурит предсказатель переходов, и весь конвейер не будет сброшен и перезапущен.

Я конечно тоже настоящий программист на C, но может лучше тогда так и было писать( с учётом локалей, если они могут повлиять на её результат )? Чтобы функция простой проверки не размазывалась на десяток макросов. Спасибо хоть на нестандартные расширения компилятора не полагается

Сравнения сами по себе не обязательно сбивают с толку предсказание переходов. Если требуется только результат сравнения (как, например, в isalpha в musl), то инструкция перехода не нужна: вместо этого останется только cmp + добавится вытаскивание значений ZF/SF из регистра с флагами. Но зависит от реализации компилятора, конечно.
Вдогонку: в наивной реализации используется арифметика: все эти вычитания и сравнения. В случае предварительно посчитанной таблицы, арифметики нет вообще, т.к. доступ по индексу для массива целых чисел еще с допентиумных времен перестал задействовать ALU.
Так ещё с пентиумных времён арифметика быстрее предпосчитанных таблиц (например, в случае с 16-битным умножением). Не говорите только, что таблички влезают в L1. Если всё время на это полагаться, то тут 256 байт в L1, там 384 байта в L1, здесь 1024 байта, и L1 кончился.
Пруфы есть? Арифметика, как минимум, нагружает ALU.
256 байт в L1, там 384 байта в L1, здесь 1024 байта, и L1 кончился.
Речь идет о нагруженных циклах с кучей итераций.
Посмотрите, сколько стоит cache miss.
Речь идет о нагруженных циклах с кучей итераций
Нагруженный цикл не может быть в 1000 инструкций длиной? С кучей алгоритмов, которым всем надо либо память, либо арифметику?
Я надеялся на примеры или доказательства, а вы просто беседуете со мной.

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

Так вот, арифметика в обсуждаемом случае плоха тем, что она как минимум нагружает ALU, который можно освободить для других задач: например, для спекулятивного выполнения инкремента счетчика на единицу.
Посмотрите, сколько стоит cache miss.
Не думал, что так можно, но раз можно, то почитайте про «instructions per cycle» в контексте профайлинга.

И чтобы не быть голословным, давайте я приведу результаты бенчмарка: https://quick-bench.com/q/ET57hypxMHbRNEfWYNoR_oNT88A
  • is_alphanumeric таблица быстрее в 3 раза
  • is_alpha таблица быстрее на 40%
  • to_upper таблица переводит в верхний регистр в 2.3 раза быстрее
  • проверка байта на четность (куда уж проще) практически одинаковая, таблица на 10% быстрее
  • нагрузим L1 посильнее: сборная солянка из 4 таблиц в одном цикле is_alnum+is_alpha+is_even+to_upper быстрее того же с расчетом на лету на 80%
Быстрее, пока влезает в L1. Разработчики библиотеки не знают, в каком алгоритме будет использоваться их isalnum, и сколько ещё таких жадных до кеша функций будет в цикле.

В тестах и некоторых примерах, конечно, всё хорошо.

Я не пытаюсь доказать, что арифметика всегда лучше. Я только хочу отметить, что не надо всё перекладывать на таблицы. Пусть и небольшие в каждой функции, в сумме они могут превысить предел L1.
Фишка именно в мэппинге в локаль. Например, в некоторых языках есть такая штука, как умлауты (находятся в extended ASCII, 128-255). «Наивная» реализация не будет воспринимать их как буквы, хотя должна (в соответствующей локали). Так что гражданин ИМХО неправ.

так он прямо об этом написал:


Теперь становится очевидно, как исправить проблему. Мой косяк. Оказывается, я не могу скормить в isalnum произвольный символ UCS-32 для проверки на его вхождение в диапазоны 0x30-0x39, 0x41-0x5A и 0x61-0x7A

а вообще от этих локалей одни проблемы. Хорошо бы выкинуть их к чертовой бабушке и везде пользоваться UTF-8.

Не поможет, локаль — это не только кодировка, один и тот же Юникод в разных локалях может работать по-разному. И если на результат isalnum культура не влияет — то вот tolower от локали даже при использовании Юникода зависит.


Наиболее известный пример — турецкая локаль, с их знаменитыми символами İ и ı.

Но такое ощущение, что он так и не понял, ЗАЧЕМ так сделано, и до конца продолжает нахваливать библиотеку с наивной (и не вполне корректной) реализацией isalpha() как образец для подражания. В общем, ИМХО, rant высосан из пальца.

С другой стороны, передавать char32_t или его аналог в функцию, которая принципиально работает только с char | EOF — значит вообще не понимать что делаешь.

С третьей стороны, раз внутри функции массивы (с возможностью вылета за пределы) — почему не делать проверку на валидность входных данных?
Всё равно проверка нужна: мы же не хотим, чтобы от текста в не той кодировке программа падала. Только она будет самописная и не оптимизированная под все возможные архитектуры.

А при чём тут кодировка? Функция не упадёт пока в неё передаётся char, какую бы кодировку этот char не использовал.

На входе у функции не char а int
       int isalnum(int c);


Один и тот же символ в разных кодировках выглядит очень по разному

echo -n я|iconv -t cp866|hexdump -C
00000000 ef |.|
echo -n я|iconv -t cp1251|hexdump -C
00000000 ff |.|
echo -n я|iconv -t utf8|hexdump -C
00000000 d1 8f |..|
cho -n я|iconv -t utf32|hexdump -C
00000000 ff fe 00 00 4f 04 00 00 |....O...|



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

И что? Это же Си, тут много где int. К слову, для первых двух ваших вариантов isalnum работает не падая, а для последних двух она просто неприменима.

Это же Си, тут много где int.


Скорее совместимость со стандартами, где положено чтобы на вход подавалось unsigned char + EOF (-1).
Получается что есть 2 функции с одинаковыми параметрами (isalnum и isalnum_l), но одна с wide chars не работает (и даже на некоторых может упасть), а вторая — работает, но требует дополнительных движений. Жаль, автор умолчал, на каком именно символе оно падает.

Заголовок спойлера
#include <stdio.h>
#include <locale.h>

int main()
{
    int c = 0x410; // русская А
    setlocale(LC_ALL,""); 
    locale_t l = duplocale(LC_GLOBAL_LOCALE);
    printf("isalnum(%d)=%d\n", c, isalnum_l(c, l));
    return 0;
}





LANG=ru_RU.UTF-8 ./a.out
isalnum(1040)=8

Логично, вернула не 0.

LANG=en_US.UTF-8 ./a.out
isalnum(1040)=8

LANG=C ./a.out
isalnum(1040)=0

Что-то я не вижу в стандарте требования чтобы isalnum_l работала со значением 0x410:


The c argument is an int, the value of which the application shall ensure is representable as an unsigned char or equal to the value of the macro EOF. If the argument has any other value, the behavior is undefined.

Нет. Это парадигма С — Если что-то не по стандарту, то можно хоть диск форматировать. За счет этого отсутсвуют всякие проверки и код работает на порядок быстрее. Но программисту нельзя допускать ошибки, да.


Особенно раньше, когда к пользователям не отсносились вроде "пусть купит еще плашку памяти и процессор помощнее", это было важно.

Где-то в мире загрустил один Торвальдс с историей про memcpy и memmove.

Торвальдс стойко выдержал этот удар судьбы, даже не стал переписывать ядро и git на хаскель.

А для тех кто на бронетанке можно пожалуйста поподробнее про эту историю?

memcpy предполагает неперекрывающиеся области памяти, memmove может работать и с перекрывающимися. Лет 10 назад в glibc поменяли реализацию memcpy, чтобы воспользоваться этим, предположительно, для увеличения производительности, в результате чего сломался Adobe Flash Player (и, возможно, другой софт, но про флеш было больше всего разговоров). В итоге Линус выразил своё фи.

Спасибо. Я не особо знаток Линуса как человека, но похоже на какой-то плач обиженной девчонки. Кому надо тот пусть и фиксит (причем довольно просто) свой код следуя как раз неплохому предложению Линуса — в своем коде пусть и заводят макросню алиасищаю memcpy на memmov, а мне пожалуйста оставьте код который работает с УБ и по стандарту (да тому который он применяет по «назначению»), но хотя бы потенциально быстрее.

Линус распинался не о том что fail-fast плох или вреден, а что неприемлем переход на fail-fast "задним числом", когда под раздачу попадают ничего непонимающие детипользователи.

and memmove() simply just checks whether the destination address is above the source address and decides to copy backwards if so


Знаете ли я тоже имею некоторое представление о сложности этого «simply just checks», т.к. задавался конкретно этим вопросом. Я не сишник и сишный стандарт как отче наш на знаю, но вот в мире с++ это нифига не простая проверка и думаю си здесь не отличается от с++. Если интересно за подробностями сюда

Так что, то что пишет Линус о том, что это чушь это он мегко говоря не прав в общем случае. Конечно, на тех платформах с которыми он привык работать наверное это действительно просто, но не на всех.

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

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

Нет, спасибо, не надо, пусть лучше будет впервую очередь коректно и во второую максимально быстро, а за дополнительными плюшками идите в memmov.
Хорошо бы выкинуть их к чертовой бабушке и везде пользоваться UTF-8.

Второй пункт прямо противоречит первому

Ну так если надо написать оптимальный по производительности код, который будет быстрым на разных архитектурах и даже микроархитектурах, то приходится писать нечитаемую дичь. Увы, но даже для разных микроархитектур x86-64 нужно компилировать разную последовательность инструкций. В zen, вроде, 2 определённые инструкции могут превращаться в один uop. Когда-то cmov в большем числе случаев следовало использовать. Естественно, приходится давать компилятору как можно больше информации и давать такой код, который компилятор сможет для разных архитектур/микроархитектур максимально эффективно транслировать в машинные коды.
Если вы посмотрите на эффективные алгоритмы умножения матриц, то там тоже будет плохочитаемый код. Увы, но красивый и быстрый код почти всегда антонимы. Важно, чтобы хотя бы интерфейсы были читаемы и просты.
Я вот сразу догадался, что isalnum'у передают char с отрицательным значением.

Такой вот у нас в C isalnum. Понять это нельзя, это можно только запомнить.

Я всегда недолюбливал локали. Теперь я знаю почему они так странно сделаны. Хотя это всё ни капли не извиняет их создателей. Спасибо.

А где тут история библиотек? Реализая из musl выглядит как написанная за пять минут, под силу даже школьнику — понятно почему она выглядит именно так. А вот почему в glibc так написано — непонятно, явно преследовали какую-то цель, которую можно посмотреть по коммитам, и для этого точно требовались все эти средства. Но эта тема остаётся нераскрыта.
А где тут история библиотек?

Наверное правильнее было бы перевести как "рассказ о ..." (в оригинале a tale of).


А вот почему в glibc так написано — непонятно, явно преследовали какую-то цель, которую можно посмотреть по коммитам, и для этого точно требовались все эти средства.

Как минимум, эта реализация, в отличие от musl, поддерживает локали (что предписано стандартом).
А столько макросов навёрнуто вероятно ради быстрой работы на всех поддерживаемых архитектурах.

Традиционно "A Tale of Two Cities", к которому, вероятно, отсылает название оригинала, переводится как "Повесть о двух городах".

Если я правильно помню, в MSVC как раз есть отладочный assert на то, что аргумент находится в допустимом диапазоне. Те, кто хоть раз «напоролся» — наверное, надолго запоминают про эту особенность функций ctype…

В голосовалке не хватает опции "Кривой стандарт ISO C". Почему не бы дополнить описание функции isalnum тем, что на всех остальных значениях возвращать false?

Это понятно. Однако в 2020-м году в разработке ПО уже другие приоритеты, поэтому лично я бы проголосовал за предложенный мною пункт.
У кого другие приоритеты, тот в 2020-м году будет писать не на Си.
Но стандарт принимается не только для тех, кто программы пишет, но и для тех, кто этими программами пользуется. Я, как потребитель C-шных программ, голосую за п. 4.

Как ни крути, если в функцию, работающую только с однобайтными кодировками передавать двухбайтный символ, в программе будет баг.
Вопрос только в том, сделать ли его детерминированным и одинаковым для всех реализаций стандартной библиотеки (и, соответственно, замедлить работу даже для корректных значений) или разрешить реализациям не обрабатывать специальным образом некорректные значения (чем glibc довольно эффективно пользуется).

И сразу медленнее! Нашли как выкрутится сейчас — найдут и как выкрутиться потом.

Мне нравится комментарий в libc:
ISO C требует, чтобы функции ctype работали
со значениями типа `unsigned char' и EOF; мы также поддерживаем отрицательные
значения `signed char' для совместимости со старыми некорректными программами

То есть, чуть-чуть, но они отступают от принципа «никаких компромисов». Добавили лишних 768 байт в таблицах, чтобы некорректный код не падал.
Автор нагнетает за счет интригующего расследования по поиску реализации функции. Но этот поиск делается за минуту с помощью опций gcc --save-temps -C. После запуска компиляции с этими опциями образуются файлы с расширением .i, в которых все будет уже на блюдечке подготовлено. Ковыряться в исходниках glibc необязательно.
Может быть, так бы он быстрее разобрался, но чтобы подготовить материал для статьи, недостаточно вывалить портянку препроцессированного кода. Нужно показать, что откуда взялось.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Минуточку внимания

Разместить