Про оптимальность программ

lex_kravetski — 23.05.2010 Чисто навскидку хочется сказать, что оптимальная программа — это та, которая работает максимально быстро. Самую малость поразмыслив, понимаешь, что надо бы дополнить: при этом ещё и правильно. Уже одно только это дополнение несколько портит всю очевидность ситуации. Действительно, которая программа оптимальнее, быстро работающая и дающая ошибку один раз на миллион или работающая чуть медленнее, но ошибающаяся раз на десять миллионов? Да хрен знает. Общего случая тут нет, есть только конкретные случаи с разными ценами ошибок, что и определяет как раз означенное понятие оптимальности.

Наиболее одарённые тут обычно говорят: оптимальнее всего программа, которая работает без ошибок и максимально быстро. Что сразу же наталкивает на рассуждения о сферических конях в абсолютном вакууме. То бишь, в случае с программами, о примитивных синтетических задачах, кои как раз и составляют основу суждений одарённых, но не имеют к реальному миру никакого отношения. И это, к слову, упирается в вопрос цены, в чём бы мы её там ни считали — в деньгах ли, по капиталистически, или в человеко-часах по коммунистически, всё одно, вопрос цены краеуголен и всеопределяющ.

Мини-алгоритм, типа сортировки массива вполне возможно написать без ошибок. Просто потому, что физически возможно за крайне небольшое время сто раз к ряду проанализировать каждую строку программы. Совокупность алгоритмов на сто тысяч строк кода физически невозможно внимательно проанализировать даже один раз. То есть, физически возможно — за сто лет, например, — но вот за короткий срок, увы…

Количество ошибок по отношению к длине кода возрастает нелинейно (за счёт роста количества взаимосвязей между логическими блоками). Таким образом, если исправление ошибок в коде из десяти строк потребует, скажем, десяти минут, то для тысячи строк это будет уже не тысяча минут, а, скажем, десять тысяч. Даже при архи-грамотном проектировании и написании кода мега-квалифицированным программистом, число ошибок в отношении к длине кода всё равно будет расти. Равно будет расти и время на их исправление. Это — первый аспект проблемы.

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

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

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

Этот частный случай с длиной алгоритма плавно и неуклонно обобщается. Положим, код на языке С выполняется в три раза быстрее аналогичного на Java, но требует в два больше раза времени на свою разработку. Считаем, что дороже — проц под ускорение или удвоение времени разработки и делаем вывод. Как правило, вывод не в пользу С.

По крайней мере, в тех случаях, когда процом вообще возможно решить проблему, что бывает, конечно, не всегда.

Идём далее. Выясняем, что понимается под «скоростью выполнения». Точнее, про скорость выполнения чего именно идёт речь. А речь обычно идёт про синтетический тест вида: «берём цикл и n раз множим в нём икс на один». В этом случае, да, на С раз в сто быстрее. Но на практике у нас нет программ, где n раз множится икс на один. А даже если мы что-то и считаем таким образом — через мини-программу, то нам, собственно, обычно пофиг, минуту она будет работать или две. Мы один раз это дело посчитаем и больше данный код никогда не запустим. Нам, собственно, гораздо более критично, за сколько времени мы оный код напишем. Ибо если на код уйдёт час вместо десяти минут, то буде он даже потом за десять секунд вместо минуты выполнится, мы всё равно около сорока девяти минут потеряли: не на расчёт — на написание кода.

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

Логика тут вполне очевидная: сыпятся, положим, нам откуда-то числа. А мы их пихаем в массив, по которому потом собираемся итерироваться. Мы заранее не знаем, сколько чисел отсыпят. Какой выход? Выходов три. Первый — попросить отсыпать одно и то же два раза. На первый раз узнать размер массива, а на втором его с нужным размером создать и заполнить. Однако тут мы пропипали всю производительность за счёт двойного запроса, который может происходить сколь угодно медленно. Второй выход — завести массив немерянных размеров, и засыпать в него пришедшее, забив на оставшуюся в конце массивов безграничную пустоту. Тут мы, соответственно, пропипём немерянно памяти, всё равно сохранив вероятность с размером немерянности массива не угадать и вылететь за его пределы при отсыпании чисел. Наконец, третий вариант — использовать не массив в чистом виде, а обёртку над ним. Которая будет внутренний массив оперативно подгонять под требуемый размер.

