Преждевременная оптимизация - корень всех благ

919 views
Skip to first unread message

Dmitry Chestnykh

unread,
Jul 30, 2008, 11:34:30 AM7/30/08
to sellm...@googlegroups.com
Disclaimer: В этом тексте содержатся
бесплатные советы. Если они вам
испортят жизнь, требуйте возврата
денег.

* * *

Один из самых популярных постулатов
программирования --
"Преждевременная оптимизация -- корень
всех бед (зол)". Этот постулат
-- _огромное зло_.

Зло
~~~

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

Вспомните, сколько раз вы возвращались
к уже написанному коду, чтобы
оптимизировать какую-то функцию? Я
сомневаюсь, что часто.

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

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

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

Вот как википедия объясняет фразу про
предварительную оптимизацию:

"Premature optimization" is a phrase used to describe a situation
where a programmer lets performance considerations affect the design
of a piece of code. This can result in a design that is not as clean
as it could have been or code that is incorrect, because the code is
complicated by the optimization and the programmer is distracted by
optimizing.

Естественно, оптимизация должна быть
разумной. Но performance
considerations должны affect the design of a piece of code!
Иначе мы
получаем Windows Vista :-) И как раз наоборот,
"преждевременная"
оптимизация приводит к тому, что мы
перерабатываем код, который только
что написали, что чаще всего приводит к
улучшению его читабельности
(если конечно, вы не решите все
переписать на ассемблере).

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

Насчет "distracted by optimizing" -- это бывает
правдой. Но опять же,
такой программист -- дурак.


Разумная оптимизация
~~~~~~~~~~~~~~~~~~~~

До написания: продумать алгоритм и все
с ним связанное (формат файлов,
возможности ОС/языка программирования/
фреймворка).


После написания:

[ написали функцию ]
|
v
[ можно написать по-другому? ] <----------------
+---+
| | | |
v v | |
[ да ] [ нет ] ---> [ подумать еще ] --+ |
| |
v |
[ замерили нужные
параметры* ] |
| |
v |
[ переписали функцию ] |
| |
v |
[ лучше?** ] |
| |
v |
[ да / нет ] ------- (пока не надоест) ---------------
+


* чаще всего оптимизируют
производительность, поэтому замеряют
время

** соответствует поставленной цели?
например, быстрее / чище код / меньше
памяти



* * *


Например, в моей программе нужно к
каждому файлу писать дополнительную
информацию. В Mac OS X это можно сделать
двумя основными путями:

1. Добавить еще один "поток" файла. Так
делает TextMate, когда вы
открываете файл: он добавляет поток с
информацией о положении каретки
в этом файле, чтобы когда вы откроете
его в следующий раз, вы
оказались в том же месте файла.

2. Рядом с файлом (или в другом месте)
положить еще один файл
(скрытый, если угодно) с информацией.

Недостаток первого метода в том, что он
работает только с HFS+
разделами. Мне это не подходит -- нужно
работать с разделами в других
форматах.

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

Далее -- как записывать информацию в
этот файл? В Cocoa это можно
сделать очень легко -- так как вся
информация внутри хранится в
NSDictionary, можно его сериализовать в Property
List.

Plist бывает трех форматов:

* XML:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN"
"http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
<key>md5</key>
<string>0b2dcb6b9cba556e6dacab5836d180ec</string>
<key>compressed</key>
<true/>
</dict>
</plist>

* Binary (пример приводить не буду).

* NeXT (old-style ASCII):

{
md5 = 0b2dcb6b9cba556e6dacab5836d180ec;
compressed = 1;
}

Бинарный трогать не будем, потому что
он не универсален и я люблю
просто текст. XML-формат PList'ов --
классная вещь по удобству
использования из Cocoa, но сам по себе --
дебильный формат (вроде как
и XML, но и не XML, потому что использует
вид key-value, вместо
использования возможностей XML). Кроме
того, если файлов 10000
(нормальный случай для моей программы),
то мы получим 10000 таких XML
Plist'ов с мусором в виде заголовка, DTD и
прочих довесков XML (хотя,
конечно, минимальный размер файла в HFS+
-- 4 Кб, поэтому все меньше 4
Кб неважно). Да и вообще, XML не люблю :)

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

NSDictionary может содержать любые объекты,
соответствующие протоколу
NSCoding. Мне нужна только поддержка NSString и
NSNumber, и не нужны
вложенные словари. Значит, формат
можно сделать таким:

md5=0b2dcb6b9cba556e6dacab5836d180ec
compressed=1

Практически .ini, только без групп. 10000
файлов. Можно сделать
сериализацию/чтение таких файлов
быстрее, чем NSDictionary сериализует
XML plist'ы, потому что нам не нужен XML
парсер.

