![]() |
|
![]() ![]() ![]() |
|
LamerTM |
|
||||
Шустрый ![]() Профиль Группа: Участник Сообщений: 97 Регистрация: 11.3.2006 Репутация: нет Всего: 0 |
На всякий случай извиняюсь, но не нашел в какой раздел это можно написать. Если будете бить, то уж лучше сразу насмерть.
![]() Тестирую время исполнения кода. Код на Delphi. Есть 2 варианта кода. Первый вариант:
Второй вариант:
Разница между ними всего в одном операторе в теле цикла for. Даже не в операторе, а в его аргументе (разный индекс массива). Чудо природы состоит в следующем. Первый код отрабатывает у меня 1093 мс. Второй - 577 мс. (У меня: AMD Duron 1100 MHz, FSB 100 MHz, чипсет VIA KT266A.) Почему так? |
||||
|
|||||
maxim1000 |
|
||||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: нет Всего: 110 |
ИМХО, дело здесь не сколько в инструкциях, сколько в доступе к памяти
побайтный доступ очень неэффективен, по сути, что байт из памяти достать, что 32-битное слово - одинаково (при условии, что его адрес кратен 4) так что в первом случае можно достать оба байта за практически то же время, что и 1 (просто достав 4-байтное слово, которое их содержит) а во втором случае их приходится доставать отдельно (т.к. нет такого 4-байтного слова, которое их содержит) для прояснения ситуации я бы порекомендовал ещё два теста:
и
если вышеописанная гипотеза верна, то второй будет по скорости приблизительно так же, как и <0,1>, да и первый сильно не отстанет (может быть больше из-за того, что операций стало реально больше) -------------------- qqq |
||||
|
|||||
LSD |
|
|||
![]() 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. |
|||
|
||||
LamerTM |
|
||||||
Шустрый ![]() Профиль Группа: Участник Сообщений: 97 Регистрация: 11.3.2006 Репутация: нет Всего: 0 |
Так дело в том, что первый случай (когда теоретически достаются сразу 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 мс. Тут я вообще в шоке. Убрал оператор, а всё стало работать медленнее. Время выполнения в каждом случае немного "шумит". В качестве результата выбиралось минимальное значение. Короче, не знаю что и думать. |
||||||
|
|||||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: нет Всего: 110 |
упс... это я напутал при чтении первого поста
![]() интересно тогда есть ещё одна мысль: не знаю, как у AMD, но у одного из специализированных процессоров, с которым я работал, была такая система: кэш не монолитный, а состоит из нескольких частей при некоторых условиях можно из этих частей выбирать данные параллельно, с экономией времени по сравнению с двумя последовательными выборками одна из возможных политик поведения кэша - исходя из локальной близости данных (т.е. при обращении к какому-то слову происходит кэширование соседних ячеек) одно и то же слово вряд ли будет помещено в разные части кэша - это слишком расточительно (кэша всегда не хватает) вот и получается что вероятная ситуация: первое слово попадает в одну часть кэша, второе - в другую это позволяет быстро выбирать их, когда дело касается двух разных ячеек когда же происходит доступ к одной и той же ячейке, то и приходится обращаться к одной и той же части кэша два раза, приходится делать это последовательно Добавлено через 1 минуту и 46 секунд кстати, на уровне компилятора можно было бы вообще представить это в виде одной операции чтения из памяти и нескольких операций над регистрами, но для этого надо быть уверенным в выровненности старта массива на границу 4-х байт Добавлено через 4 минуты и 5 секунд ![]() Идёт физик по коридору, навстречу инженер, рассказал про проведённый эксперимент, показал кривую, попросил её объяснить. Физик подумал немного и объяснил, почему так получается. Вдруг инженер с ужасом заметил, что он показал кривую вверх ногами, перевернул. Физик подумал ещё раз и тоже объяснил ![]() -------------------- qqq |
|||
|
||||
LamerTM |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 97 Регистрация: 11.3.2006 Репутация: нет Всего: 0 |
Вряд ли это связано с кэшем. Я ведь могу сделать размер массива не только 100 байт, но и миллион байт. Весь массив в кэш не влезет, ибо кэш у меня 192КБ. А тем не менее такой код:
aa[0] := aa[0]+2; aa[999999] := aa[999999]+2; Выполняется за 577 мс. Остается только считать, что такое время выполнения является нормальным, и не является следствием оптимизации. У меня уже мозги закипели от попыток понять в чём может быть причина. ![]() Выяснилось только что обработка четырех и более байт не зависит от их порядка следования. Если обрабатывать три и менее байт, то результаты зависят от их расположения. А анекдот супер. ![]() |
|||
|
||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: нет Всего: 110 |
так не весь же массив попадает в кэш здесь можно предположить, что в одну часть кэша попадает a[0], а в другую - a[999999] -------------------- qqq |
|||
|
||||
LamerTM |
|
||||||||
Шустрый ![]() Профиль Группа: Участник Сообщений: 97 Регистрация: 11.3.2006 Репутация: нет Всего: 0 |
Код:
Компилируется в такой:
А каким образом байт с номером 999999 может попасть в кэш?. Откуда системе знать какой байт я запрошу? А весь массив не помещается. Хотя я в железе полный ноль конечно. ![]() Возможно здесь играет роль повторяемость операций. На первом цикле запоминаются выбранные мной байты, а на следующих итерациях идет работа с кэшем, а не с оперативной памятью. Сделал эксперимент чтобы это проверить. Код такой:
Здесь меняются байты массива с указанным шагом (в коде шаг равен 1). Раньше я писал что порядок изменения байтов не играет роли. Так вот, выяснилось, что это не правда. ![]()
Скорее всего ближайшие данные действительно кэшируются, причем каким-то хитрым образом. Если сильно скакать по массиву, то скорость замедляется (да еще как, я думал всё зависло). Так что похоже и вправду дело в кэше в конечном счете. |
||||||||
|
|||||||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: нет Всего: 110 |
да, по идее, так и должно быть ну... в меру хитрым используется гипотеза локальности обращений к памяти: обращаются чаще к близким ячейкам поэтому, когда одно значение выбирается, то и на всякий случай выбираются и соседние ячейки дело в том, что из-за устройства оперативной памяти время доставания двух последовательных слов меньше, чем удвоенное время доставания одного слова, т.е. выгоднее обмениваться с памятью целыми пакетами -------------------- qqq |
|||
|
||||
LamerTM |
|
||||||
Шустрый ![]() Профиль Группа: Участник Сообщений: 97 Регистрация: 11.3.2006 Репутация: нет Всего: 0 |
Еще одну фишку заметил.
![]() Предыдущую таблицу можно продолжить.
Прикол - в уменьшении времени, когда шаг становится очень большим. Напомню, что прога проходит по всему массиву с заданным шагом. По окончании массива всё начинается снова. Длина массива - 1 миллион байт. Когда шаг равен 1, при одном проходе по массиву перебирается 1 миллион байт. Когда шаг равен 100, перебирается 10 000 байт. Когда шаг равен 1000, перебирается 1000 байт. Быстрое выполнение кода с маленьким шагом можно объяснить тем, что система сразу берет в кэш ближайшие данные. А вот более быстрое выполнение кода с большим шагом можно объяснить тем, что система запоминает недавно использовавшиеся адреса (или данные), и при повторном к ним обращении берет их из кэша. В случае с большим шагом получается, что общий объем перебираемых данных уменьшается, поэтому такая методика приводит к повышению производительности в этом случае. Чтобы подтвердить предположение, предыдущую прогу немного изменил. Сделал так, чтобы шаг был по-прежнему фиксирован, но при окончании прохода по массиву всё начиналось не сначала по тем же данным, а со сдвигом, чтобы при следующем проходе захватывались другие байты. Код получился такой:
Результат:
Небольшое время при шаге 500, 1000, 2000, 5000 можно объяснить кратностью шага размеру массива, что приводит к многократному проходу по тем же данным, при небольшом общем размере этих данных, которые по этой причине легко закэшировать. Небольшое изменение шага (с 1000 на 1010) приводит к сильному увеличению времени выполнения программы, т.к. реальный объем обрабатываемых адресов значительно увеличивается и в кэш не умещается. PS Не завидую я разработчикам тестов производительности. ![]() |
||||||
|
|||||||
SelenIT |
|
|||
![]() баг форума ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 3996 Регистрация: 17.10.2006 Где: Pale Blue Dot Репутация: нет Всего: 401 |
Познавательное исследование, спасибо!
-------------------- Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму! |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Тестирование программ" | |
|
Правила должны соблюдаться всеми без исключения.
Для тех, кто создаёт темы: В данном разделе запрещается размещать программы, которые в той или иной степени могут принести вред потенциальному тестеру программы (например, трояны, вирусы и т.д.)
Для тех, кто тестирует: Описывая результаты тестирования программы, указывайте тип и версию ОС, а также характеристики компьютера и прочую информацию, которая может повлиять на работоспособность. Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, mr.Anderson. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Разное тестирование | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |