Казалось бы, современное железо настолько хорошо, что оптимизация просто не нужна: всё то, что делается, будет работать хорошо и так. Но всё ли? Как скоро простая задача загрузит процессор на 100%?
Например, современный Chrome может обрабатывать примерно тысячу узлов на странице (плюс-минус пару тысяч) и, при превышении этого значения, начинает тормозить (а Firefox, кстати, нет).
В общем, хочу немного разобрать вопрос, где можно оптимизировать свою программу.
Компиляторы и интерпретаторы в деле
Давайте начнём с того, что средства разработки изначально выполняют оптимизацию. Скажем, внутри цикла вычисляется каждый раз какое-то значение и оно вообще не зависит от цикла - компилятор его вынесет посчитает вне цикла, засчёт чего потребность сократится количество инструкций.
Но это из простого; современные компиляторы и интерпретаторы довольно умны и могут делать много чего, прощая ошибки и слабости программистов.
Хотя бывают случаи, когда оптимизация, напротив, ломает код: убирает инструкции, которые выглядят неиспользуемыми. Скажем, функция задаёт некоторое значение глобальной переменной, которая нигде больше в коде не используется и компилятор с чистой совестью её удаляет; а эта переменная - псевдоним доступа к порту, в который должно быть записано значение. Этот пример был взят из кода для микроконтроллеров, хотя есть и похожие ошибки (ошибки ли?) и для вполне современных компиляторов и интерпретаторов.
Короче, доверяй, но проверяй.
Директива вместо функции
Помните, одно время для кода на C++ было популярно использовать директивы компилятора #define. Не помните? Ну да неважно, сейчас я немного про это напишу.
Директива позволяла создать что-то вроде инструкции для компилятора. Благодаря им можно было, например, ввести условное компилирование (скажем, если стоит переменная окружения XXX, то используется библиотека для windows, а если переменная не выставлена - то для gnu/linux). Это было очень удобно: код один, а с минимальными изменениями собирается для разных платформ (разумеется, через это можно было много чего настроить).
Так вот, можно было определить таким образом и функцию или вычисление. Обычно это была какая-то простая функция, вроде получить из массива по указанному номеру значение и сравнить его с передаваемым, в качестве аргумента, числом.
И когда код собирался, то компилятор, вместо такой вот функции, подставлял соответствующий код из директивы.
Хотя для такой задачи вполне можно было использовать функцию, но, оказывалось, что вычисление значения прямо в строке - быстрее (что понятно - экономился вызов функции, перемещение по стеку итп).
#define func(c) (table[(c) & 0x01] & DIGIT)
//...
if(func(3) == 0) {...}
// преобразуется в
if(table[(c) & 0x01] & DIGIT == 0) {...}
Числа с плавающей точкой грустят
И это не случайно: с ними оборудование работает и медленней и хуже. Причина - крайне тривиальная: используется более дешёвое и универсальное оборудование, которое просто не умеет хорошо обрабатывать такие данные. Неплохо - да, хорошо - нет. От этого выходит, что перемножить целых числа быстрее, чем два вещественных.
Хорошей новостью является то, что очень часто можно проводить часть вычислений с целочисленными величинами, лишь в самом конце (когда это уже стало необходимостью) приводя их к числу с плавающей точкой.
Тут, впрочем, требуется некоторая сноровка, т.к. не каждый отказ от вещественных чисел ведёт к повышению производительности
Вычисления, которые можно не делать
Тут хочу разобрать два примера.
Вычисления, которые уже сделаны
Иногда, ряд вычислений возвращает раз за разом одни и те же (или близкие, но не влияющие на точность работы) значения. И в таких случаях бывает полезней использовать таблицу готовых значений вместо того, чтобы вычислять их раз за разом. Помните таблицу Брадиса из школы? Вот точно такое же, только в вашей программе.
Суть сводится к тому, что все вычисления производятся заранее и выбирается только готовое значение, что сильно экономит время выполнения задачи (в качестве исключения, некоторые редкие, но не попавшие в таблицу значения, могут рассчитываться отдельно).
Это довольно распространённый способ оптимизации. Когда вышел Quake (кажется, первый) - все были в восторге от того, как хорошо там проработаны свет и текстуры. Но позже выяснилось, что разработчики не мучили железо понапрасну: многие значения были вычислены предварительно.
В некоторых случаях, такой подход даёт 20 кратный прирост производительности (читал про такое). Главное, не растерять эти приобретения дальше по коду.
Вычисления, которые можно не делать
На старых игровых платформах, вроде NES, было мало видеопамяти. Поэтому многие спрайты делились на части и хранились половинками. Скажем, только половина героя. Вторая половина - рисовалась как зеркально отражённая первая.
Точно такой же подход используется и для вычислений: сложные рассчёты используются лишь для части данных; прочие - вычисляются просто
Например, нам нужно вычислить точки круга; по 1 точке на каждый градус поворота. Однако, вычислив только четверть значений - мы можем утверждать, что вычислили все необходимые: отражение координат последовательно относительно осей ординат (умножение значения x и/или y на -1) - даёт необходимое значение.
x0,y0 - вычислено (относительно точки 0,0)
x1 = -x0, y1 = y0
x2 = -x0, y2 = -y0
x3 = x0, y3 = -y0
Для одной операции будет, наверное, не заметно, но вот для сотен и тысяч такая оптимизация даст положительный эффект.
Более быстрый алгоритм
Это, разумеется, очевидно, но что греха таить, мало кто из разработчиков действительно старается выбрать для решения определённой задачи наилучший алгоритм. Есть встроенная быстрая сортировка - ну и отлично, ей и воспользуемся.
Не уверен, что такой подход неправильный. Неправильно, это когда разработчика winforms гоняют на собеседовании по структурам и алгоритмам до седьмого пота, а он после только кнопочки на форму кладёт.
Кроме того, ряд алгоритмов дают свой прирост лишь на очень больших объёмах выборки: так какой смысл потратить лишний час на то, чтобы прирост производительности составил менее 2 миллисекунд?
Иными словами, к данной оптимизации следует прибегать лишь тогда, когда выгода очевидна. Например, точно известно, что данных будет очень много (сотни тысяч, а то и миллионы записей), либо что задача будет выполняться на медленном железе.
Контейнер решает
Очень важно подобрать правильный тип контейнера для хранения данных. Мы знаем массивы, деревья, односвязные и двусвязные списки и так далее. Для каждого дерева - своя структура данных и метод компоновки их в памяти. Я специально не хочу тут углубляться в существующие структуры данных и их эффективное применение: во-первых, про это и так много чего написано, во-вторых, они не являются самоцелью статьи.
Главным образом, это влияет на скорость работы с данными, хотя эффект, чаще всего, заметен либо на медленном железе, либо с большими выборками, так что тут тоже следует исходить из соображения целесообразности.
Каждая структура хранения данных имеет свои достоинства и недостатки. Скажем, односвязный список позволяет быстро пробежаться по всем элементам, но массив - позволит это сделать быстрее. Всё благодаря плотности упаковки данных (тут надо сделать примечание, я исхожу из более-менее привычного подхода к организации таких структур в памяти, однако, их реализации могут отличаться): в то время как элементы списка могут быть разбросаны по памяти, массив (с высокой вероятностью) будет размещён одним блоком.
К слову, хранимые внутри контейнеров структуры тоже имеет смысл продумывать: из-за неверной компоновки они могут занимать в памяти больше места, чем требуется, например, из-за выравнивания данных (хотя это больше к стеку относится, чем к куче). Много записей - много впустую потерянных байт.
Короче говоря, перед тем, как выбрать контейнер, хорошо бы понимать, как предстоит работать с этими данными и выбрать подходящий; если же данных будет мало и интерес к оптимизации тут отсутствует - можно смело выбирать контейнер, с которым удобней работать.
Структуры данных, от которых мы отвыкли
Не знаю как системные разработчики, но прикладное программирование давно отошло от многих эффективных подходов. Если есть возможность использовать логический тип (bool, boolean), то он используется; если требуется хранить несколько флажков - они и хранятся. Но вот вопрос: сколько памяти занимает 1 переменная логического типа? 1 бит или 1 байт? Или 32 байта, т.к. процессору удобней работать с такими типами данных? Очень вероятно, что последнее (но не обязательно).
В то же время в одну 32-разрядную целочисленную переменную можно упаковать 32 флажка (раньше, кажется, только так и делали) и проверять их значение сравнивая с маской (устанавливать, кстати, тоже).
Но пример выше - лишь один из многих и тут я могу предложить лишь получше разобраться в том, как компилятор (или интерпретатор) вашего языка обрабатывает те или иные структуры данных, т.к. оптимизация - на этот раз не быстродействия, а памяти - будет зависеть, в том числе, и от эффективности использования типов данных.
Плотно и эффективно упакованные данные позволят более экономно потратить память и, вероятно, повысить быстродействие работы приложения. Хотя код, скорее всего, будет непрост.
В итоге
Как мы видим, есть довольно много направлений для оптимизации, некоторые из них я описал, даже несмотря на то, что они возможны лишь при определённых условиях.
Использую ли я такие оптимизации? По возможности: не всегда это имеет смысл, да и возможно в принципе: сроки горят, тяжёлое наследие прежних программистов, банальная усталость и неготовность к подвигам.
Стремлюсь ли я их использовать? О да! Мне кажется, что вся моя работа строится на том, чтобы решить каждую задачу предельно оптимально и эффективно. Хотя иногда я оцениваю эту оптимальность как "выполнить задачу как можно быстрее", а иногда как "написать код, который будет лучше поддерживаться". Так что мне есть куда расти.
На этом, думаю, можно поставить что-то вроде многоточия: тема вряд ли может считаться исчерпанной. Скорее, это только начало.