На всякий случай извиняюсь, но не нашел в какой раздел это можно написать. Если будете бить, то уж лучше сразу насмерть. 

Тестирую время исполнения кода.

Код на Delphi. Есть 2 варианта кода. Первый вариант:



Второй вариант:


Разница между ними всего в одном операторе в теле цикла for. Даже не в операторе, а в его аргументе (разный индекс массива).

Чудо природы состоит в следующем.
Первый код отрабатывает у меня 1093 мс. Второй - 577 мс.

(У меня: AMD Duron 1100 MHz, FSB 100 MHz, чипсет VIA KT266A.)

Почему так?

ИМХО, дело здесь не сколько в инструкциях, сколько в доступе к памяти
побайтный доступ очень неэффективен, по сути, что байт из памяти достать, что 32-битное слово - одинаково (при условии, что его адрес кратен 4)
так что в первом случае можно достать оба байта за практически то же время, что и 1 (просто достав 4-байтное слово, которое их содержит)
а во втором случае их приходится доставать отдельно (т.к. нет такого 4-байтного слова, которое их содержит)
для прояснения ситуации я бы порекомендовал ещё два теста:

и

если вышеописанная гипотеза верна, то второй будет по скорости приблизительно так же, как и <0,1>, да и первый сильно не отстанет (может быть больше из-за того, что операций стало реально больше)

В первом варианте ты обращаешься к невыравненным данным, отсюда и штрафы за доступ (на Utra Sparc ты вообще бы ошибку получил). Здесь есть некоторые комментарии по этому поводу.

Так дело в том, что первый случай (когда теоретически достаются сразу 4 байта) работает медленнее.

Насчет тестов.
Мои (из первого поста ветки):

aa[0] := aa[0]+2;
aa[1] := aa[1]+2;
Слово одно и то же. Время выполнения: 1093 мс.


aa[0] := aa[0]+2;
aa[4] := aa[4]+2;
Здесь разные слова захватили (четырехбайтные). Время выполнения: 577 мс.


от maxim1000:

aa[0] := aa[0]+2;
aa[1] := aa[1]+2;
aa[2] := aa[2]+2;
aa[3] := aa[3]+2;
Теоретически одно слово. Время выполнения: 1155 мс.

aa[0] := aa[0]+2;
aa[3] := aa[3]+2;
время выполнения: 1093 мс.

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



Еще тесты.

aa[0] := aa[0]+2;
Время выполнения: 311 мс.

aa[1] := aa[1]+2;
Время выполнения: 311 мс.

aa[4] := aa[4]+2;
Время выполнения: 311 мс.

aa[11] := aa[11]+2;
Время выполнения: 311 мс.

Таким образом, время выполнения операции с одним байтом не зависит от индекса массива.



aa[0] := aa[0]+2;
aa[5] := aa[5]+2;
Разные слова, время выполнения: 577 мс.

aa[0] := aa[0]+2;
aa[11] := aa[11]+2;
Разные слова, время выполнения: 577 мс.

aa[10] := aa[10]+2;
aa[11] := aa[11]+2;
Одно слово, индексы "рядом", время выполнения: 1093 мс.

aa[3] := aa[3]+2;
aa[4] := aa[4]+2;
Разные слова, индексы "рядом", время выполнения: 577 мс.

Видно, что массив действительно разделен на четырехбайтные слова.
Однако, быстрее выполняются коды, обращающиеся к разным словам, а не к одному.

aa[0] := aa[0]+2;
aa[4] := aa[4]+2;
aa[8] := aa[8]+2;
Везде разные слова, время выполнения: 827 мс

aa[0] := aa[0]+2;
aa[4] := aa[4]+2; // одно слово
aa[5] := aa[5]+2; // одно слово
время выполнения: 874 мс

aa[4] := aa[4]+2;
aa[5] := aa[5]+2;
Урезанная версия предыдущего, время выполнения: 1093 мс.
Тут я вообще в шоке. Убрал оператор, а всё стало работать медленнее.

Время выполнения в каждом случае немного "шумит". В качестве результата выбиралось минимальное значение.

Короче, не знаю что и думать.

упс... это я напутал при чтении первого поста

интересно

тогда есть ещё одна мысль:
не знаю, как у AMD, но у одного из специализированных процессоров, с которым я работал, была такая система:
кэш не монолитный, а состоит из нескольких частей
при некоторых условиях можно из этих частей выбирать данные параллельно, с экономией времени по сравнению с двумя последовательными выборками

одна из возможных политик поведения кэша - исходя из локальной близости данных (т.е. при обращении к какому-то слову происходит кэширование соседних ячеек)

одно и то же слово вряд ли будет помещено в разные части кэша - это слишком расточительно (кэша всегда не хватает)

