Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 66
Ого
чо я себя идиотом почувствовал с IQ ниже, чем у креветки…
Первая мысль — за такие имена функций и переменных неплохо было бы расстреливать…
Да-да. По коду видно, что это какие-то вычисления. Автору было бы неплохо написать, что этот код решает такую-то задачу. Конечно можно по функциям сидеть и разбирать и найти известные алгоритмы, но у меня не возникает желания напрягать мозг для этого.
первая, и единственная.
в том-то и беда, что код мне достался именно в таком виде. и это нередкая ситуация из тех, когда приходится оптимизировать чей-то код
такие имена функций еще более менее читабельны. после обфускаторов/zend в еще большем лесе приходится копаться.
Вам придётся расстрелять ~всех выпускников мехмата МГУ. Подозреваю, и прочих матмехов. Иосиф Виссарионович, перелогиньтесь!
А можно разъяснить при чем тут мехмат МГУ? Их что-ли учат программировать в таком стиле?
Скорее, не учат программировать в другом. Подобный стиль написания кода похож на запись математических уравнений, которым учат матмехов, а вот умению писать читаемый код их не учит никто.
Я не то чтобы готов, на самом деле, искать причины; я просто неоднократно видел программный код в исполнении матмеха, и каждый раз он был похож на вышеприведённый, и даже хуже. Вот, красивый примерчик нашёл (разбивка на строки моя, форматирование оригинала):
Я не то чтобы готов, на самом деле, искать причины; я просто неоднократно видел программный код в исполнении матмеха, и каждый раз он был похож на вышеприведённый, и даже хуже. Вот, красивый примерчик нашёл (разбивка на строки моя, форматирование оригинала):
miss+=fabs(X[i+(N+1)*(j+1)]+X[i+(N+1)*(j-1)]+X[i+1+
N+1)*j]+X[i-1+(N+1)*j]-4*X[i+(N+1)*j]-b[i+(N+1)*j]); Мда… А у нас вот наоборот, некоторые преподы лабы не принимали, если не было единого стиля форматирования кода и адекватных имен идентификаторов…
Зато наверняка и математика была слабее. Каждому — своё.
Ряд профессоров до сих пор на Фортране пишет. У программиста на Фортране своё, аутентичное понимание адекватности имён идентификаторов. В частности, длина имени должна быть не более 6 символов. Сложно при этом выдвигать промышленные требования к читаемости кода, и слава Богу, что они не пытаются этим заниматься.
Ряд профессоров до сих пор на Фортране пишет. У программиста на Фортране своё, аутентичное понимание адекватности имён идентификаторов. В частности, длина имени должна быть не более 6 символов. Сложно при этом выдвигать промышленные требования к читаемости кода, и слава Богу, что они не пытаются этим заниматься.
Как матмех (физтех) скажу, что сложно только до выделения X[i+(N+1)*(j+1)] в семантическую единицу. Потом формула становится очень хорошо читаемой. Как будто фокус на микроскопе настроил, и все стало хорошо видно.
Я так же (хотя это и выглядит как будто наоборот) с SQL поступаю — использую всегда полные имена «базаданных».«таблица».«поле» Текста получается много, зато всегда ясно, что откуда берется. А так как писать и переписывать SQL мне приходится много, то экономится много времени на том, что не надо смотреть, откуда же берется это поле. При чтении такого SQL тоже достаточно «настроить фокус» и все хорошо видно.
Я так же (хотя это и выглядит как будто наоборот) с SQL поступаю — использую всегда полные имена «базаданных».«таблица».«поле» Текста получается много, зато всегда ясно, что откуда берется. А так как писать и переписывать SQL мне приходится много, то экономится много времени на том, что не надо смотреть, откуда же берется это поле. При чтении такого SQL тоже достаточно «настроить фокус» и все хорошо видно.
Отлично написано и наглядно. В статью в букмарки, книги в 2read.
p.s. нынче в большинстве случаев дешевле купить мощнее сервер, чем нанять толкового программиста который знает толк в оптимизации. или разрешить ему потратить только на это 1-5 дней.
p.p.s. еще есть злая штука — преждевременная и избыточная оптимизация. когда в момент разработки кода, когда еще толком не ясно что и как код будет делать — его пробуют улучшить и ускорить. в результате 2 дня оптимизируют функцию, которая потом выпиливается, т.к. agile и планы поменялись. (пример из жизни)
p.s. нынче в большинстве случаев дешевле купить мощнее сервер, чем нанять толкового программиста который знает толк в оптимизации. или разрешить ему потратить только на это 1-5 дней.
p.p.s. еще есть злая штука — преждевременная и избыточная оптимизация. когда в момент разработки кода, когда еще толком не ясно что и как код будет делать — его пробуют улучшить и ускорить. в результате 2 дня оптимизируют функцию, которая потом выпиливается, т.к. agile и планы поменялись. (пример из жизни)
А можно узнать, что можно 2 дня оптимизировать в функции? Если Вы знаете оптимизирующие хаки языка, в котором пишите, то Вы либо сразу пишите код с оптимизацией, либо в течение 5 минут заменяете все что надо на оптимизированный вариант.
Пример с python
писать вместо str += 'vasya' str = ''.join([str,'vasya'])
Или вместо for i in range(5) i = 0; while i < 5: i+=1
Пример с python
писать вместо str += 'vasya' str = ''.join([str,'vasya'])
Или вместо for i in range(5) i = 0; while i < 5: i+=1
Можно, например функция прорисовки обьекта или какой-то кастомный контрол. Во время разработки черновика приложения допустимо использовать такое решение, которое займет меньше времени. Иначе, если оптимизировать все что пишешь — уйдет больше времени на придумывание хороших решений и к дню дедлайна будет сделана треть приложения. Отлично сделана — но за нее не заплатят.
Все по делу, любой человек, который занимался оптимизацией подтвердит :)
Единственное замечание — попытка повторного использования счетчиков в циклах вкупе for private из open mp. Зачем, если можно объявлять счетчик в каждом цикле и он автоматически будет объявлен приватным при распараллеливании? Ну и заодно дать счетчикам осмысленные имена.
Единственное замечание — попытка повторного использования счетчиков в циклах вкупе for private из open mp. Зачем, если можно объявлять счетчик в каждом цикле и он автоматически будет объявлен приватным при распараллеливании? Ну и заодно дать счетчикам осмысленные имена.
скажем так, почти все оптимизации банальны, кроме SSE: все таки не каждый программист знает такие низкоуровневые функции, которые в большинстве приложений собственно и не требуются.
А данный код на том же фортране смотрелся бы куда изящнее.
А данный код на том же фортране смотрелся бы куда изящнее.
Знаете, я бы не стал говорить обо всех оптимизациях.
Я бы даже сказал, что алгоритмические оптимизации зачастую очень сложно понять без специальных пояснений. В качестве примера, почитайте Майкла Абраша «Дзен графического программирования»: там очень наглядно показано, как из одного алгоритма получить совершенно другой потём серии оптимизаций.
Я бы даже сказал, что алгоритмические оптимизации зачастую очень сложно понять без специальных пояснений. В качестве примера, почитайте Майкла Абраша «Дзен графического программирования»: там очень наглядно показано, как из одного алгоритма получить совершенно другой потём серии оптимизаций.
Меня сейчас пристрелят, но не могу не процитировать (произносится с дебильным выражением лица):
— «Папа, а с кем это ты сейчас разговаривал?» :)
По сути обсуждаемого вопроса: синтетические тесты тем плохи, что напоминают по полезности перекладывание кучки щебня в другую кучку детским совочком. В реальной жизни такая штуковины либо будет исполняться «как есть», пусть даже на бейсике и будет считать 30 секунд, а не 0.3, да и фиг с ней; если же надо считать часто и много — то начиная с подсчетов на GPU и заканчивая решениями на ПЛИС (в том числе и с использованием lookup tables), ибо прирост скорости будет несравнимый.
— «Папа, а с кем это ты сейчас разговаривал?» :)
По сути обсуждаемого вопроса: синтетические тесты тем плохи, что напоминают по полезности перекладывание кучки щебня в другую кучку детским совочком. В реальной жизни такая штуковины либо будет исполняться «как есть», пусть даже на бейсике и будет считать 30 секунд, а не 0.3, да и фиг с ней; если же надо считать часто и много — то начиная с подсчетов на GPU и заканчивая решениями на ПЛИС (в том числе и с использованием lookup tables), ибо прирост скорости будет несравнимый.
Насколько я понимаю, то с чем занимался любовными утехами автор — это реальный проект. В котором надо было улучшить производительность. Видимо кого-то-таки не устраивало, что считалось 30 секунд вместо 0,3. И этот кто-то — начальство.
Да тут вроде довольно-таки явно видно, что пример — тестовый. Я не верю в то, что будут писать ТАК реальную систему, там же непонятно нифига начиная от имен функций.
Ну, или просто у меня мало опыта, но я реальной жизни такого не видел еще. :)
Ну, или просто у меня мало опыта, но я реальной жизни такого не видел еще. :)
А, да, еще: из общения с математиками у меня возникло ощущение, что пока они свои формулы не упростят донельзя, не оптимизируют, не обсудят с коллегами, и не посидят вместе еще пару дней, споря над результатом — на реализацию не выдадут. :)
Всё это здорово, только при чем здесь высокая производительность?
Из всего здесь написанного к делу имеет отношение только выбор правильных алгоритмов, который может повысить производительность в разы (точнее, на шаги сложности функции O(*) ). Неправильный выбор алгоритма — это баг, один из самых серьезных типов багов вообще. Этот баг не позволяет использовать программу на больших объемах входных данных (то есть в реальных условиях), и править этот баг нужно _обязательно_.
Да, повышение локальности _данных_ (а не ссылок) тоже может в разы ускорить программу, но это опять же — правильный выбор структур данных и работающих с ними алгоритмов.
Всё остальное… нет, ну не то чтобы неверно. Всё это правильно. Но просто эффект… Ну, допустим, вы, просидев пару месяцев с профайлером и книжкой Гербера-Билла, добились ускорения работы программы в целом… на 20%. А нагрузка на систему за эти пару месяцев выросла на 50%. Вы потратили кучу усилий, но копали не в ту сторону.
«Низкоуровневая» оптимизация нужна и полезна, только не для высокой производительности, а для систем реального времени. Вот библиотеки Intel для работы, скажем, с изображениями — они просто бесценны, если ваша программа большую часть времени обрабатывает изображения. Какие-нибудь трансляции, или распознавание образов в реальном времени, или системы слежения за чем-то — и всё это на относительно слабом железе — вот в этих случаях вы будете выжимать из железа любые проценты. Но это «высокая удельная производительность».
А в высоконагруженных системах по мере необходимости просто добавляется один-два-десять-сто новых серверов за 1000-1500 долларов каждый. И задача программиста — обеспечить безпроблемное горизонтальное масштабирование системы на эти новые сервера. Была обработка одной структуры данных на 20 серверах, стала на 25 — и всё это прозрачно, нигде ничего не останавливалось и не переиндексировалось. И вот там уже начинаются свои трюки, засады и просторы для улучшений.
Из всего здесь написанного к делу имеет отношение только выбор правильных алгоритмов, который может повысить производительность в разы (точнее, на шаги сложности функции O(*) ). Неправильный выбор алгоритма — это баг, один из самых серьезных типов багов вообще. Этот баг не позволяет использовать программу на больших объемах входных данных (то есть в реальных условиях), и править этот баг нужно _обязательно_.
Да, повышение локальности _данных_ (а не ссылок) тоже может в разы ускорить программу, но это опять же — правильный выбор структур данных и работающих с ними алгоритмов.
Всё остальное… нет, ну не то чтобы неверно. Всё это правильно. Но просто эффект… Ну, допустим, вы, просидев пару месяцев с профайлером и книжкой Гербера-Билла, добились ускорения работы программы в целом… на 20%. А нагрузка на систему за эти пару месяцев выросла на 50%. Вы потратили кучу усилий, но копали не в ту сторону.
«Низкоуровневая» оптимизация нужна и полезна, только не для высокой производительности, а для систем реального времени. Вот библиотеки Intel для работы, скажем, с изображениями — они просто бесценны, если ваша программа большую часть времени обрабатывает изображения. Какие-нибудь трансляции, или распознавание образов в реальном времени, или системы слежения за чем-то — и всё это на относительно слабом железе — вот в этих случаях вы будете выжимать из железа любые проценты. Но это «высокая удельная производительность».
А в высоконагруженных системах по мере необходимости просто добавляется один-два-десять-сто новых серверов за 1000-1500 долларов каждый. И задача программиста — обеспечить безпроблемное горизонтальное масштабирование системы на эти новые сервера. Была обработка одной структуры данных на 20 серверах, стала на 25 — и всё это прозрачно, нигде ничего не останавливалось и не переиндексировалось. И вот там уже начинаются свои трюки, засады и просторы для улучшений.
> добились ускорения работы программы в целом… на 20%
Примерно в 200 раз.
Посоветуете более подходящий блог?
Примерно в 200 раз.
Посоветуете более подходящий блог?
Почему не over9000? =)
Я говорю о реальных проектах без явных ляпов, написанных нормальными программистами.
Понятно, что можно придумать примеры, поддающиеся ускорению и в 200, и в 200 тысяч раз.
Насчет блога — прямого попадания вроде нет, но по идее ближе всего блоги о Си++
Реальность такова, что единственный смысл использовать сегодня Си или Си++ — как раз таки выжать максимум удельной производительности.
Я говорю о реальных проектах без явных ляпов, написанных нормальными программистами.
Понятно, что можно придумать примеры, поддающиеся ускорению и в 200, и в 200 тысяч раз.
Насчет блога — прямого попадания вроде нет, но по идее ближе всего блоги о Си++
Реальность такова, что единственный смысл использовать сегодня Си или Си++ — как раз таки выжать максимум удельной производительности.
самый отрезвляющий код за этот год.
Последнего абзаца хватило бы, без простыни предшествующего текста.
1) А ты теперь скомпиль оба исходника в ICC с полной оптимизацией и сравни результаты.
2) А как ты замеряешь время? По времени выполнения кода или по процессорному времени которое даётся потоку. К тому как я вижу ты юзаешь и системные функции, по этому тут уже очень много факторов будут. тебе надо будет считать процессорное время для kernel mode и для user mode. Потому что замеры обычного времени тебе ничего не дадут. Тем более для такого малого времени тестирования.
2) А как ты замеряешь время? По времени выполнения кода или по процессорному времени которое даётся потоку. К тому как я вижу ты юзаешь и системные функции, по этому тут уже очень много факторов будут. тебе надо будет считать процессорное время для kernel mode и для user mode. Потому что замеры обычного времени тебе ничего не дадут. Тем более для такого малого времени тестирования.
Подсчет по тактам процессора — это жесть. Потому что тут ты всё равно не учитываешь многозадачность. за 1 секунду, смена потока произойдет огромное кол-во раз и как на крути у тебя будут данные завышены и сильно привязаны к состоянию системы. Потому как процессоры новые имею в себе функции энергосбережения и автоматического уменьшения таковой частоты в зависимости от нагрузки. И по этому первичная калибровка тебе мало что даст. И опять же malloc и free — как не крути но тут будут вызваны функции системы по выделению памяти, а скорость этой операция напрямую зависит от загруженности памяти, т.к. будут затрачено время на поиск свободной страницы виртуальной и физической страницы (конечно это время сверх мало, но всёже вносит свои ограничения) и таким образом по немного но собирается куча обстоятельств которые вносят погрешности
> Подсчет по тактам процессора — это жесть.
Может и жесть, но точность высокая.
С многозадачностью можно бороться запуская на чистой машине, где нет других «тяжелых» задач и путем многократного замера.
Энергосбережение и уменьшение тактовой частоты не при делах, если в proc cpuinfo указан флаг constant_tsc (гарантирующий стабильность счетчика тактов). Ибо счетчик тактов (не только он) часто используется ОС-ми для реализации функций выдачи текущего времени. Разве что с turbo boost будут небольшие проблемы.
Не каждый malloc/free вызывает ОС, более того, выделение-освобождение часто можно вынести за пределы измеряемого кода.
Может и жесть, но точность высокая.
С многозадачностью можно бороться запуская на чистой машине, где нет других «тяжелых» задач и путем многократного замера.
Энергосбережение и уменьшение тактовой частоты не при делах, если в proc cpuinfo указан флаг constant_tsc (гарантирующий стабильность счетчика тактов). Ибо счетчик тактов (не только он) часто используется ОС-ми для реализации функций выдачи текущего времени. Разве что с turbo boost будут небольшие проблемы.
Не каждый malloc/free вызывает ОС, более того, выделение-освобождение часто можно вынести за пределы измеряемого кода.
> Лирически цитируя одну замечательную женщину, «нет смысла использовать рекурсию там, где ее нет смысла использовать».
Цитируя другого замечательного человека, «нет смысла использовать мутабельные переменные там где нет смысла их использовать».
Кто-то не прав.
Цитируя другого замечательного человека, «нет смысла использовать мутабельные переменные там где нет смысла их использовать».
Кто-то не прав.
знакомый код какой-то… такое ощущение, что его давали в качества задания на одной из «Зимних Школ Intel по параллельным вычислениям»…
А теперь вот это всё — взять и подсветить.
спасибо, для меня очень полезная статья
Код таймера дали выше. А можете залить куда-нибудь весь код в итоговом виде архивом? В драйвере используются функции _function1 и пр., откуда они?
Мда, на ускорение посмотреть не получилось… Проц Core 2 Duo E8500, ось 32-бит. С включённым openmp неоптимизированный вариант выполнился нормально, оптимизированный застрял сам в себе. После отключения openmp оба варианта выполнились, но дали разные результаты. Тестировалось в gcc 4.4.3 и ~4.5.0.
#include <stdio.h>
int main() {
int n,i;
n = 33;
for (i = 0; i < n; i+=4) {
printf("%i %i %i %i\n", i,i+1,i+2,i+3);
}
return 0;
}
Выдаст не ожидаемый результат (он будет считать до 35), хотя я может не прав и в случае с array результат будет нульданные в C
int main() {
int n,i;
n = 33;
for (i = 0; i < n; i+=4) {
printf("%i %i %i %i\n", i,i+1,i+2,i+3);
}
return 0;
}
Выдаст не ожидаемый результат (он будет считать до 35), хотя я может не прав и в случае с array результат будет нульданные в C
чего-то я не понял, и почему результат неожидаемый? все верно… до i=32 (последний шаг), и выведет оно 32, 33 (32+1), 34 (32+2), 35 (32+3)
хм, ну никто и не будет разворачивать цикл с нечетным количеством итераций по 4. упомянутый мною подводный камень с кратностью. берут потом остаток от деления и досчитывают…
хм, да возможно так лучше будет работать.
будет ли подобное работать при чтение файла, например?
будет ли подобное работать при чтение файла, например?
я чет недопоняла. что должно работать? уменьшается количество обращений к модулю branch prediction — по факту уменьшения итераций в цикле.
Если не использовать системных вызовов (вход в который дороже ошибки предсказания в разы), и работать либо с хорошо буферизованным файлом либо с mmaped файлом, то будет работать.
При раскрутке циклов повышаются шансы, что компилятор что-нибудь более умное сгенерирует, например, векторизует, или префетч догадается поставить.
branch prediction от раскрутки выигрывает мало, т.к. предсказание переходов просто обязано правильно предсказывать циклы. Неверных предсказаний на каждый заход в цикл будет от 0 (ибо переходы назад — предсказываются как происходящие) до 2-3 (после нескольких итераций предсказатель увидит, что ошибался и поверит в этот цикл). Ну еще +1 ошибка на выход из цикла. )
Что еще выигрывает от раскрутки — логика цикла (проверка пора ли выходить) срабатывает реже (не на каждую итерацию, а на итерации/ степень раскрутки)
Ссылки:
en.wikipedia.org/wiki/Loop_unwinding (общее + ссылки)
software.intel.com/sites/products/documentation/studio/composer/en-us/2009/compiler_c/optaps/common/optaps_hlo_unrl.htm (что говорит документация от компилятора Интел о полезности unroll)
software.intel.com/sites/products/documentation/studio/composer/en-us/2009/compiler_c/optaps/common/optaps_perf_optstrats.htm (общее из той же документации про циклы и их оптимизацию)
При раскрутке циклов повышаются шансы, что компилятор что-нибудь более умное сгенерирует, например, векторизует, или префетч догадается поставить.
branch prediction от раскрутки выигрывает мало, т.к. предсказание переходов просто обязано правильно предсказывать циклы. Неверных предсказаний на каждый заход в цикл будет от 0 (ибо переходы назад — предсказываются как происходящие) до 2-3 (после нескольких итераций предсказатель увидит, что ошибался и поверит в этот цикл). Ну еще +1 ошибка на выход из цикла. )
Что еще выигрывает от раскрутки — логика цикла (проверка пора ли выходить) срабатывает реже (не на каждую итерацию, а на итерации/ степень раскрутки)
Ссылки:
en.wikipedia.org/wiki/Loop_unwinding (общее + ссылки)
software.intel.com/sites/products/documentation/studio/composer/en-us/2009/compiler_c/optaps/common/optaps_hlo_unrl.htm (что говорит документация от компилятора Интел о полезности unroll)
software.intel.com/sites/products/documentation/studio/composer/en-us/2009/compiler_c/optaps/common/optaps_perf_optstrats.htm (общее из той же документации про циклы и их оптимизацию)
насколько я помню, это вообще был итоговый конкурс, после зимней школы оптимизации. дали такой странный код, со словами: у вас есть 20 минут на его оптимизацию, юзайте всякие профайлеры и все что хотите. суть в том была, чтобы не сами алгоритмы оптимизировани на высоком уровне, а пользуюясь сторонними утилитами находить узкие места программы и переписывать их нормальным образом. насколько я помню, 80% кода вообще ничего не делала (что-то типа гоняла данные туда-сюда), достаточно было этот факт подменить, выкинуть эту часть и все — победа в кармане :) но за 20 минут реально сложновато в этом сраче разобраться.
они из неоптимизированной версии. да пожалуйста, тут
По поводу еще более серьезной оптимизации ветвлений и прочего есть вводная статья от IBM: http://www.ibm.com/developerworks/linux/library/l-gcc-hacks/
Там правда с упором на GCC, ядро и промышленность, но тем больше доверия заслуживают методы
Там правда с упором на GCC, ядро и промышленность, но тем больше доверия заслуживают методы
Ну и серьезные дяди (и тети?) еще проводят в конце итеративный адаптивный тюнинг a-la acovea
пасиба, почитаем
все очень интересно,
книгу Криса Касперски держал в руках, но так и не купил
куплюобязательно
еще раз спасибо за содержательную историю
книгу Криса Касперски держал в руках, но так и не купил
куплюобязательно
еще раз спасибо за содержательную историю
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Про техники оптимизации