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

Проблема: эффект кэш-промахов и ограничение пропускной способности памяти

Ваше наблюдение абсолютно верно: на современных x86-процессорах (Intel/AMD) два отдельных цикла могут работать быстрее одного объединённого. Причина кроется не в логике программы, а в том, как процессор взаимодействует с памятью через кэш.

Давайте разберёмся по шагам. Размер ваших массивов — 800 МБ каждый. Общий объём данных, с которыми работает объединённый цикл (a, b, c, d) — 3.2 ГБ. Кэш L3 современного процессора обычно составляет 8–30 МБ. Это значит, что все массивы целиком в кэш не помещаются.

Что происходит в объединённом цикле?

for (int i = 0; i < n; ++i) {
    c[i] = a[i] + b[i];   // Чтение a[i], b[i] и запись c[i]
    d[i] = c[i] * 2;      // Чтение c[i] (только что записанного) и запись d[i]
}

За одну итерацию вы выполняете:

• 2 чтения из памяти (a[i], b[i])
• 2 записи в память (c[i], d[i])

Итого — 4 операции с памятью на итерацию. Но это не всё. Самое важное: вы читаете c[i] сразу после его записи. Процессор вынужден ждать, пока запись в кэш завершится, прежде чем считать это же значение. Это называется зависимостью по данным через память (store-to-load forwarding delay).

Кроме того, когда вы идёте по массивам последовательно, процессор пытается предзагружать данные в кэш (prefetch). Но в объединённом цикле prefetch-у нужно обрабатывать 4 потока данных одновременно (a, b, c, d). Это создаёт конкуренцию за шину памяти и кэш-линии.

Что происходит в двух отдельных циклах?

// Первый цикл
for (int i = 0; i < n; ++i) {
    c[i] = a[i] + b[i];   // 2 чтения + 1 запись
}
// Второй цикл
for (int i = 0; i < n; ++i) {
    d[i] = c[i] * 2;      // 1 чтение + 1 запись
}

В первом цикле — 3 операции с памятью на итерацию. Во втором — 2 операции. Но главное преимущество: в каждом цикле prefetch работает только с двумя потоками данных. Это позволяет процессору более эффективно загружать данные в кэш.

Более того, после завершения первого цикла массив c уже полностью лежит в кэше (если размер кэша позволяет). Второй цикл читает c[i] из кэша L1/L2, что очень быстро. В объединённом же цикле c[i] может быть вытеснен из кэша до того, как вы к нему вернётесь на следующей итерации.

Техническое объяснение: пропускная способность памяти

Современные процессоры имеют ограниченную пропускную способность работы с памятью. Например, для Intel Core i7-12700K она составляет около 50 ГБ/с. Каждая операция чтения/записи занимает «слот» в шине памяти. В объединённом цикле вы используете 4 слота на итерацию, что быстрее упирается в лимит. В отдельных циклах вы используете 3 и 2 слота соответственно, что даёт больше времени для обработки данных в кэше.

Как это проверить?

Попробуйте уменьшить размер массива до 100 000 элементов (чтобы он поместился в кэш L2). Вы увидите, что объединённый цикл станет быстрее или, как минимум, не медленнее. Это подтвердит, что проблема именно в кэш-промахах.

Вывод

Не всегда меньшее количество циклов означает большую скорость. В задачах с большими объёмами данных (big data) часто выгоднее делать несколько проходов, чтобы минимизировать количество одновременных потоков к памяти и дать процессору эффективно работать с кэшем. Это называется cache-aware programming.

// Первый цикл векторизуется как:
// for i = 0 to n step 4:
//   _mm256_loadu_si256(a+i), _mm256_loadu_si256(b+i)
//   _mm256_add_epi32 -> запись в c

// Второй цикл:
//   _mm256_loadu_si256(c+i)
//   _mm256_mul_epi32 -> запись в d