вот и получается что вероятная ситуация: первое слово попадает в одну часть кэша, второе - в другую
это позволяет быстро выбирать их, когда дело касается двух разных ячеек

когда же происходит доступ к одной и той же ячейке, то и приходится обращаться к одной и той же части кэша два раза, приходится делать это последовательно

Добавлено через 1 минуту и 46 секунд
кстати, на уровне компилятора можно было бы вообще представить это в виде одной операции чтения из памяти и нескольких операций над регистрами, но для этого надо быть уверенным в выровненности старта массива на границу 4-х байт

Добавлено через 4 минуты и 5 секунд
  
Идёт физик по коридору, навстречу инженер, рассказал про проведённый эксперимент, показал кривую, попросил её объяснить. Физик подумал немного и объяснил, почему так получается. Вдруг инженер с ужасом заметил, что он показал кривую вверх ногами, перевернул. Физик подумал ещё раз и тоже объяснил 

Вряд ли это связано с кэшем. Я ведь могу сделать размер массива не только 100 байт, но и миллион байт. Весь массив в кэш не влезет, ибо кэш у меня 192КБ. А тем не менее такой код:

aa[0] := aa[0]+2;
aa[999999] := aa[999999]+2;

Выполняется за 577 мс.

Остается только считать, что такое время выполнения является нормальным, и не является следствием оптимизации.

У меня уже мозги закипели от попыток понять в чём может быть причина. 

Выяснилось только что обработка четырех и более байт не зависит от их порядка следования. Если обрабатывать три и менее байт, то результаты зависят от их расположения.



А анекдот супер. 

так не весь же массив попадает в кэш
здесь можно предположить, что в одну часть кэша попадает a[0], а в другую - a[999999]

Код:



Компилируется в такой:



А каким образом байт с номером 999999 может попасть в кэш?. Откуда системе знать какой байт я запрошу? А весь массив не помещается. Хотя я в железе полный ноль конечно. 

Возможно здесь играет роль повторяемость операций. На первом цикле запоминаются выбранные мной байты, а на следующих итерациях идет работа с кэшем, а не с оперативной памятью.



Сделал эксперимент чтобы это проверить.

Код такой:



Здесь меняются байты массива с указанным шагом (в коде шаг равен 1).
Раньше я писал что порядок изменения байтов не играет роли. Так вот, выяснилось, что это не правда.  Ниже зависимость времени выполнения от шага.



Скорее всего ближайшие данные действительно кэшируются, причем каким-то хитрым образом. Если сильно скакать по массиву, то скорость замедляется (да еще как, я думал всё зависло).

Так что похоже и вправду дело в кэше в конечном счете.

да, по идее, так и должно быть


ну... в меру хитрым
используется гипотеза локальности обращений к памяти: обращаются чаще к близким ячейкам
поэтому, когда одно значение выбирается, то и на всякий случай выбираются и соседние ячейки
дело в том, что из-за устройства оперативной памяти время доставания двух последовательных слов меньше, чем удвоенное время доставания одного слова, т.е. выгоднее обмениваться с памятью целыми пакетами

Еще одну фишку заметил. 

Предыдущую таблицу можно продолжить.



Прикол - в уменьшении времени, когда шаг становится очень большим.

Напомню, что прога проходит по всему массиву с заданным шагом. По окончании массива всё начинается снова. Длина массива - 1 миллион байт.

Когда шаг равен 1, при одном проходе по массиву перебирается 1 миллион байт.
Когда шаг равен 100, перебирается 10 000 байт.
Когда шаг равен 1000, перебирается 1000 байт.

Быстрое выполнение кода с маленьким шагом можно объяснить тем, что система сразу берет в кэш ближайшие данные.

А вот более быстрое выполнение кода с большим шагом можно объяснить тем, что система запоминает недавно использовавшиеся адреса (или данные), и при повторном к ним обращении берет их из кэша. В случае с большим шагом получается, что общий объем перебираемых данных уменьшается, поэтому такая методика приводит к повышению производительности в этом случае.

Чтобы подтвердить предположение, предыдущую прогу немного изменил. Сделал так, чтобы шаг был по-прежнему фиксирован, но при окончании прохода по массиву всё начиналось не сначала по тем же данным, а со сдвигом, чтобы при следующем проходе захватывались другие байты.

Код получился такой:



Результат:



Небольшое время при шаге 500, 1000, 2000, 5000 можно объяснить кратностью шага размеру массива, что приводит к многократному проходу по тем же данным, при небольшом общем размере этих данных, которые по этой причине легко закэшировать. Небольшое изменение шага (с 1000 на 1010) приводит к сильному увеличению времени выполнения программы, т.к. реальный объем обрабатываемых адресов значительно увеличивается и в кэш не умещается.

PS
Не завидую я разработчикам тестов производительности. 

Познавательное исследование, спасибо!