Читать «Фундаментальные алгоритмы и структуры данных в Delphi» онлайн - страница 18

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

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

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

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

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

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