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

Из Оптимизация strlen(), сообщения в блоге Колма Маккартэя. :

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

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

Иногда очень-очень быстрое движение просто сводит вас с ума.

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

P.S. Причина, по которой вы не понимаете версию 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, i.e. twice more for 32 bit */
  size += sizeof (int);
}

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

Итог:

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

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

Отвечая на вопрос ОП о том, где найти предложения по написанию кода для повышения производительности, здесь ссылка на 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_(p.c, LSIZE); p.c++ )
        if (*p.c == 0)
            return p.c - base;

    while ( !(mask = pzerobl_(*p.l)) )
        p.l++;
    return p.c - base + maskffs_(mask);
}