Проектирование программ для эффективной работы с кэшем

Эффективное использование памяти означает, что она должна быть полностью занята нужными командами и данными.

В процессорах реализована иерархия памяти:
  1. Конвейер команд и регистры процессора
  2. Кэш команды и данных, а также соответствующие таблицы преобразования адресов
  3. RAM
  4. Диск

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

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

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

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

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

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

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

На следующем рисунке приведены примеры рационального и нерационального программирования на уровне процедур. В первом варианте порядок процедур в программе отражает лишь способ мышления автора. Первая функция PriSub1 содержит точку входа в программу. Она всегда вызывает вспомогательные функции PriSub2 и PriSub3. Дополнительные функции SecSub1 и SecSub2 предназначены для выполнения некоторых редко встречающихся задач. Функции обработки ошибок ErrSub1 и ErrSub2 вызываются только в исключительных случаях.

Рис. 1. Компактность ссылок. В верхней области рисунка продемонстрировано, что двоичная программа упакована с низким уровнем компактности ссылок. Инструкции функции PriSub1 расположены в начале двоичного исполняемого кода. За ними расположены инструкции функций SecSub1, ErrSub1, PriSub2, SecSub2, ErrSub2 и PriSub3. В данном случае инструкции функций PriSub1, SecSub1 и ErrSub1 расположены в первой странице памяти. Инструкции функций PriSub2, SecSub2, ErrSub2 расположены во второй странице, а инструкции функции PriSub3 - в третьей странице памяти. Функции SecSub1 и SecSub2 используются редко, а функции ErrSub1 и ErrSub2 применяются лишь в исключительных ситуациях. Следовательно, эта программа упакована таким образом, что получился низкий уровень компактности ссылок. В результате программа занимает излишне много памяти. В нижней области рисунка показан альтернативный способ размещения программы в памяти. Функции PriSub1, PriSub2 и PriSub3 расположены в первой странице памяти. Функции PriSub3, SecSub1, SecSub2 и ErrSub1 расположены во второй странице памяти. Функция ErrSub2 занимает третью страницу памяти. Поскольку функция ErrSub2 практически никогда не используется, объем памяти, необходимый для работы программы, уменьшится на одну страницу.
Компактность ссылок

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

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

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