elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Преждевременная оптимизация - корень всех бед
elizarov

Дональд Кнут запустил в программистский мир крылатое выражение: преждевременная оптимизация - корень всех бед. Однако, дьявол кроется в деталях. Попробуем разобраться в каком смысле здесь нужно понимать слова преждевременная и оптимизация, чтобы понять откуда берутся все беды.

Оптимизация программной системы это увеличение её производительности (скорости реакции, пропускной способности и т.п.) и/или уменьшение потребления ресурсов (процессорного времени, памяти и т.п.). Та оптимизация, которая приводит к бедам, всегда подразумевает какой-нибудь компромисс. Компромисс может быть между разными аспектами производительности или потребления ресурсов, а также между ними и такими аспектами качества кода, как простота поддержки. Например, увеличивая скорость реакции системы мы потребляем больше процессорного времени, увеличивая пропускную способность мы уменьшаем скорость реакции, уменьшая потребление памяти мы усложняем код и т.п.

Одну и ту же задачу стоящую перед программистом можно всегда решить разными способами. Например, в языке Java можно проверить наличие в строке символа с помощью регулярного выражения и метода String.matches:

boolean hasAt = s.matches(".*@.*"); // (1)

а можно для этого воспользоваться методом String.contains:

boolean hasAt = s.contains("@"); // (2)

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

Ошибочно считать злой оптимизацией такое изменение кода, которое делает его лучше во всех возможных отношениях. Программист, который изменяет код ищущий символ в строке с помощью String.matches на метод String.contains, не оптимизирует его, а просто исправляет недочет в исходном коде, улучшает его. Умение писать совершенный код это то, что отличает опытного программиста от новичка. Потенциально огромное число способов решения той или иной задачи делает создание совершенного кода очень сложной задачей. Это одна из причин почему библиотеки кода с большим числом возможностей требуют много времени, чтобы их освоить в совершенстве. Ведь это требует знания всех её возможностей и умения найти тот самый код, который оптимально решает поставленную задачу.

А что если мы будем проверять наличие символа с помощью метода String.indexOf?

boolean hasAt = s.indexOf('@') >= 0; // (3)

Этот метод еще быстрей, чем второй, но намерение программиста становится менее очевидно. Это уже компромисс между производительностью и простотой кода. Простота кода тесно переплетена с аспектами стиля. Если в проекте производительность и скорость работы стоят как ключевые задачи, то использование 3-го способа при написании кода может быть приемлемо, в то время как для проекта где такие задачи не стоят, может быть и нет. При написании кода очень важен контекст, в котором решается задача. С ростом объема кода в проекте, похожие задачи возникают в разных местах. В совершенном коде, похожие задачи решаются похожим образом, приобретая форму шаблонов, которые опытные программисты узнают с одного взгляда и/или путем создания дополнительных вспомогательных библиотек.

Продолжая пример выше, замена поиска символа с помощью String.contains на вручную написанный цикл проверки символа за символом это уже чистой воды злая оптимизация. Здесь в жертву приносится простота и понятность кода, с целью получения потенциального выигрыша в производительности. Будет ли этот более сложный код написан без ошибок? Материализуется ли какой-либо заметный прирост производительности (в этом примере - нет)? Это ключевые вопросы, на которые приходится отвечать при оптимизации кода. Отрицательный ответ на любой из них это риск, который несет с собой любая оптимизация.

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

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

В Devexperts мы практически постоянно заняты написанием высокопроизводительных систем и/или систем обрабатывающих большие объемы данных из-за специфики специализации на торговле финансовыми инструментами. При написании таких систем, над производительностью системы приходится думать уже на этапе архитектуры и дизайна системы, еще до того, как написана хоть одна строчка кода. Ведь архитектуру и дизайн системы очень сложно изменить, если в процессе эксплуатации выявятся недостатки, которые нельзя устранить оптимизацией кода в рамках заложенной в систему архитектуры. Как тут избежать рисков преждевременной оптимизации?

Полностью аналогично оптимизации кода -- оптимизация архитектуры будет преждевременной, если она сделана без наличия данных. Для создания совершенной архитектуры нужно знать планируемые объемы обрабатываемых данных, ожидаемую нагрузку и т.п. Это позволит сравнить различные потенциальные способы организации системы с точки зрения ожидаемого количества взаимодействий между модулями, потребления ресурсов сети, памяти, процессора и т.п. и выбрать оптимальную архитектура для решаемой задачи. Часто это требует написание прототипов кода, чтобы проверить те или иные предположения, сделанные на этапе архитектуры и дизайна системы. Например, при создании системы высокопроизводительной системы передачи сообщений QDS, которая сейчас является ядром продукта dxFeed, необходимо было на этапе дизайна решить каким образом представлять данные о сообщениях, ибо это решение повлияет на все внутренние и внешние API. Ведь высокопроизводительная система не может себе позволить преобразовывать данные из некоего внутреннего формата в формат внешнего API, если вся суть системы заключается в быстрой передаче данных между модулями и именно эта операция является узким местом всей системы в целом.

