7. Кодирование с учетом масштабируемости
Резюме
Всегда помните о возможном росте данных. Подумайте об асимптотической сложности без преждевременной оптимизации. Алгоритмы, которые работают с пользовательскими данными, должны иметь предсказуемое и, желательно, не хуже, чем линейно зависящее от количества обрабатываемых данных время работы. Когда становится важной и необходимой оптимизация, в особенности из-за роста объемов данных, в первую очередь следует улучшать O-сложность алгоритма, а не заниматься микрооптимизациями типа экономии на одном сложении.
Обсуждение
Эта рекомендация иллюстрирует важную точку равновесия между рекомендациями 8 и 9 - не оптимизируйте преждевременно и не пессимизируйте преждевременно. Это делает данный материал трудным в написании, поскольку он может быть неверно истолкован как совет о "преждевременной оптимизации". Это не так.
Вот предпосылки для данной рекомендации. Память и дисковая емкость растут экспоненциально; например, с 1988 по 2004 год емкость дисков росла примерно на 112% в год (почти в 1900 раз за десятилетие). Очевидным следствием этого факта является то, что любой ваш сегодняшний код завтра может иметь дело с большими объемами данных - намного большими! Плохое (хуже линейного) асимптотическое поведение алгоритма рано или поздно поставит на колени даже самую мощную систему, просто завалив ее достаточным количеством данных.
Защита против такого будущего означает, что мы должны избежать встраивания в наши программы того, что станет западней при работе с большими файлами, большими базами данных, с большим количеством пикселей, большим количеством окон, процессов, битов, пересылаемых по каналам связи. Одним из важных факторов успеха такой защиты является то, что стандартная библиотека С++ обеспечивает гарантированную сложность операций и алгоритмов над контейнерами STL.
Здесь и надо искать точку равновесия. Очевидно, что неверно прибегать к преждевременной оптимизации путем использования менее понятных алгоритмов в ожидании больших объемов данных, которые могут никогда не материализоваться. Не менее очевидно и то, что неверно прибегать и к преждевременной пессимизации, закрывая глаза на сложность алгоритмов (О-сложность), а именно - стоимость вычислений как функцию от количества элементов данных, с которыми работает алгоритм.
Данный совет состоит из двух частей. Во-первых, даже до того, как станет известно, будут ли объемы данных достаточно велики, чтобы для конкретных вычислений возникла проблема, по умолчанию следует избегать использования алгоритмов, которые работают с пользовательскими данными (которые могут расти), но не способны к масштабированию, если только использование менее масштабируемого алгоритма не приводит к существенному повышению понятности и удобочитаемости кода (см. рекомендацию 6). Но все мы часто сталкиваемся с сюрпризами. Мы пишем десять фрагментов кода, думая, что они никогда не будут иметь дела с большими наборами данных. И это действительно оказывается так - в девяти случаях из десяти. В десятом случае мы сталкиваемся с проблемами производительности. Это не раз случалось с нами, и мы знаем, что это случалось (или случится) и с вами. Конечно, мы вносили исправления и передавали их потребителям, но лучше было бы избежать таких затруднений и выполнения лишней работы. Так что при прочих равных условиях (включая понятность и удобочитаемость) воспользуйтесь следующими советами.
• Используйте гибкие динамически распределяемые данные вместо массивов фиксированного размера. Массив "больший, чем наибольший массив, который мне когда-либо потребуется" приводит к ошибкам и нарушению безопасности (см. рекомендацию 77). Массивы можно использовать только тогда, когда размеры данных фиксированы и известны во время компиляции.
• Следует точно знать сложность используемого алгоритма. Не забывайте о такой ловушке, как линейный алгоритм, который вызывает другую линейную операцию, что в результате делает алгоритм квадратичным (см., например, рекомендацию 81).
• По возможности используйте линейные или более быстрые алгоритмы. Идеальны алгоритмы с константной сложностью, такие как push_back или поиск в хэш-таблице (см. рекомендации 76 и 80). Неплохи алгоритмы со сложностью O(log N), такие как операции с контейнерами set/map и lower_bound или upper_bound с итераторами произвольного доступа (см. рекомендации 76, 85 и 86). Допустима линейная сложность O(N), как, например, у vector::insert или for_each (см. рекомендации 76, 81 и 84).
• Пытайтесь избежать применения алгоритмов с более чем линейной сложностью, где это возможно. Например, по умолчанию следует затратить определенные усилия на поиск замены имеющегося алгоритма со сложностью O(N log N) или O(N) (если таковая возможна), чтобы избежать непропорционального падения производительности при существенном увеличении объема данных. Так, именно в этом заключается основная причина, по которой в рекомендации 81 советуется предпочитать операции с диапазонами (которые обычно линейны) их копиям для работы с отдельными элементами (которые обычно квадратичны, так как одна линейная операция вызывает другую линейную операцию; см. пример 1 в рекомендации 81).
• Никогда не используйте экспоненциальный алгоритм, если только вы не "приперты к стене" и не имеете другого выхода. Ищите, не жалея сил, альтернативу, прежде чем прибегнуть к экспоненциальному алгоритму, где даже небольшое увеличение данных приводит к существенному падению производительности.
Во-вторых, после того как замеры покажут, что оптимизация действительно нужна и важна, в особенности при росте данных, сконцентрируйте усилия на снижении O-сложности, а не на микрооптимизациях наподобие экономии одного сложения.
Итак, предпочтительно использовать линейные (или лучшие) алгоритмы там, где только это возможно. Избегайте, где можете, алгоритмов с более чем линейной сложностью, и уж тем более - экспоненциальных.
Ссылки
[Bentley00] §6, §8, Appendix 4 • [Cormen01] • [Kernighan99] §7 • [Knuth97a] • [Knuth97b] • [Knuth98] • [McConnell93) §5.1-4, §10.6 • [Murray93] §9.11 • [Sedgewick98] • [Stroustrup00] §17.1.2
8. Не оптимизируйте преждевременно
Резюме
Как гласит пословица, не подгоняйте скачущую лошадь. Преждевременная оптимизация непродуктивна и быстро входит в привычку. Первое правило оптимизации: не оптимизируйте. Второе правило оптимизации (только для экспертов): не оптимизируйте ни в коем случае. Семь раз отмерь, один раз оптимизируй.
Обсуждение
В [Stroustrup00] §6 имеется замечательная цитата:
Преждевременная оптимизация - корень всех бед.
- Дональд Кнут (Donald Knuth) [цитирует Хоара (Hoare)]
С другой стороны, мы не можем игнорировать эффективность.
- Ион Бентли (Jon Bentley)
Хоар и Кнут совершенно правы (см. рекомендацию 6 и эту). Но прав и Бентли (рекомендация 9).
Мы определяем преждевременную оптимизацию как усложнение дизайна или кода (что делает его менее удобочитаемым) во имя повышения производительности, когда усилия не оправдываются доказанной необходимостью повышения производительности (например, реальными измерениями и сравнением с поставленной целью). Зачастую такие усилия вообще не приводят к повышению производительности программы.
Всегда помните:
Гораздо, гораздо проще сделать корректную программу быстрой, чем быструю - корректной.
Поэтому по умолчанию не концентрируйтесь на том, чтобы сделать код быстрым, в первую очередь его надо сделать максимально понятным и удобочитаемым (рекомендация 6). Ясный код проще написать корректно, проще понять, проще переделать - и проще оптимизировать. Усложнения, включая оптимизацию, всегда можно внести позже - и только при необходимости.
Имеются две основные причины, почему преждевременная оптимизация зачастую не делает программу быстрее. Во-первых, общеизвестно, что программисты обычно плохо представляют, какой код будет быстрее или меньше по размеру, и где будет самое узкое место в разрабатываемом коде. В число таких программистов входят и авторы этой книги, и вы. Подумайте сами - современные компьютеры представляют собой исключительно сложные вычислительные модели, зачастую с несколькими работающими параллельно процессорами, глубокой иерархией кэширования, предсказанием ветвления, конвейеризацией и многим- многим другим. Компилятор, находящийся над всем этим аппаратным обеспечением, преобразует ваш исходный код в машинный, основываясь на собственном знании аппаратного обеспечения и его особенностей, с тем чтобы этот код в максимальной степени использовал все возможности аппаратного обеспечения. Над компилятором находитесь вы, с вашими представлениями о том, как должен работать тот или иной код. У вас практически нет шансов внести такую микрооптимизацию, которая в состоянии существенно повысить производительность генерируемого интеллектуальным компилятором кода. Итак, оптимизации должны предшествовать измерения, а измерениям должна предшествовать выработка целей оптимизации. Пока необходимость оптимизации не доказана - вашим приоритетом №1 должно быть написание кода для человека. (Если кто-то потребует от вас оптимизации кода - потребуйте доказательств необходимости этого.)
Во-вторых, в современных программах все больше и больше операций, скорость работы которых ограничена не процессором, а, например, работой с памятью, диском или сетью, ожиданием ответа от Web-сервиса или базы данных. В лучшем случае оптимизация такого кода приведет к тому, что ваша программа будет быстрее ожидать. Это также означает, что программист зря тратит драгоценное время на улучшение того, что не требует улучшений, вместо того, чтобы заняться тем, что действительно требует его вмешательства.
Само собой разумеется, настанет день, когда вам действительно придется заняться оптимизацией вашего кода. Когда вы займетесь этим - начните с оптимизации алгоритмов (рекомендация 7) и попытайтесь инкапсулировать оптимизацию (например, в пределах функции или класса, см. рекомендации 5 и 11), четко указав в комментариях причину проводимой оптимизации и ссылку на использованный алгоритм.
Обычная ошибка новичка состоит в том, что когда он пишет новый код, то - с гордостью! - старается сделать его оптимальным ценой понятности. Чаще всего это приводит к милям "спагетти" (говоря проще - к "соплям" в программе), и даже корректно работающий код становится очень трудно читать и модифицировать (см. рекомендацию 6).
Передача параметров по ссылке (рекомендация 25), использование префиксной формы операторов ++ и -- (рекомендация 28) или подобных идиом, которые при работе должны естественным образом "стекать с кончиков ваших пальцев", преждевременной оптимизацией не являются. Это всего лишь устранение преждевременной пессимизации (рекомендация 9).
Примеры
Пример. Ирония использования inline. Это простейшая демонстрация скрытой стоимости преждевременной микрооптимизации. Профайлеры легко могут сказать вам (исследовав количество вызовов функций), какие функции должны быть встраиваемыми, но не являются таковыми. Но те же профайлеры не в состоянии подсказать, какие встраиваемые функции не должны быть таковыми. Очень многие программисты используют "встраивание по умолчанию" во имя оптимизации, почти всегда за счет большей связности программы достигая в лучшем случае весьма сомнительных результатов. (Сказанное означает, что делать функцию встраиваемой должен компилятор, а не программист. См. [Sutter00], [Sutter02] и [Sutter04].)
Исключения
Когда вы пишете библиотеки, трудно предсказать, какие операции будут использоваться в критичном по отношению к производительности коде. Но даже автор библиотеки должен испытать свой код на производительность в разнообразных пользовательских приложениях перед тем, как усложнять свой код оптимизацией.
Ссылки
[Bentley00] §6 • [Cline99] §13.01-09 • [Kernighan99] §7 • [Lakos96] §9.1.14 • [Meyers97] §33 • [Murray93] §9.9-10, §9.13 • [Stroustrup00] §6 introduction • [Sutter00] §30, §46 • [Sutter02] §12 • [Sutter04] §25
9. Не пессимизируйте преждевременно
Резюме
То, что просто для вас, - просто и для кода. При прочих равных условиях, в особенности - сложности и удобочитаемости кода, ряд эффективных шаблонов проектирования и идиом кодирования должны естественным образом "стекать с кончиков ваших пальцев" и быть не сложнее в написании, чем их пессимизированные альтернативы. Это не преждевременная оптимизация, а избежание излишней пессимизации.
Обсуждение
Избежание преждевременной оптимизации не влечет за собой снижения эффективности. Под преждевременной пессимизацией мы подразумеваем написание таких неоправданных потенциально неэффективных вещей, как перечисленные ниже.
• Передача параметров по значению там, где применима передача параметров по ссылке (рекомендация 25).
• Использование постфиксной версии ++ там, где с тем же успехом можно воспользоваться префиксной версией (рекомендация 28).
• Использование присваивания в конструкторах вместо списка инициализации (рекомендация 48).
Не является преждевременной оптимизацией снижение количества фиктивных временных копий объектов, в особенности во внутренних циклах, если это не приводит к усложнению кода. В рекомендации 18 поощряется максимально локальное объявление переменных, но там же приведено и описание исключения - возможный вынос переменных из цикла. В большинстве случаев такое действие не усложняет понимание предназначения кода, более того, может помочь пояснить, что именно делается в цикле и какие вычисления являются его инвариантами. Конечно же, предпочтительно использовать готовые алгоритмы вместо написания явных циклов (рекомендация 84).
Два важных способа усовершенствования программы, которые делают ее одновременно и яснее, и эффективнее - это использование абстракций (см. рекомендации 11 и 36) и библиотек (рекомендация 84). Например, использование vector, list, map, find, sort и других возможностей стандартной библиотеки, стандартизированных и реализованных экспертами мирового класса, не только делают ваш код яснее и легче понимаемым, но зачастую и более быстрым.
Избежание преждевременной пессимизации становится особенно важным, когда вы пишете библиотеку. При этом вы обычно не знаете контекста использования вашей библиотеки, а поэтому должны суметь сбалансировать эффективность и возможность повторного использования. Не забывайте уроков рекомендации 7 - следует куда больше заботиться о масштабируемости, чем о выигрыше пары тактов процессора.
Ссылки
[Keffer95] pp. 12-13 • [Stroustrup00] §6 introduction • [Sutter00] §6
10. Минимизируйте глобальные и совместно используемые данные
Резюме
Совместное использование вызывает споры и раздоры. Избегайте совместного использования данных, в особенности глобальных данных. Совместно используемые данные усиливают связность, что приводит к снижению сопровождаемости, а зачастую и производительности.
Обсуждение
Это утверждение носит более общий характер, чем более узкое требование рекомендации 18.
Следует избегать данных со внешним связыванием в области видимости пространства имен или представляющих собой статические члены классов. Их применение усложняет логику программы и приводит к тесной связи между различными (и, что еще хуже, отдаленными) частями программы. Совместно используемые данные делают менее эффективным тестирование модулей, поскольку корректность фрагмента кода, использующего общие данные, обусловлена историей изменения этих данных, а кроме того, обуславливает функционирование некоторого, пока неизвестного, кода, который будет использовать эти данные позже.
Имена объектов в глобальном пространстве имен приводят к его дополнительному засорению.
Если вам никак не обойтись без глобальных объектов, объектов в области видимости пространства имен или статических членов классов, убедитесь в их корректной инициализации. Порядок инициализации таких объектов из разных единиц компиляции не определен, поэтому для корректной работы в таком случае требуются специальные методики (см. прилагаемые ссылки). Правила порядка инициализации достаточно сложны, поэтому лучше их избегать; но если вы все же вынуждены иметь с ними дело, то должны хорошо их изучить и использовать с величайшей осторожностью.
Объекты, находящиеся в области видимости пространств имен, статические члены или совместно используемые разными потоками или процессами, снижают уровень распараллеливания в многопоточных и многопроцессорных средах, и часто являются узким местом с точки зрения производительности и масштабируемости (см. рекомендацию 7). Старайтесь избавиться от совместного использования данных; используйте вместо него средства коммуникации (например, очередь сообщений).
Предпочтительно обеспечить низкую связность и минимизировать взаимодействие классов (см. [Cargill92]).
Исключения
Такие средства уровня программы, как cin, cout и cerr, являются специализированными и реализуются специальным образом. Фабрика должна поддерживать реестр функций, которые должны вызываться для создания данного типа, и такой реестр обычно один на всю программу (тем не менее предпочтительно, чтобы он был внутренним объектом по отношению к фабрике, а не глобальным совместно используемым объектом; см. рекомендацию 11).
Код, в котором объект совместно используется разными потоками, должен обеспечить сериализацию обращений к такому объекту (см. рекомендацию 12 и [Sutter04c]).
Ссылки
[Cargill92] pp. 126, 136, 169-173 • [Dewhurst03] §3 • [Lakos96] §2.3.1 • [McConnell93] §5.1-4 • [Stroustrup00] §C.10.1 • [Sutter00] §47 • [Sutter02] §16, Appendix A • [Sutter04c] • [SuttHysl03]