Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

В общем случае лекарства от пробуксовки нет. Большую часть времени блоки памяти выделяются из программы динамического распределения памяти Delphi. Кроме того, программист не может управлять конкретным расположением блоков памяти. Может случиться, например, что связанные блоки данных хранятся в разных страницах. (Здесь под словом "связанные" понимается блоки памяти, данные из которых, вероятно, будут считываться одновременно, поскольку сами данные связаны.) Одним из методов снижения риска возникновения пробуксовки является использование отдельных куч для выделения памяти для структур и данных разных приложений. Но алгоритм такого выделения в настоящей книге не приводится.

Рассмотрим пример. Предположим, что мы выделили память

под элементы объекта TList. Каждый из элементов содержит, по крайней мере, одну строку, память для которой выделяется из кучи (например, мы пользуемся 32-разрядным Delphi и элемент использует длинные строки). А теперь представим себе, что приложение уже проработало некоторое время, и элементы в объекте TList неоднократно добавлялись и удалялись. Вполне возможно, что экземпляр TList, его элементы и строки элементов распределены по разным страницам памяти. Теперь при последовательном считывании элементов объекта TList от начала до конца приложение будет обращаться ко многим страницам, что приведет к активному обмену страницами между диском и памятью. Если количество элементов достаточно мало, все страницы, относящиеся к данному приложению, могут находиться в памяти. Но если в объекте TList элементов насчитывается несколько миллионов, при их считывании приложение может породить состояние пробуксовки.

Локальность ссылок

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

Например, массив записей имеет высокий уровень локальности ссылок. Так, элемент с индексом 1 в памяти находится рядом с элементом с индексом 2 и т.д. Если приложение последовательно считывает все записи массива, локальность ссылок будет очень высокой. Обмен страницами между диском и памятью будет минимальным. Экземпляр объекта TList, содержащий указатели на тот же тип записей, несмотря на то, что это тоже массив, фактически содержащий те же данные, будет иметь низкий уровень локальности ссылок. Как было показано ранее, каждый элемент такого массива может находиться на отдельной странице. Таким образом, последовательное считывание элементов вызовет обмен данными между диском и памятью. Связанные списки (см. главу 3) также обладают низким уровнем локальности ссылок.

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

До сих пор мы говорили о локальности ссылок в смысле расстояния ("один объект находится в памяти рядом с другим объектом"), но локальность ссылок можно трактовать и по отношению ко времени. Это означает, что если элемент недавно использовался, он скоро будет использоваться снова, или, скажем, элемент X всегда используется вместе с элементом Y. Воплощением локальности ссылок во времени является кэш-память. Кэш-память (cache) представляет собой небольшой блок памяти для некоторого процесса, содержащий элементы, которые использовались недавно. При

каждом использовании элемента он копируется в кэш-память. Если кэш заполнен, при удалении элементов применяется алгоритм с удалением наиболее давно использованных элементов (least recently used, LRU), по которому элемент, который давно не использовался, замещается недавно использованным элементом. Таким образом, кэш-память содержит несколько близких в пространственном смысле элементов, которые, помимо всего прочего, близки и в смысле времени их использования.

Обычно кэш-память применяется для элементов, которые хранятся на медленных устройствах. В качестве классического примера можно привести дисковый кэш. Тем не менее, теоретически кэш виртуальной памяти мог бы работать точно таким же образом, особенно с приложениями, которые требуют большого объема памяти и используются на вычислительных машинах с небольшими объемами ОЗУ.

Кэш процессора

Оборудование, на котором мы все программируем и запускаем приложения, использует кэш в памяти. Так, например, на компьютере автора этой книги применяется высокоскоростная кэш-память объемом 512 Кб между процессором и его регистрами и основной памятью (объем которой на том же компьютере составляет 192 Мб). Эта высокоскоростная кэш-память представляет собой буфер: когда процессору необходимо считать из памяти определенные данные, кэш проверяет, есть ли эти данные в памяти, и если требуемых данных нет, считывает их. Таким образом, данные, доступ к которым осуществляется часто (обладающие высоким уровнем временной локальности ссылок) будут большую часть времени находиться в кэш-памяти.

Выравнивание данных

Еще один вопрос, касающийся оборудования, о котором следует помнить, связан с выравниванием данных. Современные процессоры устроены таким образом, что они считывают данные отдельными кусками по 32 бита. Кроме того, эти куски всегда выравниваются по границе 32 бит. Это означает, что адреса памяти, передаваемые от процессора в кэш-память, всегда делятся на четыре без остатка (4 байта = 32 бита), т.е. два младших бита адреса являются нулевыми. Когда 64-и более разрядные процессоры станут достаточно распространенными, адресация превратится в 64-битную (или 128-битную) и выравнивание будет производиться уже по новой границе.

Какое отношение имеет выравнивание данных к приложениям? При программировании необходимо убедиться, что переменные типа longint и указатели выровнены по четырехбайтовой или 32-битовой границе. Если они переходят через границу 4 байт, процессору придется выдать две команды на считывание кэш-памяти: первая команда для считывания первой части, а вторая - второй части. Затем процессору потребуется соединить две части значения и отбросить ненужные биты. (В ряде процессоров 32-битные значения всегда должны выравниваться по границе 32 бит. В противном случае возникает ошибка нарушения доступа. К счастью, процессоры Intel не требуют этого, что, в свою очередь, провоцирует программистов на некоторую небрежность.)

Всегда убеждайтесь в том, что 32-битные значения выровнены по границе 32 бит, а 16-битные значения - по границе 16 бит. Для увеличения быстродействия следует убедиться, что 64-битные значения (например, переменные типа double) выровнены по 64-битной границе.

Все это звучит достаточно сложно, но в действительности программисту очень помогает компилятор Delphi. В результате особое внимание нужно уделять только объявлению типа record. Все глобальные и локальные атомарные переменные (т.е. переменные простых типов) выравниваются должным образом. Если тип выравнивания не установлен, то 32-разрядный компилятор Delphi будет автоматически выравнивать и поля типа record. Для этого он добавляет незначащие байты. В 16-разрядной версии автоматическое выравнивание переменных атомарных типов не используется, поэтому будьте осторожны.