Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 60
На тему этой и предыдущей заметки: "Вечный вопрос измерения времени". Вдруг кому-то пригодится.
Автор исходного поста писал про 10%, «в 10 раз» у него нет.
«получаем десятикратное* увеличение скорости выполнения требуемой операции.»
Прогнав тестовую программу, получаем следующий результат — время выполнения составляет 9.4 секунды! Итого, сравнивая времена «нетто» (2.1 и 0.2 секунды соответственно) для двух вариантов расчета искомого значения, получаем десятикратное* увеличение скорости выполнения требуемой операции.
Цитата из исходного поста.
Хм, а в начале статьи
И в конце
время выполнения составляет в среднем 9.2 секунды. Если раскомментировать вызов расчетной функции, пересобрать проект и повторить эксперимент — получаем примерно 11.5 секунд.
И в конце
Описанной оптимизацией только лишь одной функции удалось сократить время обработки единичного блока данных со 160 до 140 секунд (при выполнении на i7), что составляет более 10%
Мораль #5: используйте предсказуемый рандом, чтобы результаты консистентными были.
Во1х?
привык так писать «во-первых»
ну Вы же для остальных простых людей пишете :) в таких случаях в начале статьи нужно список терминов приводить
Щаз (*) соберется критическая масса опечаток и я на утеху grammar nazi поправлю, может, пост
Но это сейчас у меня лично первый раз в жизни, когда кто-то не понял, что значит «во1х», «во2х», итп :)
(*) авторская транскрипция; автор в курсе, что в словаре пишут «сейчас»; заранее спасибо, неизвестный кэп ;)
Но это сейчас у меня лично первый раз в жизни, когда кто-то не понял, что значит «во1х», «во2х», итп :)
(*) авторская транскрипция; автор в курсе, что в словаре пишут «сейчас»; заранее спасибо, неизвестный кэп ;)
Я думал это либа какая-то, пока читал по диагонали.
Я далек от граммар нацци, но «во1х» — это ужасно. Пожалуйста, не пишите так никогда! А за пост спасибо :)
никогдааа?! 4 кнопки вместо 9, одна из которых чутка удаленный минус; в скайп-чатике быстрей-быстрей как же еще писать!? :)
Настоящие мужики на это смотрят как удачную на возможность потренировать скоропись и гибкость пальцев! :)
Если писать «1)» и «2)», то вообще по два символа получается. Следовательно:
1)пишется в 2 раза быстрее;
2)читается в 1000 раз быстрее, чем «бо-один-икс» и «бо-два-икс».
Оптимизации на лицо (если я не ошибся в бенчмарках).
1)пишется в 2 раза быстрее;
2)читается в 1000 раз быстрее, чем «бо-один-икс» и «бо-два-икс».
Оптимизации на лицо (если я не ошибся в бенчмарках).
Ошибся в обоих пунктах, увы!
1) пишется в 3 клика, а не 2, ибо скобки набираются с зажатым shift.
2) чтение в 1000 раз быстрее пробенчмаркано только на одной платформе; на моей микроархитектуре различий нет, все исполняется за одинаковое время.
А если серьезно, от всей этой ветки обсуждения у меня глаза слегка на лоб.
Количество людей, которых, хм, легкое отклонение графематики от привычной им беспокоит достаточно для того, чтобы писать комментарии, активничать с плюсиками и минусиками и, может, еще как то проявлять активную гражданскую позицию, выходит неожиданно большое — отличается от нуля.
Технический (вроде) ресурс, техническая (точно) статья, оформлена в целом, простите, не сказать, чтобы нечитаемо — а обсуждаем варианты написания «во-первых» — а еще 4 опечатки, которые я только что заодно с этим Чудовищным Отклонением от ХаброНормы исправил, не заметил почему-то никто.
Привет, дивный новый Хабр — чую, еще пара лет эволюции в этом направлении и если хоть одну запятую не там поставишь, то берегись! Буря, пусть сильнее грянет буря!!! :)
1) пишется в 3 клика, а не 2, ибо скобки набираются с зажатым shift.
2) чтение в 1000 раз быстрее пробенчмаркано только на одной платформе; на моей микроархитектуре различий нет, все исполняется за одинаковое время.
А если серьезно, от всей этой ветки обсуждения у меня глаза слегка на лоб.
Количество людей, которых, хм, легкое отклонение графематики от привычной им беспокоит достаточно для того, чтобы писать комментарии, активничать с плюсиками и минусиками и, может, еще как то проявлять активную гражданскую позицию, выходит неожиданно большое — отличается от нуля.
Технический (вроде) ресурс, техническая (точно) статья, оформлена в целом, простите, не сказать, чтобы нечитаемо — а обсуждаем варианты написания «во-первых» — а еще 4 опечатки, которые я только что заодно с этим Чудовищным Отклонением от ХаброНормы исправил, не заметил почему-то никто.
Привет, дивный новый Хабр — чую, еще пара лет эволюции в этом направлении и если хоть одну запятую не там поставишь, то берегись! Буря, пусть сильнее грянет буря!!! :)
Развитие ветки обсуждения спровоцировало всё же то, что вы стали защищать свой очень-очень странный способ написания. Ошибки/опечатки, не мешающие пониманию, уже не замечают, зато такие, почти l337-speak, слова реально сильно затрудняют чтение.
Хоть Хабр сейчас и модно ругать, но в этом случае дело не в нём.
Хоть Хабр сейчас и модно ругать, но в этом случае дело не в нём.
> Развитие ветки обсуждения спровоцировало всё же то, что
«обсуждать» тут было сразу нечего после 2го моего комментария, а теперь уже абсолютно нечего
> защищать свой… способ… Хабр… модно ругать,
глаза на лоб еще сильнее
лишний раз убеждаюсь, что чего и как не напиши — кто-нибудь обязательно все поймет настолько наоборот, что просто слов нет
остается только надеяться, что большая часть посетителей Хабра — все еще способна без особых усилий понять, что такое «во1х», отличает пояснения от оправданий, иронию от ругани, итд итп
и потому и не пишет ничего, слава Кришне, в эту замечательную подветку ;)
«обсуждать» тут было сразу нечего после 2го моего комментария, а теперь уже абсолютно нечего
> защищать свой… способ… Хабр… модно ругать,
глаза на лоб еще сильнее
лишний раз убеждаюсь, что чего и как не напиши — кто-нибудь обязательно все поймет настолько наоборот, что просто слов нет
остается только надеяться, что большая часть посетителей Хабра — все еще способна без особых усилий понять, что такое «во1х», отличает пояснения от оправданий, иронию от ругани, итд итп
и потому и не пишет ничего, слава Кришне, в эту замечательную подветку ;)
Вы говорите о количестве нажатий так, словно вы каждый вводимый символ заново ищете на клавиатуре.
отечески. спасибо андрей.
Нет, до сих пор есть активно использующиеся новые процессоры, которые ни сном ни духом про SSE. Vortex86SX хороший пример (инструкции 486ого на скоростях 200-400 МГц).
активно использующиеся новые процессоры...Vortex86SX
Ну-ну. Много у вас в Селектеле стоек с Vortex86SX?
А вот это очень правильный подход, особенно с учётом того, что через две недели выйдет новая серия процессоров на архитектуре Haswell с дополненным набором инструкций AVX2 для обработки 256-битных целочисленных векторов (8 int32_t). Естественно, код с SSE intrinsics в AVX сам не переведётся, но вышеприведённый код элементарно переделать вручную: __m128i поменять на __m256i и _mm_xxx на _mm256_xxx, тем самым поднять производительность ещё примерно в 2 раза (с учётом новых Cycles per Instruction). Ну а для старых процессоров использовать линейную обработку.
Мораль #6: найдите время запустить тест на разных компьютерах. Не в этом случае, но все же иногда алгоритм, работающий 250мс ± 200мс на настольном компьютере, может работать 200мс ± 10мс на сервере…
__m128i ab = _mm_mullo_epi32(a, b);
А не случится ли тут переполнения?
P.S. А вот у меня на Core2 нет SSE4, посоветуйте фоллбак, интересно же потестировать.
Случится. Такое же, как в исходной версии.
__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 */
Геймдевелопера не скрыть за широкими штанами )) Люблю читать статьи shodan'а.
С моралью три согласен полностью. В свое время использование вот этого варианта реализации декодера Витерби как раз дало где-то десятикратный прирост.
Результат от 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, все полностью детерминировано же). Так что фокус про «нагрев» и минимум не дисперсию прячет, а решает вообще другую проблему: нестабильные результаты от запуска к запуску на коротких бенчмарках. Результаты хочется стабильные, а не плюс-минус 20%, иначе как сравнивать. Но и получать их хочется за 10 прогонов, а не 1000, иначе каждый запуск больно долго ждать. Получилось вот так.
> Если мы хотим использовать этот код в продакшене,
Не хотим. Речь идет о benchmark'ах.
> Но очень странная идея — использовать минимум в погоне за маленькой дисперсией.
Выбор наименьшего значения по результатам огромного повторения — это попытка определить время выполнения именно того участка кода, который нас интересует и нивелировать потери на кэш-промахи, переключения контекста и т.п.
Не хотим. Речь идет о benchmark'ах.
> Но очень странная идея — использовать минимум в погоне за маленькой дисперсией.
Выбор наименьшего значения по результатам огромного повторения — это попытка определить время выполнения именно того участка кода, который нас интересует и нивелировать потери на кэш-промахи, переключения контекста и т.п.
Не путайте замер времени выполнения кучки машинных инструкций и времени выполнения огромного алгоритма. Современное железо и ОС никто не оптимизировал для быстрого выполнения сверхмалых задач, отсюда и все погрешности в первом случае. Но, когда эта кучка инструкций войдет в другую программу как составная часть, все эти погрешности окажутся раскиданными по всей программе, и время выполнения этих инструкций станет близким к минимальному, что и измеряется.
Вот если измерять скорость работы некоторого модуля целиком — тогда да, надо брать среднюю.
Вот если измерять скорость работы некоторого модуля целиком — тогда да, надо брать среднюю.
> Вы путаете бенчмаркинг ради бенчмаркинга и бенчмаркинг ради практического результата.
Я не являюсь специалистом, но мне кажеться, что Вы путаете бенчмаркинг и профилирование.
Я не являюсь специалистом, но мне кажеться, что Вы путаете бенчмаркинг и профилирование.
Кеш-промахи — вещь не случайная, а закономерная, если только они не были вызваны переключением контекста, а потому даже после операция взятия минимума они будут учтены.
Переключения же контекста — вещь довольно редкая, но долгая. Если прогонять измеряемый участок кода не более сотни раз — есть риск измерить не время выполнения кода, а время переключения контекста, вместе со временем выполнения других потоков. Стоит же числу итераций подняться до пары миллионов — и все переключения контекста затеряются в основной массе полезной работы.
До конца время выполнения к минимальному не сведется, но надо же понимать разницу между 20мкс (+400мс на то самое переключение контекста) и 1 мс (+400мкс). (Цифры взяты с потолка)
Переключения же контекста — вещь довольно редкая, но долгая. Если прогонять измеряемый участок кода не более сотни раз — есть риск измерить не время выполнения кода, а время переключения контекста, вместе со временем выполнения других потоков. Стоит же числу итераций подняться до пары миллионов — и все переключения контекста затеряются в основной массе полезной работы.
До конца время выполнения к минимальному не сведется, но надо же понимать разницу между 20мкс (+400мс на то самое переключение контекста) и 1 мс (+400мкс). (Цифры взяты с потолка)
Мне это знание за тем, что бы я мог сказать, что алгоритм (или реализация) «А» быстрее алгоритма «В».
Другое дело если мне нужен ответ на вопрос: «как долго выполняется алгоритм „А“ в реальном проекте и сколько это в процентах от общего времени (т.е. профилировка)?», — тогда я согласен, условия при которых производятся измерения должны быть максимально приближены к «боевым».
Другое дело если мне нужен ответ на вопрос: «как долго выполняется алгоритм „А“ в реальном проекте и сколько это в процентах от общего времени (т.е. профилировка)?», — тогда я согласен, условия при которых производятся измерения должны быть максимально приближены к «боевым».
Знание затем, чтобы оперативно сравнивать две версии функции на микробенчмарке, в ходе работы над ними.
Еще раз: случай абсолютно одинаковый, но время одного исполнения сильно дрожит. По понятным вполне причинам, но с этим нельзя работать. Один (один) долбаный пик иногда сильно сбивает среднее, а он вдобавок не один. Представь ситуацию: в 70% повторов выходит 120+-1 мс, именно это значение (120 мс) и интересует. По существу, медианное. Еще в 30% повторов выходит что угодно от 130 до 150 мс, потому что наведенное (!) разными внешними (!) причинами дрожание. Внезапно, среднее колбасит от 123 до 129 мс, и внезапно, все отдельные изменения в ходе работы, которые реально убирают по 1 мс, бенчмаркать невозможно. А с минимумом возможно, и при этом итерация НЕ должна длиться 1000 повторов.
Вот можно, кстати, попробовать медиану считать. Этим разом я не попробовал. Но минимум считать еще проще, результат отличается незначительно, и главное: выходит крайне стабильным и эксперименты БЫСТРЫЕ, те. с ним можно ежеминутно работать. А для окончательного мега-бенчмарка, разумеется, нужно и кучу прогонов, и дисперсию, и вообще распределение лучше бы глянуть. Вот и все.
Еще раз: случай абсолютно одинаковый, но время одного исполнения сильно дрожит. По понятным вполне причинам, но с этим нельзя работать. Один (один) долбаный пик иногда сильно сбивает среднее, а он вдобавок не один. Представь ситуацию: в 70% повторов выходит 120+-1 мс, именно это значение (120 мс) и интересует. По существу, медианное. Еще в 30% повторов выходит что угодно от 130 до 150 мс, потому что наведенное (!) разными внешними (!) причинами дрожание. Внезапно, среднее колбасит от 123 до 129 мс, и внезапно, все отдельные изменения в ходе работы, которые реально убирают по 1 мс, бенчмаркать невозможно. А с минимумом возможно, и при этом итерация НЕ должна длиться 1000 повторов.
Вот можно, кстати, попробовать медиану считать. Этим разом я не попробовал. Но минимум считать еще проще, результат отличается незначительно, и главное: выходит крайне стабильным и эксперименты БЫСТРЫЕ, те. с ним можно ежеминутно работать. А для окончательного мега-бенчмарка, разумеется, нужно и кучу прогонов, и дисперсию, и вообще распределение лучше бы глянуть. Вот и все.
Уже жалею, что снова ввязался в обсуждение. Мне кажется, ты споришь сам с собой, подразумевая какой-то свой прошлый опыт (неизвестный более никому), но зато чуть менее, чем полностью игнорируя то, что я тебе пытаюсь рассказывать про этот вполне конкретный случай. После мощного передергивания про «надо изгаляться над данными и выбрать другую метрику» (а этот бред придумал ты, но зачем-то немедленно приписал его мне) продолжать общение вообще, честно говоря, сразу неохота. Так что повторюсь последний раз, чисто для протокола, и хватит.
Да, вообще в произвольном общем случае с неизвестным распределением нижний 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? Вперед, пиши статью, будет очень интересно почитать.
Возвращаясь к оригинальному коду функции LLR() хотел бы сказать, что в зависимости от архитектуры может быть разное кол-во условных переходов. Например на ARM, где есть предикация, число переходов может быть меньше, чем на x86 и результаты оптимизации на ARM могут быть скромнее.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Про мнимые и реальные оптимизации в 10 раз, целительный SSE, и все такое