Создаем отдельный проект для этого
класса сериализации (вместо
него можно сделать категорию в NSDictionary,
но я остановился на
классе). Пишем код, обрамляем его в
Microtime()'ы и сравниваем
скорость с NSDictionary
writeToFile/dictionaryWithContentsOfFile. Отстой.
Действуем по
алгоритму, описанному выше.
Переписываем с си-строками вместо
NSString. Более-менее подойдет. Пробуем
различные варианты
fopen/mmap. Неа, оказывается быстрее
прочитать NSData, потом оттуда
getBytes и работать с полученным буфером.
Ура, мы быстрее NSDictionary
dictionaryWithContentsOfFile. А самое главное, пока
мы все
перерабатывали, код стал лучше:
читабельнее и компактнее!

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


Опыт
~~~~

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

Бред. Предполагается, что у
программиста отсутствует память, что
ли?
Естественно, если раньше какой-то
алгоритм работа быстрее, это не
значит, что в следующих 100% случаев он
будет быстрее. Но это не
значит, что все нужно замерять -- в
большинстве ситуаций можно
положиться на свой опыт (если он
основан на замерах
производительности или знании, что
делает ОС/фреймворк).


Та-дам!
~~~~~~~

А теперь, как на самом деле звучала
фраза про преждевременную
оптимизацию:

"We should forget about small efficiencies, say about 97% of the
time: premature optimization is the root of all evil."
-- Sir Tony Hoare

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

What Hoare and Knuth are really saying is that software engineers
should worry about other issues (such as good algorithm design and
good implementations of those algorithms) before they worry about
micro-optimizations such as how many CPU cycles a particular
statement consumes.
(из первой статьи в списке ниже)


Ну все, хватит пока. Оптимизируйте!


К прочтению:

* The Fallacy of Premature Optimization (обязательно!)
http://www.acm.org/ubiquity/views/v7i24_fallacy.html

* "Premature Optimization Is The Root Of All Evil" Is The Root Of Some
Evil
http://weblogs.mozillazine.org/roc/archives/2005/11/immature_optimization.html

* Weird things about git, #1: premature optimization
http://alumnit.ca/~apenwarr/log/?m=200806#24

- Дмитрий Честных.

Dmitry Chestnykh

unread,
Jul 30, 2008, 11:39:11 AM7/30/08
to sellme-dev
Гадский google groups испортил форматирование. Попробую снова.
=======================================================

muxx

unread,
Jul 30, 2008, 1:27:03 PM7/30/08
to sellme-dev
Я, когда слышал эту фразу про зло оптимизации, всегда понимал ее, как
зло оптимизации кода, но никак не зло проектирования программы, данный
этап, в этом я с вами согласен, один из самых важных.

Dmitry Chestnykh

unread,
Jul 30, 2008, 1:29:46 PM7/30/08
to sellm...@googlegroups.com
В оптимизации кода тоже нет зла :)

— Дмитрий Честных.

Anton

unread,
Jul 30, 2008, 2:02:27 PM7/30/08
to sellme-dev
Зло -- понятие растяжимое :)
Ваши рассуждения не учитывают того, что в сутках 24 часа, у проекта
есть жизненный цикл, а у программиста -- цели в жизни кроме написания
офигенно быстрого кода. Жизнь состоит из компромиссов.
Кстати, не стоит называть людей дураками только за то, что у них в
результате оптимизации получается трудночитаемый код. Это очень
некрасиво и совершенно не добавляет вашим словам убедительности.
> -- Дмитрий Честных.

Dmitry Chestnykh

unread,
Jul 30, 2008, 3:51:19 PM7/30/08
to sellm...@googlegroups.com
> Ваши рассуждения не учитывают того, что в сутках 24 часа, у проекта
> есть жизненный цикл, а у программиста -- цели в жизни кроме написания
> офигенно быстрого кода. Жизнь состоит из компромиссов.

Конечно. Поэтому на софтверном рынке куча хлама.

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

Это их проблемы, а мне убедительность не нужна :)

- Дмитрий Честных.

Dmitry Chestnykh

unread,
Jul 30, 2008, 4:02:22 PM7/30/08
to sellme-dev
> > офигенно быстрого кода. Жизнь состоит из компромиссов.
>
> Конечно. Поэтому на софтверном рынке куча хлама.

Надо добавить, что я полностью согласен насчет "компромиссов".
Просто часто не те вещи забирают время программиста:

* фичи
* удобство программирования
* высокий уровень абстракции

Эти вещи -- зло. Не абсолютное, естественно, а до какой-то степени.
Реально заслуживающие внимания вещи:

* удобство пользователя (включает и производительность программы)
* удобство изменения/добавления кода

- Дмитрий Честных.
Reply all
Reply to author
Forward
0 new messages