Эффективное использование памяти
Память — один из самых дорогостоящих компьютерных ресурсов, которого вечно не хватает; огромное количество плохих программ возникло из попыток выжать все, что можно, из того немногого, что имелось в наличии. Небезызвестная "проблема 2000 года" зачастую причисляется к разряду именно таких проблем: когда память была действительно буквально на вес золота, потратить два байта на число 19 считалось непозволительной роскошью. Действительно ли память является главной причиной проблемы или нет, — возможно, все беды возникли из-за перенесения наших бытовых привычек (мы нечасто указываем в документах, к какому веку они относятся, — это и так очевидно) на программы, — но приведенный пример отлично демонстрирует всю опасность недальновидной оптимизации.
В любом случае, времена меняются, теперь и оперативная память, и внешние носители информации стали просто удивительно дешевыми. Таким образом, главный принцип оптимизации использования памяти — тот же, что и в увеличении быстродействия: не беспокойтесь понапрасну.
Однако и сейчас могут возникнуть ситуации, когда вопрос используемого
пространства играет существенную роль. Если программе не хватает имеющейся
оперативной памяти, то некоторые ее части (страницы),, выгружаются на диск, а это отрицательно сказывается на производительности. Часто приходится видеть, насколько расточительно относятся к памяти новые версии программ. Как ни печально, но такова сегодняшняя реальность: обновление программного обеспечения часто влечет за собой покупку дополнительной памяти.
Используйте минимально возможный размер типа данных. Первый шаг к более эффективному использованию места — попытаться с минимальными изменениями лучше распределить существующую память, используя, например, минимальные из возможных типов данных. Эта экономия может означать замену int на short, если данные это позволяют, в частности такое представление используется для координат в системах двумерной графики, поскольку 16 битов, по-видимому, достаточно для любых диапазонов экранных координат. Можно экономить память и заменой double на float, но при этом надо опасаться потери точности, ведь float содержит, как правило, только 6 или 7 десятичных знаков.
В описанных и аналогичных им случаях в программу почти наверняка придется внести и другие соответствующие изменения, самым оче-видным из которых будет замена спецификаторов формата в printf и, что особенно важно, в scanf.
Логическим расширением этого подхода является кодирование информации в байте или даже в нескольких битах. Не используйте битовые поля C/C++; они ухудшают переносимость и нередко ведут к неоднозначному и неэффективному коду. Вместо этого поместите нужные операции в функции, которые будут считывать и устанавливать отдельные биты внутри слова или массива слов с помощью сдвигов или битовых масок. Такие функции возвращают группу последовательных битов из середины слова:
Если эти функции окажутся слишком медленными, их можно улучшить с помощью
технологий, описанных ранее. В C++ переопределение операторов позволяет
сделать доступ к битам похожим на простое индексирование.
Не храните то, что можете без труда вычислить. Надо сказать, что подобные изменения — не самые эффективные; они похожи на тонкую настройку кода. Глобальные улучшения, как правило, достигаются только подбором более удачной структуры данных и соответствующим изменением алгоритма. Приведем пример. Много лет назад к одному из нас обратился за помощью наш коллега: он пытался производить некоторые вычисления над матрицей, которая была так велика, что для того, чтобы она уместилась в памяти, приходилось перезагружать компьютер, сильно урезая операционную систему. Очень хотелось найти какую-нибудь альтернативу, потому что работать в подобном режиме было ужасно неудобно. Мы сразу попросили рассказать, что же представляет собой эта матрица, и выяснили, что она содержала целые числа, большая часть из которых была нулями' . И лишь менее 5 % элементов матрицы были отличны от нуля. Подобная структура тут же навела нас на мысль о представлении, в котором хранились бы только ненулевые элементы матрицы, а доступ к каждому элементу m[i][j] заменялся бы вызовом функции m(i, j ). Существует несколько способов хранить данные. Наверное, самый простой из них — это массив указателей, по одному на столбец, каждый из которых указывает на компактный массив номеров строк и соответствующих значений. При такой организации на каждый ненулевой элемент тратится больше места, однако суммарное место все же экономится; доступ к каждому элементу получается более медленным, но это все равно быстрее, чем перезагружать машину. Наш коллега принял наше предложение и был вполне доволен результатом.
Аналогичный подход мы использовали и при решении современного варианта этой проблемы. Некая система проектирования должна была представлять данные о виде поверхности и силе радиосигнала, относящиеся к достаточно большим площадям (от 100 до 200 километров в поперечнике), с разрешением в 100 метров. Сохранение этих данных в одном большом прямоугольном массиве неизбежно привело бы к переполнению памяти на машинах, для которых эта система разрабатывалась, и, соответственно, к активному дисковому обмену. Однако было ясно, что для достаточно больших территорий данные о поверхности Земли и о силе сигнала будут одинаковы, так что для решения проблемы можно было применить иерархическое представление данных, при котором регионы с одинаковыми параметрами хранились в одном элементе.
Вариации на эту тему встречаются на практике достаточно часто, и их проявления различны, но для решения можно применять один и тот же подход: храните одинаковые значения в неявном виде или просто в компактной форме, а время и пространство тратьте на оставшиеся значения. Если одинаковые данные действительно встречаются в вашей задаче достаточно часто, вы сможете добиться впечатляющих результатов.
Программа должна быть организована таким образом, чтобы специфическое представление данных сложного типа было спрятано в классе или в наборе функций, оперирующих внутренними типами данных. Подобная предосторожность даст гарантию, что возможные изменения в представлении данных не затронут остальную часть программы.
Проблемы эффективного использования места иногда проявляются и по отношению к внешнему представлению информации — и к преобразованию, и к хранению. В общем и целом, всегда, когда это возможно, информацию лучше хранить в текстовом виде, а не в каком-то двоичном представлении. Текст хорошо переносится, удобно читается; для его обработки создано великое множество инструментов; двоичное же представление лишено этих преимуществ. Аргументом в защиту двоичных данных служит обычно "скорость", однако к нему стоит относиться с изрядной долей скептицизма, поскольку различия между текстовой и двоичной формой, как правило, не столь глобальны.
Более эффективное распределение пространства зачастую покупается ценой увеличения времени исполнения программы. Некое приложение должно было передавать большой рисунок из одной программы в другую. Рисунки в достаточно простом формате РРМ занимали, как правило, около мегабайта, так что мы подумали, что было бы гораздо быстрее кодировать их для передачи в сжатом формате GIF, — тогда файлы получались бы размером примерно 50 килобайтов. Однако кодирование и декодирование GIF занимало столько времени, что это сводило на нет всю экономию от передачи файла меньшего размера, то есть мы ничего не выгадывали. Код для обработки формата GIF состоял примерно из 500 строк, а для РРМ — из 10. Таким образом, для облегчения поддержки кода мы отказались от преобразования в GIF, и программа до сих пор работает с форматом РРМ. Естественно, если бы речь шла о передаче файлов по сети, то предпочтение было бы отдано формату GIF.
