Решил собрать в кучу всякие мысли про оптимизацию. И расписать все это более или менее подробно.
Чтобы разговаривать по возможности предметно в качестве модельной рассмотрим такую задачу.
Допустим, нам надо генерировать черно-белую картинку (более точно массив байт, где 0 - соответствует белому цвету, 255 - черному). Размеры картинки будем предполагать от 5000 до 10 000 пикселей по каждой из осей. Генерация будет заключаться в отрисовке заданного набора черных прямоугольников (от 500 до 1000 штук, с размерами от 100 до 200 пикселей по каждой из осей) на белом фоне. Так же ограничимся случаем, когда стороны прямоугольников параллельны осям.
Задачка достаточно простая, и имеет массу решений. Однако, нам интересно рассмотреть подход к выбору из этих решений оптимального.
В работе по оптимизации программы можно выделить три этапа или три класса оптимизации.
1. Архитектурная оптимизация
2. Алгоритмическая оптимизация
3. Оптимизация кода
На самом деле они, естественно, не независимы. Нельзя определиться с архитектурой, не учитывая алгоритмы и глупо выбирать алгоритмы, не задумываясь о том можно ли их реализовать оптимально в данных условиях.
Архитектурная оптимизация
Чаще всего дает максимальное увеличение скорости. Здесь оптимизация зачастую определяется не только конкретной задачей, но и контекстом, в котором эта задача решается (причем контекстом в первую очередь).
Обратимся к нашей модели. Нам надо понять: как будет использоваться сгенерированная картинка? Например, возможно картинка нужна нам для вывода на экран. Экраны размеров 5 000 на 5 000 маловероятны, и это позволяет нам при запросе создать только часть картинки. Даже, если по запросу вместо 25 000 000 = 5 000 * 5 000 пикселей, мы будем генерировать 1 920 * 1 080 = 2 073 600 пикселей (т.е. в 12 раз меньше), это даст существенный прирост в скорости генерации (надо понимать, что в зависимости от выбора алгоритма прирост может быть и не 12 кратный, а при особом упорстве можно добиться даже уменьшения скорости, нет вершин, которые бы не взял человеческий идиотизм).
Еще одну возможность, которую следует рассмотреть на данном этапе это использование для генерации картинки нескольких потоков. Особенно актуально это стало в последнее время с появлением все большего числа многоядерных процессоров. Решать этот вопрос надо в тесной связи с тем, какие алгоритмы мы будем использовать. Еще раз следует уточнить, что разные этапы оптимизации тесно взаимосвязаны.
Вопросов о том, как будет использоваться наше решение, можно задать очень много и чем больше мы зададим их на данном этапе, тем меньше вероятность, что нам в дальнейшем придется переделывать все с нуля.
Дабы не быть голословным рассмотрим еще несколько уточнений, которые могут существенно повлиять на выбор варианта решения.
Генерируется ли картинка разово (т.е. приняли набор прямоугольников, сгенерировали картинку, сбросили ее куда-нибудь на диск и забыли) или это итеративный процесс (запросили одно окно из картинки, потом слегка сдвинули окно - запросили, и т.д.). Если итеративный, могут ли данные меняться между запросами? Если данные могут меняться, то каким образом? Прямоугольники только добавляются или и удаляются тоже.
Ответы на эти вопросы позволяют понять, есть ли смыл кэшировать промежуточные результаты, в какой момент отрисовывать прямоугольник (при его добавлении или на этапе генерации картинки) и т.п.
Таким образом, архитектурная оптимизация - это самый первый и наиболее важный этап, и именно он определяет начальный уровень скорости, который мы сможем (или не сможем) увеличить в дальнейшем. Т.е. надо понимать, что, конечно, и хорошую архитектуру можно загнать плохими алгоритмами и не оптимальным кодом, но точкой отсчета для скорости всегда будет служить выбранное архитектурное решение.
Алгоритмическая оптимизация
Алгоритмическая оптимизация начинается тогда, когда с архитектурой мы уже определились, и очередь дошла до выбора алгоритмов. Если на предыдущем этапе, мы определяли, как решаемая нами задача вписывается в общую структуру программы, то теперь нам надо разобрать более тонкие моменты.
Вновь вернемся к примеру с закраской прямоугольников. Самый простой алгоритм, который можно предложить для ее решения такой: проходим по всем пикселям картинки, для каждого пикселя проверяем, лежит ли он внутри прямоугольника или нет, и соответственно выставляем в нужный байт 0xFF или 0x00. Алгоритм ужасен, поскольку в худшем случае (например, когда все прямоугольники совпадают и вырождены в точку), необходимо будет для каждого пикселя проверить все прямоугольники и не найти пересечения. Второй вариант, заполнить сначала нулями весь выделенный под изображение массив, а затем, перебирая прямоугольники, закрашивать покрываемые ими пиксели. На самом деле тоже не слишком хороший вариант, например, когда прямоугольников много и они равномерно покрывают изображения, начальное обнуление массива становится длительной и лишней операцией.
И в первом и во втором алгоритме легко разбить работу на несколько потоков. В первом случае, просто разделив картинку на куски, и обрабатывая каждую часть в отдельном потоке. Во втором, первоначальное заполнение массива нулями разбивать будет, вряд ли целесообразно, а вот массив прямоугольников вполне возможно обрабатывать в разных потоках. И здесь, вполне вероятно, что первый алгоритм, сможет оказаться быстрее второго, просто за счет того, что исходное зануление массива будет общей частью для всех потоков.
Можно сделать вывод, что на данном этапе оптимизации важно определить, нет ли каких-либо особенностей у исходных данных задачи и, если таковые будут обнаружены, соответствующим образом настроить алгоритмы.
Оптимизация кода
Практически к этому этапу решение задачи уже в некотором виде реализовано, а желательно еще и отлажено. На самом деле, прежде чем браться за оптимизацию кода, совсем не плохо иметь модельный вариант реализации, с которым в дальнейшем можно будет сравнивать результаты на разных входных данные. Дело в том, что если до этого момента вполне реально делать все «красиво», т.е. иметь стройный код и хорошую структуру, то оптимизация кода обычно приводит к ухудшению его читабельности и понимаемости. Поэтому наличие рабочей (пусть и медленной версии) сильно облегчает жизнь.
На этом этапе кроме головы и компилятора, понадобятся еще и специфические инструменты - так называемые «профилировщики». Программ таких не сказать, что много, но их есть. Я пользуюсь CodeAnalyst-ом от AMD, он достаточно простой в работе, вполне устраивает меня по функциональности (хотя и имеет корявый интерфейс), а самое главное бесплатен, в отличие от схожей утилиты от Intel, стоящей что-то около 600 долларов (честно говоря, с Intel-овской утилитой не разбирался вполне допускаю, что там и возможностей побогаче и интерфейс поудобнее).
Можно, конечно, делать все на глазок, но это не оптимально. Профилировщик позволяет быстро выделить куски, с максимальным вкладом в время работы программы, и начинать оптимизацию с них.
Именно на данном этапе некоторые из частей кода, возможно, необходимо будет переписать на ассемблере, а некоторые и оптимизировать, используя SIMD инструкции. Однако, здесь важно не переусердствовать, ибо современные компиляторы с оптимизацией кода справляются вполне успешно, и стоит соблюдать баланс между «читабельностью» (которой код на ассемблере обладает в минимальной степени) и скоростью работы.
На этом пока все. В данном случае отзывы и замечания по статье приветствуются.
Комментариев нет:
Отправить комментарий