Как написать лучшую функцию strlen?

Я читаю «Write Great Code Volume 2», и он показывает следующую иммерсию:

int myStrlen( char *s ) { char *start; start = s; while( *s != 0 ) { ++s; } return s - start; } 

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

Из Оптимизации strlen () , blogpost от Colm MacCarthaigh:

К сожалению, в C мы обречены на реализацию O (n), в лучшем случае, но мы все еще не закончили … мы можем сделать что-то о самом размере n.

Это хороший пример того, в каком направлении вы можете работать, чтобы ускорить его. И еще одна цитата из нее

Иногда происходит действительно очень быстро, просто делает вас действительно безумным.

Виктор, взгляните на это:
http://en.wikipedia.org/wiki/Strlen#Implementation

PS Причина, по которой вы не понимаете версию glibc, вероятно, потому, что она использует смещение бит, чтобы найти \ 0.

Для начала это бесполезно для кодировок, таких как UTF-8 … то есть вычисление количества символов в строке UTF-8 более сложно, тогда как число байтов, конечно, так же легко подсчитать, как и в , скажем, строку ASCII.

В общем, вы можете оптимизировать некоторые платформы, читая их в более крупные регистры. Поскольку другие ссылки, опубликованные до сих пор, не имеют примера этого, вот несколько псевдо-псевдокодов для нижнего конца:

 int size = 0; int x; int *caststring = (int *) yourstring; while (int x = *caststring++) { if (!(x & 0xff)) /* first byte in this int-sized package is 0 */ return size; else if (!(x & 0xff00)) /* second byte etc. */ return size+1; /* rinse and repeat depending on target architecture, ie twice more for 32 bit */ size += sizeof (int); } 

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

Нижняя линия:

Отличный код подчеркивает читаемость по скорости во всех, кроме самых важных для критически важных дел. Напиши свой код так четко, как только можешь, и только оптимизируйте части, которые оказались узкими местами.

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

Отвечая на вопрос OP о том, где искать предложения о том, как писать код для производительности, ссылка на MIT OpenCourse на запись оптимизированного кода C (найдите ссылку «Материалы» слева от страницы).

Следующее должно быть быстрее, чем наивный алгоритм и работать для 32/64 бит.

 union intptr { char* c; long* l; #define LSIZE sizeof(long) }; #define aligned_(x, a) \ ((unsigned long) (x) % (a) == 0) #define punpktt_(x, from, to) \ ((to) (-1)/(from) (-1)*(from) (x)) #define punpkbl_(x) \ punpktt_(x, unsigned char, unsigned long) #define plessbl_(x, y) \ (((x) - punpkbl_(y)) & ~(x) & punpkbl_(0x80)) #define pzerobl_(x) \ plessbl_(x, 1) static inline unsigned long maskffs_(unsigned long x) { unsigned long acc = 0x00010203UL; if (LSIZE == 8) acc = ((acc << 16) << 16) | 0x04050607UL; return ((x & -x) >> 7) * acc >> (LSIZE*8-8); } size_t strlen(const char* base) { union intptr p = { (char*) base }; unsigned long mask; for ( ; !aligned_(pc, LSIZE); p.c++ ) if (*pc == 0) return pc - base; while ( !(mask = pzerobl_(*pl)) ) p.l++; return pc - base + maskffs_(mask); }