1 марта 2013 г.

Запись в качестве ключа TDictionary

В данной статье мы рассмотрим один тонкий момент при использования записи в качестве ключа для TDictionary.

Следуя общепринятым практикам разработки ПО, попробуем реализовать шаблон проектирования Коллекция объектов (Identity Map), с помощью TDictionary. В качестве ключа будем использовать идентификатор сущности, а в качестве значения объект сущности. Идентификаторы сущностей могут быть как простые, так и составные. Для составных будем использовать запись — идентификатор должен быть объектом-значением (Value Object). В примере мы создадим коллекцию объектов «Пользователь» для ЛОЦМАН:PLM.

В Лоцмане есть два вида пользователей: пользователи собственно PLM-системы и пользователи Workflow. Оба типа пользователей имеют одинаковые атрибуты. С точки зрения большинства компонентов пользовательского интерфейса между ними нет никакой разницы. Знать вид пользователя нужно только при вызове методов сервера приложений, при этом, при необходимости, для пользователя одного вида можно получить такого же пользователя другого вида. Поэтому мы реализуем одну сущность «Пользователь» и для PLM-системы, и для Workflow. У сущности будет составной идентификатор, в котором, кроме идентификатора пользователя ЛОЦМАН:PLM, указан вид пользователя. Получается примерно такой код:
type
    TUserID = record
    private
        FUserID: Integer;
        FIsWFUser: Boolean;
    public
        constructor Create(AUserID: Integer; 
            AIsWFUser: Boolean);
        property UserID: Integer read FUserID;
        property IsWFUser: Boolean read FIsWFUser;
    end;

constructor TUserID.Create(AUserID: Integer;
    AIsWFUser: Boolean);
begin
    FUserID := AUserID;
    FIsWFUser := AIsWFUser;
end;

type
    TUser = class(TEntityBase)
    private
        FUserID: TUserID;
    public
        property UserID: TUserID read FUserID;
    end;

var
    UserMap: TObjectDictionary<TUserID, TUser>;

begin
    UserMap := TObjectDictionary<TUserID, TUser>.Create(
        [doOwnsValues]);
end.

Попробуем добавить в коллекцию один объект и затем получить его:
procedure Test;
var
    UserID1: TUserID;
    UserID2: TUserID;
    Entity: TUser;
begin
    UserID1 := TUserID.Create(1, True);
    UserMap.Add(UserID1, TUser.Create());

    UserID2 := TUserID.Create(1, True);
    Entity := UserMap.Items[UserID2];
    // EListError: Item not found
end;

Как это ни удивительно, но такой простой код не работает. При попытке получить объект из коллекции, выбрасывается исключение EListError с сообщением «Item not found». В чем дело?

Причина кроется в выравнивании полей записи, из-за чего размер записи TUserID составляет 8 байт, в то время как используются только 5 байт, а в 3-х оставшихся хранится мусор. Используемый по умолчанию TComparer<T> сравнивает записи с помощью CompareMem(@Left, @Right, SizeOf(TUserID)), из-за чего в сравнение попадает мусор.

Решений проблемы, как обычно, может быть несколько:
  1. Вместо используемого по умолчанию TComparer<T> написать свой класс, который будет корректно сравнивать записи, не обращая внимания на мусор внутри.
  2. Использовать в записи типы данных, размер которых кратен используемому выравниванию. В этом случае в записи не будет пустых мест. Например, заменить Boolean на LongBool.
  3. Убрать случайные значения из неиспользуемых байт записи, например, заполнив их нулями.
  4. Использовать для записи ключевое слово packed. В этом случае для записи не будет использоваться выравнивание полей. Несмотря на свою простоту, этот способ самый неэффективный. Например, в описанном случае размер записи будет 5 байт. Записи будут размещены в массиве друг за другом. Для получения поля UserID из второй записи процессор загрузит в регистр 4 байта по смещению 4 в массиве, выделит из них последний байт, затем загрузит в регистр 4 байта по смещению 8, выделит из них первые 3 байта, затем объединит полученные байты в одно значение. При записи все будет еще хуже.
Я предпочитаю использовать третий вариант, как более простой и надежный. К тому же хранить мусор внутри записи — это некрасиво, даже если он нигде и не будет использоваться.

Итак, общие правила:
  1. Для записей, создаваемых на стеке, всегда вызывать FillChar.
  2. Для записей, под которые память выделяется динамически, использовать AllocMem, который выделяет память, заполненную нулями. Если используется New, то вызывать FillChar.
  3. Записи, используемые в качестве полей классов, заполняются нулями при создании объектов.
Исправляем тестовый пример:
constructor TUserID.Create(AUserID: Integer;
    AIsWFUser: Boolean);
begin
    FillChar(Self, SizeOf(Self), 0);
    FUserID := AUserID;
    FIsWFUser := AIsWFUser;
end;

Код в статье проверялся в Delphi XE. Для старых версий Delphi все написанное так же актуально, хоть в них и нет конструкторов записей, мусор из стека все так же будет попадать в неиспользуемые байты.

5 комментариев:

  1. Ответы
    1. В основном своей неэффективностью. Современным процессорам тяжело работать с невыровненными данными, скорость будет проседать в разы.

      Добавил этот вариант в статью.

      Удалить
    2. Да, эффективность доступа может быть (а может и не быть) чуть хуже. Но про "разы" - это перебор.
      Да и заполнение нулями тоже занимает какое-то время.

      Удалить
    3. В статье MSDN Windows Data Alignment on IPF, x86, and x64 пишут:

      In some experimental runs..., we saw that on a slower Pentium III (731MHz, running Microsoft Windows XP Professional), the program with the unaligned access runs about 3.25 times slower than the program with the aligned access. On a faster Pentium IV (2.53GHz, running Windows XP Professional), the program with an unaligned access runs about 2 times slower than the program with the aligned access.

      Все-таки данные не зря выравниваются компилятором.

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

    ОтветитьУдалить