Замена 32-битного счетчика цикла на 64-битный вызывает странные скачки производительности с _mm_popcnt_u64 на Intel CPU

Причина: ложная зависимость данных и перегрузка портов выполнения

Вы столкнулись с известным эффектом, который подробно исследовали разработчики Stack Overflow. Проблема не в самом цикле, а в том, как компилятор генерирует код для инструкции POPCNT в зависимости от типа счётчика.

Ключевой момент: _mm_popcnt_u64 на старых Intel Core (Sandy Bridge, Ivy Bridge) имеет латентность 3 такта и занимает только один порт выполнения (port 1). При этом он не конвейеризуется — следующая инструкция POPCNT не может начаться, пока предыдущая не завершится, если между ними есть зависимость по данным.

Теперь смотрим на сгенерированный код (дизассемблер):

Вариант с uint32_t (быстрый)

; Компилятор разворачивает цикл и использует 64-битный регистр для счётчика!
xor     ecx, ecx          ; i = 0 (32-битный, но старшие биты обнулены)
loop_start:
popcnt  rax, [rdx+rcx*8]  ; data[i]
add     r8, rax            ; result += popcnt
add     rcx, 1             ; i++
cmp     rcx, rsi
jb      loop_start

Вариант с uint64_t (медленный)

xor     rcx, rcx          ; i = 0 (64-битный)
loop_start:
popcnt  rax, [rdx+rcx*8]  ; data[i]
add     r8, rax            ; result += popcnt
add     rcx, 1             ; i++
cmp     rcx, rsi
jb      loop_start

На первый взгляд код идентичен. Но есть одно критическое различие в том, как компилятор обрабатывает регистр счётчика при разворачивании цикла.

Проблема: частичная регистровая зависимость

Для uint32_t компилятор знает, что старшие 32 бита регистра rcx гарантированно равны нулю (из-за семантики 32-битных операций в x86-64, которые обнуляют старшую половину). Это позволяет:

• Использовать ecx как индекс, не заботясь о старших битах.
• Компилятор может переиспользовать регистры и разворачивать цикл агрессивнее, создавая несколько независимых цепочек POPCNT.

Для uint64_t компилятор вынужден:

• Сохранять все 64 бита счётчика.
• Это мешает разворачиванию цикла, так как каждая итерация зависит от предыдущей через регистр rcx.
• В результате POPCNT выполняется строго последовательно — следующая начинается только после завершения предыдущей.

Почему это убивает производительность?

У POPCNT на Sandy Bridge пропускная способность (throughput) — 1 инструкция за такт, если нет зависимостей. Но из-за зависимости по счётчику фактический throughput падает до 1 инструкции за 3 такта (латентность).

С 32-битным счётчиком компилятор может развернуть цикл в 4-8 раз и использовать несколько аккумуляторов, разрывая цепочку зависимостей:

; Развёрнутый вариант (4 итерации)
popcnt  rax, [rdx]
popcnt  rbx, [rdx+8]
popcnt  rcx, [rdx+16]
popcnt  rdi, [rdx+24]
add     r8, rax
add     r8, rbx
add     r8, rcx
add     r8, rdi

Теперь 4 инструкции POPCNT могут выполняться параллельно (на разных итерациях конвейера), утилизируя порт 1 на 100%.

Решение

Лучший способ — явно помочь компилятору разорвать зависимости:

uint64_t popcnt_fast(const uint64_t* data, size_t size) {
    uint64_t result = 0;
    // Используем указатель вместо счётчика — это убирает зависимость
    const uint64_t* end = data + size;
    for (const uint64_t* p = data; p < end; ++p) {
        result += _mm_popcnt_u64(*p);
    }
    return result;
}

Или ещё лучше — ручное разворачивание с несколькими аккумуляторами:

uint64_t popcnt_unrolled(const uint64_t* data, size_t size) {
    uint64_t r1 = 0, r2 = 0, r3 = 0, r4 = 0;
    size_t i = 0;
    for (; i + 3 < size; i += 4) {
        r1 += _mm_popcnt_u64(data[i]);
        r2 += _mm_popcnt_u64(data[i+1]);
        r3 += _mm_popcnt_u64(data[i+2]);
        r4 += _mm_popcnt_u64(data[i+3]);
    }
    for (; i < size; ++i) {
        r1 += _mm_popcnt_u64(data[i]);
    }
    return r1 + r2 + r3 + r4;
}

На современных процессорах (Haswell+) POPCNT уже имеет throughput 1/такт и латентность 3, но проблема ложной зависимости может проявляться и там. Всегда проверяйте дизассемблер!