Как в библиотеке GNU (glibc) реализована функция strlen?

Реализация strlen в glibc сильно оптимизирована. Основная идея — проверять не по одному байту, а считывая и анализируя сразу машинное слово (4 байта на 32-битных, 8 байт на 64-битных системах), чтобы минимизировать количество итераций цикла.

Упрощенный алгоритм (на основе кода glibc):

1. Выравнивание указателя: Сначала обрабатываются байты до первого адреса, выровненного на границу слова.
2. Проверка словами: Затем в цикле считываются слова. Чтобы быстро проверить, есть ли в слове нулевой байт, используется битовая магия без ветвлений.
3. Определение точной позиции: Когда слово с нулевым байтом найдено, определяется точная позиция этого байта.

Ключевая оптимизация — макрос для 32-битных систем:

#define DETECT_NULL(X) (((X) - 0x01010101) & ~(X) & 0x80808080)

Он работает потому, что:

• 0x01010101 — маска, где в каждом байте установлен младший бит.
• Если в байте X ноль, то (X - 0x01) даст перенос в старший бит этого байта, который затем отлавливается маской 0x80.
• Операция & ~(X) исключает случаи, где в старшем бите байта уже была единица (т.е. байт >= 128).

Пример схематичного кода:

size_t strlen_optimized(const char *str) {
    const char *char_ptr = str;
    const unsigned long *longword_ptr;

    // Обработка невыровненных начальных байтов
    for (; ((uintptr_t)char_ptr & (sizeof(long) - 1)) != 0; ++char_ptr) {
        if (*char_ptr == '') return char_ptr - str;
    }

    // Проверка словами
    longword_ptr = (const unsigned long*)char_ptr;
    while (true) {
        unsigned long longword = *longword_ptr++;
        if (DETECT_NULL(longword) != 0) {
            // Найдено слово с нулем, определяем какой именно байт
            const char *cp = (const char*)(longword_ptr - 1);
            if (cp[0] == 0) return cp - str;
            if (cp[1] == 0) return cp - str + 1;
            // ... проверка cp[2], cp[3] ...
        }
    }
}

Эта оптимизация дает выигрыш в несколько раз по сравнению с наивной реализацией на длинных строках.