Comments 60
На тему этой и предыдущей заметки: "Вечный вопрос измерения времени". Вдруг кому-то пригодится.
+2
Автор исходного поста писал про 10%, «в 10 раз» у него нет.
-5
«получаем десятикратное* увеличение скорости выполнения требуемой операции.»
+6
Прогнав тестовую программу, получаем следующий результат — время выполнения составляет 9.4 секунды! Итого, сравнивая времена «нетто» (2.1 и 0.2 секунды соответственно) для двух вариантов расчета искомого значения, получаем десятикратное* увеличение скорости выполнения требуемой операции.
Цитата из исходного поста.
0
Хм, а в начале статьи
И в конце
время выполнения составляет в среднем 9.2 секунды. Если раскомментировать вызов расчетной функции, пересобрать проект и повторить эксперимент — получаем примерно 11.5 секунд.
И в конце
Описанной оптимизацией только лишь одной функции удалось сократить время обработки единичного блока данных со 160 до 140 секунд (при выполнении на i7), что составляет более 10%
0
Мораль #5: используйте предсказуемый рандом, чтобы результаты консистентными были.
0
Во1х?
+13
привык так писать «во-первых»
-8
ну Вы же для остальных простых людей пишете :) в таких случаях в начале статьи нужно список терминов приводить
+8
Щаз (*) соберется критическая масса опечаток и я на утеху grammar nazi поправлю, может, пост
Но это сейчас у меня лично первый раз в жизни, когда кто-то не понял, что значит «во1х», «во2х», итп :)
(*) авторская транскрипция; автор в курсе, что в словаре пишут «сейчас»; заранее спасибо, неизвестный кэп ;)
Но это сейчас у меня лично первый раз в жизни, когда кто-то не понял, что значит «во1х», «во2х», итп :)
(*) авторская транскрипция; автор в курсе, что в словаре пишут «сейчас»; заранее спасибо, неизвестный кэп ;)
-4
Я думал это либа какая-то, пока читал по диагонали.
+10
Я далек от граммар нацци, но «во1х» — это ужасно. Пожалуйста, не пишите так никогда! А за пост спасибо :)
+19
никогдааа?! 4 кнопки вместо 9, одна из которых чутка удаленный минус; в скайп-чатике быстрей-быстрей как же еще писать!? :)
-10
Настоящие мужики на это смотрят как удачную на возможность потренировать скоропись и гибкость пальцев! :)
+5
Если писать «1)» и «2)», то вообще по два символа получается. Следовательно:
1)пишется в 2 раза быстрее;
2)читается в 1000 раз быстрее, чем «бо-один-икс» и «бо-два-икс».
Оптимизации на лицо (если я не ошибся в бенчмарках).
1)пишется в 2 раза быстрее;
2)читается в 1000 раз быстрее, чем «бо-один-икс» и «бо-два-икс».
Оптимизации на лицо (если я не ошибся в бенчмарках).
+15
Ошибся в обоих пунктах, увы!
1) пишется в 3 клика, а не 2, ибо скобки набираются с зажатым shift.
2) чтение в 1000 раз быстрее пробенчмаркано только на одной платформе; на моей микроархитектуре различий нет, все исполняется за одинаковое время.
А если серьезно, от всей этой ветки обсуждения у меня глаза слегка на лоб.
Количество людей, которых, хм, легкое отклонение графематики от привычной им беспокоит достаточно для того, чтобы писать комментарии, активничать с плюсиками и минусиками и, может, еще как то проявлять активную гражданскую позицию, выходит неожиданно большое — отличается от нуля.
Технический (вроде) ресурс, техническая (точно) статья, оформлена в целом, простите, не сказать, чтобы нечитаемо — а обсуждаем варианты написания «во-первых» — а еще 4 опечатки, которые я только что заодно с этим Чудовищным Отклонением от ХаброНормы исправил, не заметил почему-то никто.
Привет, дивный новый Хабр — чую, еще пара лет эволюции в этом направлении и если хоть одну запятую не там поставишь, то берегись! Буря, пусть сильнее грянет буря!!! :)
1) пишется в 3 клика, а не 2, ибо скобки набираются с зажатым shift.
2) чтение в 1000 раз быстрее пробенчмаркано только на одной платформе; на моей микроархитектуре различий нет, все исполняется за одинаковое время.
А если серьезно, от всей этой ветки обсуждения у меня глаза слегка на лоб.
Количество людей, которых, хм, легкое отклонение графематики от привычной им беспокоит достаточно для того, чтобы писать комментарии, активничать с плюсиками и минусиками и, может, еще как то проявлять активную гражданскую позицию, выходит неожиданно большое — отличается от нуля.
Технический (вроде) ресурс, техническая (точно) статья, оформлена в целом, простите, не сказать, чтобы нечитаемо — а обсуждаем варианты написания «во-первых» — а еще 4 опечатки, которые я только что заодно с этим Чудовищным Отклонением от ХаброНормы исправил, не заметил почему-то никто.
Привет, дивный новый Хабр — чую, еще пара лет эволюции в этом направлении и если хоть одну запятую не там поставишь, то берегись! Буря, пусть сильнее грянет буря!!! :)
-7
Развитие ветки обсуждения спровоцировало всё же то, что вы стали защищать свой очень-очень странный способ написания. Ошибки/опечатки, не мешающие пониманию, уже не замечают, зато такие, почти l337-speak, слова реально сильно затрудняют чтение.
Хоть Хабр сейчас и модно ругать, но в этом случае дело не в нём.
Хоть Хабр сейчас и модно ругать, но в этом случае дело не в нём.
+7
> Развитие ветки обсуждения спровоцировало всё же то, что
«обсуждать» тут было сразу нечего после 2го моего комментария, а теперь уже абсолютно нечего
> защищать свой… способ… Хабр… модно ругать,
глаза на лоб еще сильнее
лишний раз убеждаюсь, что чего и как не напиши — кто-нибудь обязательно все поймет настолько наоборот, что просто слов нет
остается только надеяться, что большая часть посетителей Хабра — все еще способна без особых усилий понять, что такое «во1х», отличает пояснения от оправданий, иронию от ругани, итд итп
и потому и не пишет ничего, слава Кришне, в эту замечательную подветку ;)
«обсуждать» тут было сразу нечего после 2го моего комментария, а теперь уже абсолютно нечего
> защищать свой… способ… Хабр… модно ругать,
глаза на лоб еще сильнее
лишний раз убеждаюсь, что чего и как не напиши — кто-нибудь обязательно все поймет настолько наоборот, что просто слов нет
остается только надеяться, что большая часть посетителей Хабра — все еще способна без особых усилий понять, что такое «во1х», отличает пояснения от оправданий, иронию от ругани, итд итп
и потому и не пишет ничего, слава Кришне, в эту замечательную подветку ;)
-9
Вы говорите о количестве нажатий так, словно вы каждый вводимый символ заново ищете на клавиатуре.
+3
отечески. спасибо андрей.
+1
Нет, до сих пор есть активно использующиеся новые процессоры, которые ни сном ни духом про SSE. Vortex86SX хороший пример (инструкции 486ого на скоростях 200-400 МГц).
0
активно использующиеся новые процессоры...Vortex86SX
Ну-ну. Много у вас в Селектеле стоек с Vortex86SX?
+6
В Селектеле нет. А вот на предыдущей работе два этажа было забито POS-оборудованием, которое x86, но SSE ни в зуб ногой.
+1
Embedded — это отдельный мир, и те, кто в нём живёт достаточно квалифицированы, чтобы адаптировать любой код к своим нуждам. SSE интринзиками их не испугаешь.
+1
А вот это очень правильный подход, особенно с учётом того, что через две недели выйдет новая серия процессоров на архитектуре Haswell с дополненным набором инструкций AVX2 для обработки 256-битных целочисленных векторов (8 int32_t). Естественно, код с SSE intrinsics в AVX сам не переведётся, но вышеприведённый код элементарно переделать вручную: __m128i поменять на __m256i и _mm_xxx на _mm256_xxx, тем самым поднять производительность ещё примерно в 2 раза (с учётом новых Cycles per Instruction). Ну а для старых процессоров использовать линейную обработку.
+2
Мораль #6: найдите время запустить тест на разных компьютерах. Не в этом случае, но все же иногда алгоритм, работающий 250мс ± 200мс на настольном компьютере, может работать 200мс ± 10мс на сервере…
+3
__m128i ab = _mm_mullo_epi32(a, b);
А не случится ли тут переполнения?
P.S. А вот у меня на Core2 нет SSE4, посоветуйте фоллбак, интересно же потестировать.
0
Случится. Такое же, как в исходной версии.
__m128i tmp1 = _mm_mul_epu32(a,b); /* mul 2,0*/
__m128i tmp2 = _mm_mul_epu32( _mm_srli_si128(a,4), _mm_srli_si128(b,4)); /* mul 3,1 */
return _mm_unpacklo_epi32(_mm_shuffle_epi32(tmp1, _MM_SHUFFLE (0,0,2,0)), _mm_shuffle_epi32(tmp2, _MM_SHUFFLE (0,0,2,0))); /* shuffle results to [63..0] and pack */
__m128i tmp1 = _mm_mul_epu32(a,b); /* mul 2,0*/
__m128i tmp2 = _mm_mul_epu32( _mm_srli_si128(a,4), _mm_srli_si128(b,4)); /* mul 3,1 */
return _mm_unpacklo_epi32(_mm_shuffle_epi32(tmp1, _MM_SHUFFLE (0,0,2,0)), _mm_shuffle_epi32(tmp2, _MM_SHUFFLE (0,0,2,0))); /* shuffle results to [63..0] and pack */
+1
Геймдевелопера не скрыть за широкими штанами )) Люблю читать статьи shodan'а.
+7
Результат от hadd надо искать в другом месте.
Умножение матрицы 4x3 на вектор размером 4 можно делать через три штуки dpps (т.е. SSE4.2)
а можно три mulps и три haddps (SSE3)
По времени примерно одинаково (на текущих i7 haddps капельку быстрее), но не требует SSE4.2
Вот тут обсуждали: blog.lexa.ru/2011/09/13/o_vektornom_umnozhenii_vtoroi_final.html
(и там дальше по ссылкам)
Вектор на матрицу — это всякие повороты и масштабирования (что color space, что координат, один хрен)
Умножение матрицы 4x3 на вектор размером 4 можно делать через три штуки dpps (т.е. SSE4.2)
а можно три mulps и три haddps (SSE3)
По времени примерно одинаково (на текущих i7 haddps капельку быстрее), но не требует SSE4.2
Вот тут обсуждали: blog.lexa.ru/2011/09/13/o_vektornom_umnozhenii_vtoroi_final.html
(и там дальше по ссылкам)
Вектор на матрицу — это всякие повороты и масштабирования (что color space, что координат, один хрен)
0
UFO just landed and posted this here
Дисперсия там и так маленькая (теоретически вообще 0, все полностью детерминировано же). Так что фокус про «нагрев» и минимум не дисперсию прячет, а решает вообще другую проблему: нестабильные результаты от запуска к запуску на коротких бенчмарках. Результаты хочется стабильные, а не плюс-минус 20%, иначе как сравнивать. Но и получать их хочется за 10 прогонов, а не 1000, иначе каждый запуск больно долго ждать. Получилось вот так.
0
> Если мы хотим использовать этот код в продакшене,
Не хотим. Речь идет о benchmark'ах.
> Но очень странная идея — использовать минимум в погоне за маленькой дисперсией.
Выбор наименьшего значения по результатам огромного повторения — это попытка определить время выполнения именно того участка кода, который нас интересует и нивелировать потери на кэш-промахи, переключения контекста и т.п.
Не хотим. Речь идет о benchmark'ах.
> Но очень странная идея — использовать минимум в погоне за маленькой дисперсией.
Выбор наименьшего значения по результатам огромного повторения — это попытка определить время выполнения именно того участка кода, который нас интересует и нивелировать потери на кэш-промахи, переключения контекста и т.п.
0
UFO just landed and posted this here
Не путайте замер времени выполнения кучки машинных инструкций и времени выполнения огромного алгоритма. Современное железо и ОС никто не оптимизировал для быстрого выполнения сверхмалых задач, отсюда и все погрешности в первом случае. Но, когда эта кучка инструкций войдет в другую программу как составная часть, все эти погрешности окажутся раскиданными по всей программе, и время выполнения этих инструкций станет близким к минимальному, что и измеряется.
Вот если измерять скорость работы некоторого модуля целиком — тогда да, надо брать среднюю.
Вот если измерять скорость работы некоторого модуля целиком — тогда да, надо брать среднюю.
0
UFO just landed and posted this here
> Вы путаете бенчмаркинг ради бенчмаркинга и бенчмаркинг ради практического результата.
Я не являюсь специалистом, но мне кажеться, что Вы путаете бенчмаркинг и профилирование.
Я не являюсь специалистом, но мне кажеться, что Вы путаете бенчмаркинг и профилирование.
0
Кеш-промахи — вещь не случайная, а закономерная, если только они не были вызваны переключением контекста, а потому даже после операция взятия минимума они будут учтены.
Переключения же контекста — вещь довольно редкая, но долгая. Если прогонять измеряемый участок кода не более сотни раз — есть риск измерить не время выполнения кода, а время переключения контекста, вместе со временем выполнения других потоков. Стоит же числу итераций подняться до пары миллионов — и все переключения контекста затеряются в основной массе полезной работы.
До конца время выполнения к минимальному не сведется, но надо же понимать разницу между 20мкс (+400мс на то самое переключение контекста) и 1 мс (+400мкс). (Цифры взяты с потолка)
Переключения же контекста — вещь довольно редкая, но долгая. Если прогонять измеряемый участок кода не более сотни раз — есть риск измерить не время выполнения кода, а время переключения контекста, вместе со временем выполнения других потоков. Стоит же числу итераций подняться до пары миллионов — и все переключения контекста затеряются в основной массе полезной работы.
До конца время выполнения к минимальному не сведется, но надо же понимать разницу между 20мкс (+400мс на то самое переключение контекста) и 1 мс (+400мкс). (Цифры взяты с потолка)
0
Мне это знание за тем, что бы я мог сказать, что алгоритм (или реализация) «А» быстрее алгоритма «В».
Другое дело если мне нужен ответ на вопрос: «как долго выполняется алгоритм „А“ в реальном проекте и сколько это в процентах от общего времени (т.е. профилировка)?», — тогда я согласен, условия при которых производятся измерения должны быть максимально приближены к «боевым».
Другое дело если мне нужен ответ на вопрос: «как долго выполняется алгоритм „А“ в реальном проекте и сколько это в процентах от общего времени (т.е. профилировка)?», — тогда я согласен, условия при которых производятся измерения должны быть максимально приближены к «боевым».
0
Знание затем, чтобы оперативно сравнивать две версии функции на микробенчмарке, в ходе работы над ними.
Еще раз: случай абсолютно одинаковый, но время одного исполнения сильно дрожит. По понятным вполне причинам, но с этим нельзя работать. Один (один) долбаный пик иногда сильно сбивает среднее, а он вдобавок не один. Представь ситуацию: в 70% повторов выходит 120+-1 мс, именно это значение (120 мс) и интересует. По существу, медианное. Еще в 30% повторов выходит что угодно от 130 до 150 мс, потому что наведенное (!) разными внешними (!) причинами дрожание. Внезапно, среднее колбасит от 123 до 129 мс, и внезапно, все отдельные изменения в ходе работы, которые реально убирают по 1 мс, бенчмаркать невозможно. А с минимумом возможно, и при этом итерация НЕ должна длиться 1000 повторов.
Вот можно, кстати, попробовать медиану считать. Этим разом я не попробовал. Но минимум считать еще проще, результат отличается незначительно, и главное: выходит крайне стабильным и эксперименты БЫСТРЫЕ, те. с ним можно ежеминутно работать. А для окончательного мега-бенчмарка, разумеется, нужно и кучу прогонов, и дисперсию, и вообще распределение лучше бы глянуть. Вот и все.
Еще раз: случай абсолютно одинаковый, но время одного исполнения сильно дрожит. По понятным вполне причинам, но с этим нельзя работать. Один (один) долбаный пик иногда сильно сбивает среднее, а он вдобавок не один. Представь ситуацию: в 70% повторов выходит 120+-1 мс, именно это значение (120 мс) и интересует. По существу, медианное. Еще в 30% повторов выходит что угодно от 130 до 150 мс, потому что наведенное (!) разными внешними (!) причинами дрожание. Внезапно, среднее колбасит от 123 до 129 мс, и внезапно, все отдельные изменения в ходе работы, которые реально убирают по 1 мс, бенчмаркать невозможно. А с минимумом возможно, и при этом итерация НЕ должна длиться 1000 повторов.
Вот можно, кстати, попробовать медиану считать. Этим разом я не попробовал. Но минимум считать еще проще, результат отличается незначительно, и главное: выходит крайне стабильным и эксперименты БЫСТРЫЕ, те. с ним можно ежеминутно работать. А для окончательного мега-бенчмарка, разумеется, нужно и кучу прогонов, и дисперсию, и вообще распределение лучше бы глянуть. Вот и все.
0
UFO just landed and posted this here
Уже жалею, что снова ввязался в обсуждение. Мне кажется, ты споришь сам с собой, подразумевая какой-то свой прошлый опыт (неизвестный более никому), но зато чуть менее, чем полностью игнорируя то, что я тебе пытаюсь рассказывать про этот вполне конкретный случай. После мощного передергивания про «надо изгаляться над данными и выбрать другую метрику» (а этот бред придумал ты, но зачем-то немедленно приписал его мне) продолжать общение вообще, честно говоря, сразу неохота. Так что повторюсь последний раз, чисто для протокола, и хватит.
Да, вообще в произвольном общем случае с неизвестным распределением нижний outlier как показатель брать нельзя, так как иногда может подвести. Да, нужно как-нибудь фильтровать. Да, для финального мега-бенчмарка необходимо и качественно фильтровать, и вообще смотреть и анализировать распределение, и данные мерить не случайные, а несколько наоборов реальных плюс несколько специально сконструированных, итд итп. Все так, отличные верные общие выводы. Никто с ними как бы не спорит и обратного нигде никогда не писал.
Но мы говорим про конкретный и нередкий частный случай!
Нет, и в этом конкретном и в куче подобных частных случаев можно для ежеминутных итераций над фиксированными данными взять таки минимум. Это потому, что распределение скошено, нижних outliers нету (я типа смотрел свои данные), и минимум практически равен медиане. Алле, распределение известно, условия идеализированы (длинное линейное чтение из памяти), время исполнения тут вообще должно быть константой, те. наблюдаемое время t = T + random_noise, где нас интересует фактическое время T. Очевидно, что min(t) = T + min(random_noise) >= T, ситуация «min(t) маленький, но фактическое T большое» невозможна. Подчеркиваю: в данном конкретном классе случаев.
Есть красивые примеры, что в других классах бенчмарков все бывает сильно не так? Есть убедительные доказательства, что даже в данном классе бенчмарков min(random_noise) бывает сравним по порядку величины с T? Вперед, пиши статью, будет очень интересно почитать.
Да, вообще в произвольном общем случае с неизвестным распределением нижний outlier как показатель брать нельзя, так как иногда может подвести. Да, нужно как-нибудь фильтровать. Да, для финального мега-бенчмарка необходимо и качественно фильтровать, и вообще смотреть и анализировать распределение, и данные мерить не случайные, а несколько наоборов реальных плюс несколько специально сконструированных, итд итп. Все так, отличные верные общие выводы. Никто с ними как бы не спорит и обратного нигде никогда не писал.
Но мы говорим про конкретный и нередкий частный случай!
Нет, и в этом конкретном и в куче подобных частных случаев можно для ежеминутных итераций над фиксированными данными взять таки минимум. Это потому, что распределение скошено, нижних outliers нету (я типа смотрел свои данные), и минимум практически равен медиане. Алле, распределение известно, условия идеализированы (длинное линейное чтение из памяти), время исполнения тут вообще должно быть константой, те. наблюдаемое время t = T + random_noise, где нас интересует фактическое время T. Очевидно, что min(t) = T + min(random_noise) >= T, ситуация «min(t) маленький, но фактическое T большое» невозможна. Подчеркиваю: в данном конкретном классе случаев.
Есть красивые примеры, что в других классах бенчмарков все бывает сильно не так? Есть убедительные доказательства, что даже в данном классе бенчмарков min(random_noise) бывает сравним по порядку величины с T? Вперед, пиши статью, будет очень интересно почитать.
+1
Возвращаясь к оригинальному коду функции LLR() хотел бы сказать, что в зависимости от архитектуры может быть разное кол-во условных переходов. Например на ARM, где есть предикация, число переходов может быть меньше, чем на x86 и результаты оптимизации на ARM могут быть скромнее.
+1
UFO just landed and posted this here
Sign up to leave a comment.
Про мнимые и реальные оптимизации в 10 раз, целительный SSE, и все такое