UPDATE: О других аспектах программисткой деятельности написано в заметке "О программистах и компромиссах программирования".


  • 1
От себя бы добавил, что на этапе разработки понятие оптимизации кода должно отсутствовать напрочь. Оптимизируйте архитектуру, алгоритм, и т.д. Только код пишите ПРОСТОЙ, а не "оптимальный". С хорошей вероятностью компилятор оптимизирует простой код гораздо лучше, чем вы напишите "оптимальный".

Вот когда продукт уже написан, встала задача увеличения производительности, самое время проводить исследования, запускать профилировщики, искать узкие места и смотреть, что в них можно улучшить. Но не раньше.

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

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

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

Например, шаблон "быстрый путь" (fast path) - типичный способ увеличения производительности путем усложнения кода. Я планирую поделиться в своем блоге и другими, менее известными приемами, которые мне приходилось использовать.

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

Более сложный код совсем не обязательно происходит из более совершенного алгоритма (бывает что более совершенный алгоритм одновременно проще по коду). Тот же "быстрый путь" -- где тут более совершенный алгоритм? Это вообще шаблон анти-шаблон -- мы берем и дублируем кусок логики кода. То есть алгоритм тот же самый, кода большие, мест для ошибки больше. Всё делается только ради производительности. И работает одинаково хоть со статической компиляцией, хоть с динамической, хоть вообще с интерпретацией.

Про твою практику прокомментировать не могу. Можешь привести пример?


Edited at 2011-10-25 02:06 pm (UTC)

Большинство моих примеров, к сожалению, под NDA :)
Но поверь, за 7 лет работы над оптимизациями в компиляторе, я на многое насмотрелся :)

Ну тогда придумай пример, чтобы было понятно о чем идет речь. Надеюсь, опыт полученный тобой в процессе работы, не находится под NDA?

Да что-то все, что в голову лезет, как-то сразу наводит на мысли об NDA :) Уж очень конкретные примеры :)

Ну вот сталкивался я с фортрановским кодом, явно писали математики, которым когда-то сказали, что бранчи - это плохо. Они справились вместо

if (?)
a = b;
else
a = c;

написать что-то типа

a = x*b + y*c

так чтоб х и y были 0 и 1 в засимости от условия. Эффект понятен - b и c были довольно немаленькими выражениями.

Еще одни умельцы справились завести массив из 256 байт равный abs((signed char)index). Видимо, вызовы в abs() экономили. Тоже, наверное, где-то что-то слышали про оптимизации...

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

Спасибо за примеры! Стало намного понятней, почему у тебя эта тема наболела. К счастью, мне с такой "клиникой" сталкиваться практически не приходилось.

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

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

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

Одноклассница пару лет назад описывала, как у них на работе какой-то чувак догадался сильно ускорить вычисления, сделав руками loop interchange. Ну, нехорошо они в память ходили по многомерным массивам. Сделал лучше. Помогло. Молодец? Ну, молодец конечно. Вот только если б код был нормально написан и-или компилятору хотя бы "-О" сказали, он бы и разницы не заметил :)

"и-или" к тому, что я их код и флаги компиляции не видел, может что-то одно из этого и присутствовало ;)

Не могу сказать, что знаю всё, но много, и программирую достаточно давно. Так вот, я не знаю примера системы где твой первый пример был бы оптимизацией (то есть убыстрял бы код).

А вот в узком месте твоего проекта на фазе оптимизации кода приходится и не такие вещи, как loop interchange делать. Понятно, что о чем-то мог бы и компилятор догадаться (а что делать, если у тебя рабочий проект и есть такой компилятор, который есть). Но есть и такие оптимизации, о которых никакой компилятор в принципе догадаться не может (может поделюсь как-нибудь особо интересными вещами такого рода).

Заменить тебе алгоритм компилятор никогда в жизни не догадается. Даже не потому что тупой, а просто не его это дело :)

А вот о каком-нибудь interchange можно и не думать, если все в порядке с кодом. Проверь сам. Напиши что-нибудь типа

for (i...)
for (j...)
a[i,j]=b[i,j]*c[i,j];

Потом поменяй местами индексы, и сравни производительность с разными флагами компиляции. Уверяю, что даже с простейшим "-О" ты уже разницу не увидишь. Дальше можешь попробовать поусложнять код, вводя какие-нибудь фишки во внешний цикл, и ты увидишь, как на какой-то стадии компилятор сломается и уже сам развернуть циклы не сможет.
Принеси все три массива указателями через параметры функции, вызывай ее откуда-нибудь извне, и ты получишь все счастье, какое можно из-за боязни алиасинга. :)

Ты опять переходишь к конкретике. Конечно, если твой компилятор умеет loop interchange делать, то ручками это можно не делать (хотя я и вреда не вижу -- код сложней не становится).

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

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


"Какая разница компилируемый язык или нет?"

Есть большая разница, работает ли динамический оптимизатор типа жабо-хотспота, или статический. Для последнего очень важно, чтобы исходник был простой и давал как можно больше степеней свободы.

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

  • 1
?

Log in

No account? Create an account