Перевод с англ.: (C)
Dale, 14.12.2010 — 17.12.2010.
Переведено с любезного разрешения
автора.
Оригинал статьи:
Optimization: Your Worst Enemy (
Translated by permission).
Ссылку на эту статью я обнаружил в книге: James W. Grenning.
Test Driven Development for Embedded C. Поскольку рекомендациями таких людей, как Джеймс Греннинг, пренебрегать не следует, я отложил на время книгу и последовал по ссылке; а дочитав статью до конца, понял, что она должна быть интересна многим.
Оптимальность — очень ценная характеристика вообще и для программного обеспечения в частности. Когда мы говорим, что программа написана оптимально, мы обычно подразумеваем, что она не содержит ничего явно лишнего и рационально расходует ресурсы компьютера. Очень многие стремятся оптимизировать свои программы. Но многие ли действительно знают, как достигается оптимальность?
Прогресс в области вычислительной техники (отдельное спасибо
Гордону Муру за его столь любимый нами
закон) привел к тому, что напряженность борьбы за оптимальность ПО существенно снизилась в последнее время. Мощность современных персональных компьютеров настолько выросла, что мы может позволить себе транжирить некогда столь драгоценные гигагерцы и гигабайты на фантастические анимированные меню, реалистично выглядящие кнопки с тенями и прочие
элементы дружественного интерфейса. Немногочисленные уцелевшие староверы гнут свою линию, что программирование на языках высокого уровня, особенно объектно-ориентированных — зло и сила в ассемблере, что использование разных оболочек (особенно .NET) — для убогих и выбор гуру — программирование на API, и т.д. Однако когда доходит до дела, обычно оказывается, что результат их воистину титанических усилий настолько незначителен, что не они сегодня определяют погоду на рынке ПО. Побеждают те, кто первым реагирует на потребность пользователя, а лишние мегабайты — кто их считает, когда гигабайтная планка памяти стоит чуть больше десяти долларов?
Однако закон Мура не всесилен. В цифровой вселенной есть еще уголки, куда его свет не проникает. И сегодня в ходу 8-разрядные микроконтроллеры, на борту у которых припасено порой несколько килобайт флеш-памяти для хранения программ и несколько десятков байт оперативной памяти для данных. Причем они вовсе не спешат сдавать позиции, поскольку благодаря дешевизне, компактности и низкому потреблению при неплохой производительности прочно обосновались в своих нишах, куда закрыт вход их неуклюжим и прожорливым старшим собратьям. В этом мире правят свои законы, и оптимальность становится главной добродетелью — для излишеств там попросту нет места.
Впрочем, и здесь очень многие понимают оптимальность встроенного ПО довольно своеобразно. Отчасти это своеобразие объясняется бедностью инструментальных средств для разработки встроенных систем, отчасти тем, что многие разработчики систем на основе микроконтроллеров владеют паяльником гораздо увереннее, чем языками программирования, и не имеют професиональных навыков в области программной инженерии. Как известно, природа не терпит пустоты — там, где нет знаний, их заменяют предрассудки, а там, где нет уверенности, ее успешно заменяет упертость. Один из наиболее живучих предрасудков — встроенное ПО следует разрабатывать только на ассемблере; код, написанный на языках высокого уровня (в частности, на C) заведомо ущербен и неоптимален. При этом, чем меньше навыков программирования, тем крепче упертость сторонника мифа. (Есть, конечно, и другие суеверия, но они лежат за рамками данной статьи).
Итак, представляю перевод замечательной статьи, написанной человеком с огромным многолетним опытом. Он прекрасно знает предмет, о котором говорит.
Этот кричащий заголовок просто обязан привлечь ваше внимание, ибо речь пойдет о серьезных вещах.
Для начала несколько слов обо мне. Моя диссертация была одной из первых, посвященных автоматическому созданию оптимизирующих компиляторов по формальному описанию машины («Machine-Independent Generation of Optimal Local Code», CMU Computer Science Department, 1975). После защиты я провел три года в стенах CMU в качестве старшего исследователя на многопроцессорной вычислительной системе C.mmp, которая работала под управлением нашей доморощенной операционной системы Hydra, мощной и надежной. Затем я вновь вернулся к исследованиям компиляторов в рамках проекта PQCC (Production Quality Compiler-Compiler), непосредственным результатом которого стало образование Tartan Laboratories (впоследствии — просто фирма Tartan, ныне поглощенная Texas Instruments), компании по разработке компиляторов, в которой я работал в составе группы инструментальных средств. Я посвятил полтора десятка лет написанию и использованию инструментария для измерения производительности.
Это эссе в нескольких частях в основном отражает мою собственную точку зрения. Истории, рассказанные мной, не являются вымышленными. Все имена подлинные, за исключением пары имен, о которых лучше было бы вовсе не вспоминать.
Достаточно квалифицированный программист не станет писать чересчур неэффективную программу. Во всяком случае, намеренно. Оптимизация — это то, чем вы занимаетесь, когда производительность оказывается недостаточной. Иногда оптимизировать легко, иногда — трудно. Иногда оптимизация прекрасно вписывается в вашу первоначальную разработку, а иногда требует полностью разрушить вашу прекрасную абстрактную систему классов. Но всегда, я повторяю: всегда на практике оказывалось, что ни один программист не был способен предсказать или проанализировать, где окажется узкое место в части производительности, не располагая реальными данными. Совершенно неважно, какие предположения вы строите по поводу утечки времени: в конце концов вы с изумлением обнаружите, что истинная причина кроется совсем в другом месте.
Вы занимаетесь оптимизацией потому, что у вас возникли проблемы с производительностью. Иногда это вычислительная оптимизация: ваши манипуляции с битовыми картами оказались чересчур медленными. Иногда это оптимизация доступа к данным: слишком много времени уходит на ввод данных в машину. Порой это алгоритмическая оптимизация: вы что-то делаете неверно. Если вы не понимаете разницы между сортировкой n2 и сортировкой n*log(n), скорее всего, у вас уже сейчас большие проблемы; впрочем, само по себе это знание не столь полезно.
Несколько лет назад я работал над сложной программой, которая должна была выполнять семантическую перекрестную проверку между «инструкциями» программы и «объявлениями» (в действительности это была система сравнения ограничений 4GL, но эти детали сейчас не столь важны). Я обнаружил, что операция имела сложность n3 (строго говоря, m*n2, но m и n чаще всего оказывались одного порядка величины). Далее возможны три подхода:
- Наивный подход. Вы даже не подозреваете, что у вас возникла проблема n3. Скорее всего, у вас большие неприятности, поскольку, если даже это и есть узкое место, вы ничего об этом не знаете.
- Формальный академический подход. Вы осознали, что у вас проблема n3; кроме того, вы знаете, что это — вселенское зло, и переписываете алгоритм.
- Инженерный подход. Вы осознали, что у вас проблема n3; вы применяете инструменты для того, чтобы оценить ее действительное влияние на систему.
Единственно практичный подход к оптимизации — инженерный. Я измерил производительность, и на самом большом «реальном» примере из тех, что я располагал, выяснилось, что n почти всегда равно 1, иногда 2, изредка 3 и в единственном случае 4. Этого слишком мало, чтобы оказывать реальное влияние на производительность. Действительно, алгоритм имел сложность n3, но n было настолько мало, что не было необходимости в переписывании кода. Переписать код было бы весьма сложно, задержало бы проект в целом на пару недель, а также пришлось бы добавить по паре указателей в каждый узел дерева в и без того уже тесном адресном пространстве миникомпьютера.
Я также написал диспетчер-распределитель памяти, которым все пользовались. Я потратил массу времени на вылизывание его производительности, сделав самым быстрым диспетчером в своем классе. Эта эпопея подробно описана в книге «IDL: The Language and its Implementation» (Nestor, Newcomer, Gianinni and Stone, Prentice-Hall, 1990), которая, к сожалению, давно распродана. Одна из групп, использовавших его, пользовалась инструментом измерения производительности PC sampling под Unix. Этот инструмент периодически делает выборки содержимого программного счетчика (PC) для определения, какая часть программы выполняется, и после продолжительного выполнения строит «гистограмму плотности» для выявления мест, где программа проводит большую часть времени. Она ясно указала, что изрядная часть времени было проведена в диспетчере памяти. Это ни о чем мне не говорило, но все показывали пальцем в мою сторону.
Я включил в диспетчер маленький хук, который подсчитывал число его вызовов. Оказалось, что он был вызван более 4,000,000 раз. Ни один вызов не длился дольше минимально измеримого интервала в 10µs (примерно 10 инструкций на нашей машине в 1 MIPS), но все же 40,000,000 микросекунд — это 40 секунд. На самом деле еще больше, поскольку было еще 4,000,000 операций освобождения памяти, которые были даже быстрее, но все же суммарное время составило более 50% от общего времени выполнения.
Почему так случилось? Потому что незаметная для программистов критическая функция, которую мы вызывали во внутреннем цикле нескольких алгоритмов, выделяла рабочий буфер размером от 5 до 10 байт, делала свое дело и освобождала его. После того, как мы заменили его локальным стеком на 10 байт, время, проведенное в диспетчере памяти, упало примерно до 3% от общего времени выполнения программы.
Без этих данных мы не узнали бы, почему на диспетчер тратится так много времени. Вообще инструменты измерения производительности, основанные на выборках PC, — весьма слабый тип инструментов, и их результаты не внушают мне доверия. Подробнее смотрите мою статью «Profiling for Performance» в
Dr. Dobb's Journal (18,1) January, 1993, pp.80-87.
Классический промах в оптимизации был сделан несколько лет назад одним из крупнейших производителей ПО. У нас была их первая интерактивная система с разделением времени, и это был во многом поучительный опыт. Один из экспериментов поставила группа разработки компилятора FORTRAN. Сегодня каждый разработчик компиляторов знает, что чем больший размер хэш-таблицы вы используете для таблицы символов, тем выше будет производительность поиска в ней. Когда вы пишете многопроходный компилятор на мэйнфрейме, имеющем 32K оперативной памяти, вы приходите к использованию относительно маленькой таблицы символов, но при этом создаете превосходный алгоритм хэширования, уменьшая вероятность коллизии (в отличие от двоичного поиска, имеющего сложность log(n), хорошая хэш-таблица имеет постоянную производительность до некоторой плотности, так что пока вы сохраняете плотность ниже этого порога, вы можете рассчитывать на среднюю стоимость поиска символа от 1 до 2. Совершенная хэш-таблица (которую обычно предварительно вычисляют для константных символов) имеет постоянную производительность примерно между 1.0 и 1.3; если она достигает 1.5, следует переработать хэширование, чтобы ее уменьшить).
И вот эта самая группа разработки компиляторов обнаруживает, что теперь у нее в распоряжении не 32К, не 128К и даже не 512К. Теперь они располагают виртуальным адресным пространством 4GB. Теперь вы можете услышать от них: «Эй, а давайте-ка использовать действительно большую хэш-таблицу!», «Как насчет таблицы в 1 MB?». Так они и сделали. Но при этом у них есть еще и совершенная технология компиляции, разработанная для маленьких и довольно плотных хэш-таблиц. Поэтому в итоге символы оказались довольно однородно распределены между 256 страницами по 4K в пределах этого 1MB, что привело к тому, что каждый доступ к символу вызывал страничный отказ. Компилятор вел себя безобразно. Вернувшись обратно к символьной таблице в 64K, они обнаружили, что хотя этот алгоритм имел «абсолютную» производительность хуже с чисто алгоритмической точки зрения (требуя больше инструкций на поиск символа), он тем не менее работал на порядок быстрее, поскольку не вызывал такого количества страничных отказов. Так что порой третьестепенные факторы имеют важное значение.
Также остерегайтесь
C. Нет, это не скорость света. Когда речь идет о производительности, алгоритмическая производительность для
n выражается функцией
C*f(n). Так, алгоритм
n2 формально описывается как
C*n2; это означает, что производительность определяется как константа, умноженная на квадрат числа элементов. Мы сокращаем это до
O(n2), что означает «порядок
n2», и в повседневной речи зачастую попросту опускаем слово «порядок». Но никогда не забывайте о существовании
C! (Если вы незнакомы с нотацией Ландау, см.
примечание переводчика в конце статьи).
Несколько лет назад я участвовал в проекте, который производил отчет в виде листингов, отсортированных различными способами. При первой попытке (это было еще до C и qsort) я просто реализовал обычную пузырьковую сортировку, алгоритм O(n2). После первоначального тестирования я подал ему на вход реальные данные. Через десять минут после того, как на консоль вывелось сообщение «Starting reports», никаких отчетов так и не появилось. Серия проверок показала, что большая часть времени уходила на подпрограмму сортировки. Что ж, пришлось мне побороть свою лень. Я выудил свой проверенный алгоритм сортировки heapsort (n*log(n)) и потратил час на его модификацию под свое приложение (не забывайте, я уже говорил, что qsort в то время еще не существовал). Решив проблему, я запустил программу снова. Через семь минут после входа в фазу построения отчета никакой результат так и не появился.
Проверка выявила нечто интересное: большая часть времени затрачивалась на сравнение строк (аналог strcmp). Решив проблему O, я получил неучтенную проблему C. Тогда я сделал некое подобие составной таблицы символов, содержащей все имена, и назначил каждой структуре символов целое число. Таким образом, когда мне нужно было сортировать подструктуру, я делал лишь целочисленную сортировку. После уменьшения C на всю фазу сортировки требовалось менее 30 секунд. Второстепенный фактор, но весьма значительный.
Итак, алгоритмическая производительность, в частности производительность подкачки страниц, может иметь значение. К сожалению, у нас не было подходящих инструментов ни для измерения интенсивности страничных отказов, ни для реорганизации кода с целью их уменьшения.
Некоторые инструменты для измерения производительности определяют общее время, затраченное в пользовательском режиме, и игнорируют время выполнения ядра. Это может замаскировать влияние приложения на нагрузку ядра. Например, несколько лет назад мы измеряли производительность одной программы, которая оказалась чрезвычайно низкой. Мы не нашли никаких «горячих точек» в смысле затрат процессорного времени. Однако в один прекрасный момент я взглянул на данные трассировки и обнаружил, что подпрограмма ввода данных вызывалась около миллиона раз; в общем это неудивительно, когда вы читаете мегабайты входных данных, но что-то все же показалось мне странным.
Я пригляделся повнимательнее. При каждом вызове она обращалась к ядру для чтения единственного байта из файла! Я заменил ее на считывание 8K в буфер за одно обращение, и производительность тут же выросла в 30 раз! Извлекаем отсюда урок: время выполнения ядра имеет значение, и время переключения в ядро тоже имеет значение. Не случайно GDI в NT 4.0 больше не является пользовательским процессом, а интегрирован в ядро. Переключения в режим ядра оказывали основное влияние на производительность.
Определить, что именно следует оптимизировать, легко: те части программы, которые потребляют наибольшее время. Однако локальная оптимизация, игнорирующая глобальные проблемы производительности, бессмысленна. Первостепенные факторы (например, общее время, проведенное в диспетчере памяти), могут не давать основной вклад. Измеряйте, измеряйте и еще раз измеряйте.
(На самом деле это лирическое отступление, даже с некоторой долей самовосхваления. Если хотите, можете перейти к следующему разделу. Мое дело предупредить вас).
На заре появления C его диспетчер памяти был одним из наихудших среди существующих. Он работал по принципу «первый попавшийся»; это означало, что диспетчер полз по списку свободных областей в поисках блока не меньше запрошенного, и если находил такой, расщеплял его и возвращал остаток в список свободных областей памяти. Он работал так медленно, как только мог, и фрагментировал память, как только мог. На самом деле все было даже хуже, чем вы могли бы себе представить. В действительности он разгуливал по списку всех блоков памяти, как свободных, так и уже выделенных, и должен был пропускать уже выделенные блоки. Поэтому по мере того как вы получали все больше блоков, его производительность падала, и поскольку постепенно блоки становились слишком малы для использования, они становились лишь бесполезной обузой.
Я работал в CMU по одногодичному исследовательскому контракту. Моя первая реакция по поводу использования среды Unix была такой: я повернулся к одному из коллег и произнес: «Как вы можете так жить?». Программные технологии в 1990-х были совершенно теми же, что и десятилетием раньше, когда я покидал CMU, с тем лишь исключением, что сейчас компилятор не работал (он генерировал некорректный код для простейших конструкций C), отладчик не работал, трассировщик (выдававший лишь списки шестнадцатиричных адресов без символов) был бесполезен, компоновщик не работал, и не было ничего, хотя бы отдаленно напоминающего приличную систему документирования. Помимо этих «незначительных» дефектов, я полагаю, это была прекрасная среда. Поработав некоторое время с Microsoft C, с CodeView и даже в ранних версиях среды Visual C, я привык предъявлять высокие требования к своим инструментам, и Unix (по крайней мере, в те времена) до них недотягивал, причем очень сильно. Я не скрывал свое мнение по этому поводу.
Однажды мы обсуждали один алгоритм, и в нем требовалось выделение некоторого количества памяти. Я был убежден, что это неприемлемо, поскольку выделение памяти — слишком дорогая операция. Я сказал нечто вроде:
- Что ж, разумеется, если вы будете использовать этот бестолковый диспетчер памяти из Unix, обязательно возникнут проблемы по части производительности. Приличный диспетчер памяти решил бы эту проблему.
Один из присутствующих на совещании набросился на меня:
- Мне надоело слушать, как вы критикуете Unix. Что вы вообще можете понимать в диспетчерах памяти?
Я заглянул в свой офис, где хранился экземпляр книги по IDL, принес его и раскрыл на странице с главой «Выделение памяти».
- Видите это?
- Да.
- Как называется глава?
- «Выделение памяти».
Я закрыл книгу и показал обложку.
- Вам знакомо это имя?
- Да, конечно, это же вы.
- Замечательно. Я написал эту главу. Она посвящена написанию высокопроизводительного диспетчера памяти с минимальной фрагментацией. Вы спрашивали, что я понимаю в диспетчерах памяти? Вот, я написал об этом книгу.
Больше на меня никогда не нападали по поводу моей критики Unix.
К слову, выделение памяти в NT реализовано очень похоже на мой алгоритм, описанный в книге по IDL, а он, в свою очередь, базируется на алгоритме quickfit, разработанном Чаком Вайнстоком в его диссертации, защищенной в CMU примерно в 1974 году.
Не занимайтесь бессмысленной заумной оптимизацией. Это относится, например, к тем, кто пытается «оптимизировать» GUI. Зашитые в код константы, распределенный доступ, изощренные алгоритмы... В результате получаем нечто, что сложно разрабатывать, трудно отлаживать и абсолютно невозможно сопровождать.
В данном случае оптимизация не имеет смысла. Подробнее можете прочитать в моем эссе по поводу единственно разумного подхода к управлению диалоговыми элементами. Я кратко передам здесь основную идею.
Почему эффективность не имеет никакого значения, когда вы улучшаете меню или элементы управления? Посмотрим с точки зрения человеческого фактора. Мышь удалена от уха примерно на 2 фута. Звук распространяется со скоростью примерно 1100 футов в секунду. Это значит, что звуку от щелчка кнопки мыши или клавиши клавиатуры требуется около 2 миллисекунд, чтобы достичь уха. Длина нейронов от кончиков пальцев до мозга составляет для взрослого человека около 3 футов. Скорость распространения нервных импульсов составляет примерно 300 футов в секунду, следовательно, ощушение от щелчка мышью или нажатия на клавишу дстигает мозга через 10 миллисекунд. Задержка восприятия добавит еще от 50 до 250 миллисекунд.
А теперь прикинем, сколько инструкций Пентиум может выполнить за 2ms, 10ms, 100ms? За 2ms машина с тактовой частотой 500MHz выполнит 1,000,000 тактов, так что вы можете выполнить массу инструкций за это время. Даже для старенького Пентиума на 120MHz задержка, вызванная накладными расходами на обслуживание элементов управления, не будет заметна.
Это не помешало Microsoft полностью разрушить объектную модель C++, построенную на хэндлерах сообщений; когда вы вызываете CWnd::OnWhatever(...), вместо действительного вызова DefWindowProc с переданными вами параметрами они повторно используют параметры последнего сообщения для вызова ::DefWindowProc. Цель — «уменьшение размера исполняющей системы MFC», как будто несколько сотен лишних инструкций в объемистой DLL могут иметь значение! Даже я могу разобраться, как раскрыть CWnd::OnAnything в вызов DefWindowProc.
Несколько лет назад, как я уже упоминал во вступлении, я работал на большой многопроцессорной системе (16 процессоров). Мы использовали доработанные миникомпьютеры PDP-11, которые были относительно медленными. Мы программировали их на языке Bliss-11, который, насколько мне известно, до сих пор остается лучшим оптимизирующим компилятором в мире (хотя я видел несколько весьма впечатляющих оптимизаций в Microsoft C/C++). Выполнив некоторые измерения производительности, мы определили, что алгоритм подкачки страниц был самым узким местом. Поэтому нашим первым предположением было то, что алгоритм подкачки страниц ошибочен. Мы обследовали код, и человек, ответственный за поддержку алгоритма подкачки страниц , переписал его с учетом наших данных и получил новый, гораздо более быстрй алгоритм управления страницами, затратив на это неделю.
Тем временем в MIT все еще использовали MULTICS. Они обнаружили серьезную проблему с производительностью системы подкачки страниц. Она была написана на языке EPL, подобном PL/1. Предполагалось, что проблема была обусловлена неэффективностью кода, вызванной использованием языка высокого уровня, поэтому они затеяли переписывание алгоритма управления на ассемблере. Год спустя код был готов и внедрен в работающую систему. Производительность упала на 5%. В результате расследования было обнаружено, что в основной алгоритм вкралась ошибка. Они взяли код на EPL, переписали алгоритм и внедрили улучшенный алгоритм за несколько недель. Урок: не оптимизируйте то, что не относится к проблеме. Сначала разберитесь с самой проблемой. Потом, и только потом, займитесь оптимизацией. В противном случае оптимизация — пустая трата времени и может даже ухудшить производительность.
В компиляторе Bliss атрибут переменной register говорит компилятору: «ты должен выделить регистр для этой переменной». В языке C это значит: «мне бы хотелось, чтобы ты выделил регистр для этой переменной». Многие программисты решили, что им следует поместить некоторые переменные в регистры, чтобы улучшить код. Компилятор Bliss был великолепен; он имел весьма интеллектуальную систему распределения регистров и в отсутствие явных указаний от программиста сам распоряжался выделением регистров под переменные, если это давало лучший код. Явное выделение регистра под переменную означает, что регистр недоступен для хранения общих подвыражений, особенно подвыражений для доступа к структурам данных. После большого числа экспериментов мы определили, что добавление атрибута register к объявлению переменной почти неизменно давало в результате код гораздо хуже того, который получался, когда компилятор сам выполнял распределение. В случае внутренних циклов многочасовые усилия обычно приводили к небольшому увеличению производительности, но в целом программисты пришли к пониманию, что любые попытки оптимизации могут привести к ухудшению кода, если вы не изучили сгенерированный машинный код тщательно и не выполнили множество экспериментов по измерению производительности.
Если вы слышали о тестах производительности SPECmark, то наверняка вы в курсе, как они работают. В частности, IBM написала программу, которая получает на входе программу на FORTRAN'е, такую как бенчмарка умножения матриц SPEC, и выдает другую программу на FORTRAN'е, которая оптимизирована с учетом архитектуры кэша машины, на которой она будет запущена. Несколько параметров описывали все стратегии кэширования для каждой из моделей семейства RISC 6000. Исходная программа давала 45 SPECmark. После преобразования тест показал более 900 SPECmark. Это увеличение производительности в 20 раз основано исключительно на эффекте четвертого порядка — попадании в строку кэша. Если вы занимаетесь обработкой изображений, особенно больших, знание тонкостей работы кэша (даже относительно машинно-независимых) может наградить вас увеличением производительности на порядок.
Наивный подход (оптимизация на уровне исходного кода) далек по эффективности от оптимизации верхнего уровня. Оптимизация подкачки страниц, оптимизация строк кэша и оптимизация выделения памяти зачастую могут иметь гораздо больший эффект, чем оптимизация на уровне исходного кода. Следом идет алгоритмическая оптимизация, особенно если ваша проблема не обусловлена подкачкой страниц или кэшем. Только после того, как все это сделано, и, естественно, вы измерили все, что могли, имеет смысл заняться оптимизацией на уровне исходного кода. Если этого требует ваша предметная область, может даже иметь смысл перекодировать внутренние циклы, особенно для таких алгоритмов, как свертка и DSP, на ассемблере. Обычно это делают, чтобы получить преимущество от использования потоковых инструкций или MMX.
Пожалуй, самый наглядный пример программистской глупости в чистом виде при «оптимизации» кода имел место, когда я занимался портированием большой библиотеки, которую мы использовали в нашем исследовательском проекте. Можете представить себе это как портирование с 16-разрядной архитектуры на 32-разрядную (на самом деле это было портирование с 18 разрядов на 36, и язык был не C, но эти детали в данном случае не имеют решающего значения — вы можете написать ужасный код на любом языке, и мне доводилось видеть программистов на C, которые писали ничут не лучше). Порт в основном работал, но была очень странная проблема, которая проявлялась лишь в некоторых редких случаях, но приводила к аварийному завершению программ, использующих библиотеку. Я начал поиск. Куча оказалась поврежденной. Когда я обнаружил причину повреждения кучи, ей оказался неправильный указатель, который позволял запись в случайное место в куче. Как же испортился этот указатель? Потратив добрых 12 часов на отладку, я нашел действительного виновника. Еще через 5 часов я обнаружил, что у программиста, который писал код конструктора для структуры данных, была структура наподобие:
{
char * p1;
char * p2;
}
, где указатели раньше были 16-разрядными, а теперь стали 32-разрядными. Поискав код инициализации, вместо ожидаемого
something->p1 = NULL;
something->p2= NULL;
, я обнаружил нечто вроде:
(*(DWORD*)&something.p1) = 0;
! Когда я встретился с этим программистом, он обосновал это тем, что таким образом можно обнулить два указателя одной инструкцией записи двойного слова (это был мейнфрейм, а не x86), и разве это не разумная оптимизация? Само собой, когда указатели стали 32-разрядными, эта оптимизация обнуляла лишь один из двух указателей, при этом второй принимал значение либо NULL (в большинстве случаев), либо порой указывал на кучу самым разрушительным образом.
Я указал, что такая оптимизация имела место единственный раз во время создания объекта (в среднем приложения, использовавшие нашу библиотеку, создавали порядка шести экземпляров этого объекта), и что до вчерашнего дня я потратил не только 17 часов своего рабочего времени, но и 6 часов процессорного. Если бы мы исправили эту ошибку и циклически запускали ранее сбоившую программу по кругу, перезапуская ее каждый раз после завершения, общее сэкономленное этим хаком процессорное время за 14 лет не превысило бы того, которое было потрачено на поиск и исправление этой бессмыслицы!
Несколько лет спустя он продолжал делать подобные трюки. Некоторые люди ничему не учатся.
Оптимизация нужна лишь тогда, когда она действительно нужна. Когда она нужна, она значит очень много, но до тех пор, пока вы не выяснили, что она действительно нужна, не тратьте на нее время. Даже если вы точно знаете, что она нужна, вам необходимо определиться, где именно она нужна. Не располагая результатами измерений производительности, вы не знаете точно, что именно следует оптимизировать, и почти наверняка оптимизируете не то, что нужно.
Результатом станет непонятный код, который трудно писать, трудно отлаживать и трудно сопровождать, и который к тому же не решает вашу проблему. Таким образом, он имеет двойной недостаток: стоимость разработки и сопровождения ПО растет, и при этом нет никакого выигрыша в производительности.
С таким сочетанием трудно бороться. Теперь-то вы поняли, что я имел в виду в своем заголовке?
Copyright © 1999 The Joseph M. Newcomer Co.
Last modified: April 20, 2008
Вы можете связаться с автором по eMail:
newcomer@flounder.com и задать ему вопрос или поделиться своими мыслями по поводу опубликованного.
Небольшое (которое по ходу дела успело подрасти) пояснение для тех, кто ранее не встречался с примененной автором статьи нотацией.
В курсе математического анализа при изучании асимптотического поведения функций вводится
нотация Ландау (нет, не того
Льва Ландау, учебниками которого пугали многие поколения будущих физиков-теоретиков, а его
однофамильца из Германии, который ввел обозначения, известные нам как «O большое» и «o малое», основываясь на работах Пауля Бахмана).
Здесь приведено формальное описание этих обозначений.
Для тех, кто предпочитает неформальное описание: обозначение
f(x) = O(g(x)) обозначает, что функция
f(x) в некоторой окрестности имеет порядок величины
g(x). Например, когда говорят, что алгоритм имеет
сложность n2, это означает, что если подать на вход алгоритма
n элементов, время их обработки составит не более
C*n2, где
C — некоторая константа (можно с достаточной точностью считать, что это время обработки одного элемента данных).
Есть ли польза от такого определения? Ведь не зная точного значения C, мы не можем определить общее время выполнения.
Безусловно, есть. Во-первых, быстрый прогресс вычислительного оборудования приводит к тому, что новые компьютеры имеют производительность на порядок выше предшественников, еще не списанных в утиль. Один и тот же алгоритм может выполняться 1 секунду на одном компьютере и 10 — на другом. Говорить о конкретном значении C можно только в контексте определенной конфигурации аппаратных средств.
Во-вторых, что даже более существенно, нам зачастую интересно не столько абсолютное время работы программы сейчас (в конце концов, его можно попросту замерить секундомером, не углубляясь в теорию, причем это будет куда более точной оценкой), сколько ее (программы) масштабируемость.
Сегодня получение отчета по нашей базе данных в сотню миллионов записей занимает час. У топ-менеджеров есть планы расширения бизнеса. Как поведет себя система, когда количество записей в базе возрастет на порядок, в 10 раз? Сколько времени займет обработка в новых условиях? Не окажется ли, что уже пора запускать новый расчет, а старый еще не успел завершиться?
Для человека, далекого от компьютера, ответ очевиден: если объем работы увеличился в 10 раз, само собой разумеется, что ее выполнение потребует в 10 раз больше времени. Специалист менее категоричен. Он ответит, что все зависит от сложности алгоритма. Рассмотрим результаты в нашем случае для наиболее типичных порядков сложности:
| Сложность | Время |
| 1. | O(1) | 1.0 |
| 2. | O(log(n)) | 3.3 |
| 3. | O(n) | 10.0 |
| 4. | O(n*log(n)) | 33.2 |
| 5. | O(n2) | 100.0 |
| 6. | O(n3) | 1000.0 |
| 7. | O(n!) | 3628800.0 |
О сложности O(1) можно только мечтать. Время выполнения алгоритма всегда одинаково, независимо от количества входных данных. Такие идеальные характеристики обычно имеют ценнейшие программы типа Hello World, которым все равно, сколько данных им подано.
Сложность O(log(n)) лежит на пути в программистский рай (логарифм обычно подразумевается по основанию 2, но принципиального значения это, вообще говоря, не имеет). Алгоритмы, имеющие такую сложность, прекрасно масштабируются, поскольку с ростом объемов входных данных время обработки растет очень медленно. Из наиболее полезных примеров можно назвать двоичный поиск.
Сложность O(n) типична для примитивных процессов обработки, когда каждый элемент данных обсчитывается изолированно от других. В этом случае предположения дилетантов о том, что время выполнения работы пропорционально количеству входных данных, оправдано (траншею длиной 10 метров землекоп будет рыть примерно в 10 раз дольше, чем длиной в 1 метр).
Сложность O(n*log(n)) свойственна великому множеству полезных и добротных алгоритмов. Время выполнения растет быстрее, чем линейная функция, но не сильно быстрее. Такая масштабируемость в большинстве случаев остается практически приемлемой.
Сложностью
O(n2) обладают многие примитивные алгоритмы вроде
пузырьковой сортировки. Обычно это сигнал, что имеет смысл поискать более эффективное решение, хотя не факт, что такое решение имеется в данном случае.
Алгоритм O(n3) в большинстве случаев можно считать немасштабируемым — если сегодня наша программа выполняется за 1 час, после роста данных в 10 раз время ее выполнения составит 1000 часов, то есть почти 42 дня. Вряд ли отчет полуторамесячной давности имеет реальную ценность.
Хуже алгоритма O(n!), пожалуй, трудно что-то придумать...
В неформальном общении, как упоминает автор статьи, обозначения O и C для краткости опускают и говорят просто «алгоритм имеет сложность n2».
Почему же автор призывает нас не забывать о C? Как я уже упоминал ранее, простейшие алгоритмы часто имеют сложность n2, более сложные — n*log(n). Предположим, что у нас есть два таких алгоритма, причем для одного элемента (n = 1) данных простой (n2) выполняется за 10 миллисекунд (C = 0.01), сложный (n*log(n)) — за 100 (C = 0.1). Каковы будут затраты времени на обработку 4-х элементов?
В первом случае t = 0.01*42 = 0.16, то есть 160 миллисекунд. Во втором имеем t = 0.1*4*2 = 0.8, то есть 800 миллисекунд. Итак, хотя с точки зрения теории первый алгоритм значительно хуже, тем не менее в данном конкретном случае он дает пятикратный выигрыш во времени.
Конечно, на больших объемах данных хороший алгоритм непременно возьмет свое. Возьмем n = 1000. Теперь первый вариант дает t = 0.01*10002 = 10000 (2 часа 47 минут). Второй вариант: t = 0.1*1000*log(1000) ~ 990, то есть примерно 16 с половиной минут. Разница весьма впечатляет, и с ростом n становится все больше.
На этом примере хорошо видно, когда оптимизация — друг, а когда становится врагом. Вот почему автор настаивает: сначала измерьте все, что относится к производительности, и лишь потом оптимизируйте, иначе оптимизация выйдет боком.