Итак, для моего окончательного задания в моем классе Computer Systems нам нужно оптимизировать эти forloops быстрее, чем оригинал. Базовый класс составляет менее 7 секунд, а полный уровень составляет менее 5 секунд с нашего сервера linux. Этот код, который у меня здесь, составляет около 5,6 секунды. Я думаю, мне, возможно, придется использовать указатели с этим в некотором роде, чтобы заставить его двигаться быстрее, но я не уверен. Может ли кто-нибудь предложить какие-либо советы или варианты, которые у меня есть? Большое вам спасибо!
QUICKEDIT: файл должен оставаться 50 строк или меньше, и я игнорирую те строки с комментариями, которые включил инструктор.
Ответ 2
Повторная публикация измененной версии моего ответа из оптимизированной суммы массива удвоений в C, так как этот вопрос получил до -5. ОП другого вопроса сформулировал это скорее как "то, что еще возможно", поэтому я взял его на свое слово и сбрасывал информацию о векторизации и настройке для текущего процессора.:)
OP этого вопроса в конце концов сказал, что ему не разрешено использовать параметры компилятора выше -O0, что, я думаю, также имеет место здесь.
Резюме:
-
Почему использование -O0 искажает вещи (несправедливо наказывает вещи, которые хороши в нормальном коде для обычного компилятора).
-
Вещь, которая не соответствует назначению.
-
Типы оптимизации. Задержка FP против пропускной способности и цепочки зависимостей. Ссылка на сайт Agner Fog. (Основное чтение для оптимизации).
-
Эксперименты, позволяющие компилятору оптимизировать его (после исправления, чтобы не оптимизировать). Лучший результат с автоматической векторизации (без изменений источника): gcc: вдвое быстрее, чем оптимальный векторный цикл. clang: с той же скоростью, что и вектором с ручным вектором.
-
Еще несколько комментариев о том, почему более крупные выражения являются первыми победами только с -O0.
-
Исходные изменения для получения хорошей производительности без -ffast-math, что делает код ближе к тому, что мы хотим сделать компилятору. Также некоторые правила - идеи адвокации, которые были бы бесполезны в реальном мире.
-
Векторизация цикла с нейтральными векторами архитектуры GCC, чтобы увидеть, насколько близки автоинъекционирующие компиляторы, соответствующие производительности идеального asm-кода (поскольку я проверил выход компилятора).
Я думаю, что пункт назначения - это сортировать оптимизацию производительности на уровне ассемблера с использованием C без оптимизации компилятора. Это глупо. Он смешивает то, что компилятор сделает для вас в реальной жизни тем, что требует изменений на уровне исходного кода.
-O0 не просто "не оптимизирует", он делает переменные хранилища компилятора в памяти после каждого утверждения, а не сохраняет их в реестрах. Он делает это, чтобы получить ожидаемые результаты, если вы установите точку останова с помощью gdb и измените значение (в памяти) переменной C. Или даже если вы jump к другой строке в той же функции. Поэтому каждый оператор C должен быть скомпилирован в независимый блок asm, который запускается и заканчивается всеми переменными в памяти. Для современного переносного компилятора, такого как gcc, который уже преобразуется через несколько внутренних представлений потока программы на пути от источника к asm, эта часть -O0 требует явно де-оптимизируя свой график потока данных обратно в отдельные операторы C.. Эти хранилища/перезагрузки удлиняют каждую цепочку зависимостей, связанных с циклом, поэтому это ужасно для крошечных циклов (например, 1 цикл за итерацию против 6 с узким местом в обновлениях счетчика циклов).
С gcc -O0 ключевое слово register позволяет gcc хранить var в регистре вместо памяти и, таким образом, может иметь большое значение в жестких циклах (Пример в проводнике компилятора Godbolt). Но это только при -O0. В реальном коде register не имеет смысла: компилятор пытается оптимально использовать доступные регистры для переменных и временных рядов. register уже устарел в ISO С++ 11 (но не C11), а есть предложение удалить его с языка вместе с другие устаревшие вещи, такие как триграфы.
С дополнительными переменными -O0 ушибает индексирование массива немного больше, чем приращение указателя.
Индексирование массивов обычно упрощает чтение кода. Компиляторы иногда не могут оптимизировать такие вещи, как array[i*width + j*width*height], поэтому неплохо изменить источник, чтобы сделать оптимизацию прокрутки, увеличивая количество умножений на +=.
На уровне asm индексирование массива против приращения указателя приближается к той же производительности. (например, x86 имеет режимы адресации, такие как [rsi + rdx*4], которые бывают такими же быстрыми, как [rdi]. за исключением Sandybridge и более поздних версий.) Это задание компилятора для оптимизации вашего кода на с использованием увеличения указателя, даже если источник использует индексирование массива, когда это быстрее.
Для хорошей производительности вы должны знать, что компиляторы могут и не могут сделать. Некоторые оптимизации являются "хрупкими", и небольшое, казалось бы, невинное изменение источника приведет к тому, что компилятор не сделает оптимизацию, которая необходима для быстрого запуска некоторого кода. (например, вытягивание постоянного вычисления из цикла или подтверждение того, как разные условия ветвления связаны друг с другом и упрощение.)
Помимо всего этого, это образец дерьма, потому что у него нет ничего, чтобы остановить умный компилятор от оптимизации всего. Он даже не печатает сумму. Даже gcc -O1 (вместо -O3) отбросил часть цикла.
(вы можете исправить это, напечатав sum в конце. gcc и clang, похоже, не понимают, что calloc возвращает обнуленную память и оптимизирует ее до 0.0. См. мой код ниже.)
Обычно вы добавляете свой код в функцию и вызываете его в цикле из main() в другой файл. И скомпилируйте их отдельно, без цельной программы для перекрестных файлов, поэтому компилятор не может делать оптимизацию на основе констант времени компиляции, с которыми вы его вызываете. Повторяющийся цикл, который так сильно обертывается вокруг фактического цикла над массивом, вызывает хаос с оптимизатором gcc (см. Ниже).
Кроме того, в другой версии этого вопроса была неинициализированная переменная. Похоже, что long int help был введен ОП этого вопроса, а не проф. Поэтому мне придется понизить мою "полную бессмыслицу" до просто "глупого", потому что код даже не печатает результат в конце. Это самый распространенный способ заставить компилятор не оптимизировать все в микробизнесе, подобном этому.
Я предполагаю, что ваш профессор упомянул несколько вещей о производительности. В этом случае может возникнуть криптон разных вещей, многие из которых, как я полагаю, не упоминались в классе CS 2-го года.
Помимо многопоточности с openmp, векторизация выполняется с помощью SIMD. Существуют также оптимизация для современных конвейерных процессоров: в частности, избегайте одной длинной цепи зависимостей.
Дальнейшее существенное чтение:
Ваше руководство по компилятору также имеет важное значение, особенно. для кода с плавающей точкой. Плавающая точка имеет ограниченную точность и не является ассоциативной. Окончательная сумма зависит от того, какой заказ вы выполняете. Обычно разница в ошибке округления небольшая, поэтому компилятор может получить большое ускорение, переупорядочивая вещи, если вы используете -ffast-math для его разрешения.
Вместо того, чтобы просто разворачивать, хранить несколько аккумуляторов, которые вы только добавляете в конце, как вы делаете с sum0.. sum9 unroll -по-10. Инструкции FP имеют среднюю задержку, но высокую пропускную способность, поэтому вам нужно держать несколько операций FP в полете, чтобы поддерживать насыщенность блоков выполнения с плавающей точкой.
Если вам нужно, чтобы результат последнего op был завершен до того, как начнется следующий, вы ограничены задержкой. Для FP добавить, что один на 3 цикла. В Intel Sandybridge, IvB, Haswell и Broadwell пропускная способность FP add составляет один за цикл. Поэтому вам нужно сохранить как минимум 3 независимых оператора, которые могут быть в полете сразу, чтобы насытить машину. Для Skylake, 2 за цикл с латентностью 4 такта. (На стороне плюса для Skylake FMA сокращается до 4 циклов).
В этом случае также есть базовые вещи, такие как вытаскивание вещей из цикла, например. help += ARRAY_SIZE.
параметры компилятора
Давайте начнем с просмотра того, что может сделать компилятор для нас.
Я начал с оригинальной внутренней петли, вытащив всего help += ARRAY_SIZE и добавив printf в конец, так что gcc не все оптимизирует. Попробуйте некоторые параметры компилятора и посмотрите, что мы можем достичь с помощью gcc 4.9.2 (на моем i5 2500k Sandybridge. 3.8GHz max turbo (небольшой OC), 3,3 ГГц устойчиво (не имеет значения для этого короткого теста):
-
gcc -O0 fast-loop-cs201.c -o fl: производительность 16.43s - полная шутка. Переменные сохраняются в памяти после каждой операции и перезагружаются до следующего. Это узкое место и добавляет много латентности. Не говоря уже о потере фактических оптимизаций. Код времени/настройки с помощью -O0 не является полезным. -
-O1: 4.87s
-
-O2: 4.89s
-
-O3: 2.453s (использует SSE для выполнения 2 раза. Я, конечно, использую 64-битную систему, поэтому аппаратная поддержка -msse2 является базовой линией.)
-
-O3 -ffast-math -funroll-loops: 2.439s
-
-O3 -march=sandybridge -ffast-math -funroll-loops: 1.275s (использует AVX для выполнения 4 раза).
-
-Ofast ...: нет усиления
-
-O3 -ftree-parallelize-loops=4 -march=sandybridge -ffast-math -funroll-loops: 0m2.375s реальный, 0m8.500s пользователь. Похоже, что накладные расходы убили его. Он генерирует только 4 потока, но внутренний цикл слишком короткий для того, чтобы он стал выигрышем: он собирает суммы каждый раз, вместо того, чтобы давать каждому нитку 1/4 итераций внешнего цикла.
-
-Ofast -fprofile-generate -march=sandybridge -ffast-math, запустите его, затем нажмите
-Ofast -fprofile-use -march=sandybridge -ffast-math: 1.275s. оптимизация с учетом профиля - хорошая идея, когда вы можете использовать все соответствующие кодовые пути, поэтому компилятор может принимать более эффективные решения для развертывания/вложения.
-
clang-3.5 -Ofast -march=native -ffast-math: 1.070s. (clang 3.5 слишком стар, чтобы поддерживать -march=sandybridge. Вы должны предпочесть использовать версию компилятора, достаточно новую, чтобы знать о целевой архитектуре, для которой вы настраиваете, например, при использовании -march для создания кода, который не нужен для работы на старых архитектурах.)
gcc -O3 векторизован смешно: внутренний цикл выполняет 2 (или 4) итерации внешнего цикла параллельно, передавая один элемент массива всем элементам регистра xmm (или ymm) и выполняя addpd на этом. Таким образом, он видит, что одни и те же значения добавляются повторно, но даже -ffast-math не позволяет gcc просто превращать его в умножение. Или переключите петли.
clang-3.5 векторизует намного лучше: он вектурирует внутренний цикл, а не внешний, поэтому ему не нужно транслировать. Он даже использует 4 векторных регистра как 4 отдельных аккумулятора. Тем не менее, он не предполагает, что calloc возвращает выровненную память, и по какой-то причине он считает, что лучшим вариантом является пара 128-битных нагрузок.
vmovupd -0x60(%rbx,%rcx,8),%xmm4`
vinsertf128 $0x1,-0x50(%rbx,%rcx,8),%ymm4,%ymm4
Это на самом деле медленнее, когда я говорю, что массив выровнен. (с глупым взломом, вроде array = (double*)((ptrdiff_t)array & ~31);, который на самом деле генерирует инструкцию для маскировки низких 5 бит, потому что clang-3.5 не поддерживает gcc __builtin_assume_aligned.) Я думаю, что способ, которым жесткая петля 4x vaddpd mem, %ymmX,%ymmX выравнивается ставит cmp $0x271c,%rcx пересечение границы 32B, поэтому он не может использовать макро-предохранитель с jne. Однако пропускная способность uop не должна быть проблемой, поскольку этот код получает только 0,65 дюйма за цикл (и 0,93 мк/цикл), согласно perf.
Ahh, я проверил с помощью отладчика, а calloc возвращает указатель с 16-кратным увеличением. Таким образом, половина доступа к памяти 32B пересекает линию кэша, что вызывает значительное замедление. Немного быстрее сделать две отдельные нагрузки 16B, когда ваш указатель выравнивается по 16B, но не 32B-выровнен, на Sandybridge. (gcc включает -mavx256-split-unaligned-load и ...-store для -march=sandybridge, а также для стандартной настройки tune = generic с -mavx, которая не очень хорошая особенно для Haswell или с памятью, которая обычно выравнивается компилятором, не знает об этом.)
Изменения уровня источника
Как видно из clang beating gcc, несколько аккумуляторов превосходны. Наиболее очевидный способ сделать это:
for (j = 0; j < ARRAY_SIZE; j+=4) { // unroll 4 times
sum0 += array[j];
sum1 += array[j+1];
sum2 += array[j+2];
sum3 += array[j+3];
}
а затем не собирайте 4 аккумулятора в один, пока не закончите внешний контур.
Из вашего (с другого вопроса) смены источника
sum += j[0]+j[1]+j[2]+j[3]+j[4]+j[5]+j[6]+j[7]+j[8]+j[9];
фактически имеет аналогичный эффект, благодаря выполнению вне очереди. Каждая группа из 10 представляет собой отдельную цепочку зависимостей. правила порядка операций говорят, что значения j сначала добавляются вместе, а затем добавляются в sum. Таким образом, цепочка зависимостей, связанная с циклом, по-прежнему остается только латентностью одного добавления FP, и для каждой группы из 10. существует много независимых работ. Каждая группа представляет собой отдельную цепочку зависимостей из 9 добавлений и требует достаточно нескольких инструкций для выхода из аппаратное обеспечение выполнения заказа, чтобы увидеть начало следующей цепочки, и найдите parallelism, чтобы сохранить эти средние задержки, а также высокопроизводительные модули исполнения FP.
С -O0, как вам кажется, ваше глупое присваивание, значения сохраняются в ОЗУ в конце каждого утверждения. Написание более длинных выражений без обновления каких-либо переменных, даже временных, сделает -O0 быстрее, но это не является полезной оптимизацией. Не тратьте время на изменения, которые помогают только с -O0, особенно. не за счет удобочитаемости.
Используя 4 переменные аккумулятора и не добавляя их вместе до тех пор, пока конец внешнего цикла не победит автоинкрементатор clang. Он по-прежнему работает только с 1,66 с (против 4,89 для gcc-не-векторизованных -O2 с одним аккумулятором). Даже gcc -O2 без -ffast-math также получает 1,66 с для этого изменения источника. Обратите внимание, что ARRAY_SIZE, как известно, кратно 4, поэтому я не включил код очистки для обработки последних элементов "вверх-до" (или чтобы не пропустить конец конца массива, что произойдет, как написано сейчас), Это действительно легко получить что-то неправильно и прочитать за конец массива при этом.
gcc, с другой стороны, делает это векторизацию, но также пессимизирует (не оптимизирует) внутренний цикл в одну цепочку зависимостей. Я думаю, что он снова выполняет несколько итераций внешнего цикла.
Используя gcc независимые от платформы векторные расширения, я написал версию, которая компилируется в явно оптимальный код:
// compile with gcc -g -Wall -std=gnu11 -Ofast -fno-tree-vectorize -march=native fast-loop-cs201.vec.c -o fl3-vec
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <string.h>
// You are only allowed to make changes to this code as specified by the comments in it.
// The code you submit must have these two values.
#define N_TIMES 600000
#define ARRAY_SIZE 10000
int main(void)
{
double *array = calloc(ARRAY_SIZE, sizeof(double));
double sum = 0;
int i;
// You can add variables between this comment ...
long int help = 0;
typedef double v4df __attribute__ ((vector_size (8*4)));
v4df sum0={0}, sum1={0}, sum2={0}, sum3={0};
const size_t array_bytes = ARRAY_SIZE*sizeof(double);
double *aligned_array = NULL;
// this more-than-declaration could go in an if(i == 0) block for strict compliance with the rules
if ( posix_memalign((void**)&aligned_array, 32, array_bytes) ) {
exit (1);
}
memcpy(aligned_array, array, array_bytes); // In this one case: faster to align once and have no extra overhead for N_TIMES through the loop
// ... and this one.
// Please change 'your name' to your actual name.
printf("CS201 - Asgmt 4 - I. Forgot\n");
for (i = 0; i < N_TIMES; i++) {
// You can change anything between this comment ...
/*
#if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__) >= 407 // GCC 4.7 or later.
array = __builtin_assume_aligned(array, 32);
#else
// force-align for other compilers. This loop-invariant will be done outside the loop.
array = (double*) ((ptrdiff_t)array & ~31);
#endif
*/
assert ( ARRAY_SIZE / (4*4) == (ARRAY_SIZE+15) / (4*4) ); // We don't have a cleanup loop to handle where the array size isn't a multiple of 16
// incrementing pointers can be more efficient than indexing arrays
// esp. on recent Intel where micro-fusion only works with one-register addressing modes
// of course, the compiler can always generate pointer-incrementing asm from array-indexing source
const double *start = aligned_array;
while ( (ptrdiff_t)start & 31 ) {
// annoying loops like this are the reason people use aligned buffers
sum += *start++; // scalar until we reach 32B alignment
// in practice, this loop doesn't run, because we copy into an aligned buffer
// This will also require a cleanup loop, and break our multiple-of-16 doubles assumption.
}
const v4df *end = (v4df *)(aligned_array+ARRAY_SIZE);
for (const v4df *p = (v4df *)start ; p+3 < end; p+=4) {
sum0 += p[0]; // p+=4 increments the pointer by 4 * 4 * 8 bytes
sum1 += p[1]; // make sure you keep track of what you're incrementing
sum2 += p[2];
sum3 += p[3];
}
// the compiler might be smart enough to pull this out of the inner loop
// in fact, gcc turns this into a 64bit movabs outside of both loops :P
help+= ARRAY_SIZE;
// ... and this one. But your inner loop must do the same
// number of additions as this one does.
/* You could argue legalese and say that
if (i == 0) {
for (j ...)
sum += array[j];
sum *= N_TIMES;
}
* still does as many adds in its *INNER LOOP*, but it just doesn't run it as often
*/
}
// You can add some final code between this comment ...
sum0 = (sum0 + sum1) + (sum2 + sum3);
sum += sum0[0] + sum0[1] + sum0[2] + sum0[3];
printf("sum = %g; help=%ld\n", sum, help); // defeat the compiler.
free (aligned_array);
free (array); // not strictly necessary, because this is the end of main(). Leaving it out for this special case is a bad example for a CS class, though.
// ... and this one.
return 0;
}
Внутренний цикл компилируется в:
4007c0: c5 e5 58 19 vaddpd (%rcx),%ymm3,%ymm3
4007c4: 48 83 e9 80 sub $0xffffffffffffff80,%rcx # subtract -128, because -128 fits in imm8 instead of requiring an imm32 to encode add $128, %rcx
4007c8: c5 f5 58 49 a0 vaddpd -0x60(%rcx),%ymm1,%ymm1 # one-register addressing mode can micro-fuse
4007cd: c5 ed 58 51 c0 vaddpd -0x40(%rcx),%ymm2,%ymm2
4007d2: c5 fd 58 41 e0 vaddpd -0x20(%rcx),%ymm0,%ymm0
4007d7: 4c 39 c1 cmp %r8,%rcx # compare with end with p
4007da: 75 e4 jne 4007c0 <main+0xb0>
(Для получения дополнительной информации см. вывод онлайн-компилятора в проводнике компилятора godbolt. Компилятор -xc компилируется как C, а не С++. Внутренний цикл от .L3 до jne .L3. См. x86 для wiki для x86 asm ссылок. См. также этот q & о микро-синтезе, который не происходит в семействе SnB, который ведет Agner Fog 't обложка).
производительности:
$ perf stat -e task-clock,cycles,instructions,r1b1,r10e,stalled-cycles-frontend,stalled-cycles-backend,L1-dcache-load-misses,cache-misses ./fl3-vec
CS201 - Asgmt 4 - I. Forgot
sum = 0; help=6000000000
Performance counter stats for './fl3-vec':
1086.571078 task-clock (msec) # 1.000 CPUs utilized
4,072,679,849 cycles # 3.748 GHz
2,629,419,883 instructions # 0.65 insns per cycle
# 1.27 stalled cycles per insn
4,028,715,968 r1b1 # 3707.733 M/sec # unfused uops
2,257,875,023 r10e # 2077.982 M/sec # fused uops. lower than insns because of macro-fusion
3,328,275,626 stalled-cycles-frontend # 81.72% frontend cycles idle
1,648,011,059 stalled-cycles-backend # 40.47% backend cycles idle
751,736,741 L1-dcache-load-misses # 691.843 M/sec
18,772 cache-misses # 0.017 M/sec
1.086925466 seconds time elapsed
Я до сих пор не знаю, почему он получает такие низкие инструкции за цикл. Внутренний цикл использует 4 отдельных аккумулятора, и я проверил с gdb, что указатели выровнены. Таким образом, проблемы с кеш-банками не должны быть проблемой. В кэше Sandybridge L2 может поддерживаться одна передача 32B за цикл, которая должна идти в ногу с тем, что один вектор 32 FP добавляет за цикл.
32B нагрузки от L1 занимают 2 цикла (это было только после того, как Хасуэлл, который Intel сделал 32B, загружал однотактную операцию). Однако есть 2 порта нагрузки, поэтому устойчивая пропускная способность составляет 32 Б за цикл (чего мы не достигаем).
Возможно, нагрузки должны быть конвейерными впереди, когда они используются, чтобы свести к минимуму заполнение ROB (буфера повторного заказа) при загрузке груза? Но счетчики perf указывают на довольно высокую частоту попадания кеша L1, поэтому аппаратная предварительная выборка от L2 до L1, похоже, выполняет свою работу.
0,65 инструкций за цикл составляют примерно половину пути для насыщения векторного сумматора FP. Это расстраивает. Даже IACA говорит, что цикл должен выполняться в 4 циклах на итерацию. (то есть насыщают порты нагрузки и порт1 (где живет сумматор FP)):/
update: Я полагаю, что пропускная способность L2 была проблемой в конце концов. Недостаточно буферов заполнения строки, чтобы обеспечить достаточное количество промахов в полете для поддержания максимальной пропускной способности каждого цикла. Пропускная способность L2 ниже пиковой на процессорах Intel SnB/Haswell/Skylake.
См. также Одиночная потоковая пропускная способность памяти на Sandy Bridge (тема форума Intel, с большим обсуждением о том, какая пропускная способность и как latency * max_concurrency является одним из возможных узких мест. См. также раздел "Latency Bound Platforms" в ответ на расширенный REP MOVSB для memcpy, ограниченная память concurrency является узким местом для нагрузок, а также как для магазинов, но для нагрузок prefetch в L2 означает, что вы не можете ограничиваться исключительно буферами Line Fill для выдающихся пропусков L1D.
Уменьшение ARRAY_SIZE до 1008 (кратное 16) и увеличение N_TIMES в 10 раз привело к снижению времени выполнения до 0,5 с. Это 1.68 insns за цикл. (Внутренний цикл - 7 полных инструкций для добавления 4 FP, таким образом, мы, наконец, насыщаем блок добавления FP вектора и порты загрузки.) Плитка петли - намного лучшее решение, см. Ниже.
Процессоры Intel имеют только 32 тыс. кэшей L1-данных и L1-команд. Я думаю, что ваш массив почти не вписывался в 64kiB L1D на CPU AMD K10 (Стамбул), но не Bulldozer-family (16kiB L1D) или Ryzen (32kiB L1D).
Gcc попытка векторизации путем трансляции одного и того же значения в параллельный add не кажется настолько сумасшедшим. Если бы это удалось сделать правильно (используя несколько аккумуляторов, чтобы скрыть латентность), это позволило бы насытить векторный сумматор FP с половиной полосы пропускания памяти. Как-будто, это было в значительной степени стиранием, возможно, из-за накладных расходов на вещание.
Кроме того, это довольно глупо. N_TIMES - это просто повторение make-work. На самом деле мы не хотим оптимизировать многократное выполнение одинаковой работы. Если мы не хотим побеждать в таких глупых заданиях. Путь к исходному уровню для этого состоит в том, чтобы увеличить i в той части кода, которую мы разрешили изменить:
for (...) {
sum += a[j] + a[j] + a[j] + a[j];
}
i += 3; // The inner loop does 4 total iterations of the outer loop
Более реалистично, чтобы справиться с этим, вы могли бы обменивать свои петли (цикл над массивом один раз, добавляя каждое значение N_TIMES раз). Я думаю, что я читал, что компилятор Intel иногда сделает это за вас.
Более общий метод называется блокировкой кеша или черепицей петли. Идея состоит в том, чтобы работать с вашими входными данными в небольших блоках, которые вписываются в кеш. В зависимости от вашего алгоритма, можно сделать несколько этапов вещи на куске, а затем повторить для следующего фрагмента, вместо того, чтобы каждый цикл цикла на весь вход. Как всегда, как только вы узнаете правильное имя для трюка (и что оно вообще существует), вы можете загрузить большую часть информации.
Вы можете использовать правила-юриста, чтобы вставить код interchanged внутри блока if (i == 0) в той части кода, которую вы можете изменить. Он по-прежнему будет делать то же количество дополнений, но в более оптимальном для кеша порядке.
