6.1. Представление сложных типов данных в памяти
Оперативную память компьютера можно представить как набор пронумерованных ячеек - слов. Размер слова зависит от конкретной модели компьютера. Например, на IBM PC слово имеет размер один байт. Это означает, что байт – минимальная единица памяти, имеющая свой адрес (порядковый номер). На других типах компьютеров размер слова может меняться. У суперкомпьютеров слово может достигать четырех байт.
Все работающие на компьютере программы должны как можно быстрее вычислять адреса отдельных элементов переменных, относящихся к сложным типам данных (скажем, элементов массива или полей записи). В массиве адрес j-го элемента будет равен
j=i0+js, |
( 3.0) |
где i0 – адрес первого элемента массива, s - число слов памяти, занимаемых одним элементом.
Для упрощения вычислений желательно устранить медленную операцию умножения. Поэтому оптимальный случай - s=1 или s=int(s).
Для достижения указанного
оптимального варианта применяют
выравнивание данных (padding).
При выравнивании s
округляют до ближайшего большего целого
(обозначается
).
Предположим, что размер слова на нашем
компьютере равен двум байтам, а размер,
занимаемый одним элементом массива -
пять байт или 2,5 слова. Выравнивание
приведет к тому, что под каждый элемент
будет выделено 3 слова, а "полслова"
останутся незанятыми (Рис. 6 .13).
Рис. 6.13. Выравнивание данных.
Очевидное преимущество выравнивания – повышение скорости работы программы, так как умножение на целое число выполняется в сотни раз быстрее, чем на вещественное. Особенно быстро выполняется умножение на числа, являющиеся степенями двойки, так как для них умножение можно заменить поразрядным сдвигом. Недостаток выравнивания – часть памяти остается неиспользуемой и фактически пропадает впустую.
Коэффициент использования памяти u равен
|
( 3.0) |
В идеале u=1 (вся память используется).
Итак, выравнивать данные или нет? Нужно рассмотреть следующие соображения:
1. Выравнивание требует лишней памяти 2. Отсутствие выравнивания требует организации доступа к части слова 3. Доступ к части слова приводит к заметному увеличению объема программы.
6.2. Упаковка элементов сложных типов данных
Как правило, организация доступа к части слова – дело хлопотное и небыстрое. Из-за этого выравнивание чаще всего применяется. Но бывают ситуации, когда необходимо использовать каждый байт памяти. Если s<0.5, то в одном слове поместится более одного элемента массива. Тогда удастся выполнить упаковку (packing) нескольких элементов в одно слово. В этом случае коэффициент использования памяти равен
|
( 3.0) |
,где n – число элементов массива, умещающихся в одном слове.
Для доступа к i-му элементу упакованного массива программе придется выполнить следующие действия:
1. Вычислить адрес слова j = i DIV n. 2. Вычислить смещение элемента внутри этого слова k = i MOD n.
Чтобы массив или запись упаковывались, при их описании указывается ключевое слово PACKED:
TA=PACKED ARRAY …
TR=PACKED RECORD …