Я просматривал strlenкод здесь и мне было интересно, действительно ли нужны оптимизации, используемые в коде? Например, почему что-то вроде следующего не работает одинаково хорошо или лучше?
unsigned long strlen(char s[]) {
unsigned long i;
for (i = 0; s[i] != '\0'; i++)
continue;
return i;
}Разве не проще и / или проще код оптимизировать компилятор?
Код strlenна странице за ссылкой выглядит так:
/* Copyright (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc. This file is part of the GNU C Library. Written by Torbjorn Granlund (tege@sics.se), with help from Dan Sahlin (dan@sics.se); commentary by Jim Blandy (jimb@ai.mit.edu). The GNU C Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. The GNU C Library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with the GNU C Library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ #include <string.h> #include <stdlib.h> #undef strlen /* Return the length of the null-terminated string STR. Scan for the null terminator quickly by testing four bytes at a time. */ size_t strlen (str) const char *str; { const char *char_ptr; const unsigned long int *longword_ptr; unsigned long int longword, magic_bits, himagic, lomagic; /* Handle the first few characters by reading one character at a time. Do this until CHAR_PTR is aligned on a longword boundary. */ for (char_ptr = str; ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; ++char_ptr) if (*char_ptr == '\0') return char_ptr - str; /* All these elucidatory comments refer to 4-byte longwords, but the theory applies equally well to 8-byte longwords. */ longword_ptr = (unsigned long int *) char_ptr; /* Bits 31, 24, 16, and 8 of this number are zero. Call these bits the "holes." Note that there is a hole just to the left of each byte, with an extra at the end: bits: 01111110 11111110 11111110 11111111 bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD The 1-bits make sure that carries propagate to the next 0-bit. The 0-bits provide holes for carries to fall into. */ magic_bits = 0x7efefeffL; himagic = 0x80808080L; lomagic = 0x01010101L; if (sizeof (longword) > 4) { /* 64-bit version of the magic. */ /* Do the shift in two steps to avoid a warning if long has 32 bits. */ magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; himagic = ((himagic << 16) << 16) | himagic; lomagic = ((lomagic << 16) << 16) | lomagic; } if (sizeof (longword) > 8) abort (); /* Instead of the traditional loop which tests each character, we will test a longword at a time. The tricky part is testing if *any of the four* bytes in the longword in question are zero. */ for (;;) { /* We tentatively exit the loop if adding MAGIC_BITS to LONGWORD fails to change any of the hole bits of LONGWORD. 1) Is this safe? Will it catch all the zero bytes? Suppose there is a byte with all zeros. Any carry bits propagating from its left will fall into the hole at its least significant bit and stop. Since there will be no carry from its most significant bit, the LSB of the byte to the left will be unchanged, and the zero will be detected. 2) Is this worthwhile? Will it ignore everything except zero bytes? Suppose every byte of LONGWORD has a bit set somewhere. There will be a carry into bit 8. If bit 8 is set, this will carry into bit 16. If bit 8 is clear, one of bits 9-15 must be set, so there will be a carry into bit 16. Similarly, there will be a carry into bit 24. If one of bits 24-30 is set, there will be a carry into bit 31, so all of the hole bits will be changed. The one misfire occurs when bits 24-30 are clear and bit 31 is set; in this case, the hole at bit 31 is not changed. If we had access to the processor carry flag, we could close this loophole by putting the fourth hole at bit 32! So it ignores everything except 128's, when they're aligned properly. */ longword = *longword_ptr++; if ( #if 0 /* Add MAGIC_BITS to LONGWORD. */ (((longword + magic_bits) /* Set those bits that were unchanged by the addition. */ ^ ~longword) /* Look at only the hole bits. If any of the hole bits are unchanged, most likely one of the bytes was a zero. */ & ~magic_bits) #else ((longword - lomagic) & himagic) #endif != 0) { /* Which of the bytes was the zero? If none of them were, it was a misfire; continue the search. */ const char *cp = (const char *) (longword_ptr - 1); if (cp[0] == 0) return cp - str; if (cp[1] == 0) return cp - str + 1; if (cp[2] == 0) return cp - str + 2; if (cp[3] == 0) return cp - str + 3; if (sizeof (longword) > 4) { if (cp[4] == 0) return cp - str + 4; if (cp[5] == 0) return cp - str + 5; if (cp[6] == 0) return cp - str + 6; if (cp[7] == 0) return cp - str + 7; } } } } libc_hidden_builtin_def (strlen)
Почему эта версия работает быстро?
Разве это не делает много ненужной работы?
c
optimization
glibc
portability
strlen
Гонки легкости на орбите
источник
источник
sysdepsвместо этого будет использоваться рукописная реализация на ассемблере из каталога, в большинстве поддерживаемых архитектур glibc (наиболее часто используемая архитектура, которая не имеет замены, - это MIPS).Ответы:
Вам не нужно, и вы никогда не должны писать такой код, особенно если вы не являетесь поставщиком компилятора C / стандартной библиотеки. Это код, используемый для реализации
strlenс некоторыми весьма сомнительными оценками скорости и предположениями (которые не проверяются с утверждениями или не упоминаются в комментариях):unsigned long4 или 8 байтовunsigned long longа неuintptr_tunsigned longsБолее того, хороший компилятор может даже заменить код, написанный как
(обратите внимание, что это должен быть тип, совместимый с
size_t) со встроенной версией встроенного компилятораstrlenили векторизовать код; но компилятор вряд ли сможет оптимизировать сложную версию.strlenФункция описывается С11 7.24.6.3 , как:Теперь, если указанная строка
sнаходится в массиве символов, достаточно длинном, чтобы содержать строку и завершающий NUL, поведение будет неопределенным, если мы получим доступ к строке после нулевого терминатора, например, вТак что на самом деле единственный способ в полностью переносимой / совместимой со стандартами C реализации правильно это так, как написано в вашем вопросе , за исключением тривиальных преобразований - вы можете притвориться быстрее, развернув цикл и т. Д., Но это все еще нужно сделать один байт за раз.
(Как отметили комментаторы, когда строгая переносимость является слишком обременительным, использование разумных или безопасных предположений не всегда плохо. Особенно в коде, который является частью одной конкретной реализации на Си. Но вы должны понимать правила, прежде чем знать, как / когда вы можете согнуть их.)
Связанная
strlenреализация сначала проверяет байты индивидуально, пока указатель не укажет на естественную границу выравнивания 4 или 8 байтовunsigned long. Стандарт C говорит, что доступ к указателю, который не выровнен должным образом, имеет неопределенное поведение , поэтому это абсолютно необходимо сделать для того, чтобы следующий грязный трюк был еще более грязным. (На практике на некоторых архитектурах ЦП, отличных от x86, некорректно загружается слово или двойное слово. C не является переносимым языком ассемблера, но этот код использует его таким образом). Это также то, что позволяет читать после конца объекта без риска сбоев в реализациях, где защита памяти работает в выровненных блоках (например, страницы виртуальной памяти размером 4 КБ).Теперь перейдем к грязной части: код нарушает обещание и читает 4 или 8 8-битных байтов за раз (a
long int) и использует битовый трюк с добавлением без знака, чтобы быстро выяснить, были ли какие-либо нулевые байты в этих 4 или 8 байты - он использует специально созданное число, которое заставляет бит переноса изменять биты, которые перехватываются битовой маской. В сущности, тогда можно было бы выяснить, являются ли какие-либо из 4 или 8 байтов в маске нулями, предположительно быстрее, чем цикл по каждому из этих байтов. Наконец, в конце есть цикл для определения, какой байт был первым нулем, если таковой имеется, и для возврата результата.Самая большая проблема в том , что в
sizeof (unsigned long) - 1случаях изsizeof (unsigned long)случаев он будет читать после конца строки - только если нулевой байт в последнем Accessed байта (т.е. прямой порядок байтов самым значительным, и в биг-младшему наименее значимый) , это не доступ к массиву за пределами!Код, даже если он используется для реализации
strlenв стандартной библиотеке C, является плохим кодом. В нем есть несколько аспектов, определяемых реализацией и не определенных, и его не следует нигде использовать вместо предоставляемых системойstrlen- я переименовал функциюthe_strlenздесь и добавил следующееmain:Размер буфера тщательно определен, чтобы в нем можно было хранить только
hello worldстроку и терминатор. Однако на моем 64-битном процессореunsigned longэто 8 байтов, поэтому доступ к последней части будет превышать этот буфер.Если я компилировать с
-fsanitize=undefinedи-fsanitize=addressи запустить полученную программу, я получаю:то есть случилось что-то плохое.
источник
Там было много (немного или полностью) неправильных предположений в комментариях о некоторых деталях / предыстории для этого.
Вы смотрите на оптимизированную реализацию glibc, оптимизированную для резервного копирования. (Для ISA, у которых нет рукописной реализации asm) . Или старая версия этого кода, которая все еще находится в исходном дереве glibc. https://code.woboq.org/userspace/glibc/string/strlen.c.html - это браузер кода, основанный на текущем git-дереве glibc. По-видимому, он все еще используется несколькими основными целями glibc, включая MIPS. (Спасибо, @zwol).
На популярных ISA, таких как x86 и ARM, glibc использует рукописный asm
Таким образом, стимул изменить что-либо в этом коде ниже, чем вы думаете.
Этот битхак-код ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) не тот, который на самом деле работает на вашем сервере / настольном компьютере / ноутбуке / смартфоне. Это лучше, чем простой байтовый цикл, но даже этот битхак довольно плох по сравнению с эффективным asm для современных процессоров (особенно x86, где AVX2 SIMD позволяет проверять 32 байта с помощью пары инструкций, позволяя от 32 до 64 байтов в такт Цикл в основном цикле, если данные горячие в кеше L1d на современных процессорах с 2 / тактовой векторной нагрузкой и пропускной способностью ALU, т.е. для строк среднего размера, где накладные расходы при запуске не доминируют.)
glibc использует приемы динамического связывания для
strlenопределения оптимальной версии для вашего процессора, поэтому даже в x86 есть версия SSE2 (16-байтовые векторы, базовый для x86-64) и версия AVX2 (32-байтовые векторы).x86 имеет эффективную передачу данных между векторными и универсальными регистрами, что делает его уникальным (?) подходящим для использования SIMD для ускорения функций в строках неявной длины, где управление циклом зависит от данных.
pcmpeqb/pmovmskbпозволяет тестировать 16 отдельных байтов одновременно.glibc имеет версию AArch64, аналогичную версии с использованием AdvSIMD , и версию для процессоров AArch64, где vector-> GP регистрирует останов конвейера, поэтому он действительно использует этот битхак . Но использует счетчики, ведущие к нулям, чтобы найти байт внутри регистра, как только он получит попадание, и использует эффективный доступ без выравнивания AArch64 после проверки на пересечение страниц.
Также связано: почему этот код в 6.5 раз медленнее с включенной оптимизацией? есть некоторые подробности о том, что является быстрым или медленным в x86 asm для
strlenс большим буфером и простой реализацией asm, что может быть полезно для gcc, чтобы знать, как встроить. (Некоторые версии gcc неразумно встроены,rep scasbчто очень медленно, или битовый хакер по 4 байта за раз, как этот. Поэтому рецепт GCC inline-strlen нуждается в обновлении или отключении.)У Asm нет "неопределенного поведения" в стиле C ; доступ к байтам в памяти безопасен, как вам угодно, и выровненная загрузка, включающая в себя любые допустимые байты, не может дать сбой. Защита памяти происходит с гранулярностью выровненных страниц; Выровненный доступ, более узкий, чем тот, который не может пересечь границу страницы. Безопасно ли читать за пределами буфера на одной и той же странице на x86 и x64? Те же рассуждения применимы к машинному коду, который этот хакер C заставляет компиляторы создавать для автономной не встроенной реализации этой функции.
Когда компилятор генерирует код для вызова неизвестной не встроенной функции, он должен предполагать, что функция изменяет любые / все глобальные переменные и любую память, на которую может иметь указатель. то есть все, кроме местных жителей, у которых не было экранирования адреса, должно быть синхронизировано в памяти через вызов. Это относится к функциям, написанным в asm, очевидно, но также и к библиотечным функциям. Если вы не включаете оптимизацию во время компоновки, она применяется даже к отдельным единицам перевода (исходным файлам).
Почему это безопасно как часть glibc, но никак иначе.
Наиболее важным фактором является то, что это
strlenне может влиять ни на что другое. Это не безопасно для этого; он содержит строгий псевдоним UB (чтениеcharданных черезunsigned long*).char*разрешено Алиас что - либо другое , но обратное не верно .Это функция библиотеки для заранее скомпилированной библиотеки (glibc). Это не будет встроено с оптимизацией времени соединения к вызывающим. Это означает, что он просто должен скомпилировать в безопасный машинный код для автономной версии
strlen. Это не должно быть портативным / безопасным C.Библиотека GNU C должна компилироваться только с GCC. Очевидно, что не поддерживается компиляция с использованием clang или ICC, даже если они поддерживают расширения GNU. GCC - опережающий компилятор, который превращает исходный файл C в объектный файл машинного кода. Не интерпретатор, поэтому, если он не встроен во время компиляции, байты в памяти - это просто байты в памяти. т.е. UB со строгим псевдонимом не опасен, когда доступ с разными типами происходит в разных функциях, которые не связаны друг с другом.
Помните , что
strlenповедение «S определяется по стандарту ISO C. Это имя функции определенно является частью реализации. Компиляторы, такие как GCC, даже обрабатывают имя как встроенную функцию, если вы не используете ее-fno-builtin-strlen, поэтому онаstrlen("foo")может быть константой времени компиляции3. Определение в библиотеке используется только в том случае, если gcc решает на самом деле передать ему вызов, а не вставлять свой собственный рецепт или что-то в этом роде.Когда UB не виден компилятору во время компиляции, вы получаете нормальный машинный код. Машинный код должен работать в случае не-UB, и даже если вы хотели , чтобы, нет никакого способа для ASM , чтобы обнаружить , какие типы вызывающие клали данные в указываемом в память.
Glibc скомпилирован в автономную статическую или динамическую библиотеку, которая не может быть встроена в оптимизацию во время соединения. Сценарии сборки glibc не создают «жирных» статических библиотек, содержащих машинный код + внутреннее представление gcc GIMPLE для оптимизации во время компоновки при встраивании в программу. (т.е.
libc.aне будет участвовать в-fltoоптимизации времени соединения с основной программой.) Построение glibc таким образом было бы потенциально небезопасно для целей, которые фактически используют это.c.Фактически, как комментирует @zwol, LTO не может использоваться при сборке самого glibc из-за «хрупкого» кода, подобного этому, который может сломаться, если будет возможно встраивание между исходными файлами glibc. (Есть некоторые внутренние применения
strlen, например, возможно, как частьprintfреализации)Это
strlenделает некоторые предположения:CHAR_BITкратно 8 . Правда на всех системах GNU. POSIX 2001 даже гарантируетCHAR_BIT == 8. (Это выглядит безопасным для систем сCHAR_BIT= 16или32, как некоторые DSP; цикл unaligned-prologue будет всегда выполнять 0 итераций, если,sizeof(long) = sizeof(char) = 1потому что каждый указатель всегда выровнен иp & sizeof(long)-1всегда равен нулю.) Но если у вас был набор символов не-ASCII, где chars равны 9 или 12 бит в ширину,0x8080...это неправильный шаблон.unsigned longсоставляет 4 или 8 байтов. Или, может быть, он будет работать для любого размераunsigned longдо 8, и он используетassert()для проверки этого.Эти два невозможны UB, они просто не переносимы для некоторых реализаций Си. Этот код является (или был) частью реализации C на платформах, где он работает, так что это нормально.
Следующее предположение является потенциальным C UB:
0- UB; это может бытьchar[]массив C, содержащий,{1,2,0,3}например)Этот последний момент - то, что делает безопасным чтение после конца объекта C здесь. Это довольно безопасно, даже если встраивать с текущими компиляторами, потому что я думаю, что в настоящее время они не считают, что путь исполнения недоступен. Но, в любом случае, строгий псевдоним уже стоит на пороге, если вы когда-нибудь позволите этому встроиться.
Тогда у вас будут проблемы, такие как старый небезопасный
memcpyмакрос CPP ядра Linux, который использует приведение указателей кunsigned long( gcc, строгое псевдонимы и ужасные истории ).Это
strlenвосходит к эпохе, когда вы могли бы сойти с рук в общем такие вещи ; Раньше до GCC3 он был довольно безопасным без предостережения «только когда не встраивался».UB, который виден только при взгляде через границы вызова / возврата, не может повредить нам. (например, вызывая это
char buf[]вместо массиваunsigned long[]приведения к aconst char*). Как только машинный код установлен в камне, он просто работает с байтами в памяти. При вызове не встроенной функции необходимо предположить, что вызываемый объект считывает любую / всю память.Написание этого безопасно, без строго псевдонимов UB
Атрибут типа НКУ
may_aliasдает тип такой же псевдоним, ничего лечения какchar*. (Предложено @KonradBorowsk). В настоящее время заголовки GCC используют его для векторных типов x86 SIMD,__m128iтак что вы всегда можете это сделать безопасно_mm_loadu_si128( (__m128i*)foo ). (См. 'Reinterpret_cast`ing между аппаратным указателем вектора и соответствующим типом неопределенного поведения? Для получения дополнительной информации о том, что это делает и не означает.)Вы также можете использовать
aligned(1)для выражения типа сalignof(T) = 1.typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;Портативный способ выразить нагрузку на псевдонимы в ISO - это то
memcpy, что современные компиляторы знают, как встроить в качестве одной инструкции загрузки. напримерЭто также работает для не выровненных нагрузок, потому что
memcpyработает как-будтоchar-на-время доступа. Но на практике современные компиляторы это прекрасно понимаютmemcpy.Опасность здесь заключается в том, что если GCC не знает наверняка, что
char_ptrвыровнено по словам, оно не встроит его на некоторых платформах, которые могут не поддерживать невыровненные загрузки в asm. например, MIPS до MIPS64r6 или более ранняя версия ARM. Если бы вы получили реальный вызов функции, чтобыmemcpyпросто загрузить слово (и оставить его в другой памяти), это было бы катастрофой. GCC иногда может видеть, когда код выравнивает указатель. Или после цикла char-at-a-time, который достигает удлиненной границы, вы можете использоватьp = __builtin_assume_aligned(p, sizeof(unsigned long));Это не исключает возможности UB для чтения за объектом, но с текущим GCC это не опасно на практике.
Почему необходим оптимизированный вручную C-источник: современные компиляторы недостаточно хороши
Оптимизированный вручную ассм может быть еще лучше, если вы хотите, чтобы каждая последняя капля производительности для широко используемой стандартной функции библиотеки. Особенно за что-то подобное
memcpy, но такжеstrlen. В этом случае было бы намного проще использовать C с внутренними компонентами x86, чтобы использовать преимущества SSE2.Но здесь мы просто говорим о версии C наивной против bithack без каких-либо специфичных для ISA функций.
(Я думаю, что мы можем принять его как
strlenдостаточно широко используемое, поэтому важно, чтобы оно работало максимально быстро. Поэтому возникает вопрос, можем ли мы получить эффективный машинный код из более простого источника. Нет, мы не можем.)Текущие GCC и clang не способны автоматически векторизовать циклы, где число итераций не известно до первой итерации . (Например, должна быть возможность проверить, будет ли цикл выполняться по крайней мере 16 итераций перед выполнением первой итерации.) Например, возможна автовекторизация memcpy (буфер явной длины), но не strcpy или strlen (строка неявной длины), учитывая текущий компиляторы.
Это включает в себя поисковые циклы или любой другой цикл с зависимым от данных,
if()breakа также счетчиком.ICC (компилятор Intel для x86) может автоматически векторизовать некоторые поисковые циклы, но все еще создает наивный асимметричный асимметричный ассемблер для простого / наивного C,
strlenтакого как libc в OpenBSD. ( Godbolt ). (Из ответа @ Песке ).Оптимизированный вручную libc
strlenнеобходим для производительности с текущими компиляторами . Переход по 1 байту за раз (при развертывании, возможно, 2 байта за цикл на широких суперскалярных процессорах) жалок, когда основная память может поддерживать около 8 байтов за цикл, а кэш-память L1d может доставлять от 16 до 64 за цикл. (2x 32-байтовые загрузки за цикл на современных основных процессорах x86 начиная с Haswell и Ryzen. Не считая AVX512, который может снизить тактовые частоты только для использования 512-битных векторов; именно поэтому glibc, вероятно, не спешит добавлять версию AVX512 Хотя AVX512VL + BW с 256-битными векторами маскируются, сравниваются с маской и /ktestилиkortestмогут сделатьstrlenболее дружественным к гиперпоточности, уменьшив количество операций / итераций.)Я включаю не x86 здесь, это "16 байт". например, большинство процессоров AArch64, по-моему, могут сделать это, а некоторые, безусловно, больше. А некоторые имеют достаточную пропускную способность,
strlenчтобы не отставать от этой полосы пропускания нагрузки.Конечно, программы, работающие с большими строками, обычно должны отслеживать длины, чтобы избежать необходимости повторного поиска длины строк C неявной длины. Но производительность от короткой до средней длины все еще выигрывает от рукописных реализаций, и я уверен, что некоторые программы в конечном итоге используют strlen для строк средней длины.
источник
CHAR_BIT == 8является требованием POSIX (по состоянию на -2001 rev; см. Здесь ). (4) Откатная реализация Cstrlenиспользуется для некоторых поддерживаемых процессоров, я считаю, что наиболее распространенным является MIPS.__attribute__((__may_alias__))атрибут (это непереносимо, но для glibc должно быть хорошо).char*, но все равно UB - читать / записыватьcharобъект (например, часть achar[]) через along*. Строгое правило псевдонимов и указатели 'char *'CHAR_BITдолжны быть как минимум 8 ( см. Приложение E к C11), поэтому, по крайней мере, 7-битныйcharкод не должен беспокоить юриста. Это было мотивировано требованием: «Для строковых литералов UTF-8 элементы массива имеют типcharи инициализируются символами многобайтовой последовательности символов, как закодировано в UTF-8».Это объясняется в комментариях к файлу, который вы связали:
и:
В С можно подробно рассуждать об эффективности.
Менее эффективно перебирать отдельные символы, ищущие ноль, чем тестировать более одного байта за раз, как это делает этот код.
Дополнительная сложность возникает из-за необходимости обеспечить выравнивание тестируемой строки в нужном месте, чтобы начать тестирование более одного байта за раз (вдоль границы длинного слова, как описано в комментариях), и из-за необходимости гарантировать, что предположения о размерах типов данных не нарушаются при использовании кода.
В большинстве (но не во всех) современных разработках программного обеспечения такое внимание к деталям эффективности не является необходимым или не стоит затрат на дополнительную сложность кода.
Единственное место, где имеет смысл обратить внимание на эффективность, как это, в стандартных библиотеках, как пример, который вы привели.
Если вы хотите узнать больше о границах слов, посмотрите этот вопрос и отличную страницу википедии.
источник
В дополнение к отличным ответам здесь я хочу отметить, что код, связанный с этим вопросом, предназначен для реализации GNU
strlen.Реализация OpenBSD
strlenочень похожа на код, предложенный в вопросе. Сложность реализации определяется автором.РЕДАКТИРОВАТЬ : код OpenBSD, который я связал выше, выглядит резервной реализацией для ISA, у которых нет собственной реализации asm. Существуют разные реализации в
strlenзависимости от архитектуры. Например, код для amd64strlen- asm. Аналогично комментариям / ответам PeterCordes, указывающим на то, что неустранимые реализации GNU также являются asm.источник
s - strне определено, если результат не представлен вptrdiff_t.PTRDIFF_MAX. Но по-прежнему возможноmmapбольше памяти, чем в Linux, по крайней мере (например, в 32-разрядном процессе под ядром x86-64 я мог бы отобразить около 2,7 ГБ непрерывно, прежде чем у меня начались сбои). ИДК об OpenBSD; ядро может сделать невозможным достижение этогоreturnбез сегфагинга или остановки в пределах размера. Но да, вы могли бы подумать, что защитное кодирование, которое избегает теоретического C UB, будет тем, что OpenBSD захочет сделать. Даже при том, чтоstrlenне может быть встроенным, и реальные компиляторы просто скомпилируют его в вычитание.Короче говоря, это оптимизация производительности, которую стандартная библиотека может сделать, зная, с каким компилятором она скомпилирована - вы не должны писать такой код, если только вы не пишете стандартную библиотеку и можете зависеть от конкретного компилятора. В частности, он обрабатывает число выравнивания байтов одновременно - 4 на 32-битных платформах, 8 на 64-битных платформах. Это означает, что это может быть в 4 или 8 раз быстрее, чем простая итерация байтов.
Чтобы объяснить, как это работает, рассмотрите следующее изображение. Предположим, здесь 32-битная платформа (выравнивание 4 байта).
Допустим, что буква "H" из "Привет, мир!" Строка была предоставлена в качестве аргумента для
strlen. Поскольку процессору нравится выравнивать вещи в памяти (в идеале,address % sizeof(size_t) == 0), байты перед выравниванием обрабатываются побайтово, используя медленный метод.Затем для каждого блока размера выравнивания путем вычисления
(longbits - 0x01010101) & 0x80808080 != 0проверяется, равен ли ноль любой из байтов в целом числе. Этот расчет имеет ложное срабатывание, когда хотя бы один из байтов больше0x80, но чаще всего он должен работать. Если это не так (как в желтой области), длина увеличивается на размер выравнивания.Если какой-либо из байтов в целом числе оказывается равным нулю (или
0x81), то строка проверяется побайтно для определения позиции нуля.Это может сделать доступ за пределы допустимого, однако, поскольку он находится в пределах выравнивания, это более вероятно, чем не очень хорошо, единицы отображения памяти обычно не имеют точности уровня байтов.
источник
size_tне гарантируется выравнивание.Вы хотите, чтобы код был правильным, поддерживаемым и быстрым. Эти факторы имеют различное значение:
«правильно» абсолютно необходимо.
«Сопровождаемость» зависит от того, сколько вы собираетесь поддерживать код: более 40 лет strlen была библиотечной функцией Standard C. Это не изменится. Поэтому ремонтопригодность совершенно не важна - для этой функции.
«Быстрый»: во многих приложениях strcpy, strlen и т. Д. Используют значительное количество времени выполнения. Для достижения такого же общего прироста скорости, как и в этой сложной, но не очень сложной реализации strlen путем улучшения компилятора, потребуются героические усилия.
Быть быстрым имеет еще одно преимущество: когда программисты узнают, что вызов «strlen» является самым быстрым методом, они могут измерить количество байтов в строке, они больше не испытывают соблазна написать свой собственный код, чтобы ускорить процесс.
Так что для strlen скорость гораздо важнее, а удобство сопровождения гораздо менее важно, чем для большинства кода, который вы когда-либо будете писать.
Почему это должно быть так сложно? Скажем, у вас есть строка длиной 1000 байт. Простая реализация будет проверять 1000 байтов. Текущая реализация, вероятно, будет проверять 64-битные слова за раз, что означает 125 64-битных или восьмибайтовых слов. Он может даже использовать векторные инструкции, проверяющие, скажем, 32 байта за раз, что будет еще сложнее и еще быстрее. Использование векторных инструкций приводит к тому, что код немного более сложный, но довольно простой: проверка того, является ли один из восьми байтов в 64-битном слове нулевым, требует некоторых хитрых приемов. Таким образом, для средних и длинных строк этот код может быть примерно в четыре раза быстрее. Для такой важной функции, как strlen, стоит написать более сложную функцию.
PS. Код не очень переносимый. Но это часть библиотеки Standard C, которая является частью реализации - она не должна быть переносимой.
PPS. Кто-то опубликовал пример, в котором инструмент отладки жаловался на доступ к байту за концом строки. Может быть разработана реализация, которая гарантирует следующее: Если p является действительным указателем на байт, то любой доступ к байту в том же выровненном блоке, который будет иметь неопределенное поведение в соответствии со стандартом C, будет возвращать неопределенное значение.
PPPS. Intel добавила инструкции к своим более поздним процессорам, которые образуют строительный блок для функции strstr () (поиск подстроки в строке). Их описание ошеломляет, но они могут сделать эту функцию, вероятно, в 100 раз быстрее. (По сути, учитывая массив a, содержащий «Hello, world!» И массив b, начинающийся с 16 байтов «HelloHelloHelloH» и содержащий больше байтов, он выясняет, что строка a не встречается в b раньше, чем начиная с индекса 15) ,
источник
Вкратце: проверка строки за байтом может быть медленной на архитектурах, которые могут извлекать большие объемы данных за раз.
Если проверка на нулевое завершение может быть выполнена на 32- или 64-битной основе, это уменьшает количество проверок, которые должен выполнить компилятор. Это то, что пытается сделать связанный код с учетом конкретной системы. Они делают предположения об адресации, выравнивании, использовании кэша, нестандартных настройках компилятора и т. Д. И т. Д.
Чтение за байтом, как в вашем примере, будет разумным подходом для 8-битного процессора или при написании переносимой библиотеки, написанной на стандартном C.
Глядя на стандартные библиотеки C, чтобы посоветовать, как писать быстрый / хороший код, не очень хорошая идея, потому что он будет непереносимым и будет опираться на нестандартные предположения или плохо определенное поведение. Если вы новичок, чтение такого кода, скорее всего, будет более вредным, чем образовательный.
источник
if()break. ICC может автоматически векторизовать такие циклы, но IDK, как хорошо это делает с наивным strlen. И да, SSE2pcmpeqb/pmovmskbэто очень хорошо для STRLEN, тестирование 16 байт за один раз. code.woboq.org/userspace/glibc/sysdeps/x86_64/strlen.S.html - версия glibc для SSE2. Смотрите также этот Q & A .Одна важная вещь, не упомянутая в других ответах, заключается в том, что FSF очень осторожно следит за тем, чтобы частный код не превращался в проекты GNU. В стандартах кодирования GNU в разделе « Ссылка на проприетарные программы» есть предупреждение об организации вашей реализации таким образом, чтобы ее нельзя было спутать с существующим проприетарным кодом:
(Акцент мой.)
источник
strlen(), вероятно, получатся похожими или идентичными существующему коду. Нечто такое «сумасшедшее», как реализация glibc, не может быть отслежено подобным образом. Учитывая, как много было законных споров заrangeCheck- 11 строк кода! - в борьбе Google / Oracle я бы сказал, что озабоченность FSF была вполне обоснованной.