Почему поэлементное сложение в двух отдельных циклах выполняется намного быстрее, чем в одном объединённом цикле?

Проблема: кэш-промахи и векторные регистры

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

Подробное объяснение

Давайте разберём, что происходит в каждом случае на уровне процессора и кэша.

Вариант 1: два отдельных цикла

Первый цикл:

• Итеративно читает a[i] и b[i] (последовательный доступ вперёд).
• Пишет результат в c[i].

Второй цикл:

• Читает c[i] (который только что записан в кэш L1/L2) и d[i].
• Пишет результат в e[i].

Здесь данные уже горячие в кэше — массив c был записан в первом цикле и остался в кэш-памяти. Компилятор также может применить авто-векторизацию (использовать SIMD-инструкции, например AVX2), потому что каждый цикл имеет простой шаблон доступа и независимые операции.

Вариант 2: один объединённый цикл

Внутри одной итерации:

• Читаем a[i], b[i].
• Пишем c[i].
• Тут же читаем c[i] (который только что записан) и d[i].
• Пишем e[i].

Кажется, что это эффективно, но на практике:

• Зависимость по данным: запись в c[i] и последующее чтение того же элемента создают ложную зависимость (store-to-load forwarding), которая может блокировать конвейер процессора, особенно если компилятор не может гарантировать, что c и e не пересекаются в памяти (хотя они разные, компилятор может быть консервативен из-за strict aliasing).
• Проблемы с кэшем: вы одновременно работаете с 4 массивами (a, b, c, d, e), что превышает количество ассоциативных путей в кэше L1 (обычно 8-16). Это вызывает кэш-конфликты и промахи.
• Векторизация: компилятору сложнее векторизовать такой цикл из-за смешанных операций чтения-записи. В двух отдельных циклах он может легко применить SIMD, а здесь — нет, или применяет менее эффективно.

Демонстрация на ассемблере

Скомпилируйте с флагом -O2 -mavx2 -S — вы увидите, что в первом случае генерируются компактные SIMD-инструкции, а во втором — скалярный код с множеством перемещений.

// Примерный псевдо-ассемблер для двух циклов (векторизовано):
loop1:
    vmovdqu ymm0, [a+rdi]
    vpaddd  ymm0, ymm0, [b+rdi]
    vmovdqu [c+rdi], ymm0
    add rdi, 32
    cmp rdi, N
    jl loop1

loop2:
    vmovdqu ymm0, [c+rdi]
    vpaddd  ymm0, ymm0, [d+rdi]
    vmovdqu [e+rdi], ymm0
    add rdi, 32
    cmp rdi, N
    jl loop2

// Для одного цикла (скалярно):
loop:
    mov eax, [a+rdi]
    add eax, [b+rdi]
    mov [c+rdi], eax
    mov eax, [c+rdi]  // повторное чтение!
    add eax, [d+rdi]
    mov [e+rdi], eax
    inc rdi
    cmp rdi, N
    jl loop

Как исправить?

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

• Используйте __restrict__ или std::assume_aligned (C++20) для указания отсутствия алиасинга.
• Используйте временную переменную, чтобы разорвать зависимость:

for (size_t i = 0; i < N; ++i) {
    int tmp = a[i] + b[i];  // читаем a и b
    c[i] = tmp;             // пишем в c
    e[i] = tmp + d[i];      // используем tmp, а не c[i]
}

Это позволяет компилятору векторизовать обе операции и избежать store-to-load forwarding. На практике такой вариант часто сравнивается по скорости с двумя циклами.