Третий случай, конечно, работает медленнее, чем массив с заранее заданным размером, в который напрямую пихают числа. Но при этом он быстрее двойного запроса, безопаснее в смысле неугадывания размера и потребляет несколько меньше памяти. Легко догадаться, что в среднем следует использовать именно его. Если же итерации весьма и весьма часты, то следует либо после заполнения массив из обёртки извлечь и пользоваться им, либо же внутри обёртки грамотно предусмотреть итерирование — например, в виде итерирования напрямую по массиву с вызовом переданной функции по ссылке (или по безымянной имплементации интерфейса в случае с Java).

Мы видим, что не смотря на очевидное преимущество массива в синтетическом тесте, реальная задача для своего оптимального решения прямо таки потребовала обёртки над массивом. Более того, если бы мы упёрлись в массив, поскольку он быстрее в синтетическом тесте работал, то наше решение работало бы медленнее. Подчеркну: работало бы медленнее, а не просто было бы более трудоёмким в реализации.

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

В ряде случаев мы действительно можем заранее узнать количество объектов, однако в ряде других случаев — не можем. И этот другой ряд требует несколько иного подхода, как бы «заставляя» нас сменить массив на некоторую его обёртку. Дополнительные задачи «заставляют» эту обёртку усугублять. Так, например, поиск элемента по ключу не просто более трудоёмок без мапов, он ещё и работает существенно медленнее при прямом переборе всех элементов массива на фоне поиска через хэш.

Возможность организовать некие данные в структуру не только упорядочивает код, но и позволяет передать кучу данных разом — по ссылке, а не создавать копию каждой переменной для отсылки в функцию. Использование структур в результате не только тормозит некоторые фрагменты программы, но и ускоряет другие. Вкупе с другими плюшками — выигрыш. Однако возникает проблема времени жизни этих структур-объектов. Через некоторое время она становится настолько масштабной, что половина времени уходит на разруливание вопросов с управлением этим самым временим жизни. И 90% багов обратно же концентрируется в этой области. При этом былых багов вовсе не стало на 90% меньше. О нет, новые баги — новые. Они не за счёт исчезновения всех старых.

Для приведения оного беспредела к сколь либо приемлемому состоянию программист для начала вводит фабрики. Потом, осознав, что объекты всё равно приходится вовремя удалять, делает подсчёт ссылок. Подсчёт ссылок из отдельных объектов переползает в некоторый менеджер и… Этот менеджер — сборщик мусора и есть. Только работает он гораздо медленнее явовского и глючит временами. Оно и понятно: времени-то на отладку и оптимизацию у программиста не было. В потенциале, само собой, он благодаря доступу к низкому уровню имел возможность написать свой турбо-быстрый сборщик мусора, однако в среднем он написал не его, а что-то совсем другое, несравнимое.

Сборщик мусора, вдобавок, быстрее очищает память, чем последовательный вызов delete для всех по очереди объектов, поскольку имеет возможность очищать некоторый блок памяти целиком, в одно действие. Так что для полной имитации оного надо ещё и менеджер памяти свой делать.

Объекты и прочие абстрактные концепции падают не с неба, не являются следствием повального падения квалификации, напротив, их появление вызвано оной квалификации неуклонным ростом. Опытный программист рано или поздно начинает осознавать необходимость такого рода абстракций, нужных не только за ради простоты работы, но и эффективности результата. А вот уже в следствие введения абстракций появляется возможность занять некоторой работой тех, кто ранее по уровню навыков просто в ней участвовать не мог. Чем, собственно, освободить высококвалифицированных от исполнения упростившихся задач и использовать их там, где задачи сильно сложнее. Причём, настолько сложнее, что до появления ценных абстракций эти задачи просто нереально было решить за разумные сроки.

Часто говорят, будто языки, отличные от низкоуровневых, побуждают программиста писать хреново. На самом деле, тот, кто пишет хреновую программу на Java, если бы стал вдруг писать на С++, написал бы такой адский трэш, что лучше бы уж вообще ничего не писал. На более удобных языках результат будет лучше и у хреновых программистов и у отличных. Просто результаты труда хренового программиста на менее удобном языке вообще бы практически отсутствовали. И эту работу, как легко догадаться, пришлось бы делать отличному. Что, как легко догадаться, не дало бы ему сделать какую-то другую работу. До последнего, впрочем, легко догадаться, по ходу, не всем.

