считывание кэш-памяти: первая команда для считывания первой части, а вторая - второй части. Затем процессору потребуется соединить две части значения и отбросить ненужные биты. (В ряде процессоров 32-битные значения всегда должны выравниваться по границе 32 бит. В противном случае возникает ошибка нарушения доступа. К счастью, процессоры Intel не требуют этого, что, в свою очередь, провоцирует программистов на некоторую небрежность.)
Всегда убеждайтесь в том, что 32-битные значения выровнены по границе 32 бит, а 16-битные значения - по границе 16 бит. Для увеличения быстродействия следует убедиться, что 64-битные значения (например, переменные типа double) выровнены по 64-битной границе.
Все это звучит достаточно сложно, но в действительности программисту очень помогает компилятор Delphi. В результате особое внимание нужно уделять только объявлению типа record. Все глобальные и локальные атомарные переменные (т.е. переменные простых типов) выравниваются должным образом. Если тип выравнивания не установлен, то 32-разрядный компилятор Delphi будет автоматически выравнивать и поля типа record. Для этого он добавляет незначащие байты. В 16-разрядной версии автоматическое выравнивание переменных атомарных типов не используется, поэтому будьте осторожны.
Автоматическое выравнивание переменных иногда может ввести программиста в заблуждение. Если, например, объявлен следующий тип record в 32-разрядной версии Delphi, каким будет результат выполнения операции sizeof(TMyRecord)?
type
TMyRecord = record
aByte : byte;
aLong : longint;
end;
Многие без сомнения ответят, что, дескать, 5 байт (и это было бы правильно для Delphi1). Однако верным ответом будет 8 байт. Компилятор автоматически вставит три байта между полем aByte и along, просто чтобы выровнять последнее поле по границе 4 байт.
Если тип record объявить следующим образом:
type
TMyRecord = packed record
aByte : byte;
aLong : longint;
end;
то функция sizeof(TMyRecord) даст результат 5. Однако в этом случае доступ к полю aLong потребует больше времени, чем в предыдущем примере, поскольку значение поля будет переходить через границу 4 байт. Следовательно, правило можно сформулировать так: если используется ключевое слово packed, поля в записи должны располагаться таким образом, чтобы данные были выровнены по границе 4 байт. Сначала объявите 4-байтные поля, а затем уже все остальные. Это правило применяется во всех кодах, приведенных в настоящей книге. И еще одно, никогда не угадывайте размер записи, а пользуйтесь для этого функцией sizeof.
Кстати, следует знать, что диспетчер динамического распределения памяти Delphi также помогает выполнять выравнивание данных. Он выравнивает не только 4-байтные значения по границе 4 байт, но и 8-байтные значения по границе 8 байт. Это имеет большое значение для переменных типа double: операции с числами с плавающей запятой выполняются быстрее, если переменные типа double выровнены по границе 8 байт. Если задачи по программированию связаны с использованием большого количества числовых переменных, убедитесь, что поля типа double в записях выровнены по границе 8 байт.
Пространство или время
Чем больше мы изучаем, разрабатываем и анализируем алгоритмы, тем чаще мы сталкиваемся с одним универсальным законом вычислительной техники: быстрые алгоритмы, как правило, требуют больше памяти. Таким образом, для использования быстрого алгоритма необходимо располагать большим объемом памяти.
Рассмотрим это на простом примере. Предположим, что требуется разработать алгоритм, который бы определял количество установленных бит в байте. Первый вариант алгоритма показан в листинге 1.3.
Листинг 1.3. Первоначальная функция определения количества установленных битов в байте
function CountBitsl(B : byte):byte;
begin
Result := 0;
while (B <> 0) do
begin
if Odd(B) then
inc(Result);
B := B shr 1;
end;
end;
Как видите, в этой функции не используются промежуточные переменные. Она просто считает установленные биты путем деления значения на 2 (сдвиг целого значения на один бит вправо эквивалентно делению на 2) и определения количества полученных нечетных результатов. Цикл завершается, когда будет получено значение 0, поскольку в этом случае очевидно, что установленных битов больше нет. Значение О большого для приведенного алгоритма зависит от количества установленных битов в параметре, и в худшем случае внутренний цикл будет выполнен восемь раз. Таким образом, это алгоритм класса O(n).
Описанный алгоритм вполне очевиден и, если не принимать во внимание возможность его реализации на языке ассемблера, улучшить его практически невозможно.
Тем не менее, давайте рассмотрим назначение алгоритма с другой точки зрения. В качестве входного значения функция принимает 1-байтный параметр, с помощью которого можно передать всего 256 значений. В таком случае, почему бы нам заранее не вычислить все возможные ответы и не записать их в статический массив? Реализация нового алгоритма приведена в листинге 1.4.
Листинг 1.4. Улучшенная функция определения количества установленных битов в байте const
BitCounts : array [0..255] of byte =
(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
