Насколько опасен этот "быстрый"?

strlen - довольно простая функция, и, очевидно, O (n) вычисляется. Тем не менее, я видел несколько подходов, которые работают более чем на одного персонажа за раз. См. Пример 5 здесь или этот подход здесь. Основным способом этой работы является реинтерпрет-литье буфера char const* в буфер uint32_t const*, а затем проверка по четыре байта за раз.

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

Я думаю, что это включает UB по двум причинам:

Потенциальная развязка вне допустимой памяти
Потенциальное разыменование неглавного указателя

(_{^{Обратите внимание, что проблема с псевдонимом отсутствует, можно подумать, что uint32_t псевдонимы как несовместимый тип и код после strlen (например, код, который может изменить строку) может выйти из строя до strlen, но оказывается, что char является явным исключением из строкового сглаживания}}).

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

Ответ 1

Метод действителен, и вы не избежите его, если вы позвоните в нашу библиотеку C strlen. Если эта библиотека является, например, последней версией библиотеки GNU C (по крайней мере, для определенных целей), она делает то же самое.

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

Это, безусловно, не является корректным поведением в C, и поэтому он переносит бремя тщательной проверки при переносе из одного компилятора в другой. Он также запускает ложные срабатывания из детекторов доступа вне пределов, таких как Valgrind.

Valgrind пришлось заплатить, чтобы работать над Glibc. Без патчей вы получаете такие неприятные ошибки, как:

==13669== Invalid read of size 8
==13669==    at 0x411D6D7: __wcslen_sse2 (wcslen-sse2.S:59)
==13669==    by 0x806923F: length_str (lib.c:2410)
==13669==    by 0x807E61A: string_out_put_string (stream.c:997)
==13669==    by 0x8075853: obj_pprint (lib.c:7103)
==13669==    by 0x8084318: vformat (stream.c:2033)
==13669==    by 0x8081599: format (stream.c:2100)
==13669==    by 0x408F4D2: (below main) (libc-start.c:226)
==13669==  Address 0x43bcaf8 is 56 bytes inside a block of size 60 alloc'd
==13669==    at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==13669==    by 0x8063C4F: chk_malloc (lib.c:1763)
==13669==    by 0x806CD79: sub_str (lib.c:2653)
==13669==    by 0x804A7E2: sysroot_helper (txr.c:233)
==13669==    by 0x408F4D2: (below main) (libc-start.c:226)

Glibc использует инструкции SSE для вычисления wcslen восьми байтов за раз (вместо четырех, ширины wchar_t). При этом он обращается к офсету 56 в блоке шириной 60 байтов. Однако обратите внимание, что этот доступ никогда не может пересекать границу страницы: адрес делится на 8.

Если вы работаете на ассемблере, вам не нужно дважды думать о технике.

Фактически, этот метод используется довольно немного в некоторых оптимизированных аудиокодеках, с которыми я работаю (с целью ARM), которые содержат множество языков ассемблера, написанных вручную, в наборе инструкций Neon.

Я заметил это при запуске Valgrind на коде, который интегрировал эти кодеки, и связался с продавцом. Они объяснили, что это всего лишь безобидная техника оптимизации цикла; Я прошел через ассемблер и убедился, что они правы.

Ответ 2

(1) может случиться. Там ничего не мешает вам взять strlen строки рядом с выделенной страницей, что может привести к доступу к концу выделенной памяти и приятному большому сбою. Как вы заметили, это можно было бы смягчить, заполнив все ваши распределения, но тогда у вас должны быть какие-то библиотеки, сделайте то же самое. Хуже того, вам нужно организовать компоновщик и ОС, чтобы всегда добавлять это дополнение (помните, что OS пропускает argv [] в буфере статической памяти где-нибудь). Накладные расходы на это не стоят.

(2) также определенно происходит. Более ранние версии ARM-процессоров генерируют прерывания данных при неглавных доступах, которые либо заставляют вашу программу умирать с ошибкой шины (или останавливать CPU, если вы используете bare-metal), либо заставляете очень дорогое ловушку через ядро обрабатывать несвязанный доступ. Эти ранее чипы ARM по-прежнему широко используются в старых мобильных телефонах и встроенных устройствах. Позже ARM-процессоры синтезируют множественные текстовые обращения, чтобы иметь дело с негласными доступами, но это приведет к общей более низкой производительности, поскольку вы в основном удваиваете количество загрузок памяти, которые вам нужно делать.

Многие текущие ( "современные" ) ПОС и встроенные микропроцессоры не имеют логики для обработки неприсоединенных доступов и могут вести себя непредсказуемо или даже бессмысленно при заданных несогласованных адресах (я лично видел чипы, которые просто маскируют нижние биты, что дадут неправильные ответы, а другие, которые будут просто давать результаты мусора с неприсоединившимися обращениями).

Таким образом, это смехотворно опасно использовать во всем, что должно быть отдаленно переносимым. Пожалуйста, пожалуйста, не используйте этот код; используйте libc strlen. Обычно это будет быстрее (оптимизировано для вашей платформы) и сделает ваш код переносимым. Последнее, что вам нужно, - это то, что ваш код тонко и неожиданно ломается в некоторой ситуации (строка ближе к концу выделения) или на каком-то новом процессоре.

Ответ 3

Дональд Кнут, человек, который написал 3 + тома по умным алгоритмам, сказал: "Преждевременная оптимизация - это корень всего зла".

strlen() используется много, поэтому он действительно должен быть быстрым. Riffing на замечании wildplasser: "Я бы доверял библиотечной функции", что заставляет вас думать, что функция библиотеки работает байт за раз? Или медленно?

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

Я скомпилировал простую программу на C и посмотрел на свою 64-битную систему, которая использует функцию GNU glibc. Код, который я видел, был довольно сложным и выглядел довольно быстро с точки зрения работы с шириной регистра, а не байта за раз. Код, который я видел для strlen(), написан на языке ассемблера, поэтому, вероятно, не есть ненужных инструкций, которые вы могли бы получить, если бы это был скомпилированный C-код. То, что я увидел, было rtld-strlen.S. Этот код также разворачивает циклы, чтобы уменьшить накладные расходы при циклировании.

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

И если вы пишете собственный strlen, сравните его с существующей реализацией.

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

Ответ 4

Я согласен с этим на bletcherous технику, но я подозреваю, что она, скорее всего, будет работать большую часть времени. Это только segfault, если строка оказывается прямо против конца вашего сегмента данных (или стека). Подавляющее большинство строк (которые статически или динамически распределены) не будут.

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

Если выравнивание является проблемой, вы можете позаботиться об этом в быстрой реализации strlen; вам не придется бегать, пытаясь выровнять все строки.

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