Разумные сроки, обратно, упираются в цену вопроса. При решении задач «в лоб», скорость появления следующего приложения возрастает не особенно сильно. Да, программист часть решений теперь уже помнит, но всё равно вынужден их набирать заново. Ну или копипастить из прежнего кода и вдумчиво модифицировать. В обоих вариантах попутно каждый раз восстанавливая в памяти все детали и нюансы. Внесение в язык процедур позволяет часть уже решённых задач перенести в новый код не копипастом, а библиотекой. И вызывать его быстро и коротко просто по ссылке-процедуре. Каждая следующая абстрактная концепция делает всё бо?льшую часть ранее написанного кода переносимой. Объекты позволяют перенести не только некий блок кода целиком, но и вклиниваться в его составные части. Внутренние объекты и функции как объекты первого рода позволяют вклинивание сделать ощутимо более лаконичным и гибким. Аспекты позволяют вклиниться сразу во множество функций, а не в каждую по отдельности и так далее. В результате внедрения этих концепций квалифицированный программист сокращает время написания каждого следующего приложения в десятки раз. И да, неквалифицированный сам не сокращает, однако и он пишет в десятки раз быстрее — пользуясь наработками квалифицированного. Падение стоимости разработки — астрономическое. При этом ещё и надёжность растёт. И даже, как ни странно, в среднем растёт скорость работы программы. Либо же, как альтернатива, её функциональность.

Далее. Большой объём кода при ограниченном времени разработки не позволяет произвести полную оптимизацию каждого его фрагмента. Поэтому при низкоуровневом подходе, хоть и существует возможность лучшей оптимизации, но возможность эта — гипотетическая. В среднем будет использован не тот идеально оптимизированный на низком уровне вариант, мыслящийся носителем идеи Безграничной Квалификации Пряморуких, а тот, который можно реализовать быстрее. Кроме того, разработчик не имеет возможности проводить по каждому чиху полноценные исследования, на это есть время только у того, кто специально занимается данной конкретной проблемой долгое время. По этим причинам низкоуровневое решение в среднем будет работать не только менее стабильно, чем высокоуровневое, но ещё и медленнее. Оптимальный вариант с некоторыми вызванными высоким уровнем накладными задержками скорее всего будет всё равно более быстрым, чем сделанный навскидку какой-то иной вариант. Ну а если один из таких фрагментов придётся на «бутылочное горлышко», то уже пофиг, что какие-то другие места были мастерски соптимизированны — всё в сумме работать всё равно будет медленно.

Что, к слову, регулярно являет себя миру. Вот, например, нужен был нам картографический сервер. Нашли два. Один на Java, второй — на С++. Ну все ж знают, что Java тормозит. Наверняка С++-ный будет быстрее. Хрен бы там. Он мало, что умел меньше явовского, так ещё и то, что умел, делал раз в пять медленнее. Казалось бы, быстрый С++, медленная Java. Ан нет. Всё строго наоборот. Все потенциальные накладные расходы Явы и все возможные оптимизации С на низком уровне привели совсем к иному результату, нежели обычно ожидается. А всё почему? Потому что JIT хоть и даёт не самый мощный результат из возможных, однако программисты в среднем дают ещё менее мощный результат, пытаясь вручную что-то там с памятью и регистрами соптимизировать.

То количество кода, из которого в совокупности состоит даже не очень большое современное приложение, ни один человек на Земле не сможет удержать в памяти. Ни один человек не сможет даже запомнить все нюансы и детали. Группа людей, не имея возможности оформить код в относительно выскоуровневые модули, не сможет банально рассказать друг другу, каким образом интегрировать их в единое целое. В результате гипотетически оптимальное приложение просто не будет физически существовать. В теории оно очень быстро работает, на практике оно не работает вообще — его нет.

Те программы, которые мы сегодня видим и регулярно используем, в гипотетическом мире одних только низкоуровневых языков просто не появились бы. Вместо Ворда с Ин Дизайна всё бы сейчас набиралось и версталось в досовском редакторе текстов. А Лексикон казался бы вершиной развития технологий. Стоимость разработки бухгалтерской программы для мелкого предприятия исчислялась бы в десятках миллионов долларов. О да, эта программа гипотетически «летала бы» на 286-м. А что толку? Кто бы за это дело заплатил? Кто бы выждал десять лет до появления результата?

Низкий уровень позволяет достичь выдающейся производительности приложения в теории. Высокий — физического существования этого приложения.

Рост уровня языков — неизбежен. Неизбежно и оформление кода в высокоуровневые абстракции, которые своим существованием замедляют работу синтетических тестов, но хотя бы делают возможным написание приложений с огромной функциональностью. Неизбежно и упрощение низкоуровневых концепции за ради возможности привнесения высокоуровневых. Это не бага, это — фича. Так и должно быть и слава богу, что так есть.

Оставить комментарий

Популярные посты:

• Ранее
• Архив