Во времена, когда интернет только зарождался, обычно первым провайдером в городе становилась междугородняя ТТС (телефонно-телеграфная станция), или "междугородка". Ну а у кого ещё были доступы к каналам связи? Вы наверное не застали уже те времена диал-апа, связи по аналоговой телефонной линии, свистящих и шипящих модемов на 9.6 кбита в секунду.
У нашего провайдера был свой сайт, поддерживаемый энтузиастами - работниками ТТС. И вот однажды эти ребята сами организовали и объявили на своём сайте конкус программистов. Задание конкурса опишу менее формально, чем было представлено в конкурсе, сделаю его чуть более читабельным.
Задание конкурса
Есть файл с таблицей чисел, по которой надо построить графики. Числа в файле представлены в текстовом выражении, т.е., по сути это текстовый файл. Столбцы - отдельные графики. Строки - значения ординат (y) для одного значения абсцисс (x). Строки разделены символом новой строки (\n), Числа в строке разделены символом табуляции (это не было прописано в задании, и я сначала учитывал и пробелы, и считал даже "ширину табуляции").
Нужно написать программу на языке C, которая создаёт картинку - файл формата bmp. На картинке должны быть изображены графики, построенные по данным из вышеописанного файла. Программа должна принимать из командной строки три параметра: ширину и высоту графика в пикселях, и имя файла с данными.
Числа в файле - вещественные, т.е. могут быть с дробной частью, могут быть в экспотенциальной нотации. Например такие: -12.543 -1.6875e+7. Все графики должны быть разного цвета. И нельзя использовать никаких библиотек, кроме стандартных библиотек ввода-вывода. Т.е. нужно было "вручную" сформировать bmp-файл. Ссылка на описание формата bmp была указана в условии конкурса.
Условия проведения конкурса
Конкурс длился несколько дней. Не помню сейчас сколько, может неделю, может больше. Участники конкурса должны написать программу, и прислать её исходный текст на email, указанный в условиях. Организаторы компилируют присланные участниками исходники. Сначала программы проверяются на то, что они вообще формируют корректные картинки, соответствующие данным, на которой их запускают.
Потом программы запускаются в цикле много тысяч раз, замеряется время выполнения и делится на количество итераций цикла (количество запусков). Таким образом для каждой программы получается среднее время выполнения. Побеждает тот, чья программа покажет минимальное время (т.е. побеждает автор самой быстрой программы).
Файл данных, на котором происходят запуски, участникам неизвестен. Неизвестно количество графиков (столбцов в файле), неизвестно количество точек в каждом графике (количество строк в файле).
Зато известны результаты запуска и твоей программы, и программ других участников. Ведь число попыток не ограничивалось! После того, как ты отправил email с кодом своей программы, её тестируют, замеряют время выполнения, и публикуют его на сайте в таблице с результатами участников. Если время не изменилось, или даже увеличилось по сравнению с предыдущей лучшей версией твоей программы, тебе просто напишут письмо об этом. Т.е. учитывается только твой лучший результат.
Гонка и результаты
Несмотря на простоту, задача включает в себя несколько подзадач, над которыми можно подумать:
- чтение, распарсивание и запоминание данных
- нахождение глобальных минимума и максимума среди всех функций, ведь все графики должны быть изображены на одной картинке
- как выбрать цвет, разный для разных графиков, число которых заранее неизвестно
- что показывать между соседними известными точками, если например точек всего будет 100, а требуемая ширина графика - 1000 пикселей
- собственно формирование файла формата bmp
Но всё это "технические мелочи". Вскоре у меня была рабочая программа, и я включился в гонку за минимальным временем выполнения. Всего я отослал 3 версии программы. Смотрел на таблицу с текущими результатами, на свою программу, и искал - что-же тут ещё можно ускорить, что тут лишнее?
Гонка была напряжённая, лидеры шли "нос в нос", нас разделяли 15, 10, еденицы миллисекунд. В "хвосте" между соседними местами была разница и в 60 миллисекунд. Сами организаторы конкурса написали что не ожидали таких плотных результатов и сильно увеличили количество итераций цикла запуска программ. И вот, время, отведённое на конкурс, закончилось. Я занял 4-ое место.
Организаторы опубликовали файл, на котором они прогоняли программы. Там было по 10 тысяч точек на каждый график, количество графиков не помню, но не менее четырёх. И, самое интересное - опубликовали исходные коды всех участников.
Моя программа кстати была самая короткая среди всех. Я даже откопал её в своих архивах, можете посмотреть её здесь: https://github.com/mars37/dev.initit/blob/master/c/graph.c Не вините за некоторые траблы с отступами, дикие времена были
В чём секрет победителя?
Ну что-ж, "краткость - сестра" конечно, но выигрывала не самая лаконичная программа, а самая быстрая. И что было интересно - отрыв самой быстрой программы от второго места. Я уже писал что мы шли "нос к носу", разрыв между результатами программ на местах 2, 3, 4, 5 были единицы миллисекунд. А вот самая быстрая программа опережала конкурента аж почти на 20 миллисекунд. Это было много для того конкурса.
Так за счёт чего программа-лидер выполнялась быстрее? Это как раз то место, ради которого я и пишу эту статью.
Программа - лидер была не только быстрее остальных, её исходник был самым большим из всех. Не просто больше, а "очень сильно" больше, в несколько раз больше. Открывая исходник, я думал - "что-же там за алгоритм-то такой хитрый"?! Сижу, разбираюсь … Ага, вот чтение, вот данные складываются, вот цвет выбирается, вот основной цикл "рисования". Пока ничего хитрого, необычного.
Только что за условие окончания такое странное? Вот точка добавляется, ага. Тоже ничего особенного. Интересно - цикл на этом не заканчивается, чтобы перейти к следующей точке. Следующая точка добавляется прямо тут-же. Так это-же просто повторение кода, "копи-паст". И ещё раз такой-же кусок кода. И ещё. И ещё. Ого! Так вот чем всё тело цикла заполнено! Копи-паст бесчисленное количество раз!
Тут до меня дошло, почему программа работала быстрее конкурентов, и почему её исходник такой огромный. Она экономила на проверке условия завершения цикла. В её теле цикла один кусок кода повторялся 100 раз! Например, надо построить график шириной в 10 тысяч пикселей. Моя программа (и программы других участников) выполняла "основной цикл" 10 тысяч раз. Т.е. 10 тысяч раз проверялось условие окончания цикла, и выполнялось тело цикла. А программа-лидер делала цикл всего 100 раз. Т.е. всего 100 раз выполнялась проверка условия окончания цикла. А в теле цикла обрабатывалась последовательно, без лишних проверок, сотня точек.
Дикая оптимизация
Конечно, в реальном, "промышленном" проекте такой код просто не прошёл бы код-ревью. Такой "копи-паст" - грубое нарушение одного из основных принципов разработки программного обеспечения - DRY (Don't repeat yourself). Приёмы, позволяющие ускорить какую-то систему за счёт нарушения основных принципов разработки, я называю "дикой оптимизацией".
Выигрыш времени выполнения от таких "грязных приёмов" чаще всего слишком мал, чтобы оправдать сложность поддержки, модификации такого кода. Чаще всего. Но иногда, возможно, такие приёмы позволят принести реальную пользу. Например выиграть конкурс
В данном случае, экономия была, грубо говоря, за счёт того, что меньше выполнялась проверка условия. Но это быстрая операция. Экономия на ней - "копейки". Гораздо большей экономии можно достичь там, где например вместо простого кода, напрямую реализующего нужный функционал, используется сложная иерархия классов, написанная "астронавтами от архитектуры".
Однажды я перерабатывал процедуру сложной конвертации данных, с десятком миллионов объектов, у каждого из которых могли быть десятки разных свойств. Сам алгоритм процедуры был сложный, со сравнением свойств, с объединением объектов. Процедура должны была периодически запускаться, и обновлять данные в одной системе, на основании огромного количества данных в другой системе. Написано это было на Java, с соблюдением всех принципов разработки. Была только одна проблема: она выполнялась две недели!!! За это время актуальность данных становилась уже, мягко говоря, сомнительной. Да ещё и не всегда процедура доходила до конца, иногда она падала с ошибками.
Я переработал структуру данных, выделил отдельно неважную процедуру, переписал алгоритм, избавился от ORM, заодно нарушил парочку принципов, уффф. Зато процедура теперь стала стабильной, не падала, и выполнялась … барабанная дробь … всего за два часа! Теперь можно было запускать её не два раза в месяц в лучшем случае, а, например, два раза в день.
Не оптимизируй преждевременно
Но не надо думать, что я призываю не обращать внимания на принципы разработки, копипастить, применять сразу микрооптимизацию, и вообще творить в коде любую дичь. Нет! Сначала научитесь писать код "по всем правилам", выстраданным тысячами программистов. Эти принципы не "с потолка" взялись. И лишь в тех случаях, когда "по другому никак", когда вы знаете чем жертвуете и ради чего (например читабельностью и поддерживаемостью кода ради экономии двух недель), тогда и карты вам в руки.