Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Один и тот же код по сути, а работает разное время 
:(
    Опции темы
LamerTM
Дата 15.9.2007, 09:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 97
Регистрация: 11.3.2006

Репутация: нет
Всего: 0



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

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

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

Код

procedure TForm1.Button1Click(Sender: TObject);
var       i: Integer;
          n: TDateTime;
          aa: array of byte;
begin
          SetLength(aa, 100);
          n := Now;
          for i := 0 to 100000000 do
          begin
          aa[0] := aa[0]+2;
          aa[1] := aa[1]+2; // индекс=1
          end;
          Label1.Caption := IntToStr(MilliSecondsBetween(Now, n));
end;


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

Код

procedure TForm1.Button1Click(Sender: TObject);
var       i: Integer;
          n: TDateTime;
          aa: array of byte;
begin
          SetLength(aa, 100);
          n := Now;
          for i := 0 to 100000000 do
          begin
          aa[0] := aa[0]+2;
          aa[4] := aa[4]+2; // индекс=4
          end;
          Label1.Caption := IntToStr(MilliSecondsBetween(Now, n));
end;

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

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

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

Почему так?
PM MAIL   Вверх
maxim1000
Дата 15.9.2007, 10:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: нет
Всего: 110



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

          aa[0] := aa[0]+2;
          aa[1] := aa[1]+2;
          aa[2] := aa[2]+2;
          aa[3] := aa[3]+2;

и
Код

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

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


--------------------
qqq
PM WWW   Вверх
LSD
Дата 15.9.2007, 11:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Leprechaun Software Developer
****


Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: нет
Всего: 538



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


--------------------
Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.
PM MAIL WWW   Вверх
LamerTM
Дата 15.9.2007, 13:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 97
Регистрация: 11.3.2006

Репутация: нет
Всего: 0



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

          aa[0] := aa[0]+2;
          aa[1] := aa[1]+2;
          aa[2] := aa[2]+2;
          aa[3] := aa[3]+2;

и
Код

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

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

Так дело в том, что первый случай (когда теоретически достаются сразу 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 мс.
Тут я вообще в шоке. Убрал оператор, а всё стало работать медленнее.

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

Короче, не знаю что и думать.
PM MAIL   Вверх
maxim1000
Дата 15.9.2007, 15:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: нет
Всего: 110



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

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

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

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

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

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

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

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


--------------------
qqq
PM WWW   Вверх
LamerTM
Дата 16.9.2007, 14:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 97
Регистрация: 11.3.2006

Репутация: нет
Всего: 0



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

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

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

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

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

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



А анекдот супер. smile
PM MAIL   Вверх
maxim1000
Дата 16.9.2007, 14:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: нет
Всего: 110



Цитата(LamerTM @  16.9.2007,  14:51 Найти цитируемый пост)
aa[0] := aa[0]+2;
aa[999999] := aa[999999]+2;

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


--------------------
qqq
PM WWW   Вверх
LamerTM
Дата 16.9.2007, 17:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 97
Регистрация: 11.3.2006

Репутация: нет
Всего: 0



Код:

Код

          for i := 0 to 100000000 do
          begin
          aa[0] := aa[0]+2;
          aa[999999] := aa[999999]+2;
          end;


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

Код

        mov eax,$05f5e101
loop:   mov edx,[ebp-$0c]
        add byte ptr [edx],$02
        mov edx,[ebp-$0c]
        add byte ptr [edx+$000f423f],$02
        dec eax
        jnz -$13 (loop)


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

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



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

Код такой:

Код

procedure TForm1.Button1Click(Sender: TObject);
var       i, j, k: Integer;
          n: TDateTime;
          aa: array of byte;
begin
          SetLength(aa, 1000000);
          n := Now;
          j := 0;
          k := 0;
          for i := 0 to 100000000 do
          begin
          aa[j] := aa[j]+2;
          j := j + 1;                 // шаг
          if j > 999999 then j := 0;
          end;
          Label1.Caption := IntToStr(MilliSecondsBetween(Now, n));
          Caption := IntToStr(j);
end;


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

Код

Шаг      Время выполнения кода, мс
1        468
2        670
3        921
4        1108
5        1342
6        1561
10       2234
20       3905
40       6703
100      14750


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

Так что похоже и вправду дело в кэше в конечном счете.
PM MAIL   Вверх
maxim1000
Дата 16.9.2007, 20:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: нет
Всего: 110



Цитата(LamerTM @  16.9.2007,  17:25 Найти цитируемый пост)
Возможно здесь играет роль повторяемость операций. На первом цикле запоминаются выбранные мной байты, а на следующих итерациях идет работа с кэшем, а не с оперативной памятью.

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

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

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


--------------------
qqq
PM WWW   Вверх
LamerTM
Дата 17.9.2007, 13:59 (ссылка) |    (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 97
Регистрация: 11.3.2006

Репутация: нет
Всего: 0



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

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

Код

Шаг      Время выполнения кода, мс
1        468
2        670
3        921
4        1108
5        1342
6        1561
10       2234
20       3905
40       6703
100      14750
200      10468
500      1921
1000     749
2000     703
5000     577


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

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

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

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

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

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

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

Код

procedure TForm1.Button1Click(Sender: TObject);
var       i, j, k: Integer;
          n: TDateTime;
          aa: array of byte;
begin
          SetLength(aa, 1000000);
          n := Now;
          j := 0;
          k := 0;
          for i := 0 to 100000000 do
          begin
          aa[j] := aa[j]+2;
          j := j + 1000;                 // шаг
          if j > 999999 then j := j - 1000000; // новый варинат (со сдвигом)
          //if j > 999999 then j := 0; // старай вариант
          end;
          Label1.Caption := IntToStr(MilliSecondsBetween(Now, n));
          Caption := IntToStr(j);
end;


Результат:

Код

Шаг      Время выполнения кода, мс
1        468
2        718
3        952
4        1188
5        1358
6        1624
10       2484
20       4047
40       6811
100      14780
200      10484
500      1906
990      10766
1000     672
1010     10875
1020     9812
1990     8547
2000     656
2010     8561
5000     484
5010     3546
5100     10781


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

PS
Не завидую я разработчикам тестов производительности. smile
PM MAIL   Вверх
SelenIT
Дата 16.7.2011, 22:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


баг форума
****


Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: нет
Всего: 401



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


--------------------
Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Тестирование программ"
mr.Anderson

Правила должны соблюдаться всеми без исключения.

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

Для тех, кто создаёт темы:

В данном разделе запрещается размещать программы, которые в той или иной степени могут принести вред потенциальному тестеру программы (например, трояны, вирусы и т.д.)

  • Публикуя ссылку на программу, обязательно проверьте её работоспособность.
  • ОБЯЗАТЕЛЬНО: напишите название программы, а главное - её описание и приведите хотя бы один скриншот. Скриншот по размерам не более 500х500 пикселов, для скриншотов большего размера приводите ссылки на них.
  • Программа, которую Вы даёте на тестирование, должна быть откомпилирована, так как не каждый является программистом, да и мало кто будет ради тестирования устанавливать соответствующий софт.

Для тех, кто тестирует:

Описывая результаты тестирования программы, указывайте тип и версию ОС, а также характеристики компьютера и прочую информацию, которая может повлиять на работоспособность.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, mr.Anderson.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Разное тестирование | Следующая тема »


 




[ Время генерации скрипта: 0.1118 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.