Как в GNU реализована функция strlen?

GNU strlen: наивная реализация vs оптимизированная

Наивная реализация (учебная)

Простейший способ подсчитать длину строки — просто считать символы до нулевого терминатора:

size_t strlen(const char *str) {
    size_t length = 0;
    while (str[length] != '\0') {
        length++;
    }
    return length;
}

Эта версия понятна, но неэффективна для длинных строк.

Оптимизированная реализация GNU libc

GNU использует SIMD инструкции (SSE, AVX и т.д.) для ускорения. Вот упрощенная версия логики:

1. Выравнивание указателя

size_t strlen(const char *s) {
    const char *start = s;
    
    // Указатель может быть не выровнен — обрабатываем байт за байтом
    // пока не выровняем на границу word'а (обычно 8 байт)
    while ((size_t)s % 8 != 0) {
        if (*s == '\0') {
            return s - start;
        }
        s++;
    }
    // Теперь s выровнен

2. Проверка слов целиком

Вместо проверки по одному байту, GNU проверяет целые слова (64 бита):

    // Константа для проверки нулевых байтов в слове
    // Для 64-битного слова: 0x0101010101010101
    const uint64_t mask = 0x0101010101010101UL;
    const uint64_t high_bit = 0x8080808080808080UL;
    
    uint64_t *words = (uint64_t *)s;
    
    while (1) {
        uint64_t word = *words++;
        
        // Проверяем есть ли нулевой байт в слове
        // Магия: если байт нулевой, его XOR с маской даст ноль
        if ((word - mask) & ~word & high_bit) {
            // Нулевой байт найден!
            // Теперь определяем его позицию
            s = (char *)(words - 1);
            
            while (*s != '\0') s++;
            
            return s - start;
        }
    }
}

Как работает магический трюк

Определение нулевого байта в слове

Несколько значений:

• word = 0x6261636400000000 ("abc" + нули)
• mask = 0x0101010101010101
• high_bit = 0x8080808080808080

word           = 0x6261636400000000
word - mask    = 0x6160626300FFFFFF  (вычитаем магическую константу)
~word          = 0x9D9E9C9BFFFFFFFF  (инвертируем)
(word - mask) & ~word & high_bit:
  Если есть нулевой байт, результат != 0

Для слова со встроенным нулем:

word = 0x6261630000000000
word - mask = 0x6160620000FFFFFF
~word = 0x9D9E9D00FFFFFFFF
result = (0x6160620000FFFFFF) & (0x9D9E9D00FFFFFFFF) & (0x8080808080808080)
       = 0x8080000000000000  (ненулевое! нулевой байт найден)

Реальная реализация в glibc (asm optimized)

Fактическая GNU strlen часто написана на ассемблере для каждой платформы:

; x86-64 версия (упрощено)
strlen:
    xor     rax, rax            ; длина = 0
    mov     rcx, 0x0101010101010101
    
.align  16
.L1:
    mov     rdx, [rdi + rax]    ; загружаем 8 байт
    lea     r8d, [rax + 8]
    
    mov     r9, rdx
    sub     r9, rcx             ; r9 = rdx - mask
    
    not     rdx                 ; инвертируем
    and     rdx, r9
    and     rdx, 0x8080808080808080
    
    je      .L1                 ; если нет нуля, продолжаем
    
    ; Нулевой байт найден, определяем позицию
    bsf     rdx, rdx            ; найти позицию первого бита
    shr     rdx, 3              ; разделить на 8
    add     rax, rdx            ; добавить к позиции в слове
    
    ret

Почему это быстро

1. Обработка по 8 байт за раз — в 8 раз меньше итераций
2. Один выход из цикла — вместо проверки каждого байта
3. SIMD-friendly — можно еще оптимизировать с SSE/AVX
4. Cache-friendly — выравнивание улучшает работу кэша

Сравнение производительности

// Наивная версия: ~1 цикл на байт
naive strlen("Hello") = 5 операций

// Оптимизированная версия: ~1 цикл на 8 байт
optimized strlen("Hello") = 1-2 операции

// Для длинной строки (1 MB):
naive: 1,000,000 итераций
optimized: 125,000 итераций

Современные оптимизации (AVX-512)

Новейшие версии GNU libc используют AVX-512 для обработки 64 байт за раз на поддерживающих процессорах.

Вывод

GNU strlen демонстрирует классический пример системного программирования:

1. Начинаем с простой версии
2. Профилируем и видим узкое место
3. Оптимизируем, используя особенности CPU и памяти
4. Пишем на ассемблере для максимальной производительности

Это напоминает, почему стандартные библиотеки важны — они содержат годы оптимизаций за счет простого вызова strlen().