Типы данных с копированием-при-модификации (оптимизированный вариант)

20:00 | Статьи Автор: Vadim Godunko

В прошлой статье была рассмотрена разработка типа данных с копированием-при-модификации, в этот же раз внимание будет уделено оптимизации реализации, в частности:

  • исключено выделение динамической памяти для “пустого” совместно используемого объекта;
  • в некоторых случаях исключено выделение динамической памяти для копии объекта при подготовке к модификации;
  • исключено выполнение дорогих операций атомарного инкремента/декремента при использовании “пустого” совместно используемого объекта;
  • обеспечена возможность категоризации пакета как Preelaborate, а типа данных как Preelaborable_Initialization.

Выделяемый при создании каждого объекта сегмент совместно используемой памяти всегда освобождается при установке значения или присваивании объекту значения другого объекта, т.е. фактически всегда он освобождается до использования. Поскольку операция выделения памяти в куче достаточно ресурсоёмкая, желательно исключить ненужные выделения/освобождения сегментов памяти. Сделать это можно разово выделив сегмент памяти для “пустого” совместно используемого объекта, например, при предысполнении спецификации пакета.

1
2
3
4
5
6
7
   Empty_Shared : Shared_Data_Access := new Shared_Data;

   type Holder is new Ada.Finalization.Controlled with record
      Data : Shared_Data_Access := Empty_Shared;
   end record;

   overriding procedure Initialize (Self : in out Holder);

Для корректного подсчёта ссылок необходимо добавить подпрограмму Initialize, задача которой заключается в увеличении счётчика ссылок при инициализации объекта по умолчанию.

1
2
3
4
   procedure Initialize (Self : in out Holder) is
   begin
      Reference (Self.Data);
   end Initialize;

Использование разово выделенного при предысполнении сегмента памяти имеет оборотную сторону — пакет более не может быть классифицирован как Preelaborate, а тип данных как Preelaborable_Initialization. Столь жесткая классификация пакета и типа может быть полезна в некоторых применениях (например, при использовании средств распределённых вычислений). Исправить ситуацию возможно за счёт отказа от распределения “пустого” совместно используемого сегмента памяти в динамической памяти и распределении его статически.

1
2
3
4
5
   Empty_Shared : aliased Shared_Data := (others => <>);

   type Holder is new Ada.Finalization.Controlled with record
      Data : Shared_Data_Access := Empty_Shared'Access;
   end record;

При этом необходимо исключить выполнение освобождения статически выделенного сегмента памяти в подпрограмме Unreference:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   procedure Unreference (Self : in out Shared_Data_Access) is
   procedure Free is
     new Ada.Unchecked_Deallocation (Shared_Data, Shared_Data_Access);
   begin
      if Counters.Decrement (Self.Counter'Access) then
         if Self /= Empty_Shared'Access then
            Free (Self);
         else
            Self := null;
         end if;
      else
         Self := null;
      end if;
   end Unreference;

Фактически же получается, что значение счётчика статически распределённого сегмента не представляет никакого интереса. Поскольку операции атомарного инкремента/декремента значительно более ресурсоёмки нежели проверка значения и переход, вполне логично полностью отказаться от поддержания значения счётчика для статически выделенного сегмента в актуальном состоянии, для чего можно переписать реализацию Reference и Unreference (обратите внимание на использование короткозамкнутой формы логических операций, гарантирующей последовательность вычисления предикатов):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
   procedure Reference (Self : not null Shared_Data_Access) is
   begin
      if Self /= Empty_Shared'Access then
         Counters.Increment (Self.Counter);
      end if;
   end Reference;

   procedure Unreference (Self : in out Shared_Data_Access) is
      procedure Free is
        new Ada.Unchecked_Deallocation (Shared_Data, Shared_Data_Access);
   begin
      if Self /= Empty_Shared'Access
        and then Counters.Decrement (Self.Counter'Access)
      then
         Free (Self);
      else
         Self := null;
      end if;
   end Unreference;

Теперь обратив внимание на выделение динамической памяти при подготовке к модификации значения в подпрограмме Detach. Сейчас подготовка к модификации заключается в выделении нового сегмента для совместно используемого объекта в динамической памяти. Однако, если значение счётчика равно единице, то такое выделение не имеет смысла, поскольку старый объект будет освобождён непоследственно после копирования значения; а следовательно можно использовать старый объект, не только исключив выделение динамической памяти, но и сэкономив на выполнении копирования данных. Отметим, что подготавливаемый к модификации объект не должен быть статически выделенным “пустым” объектом, в противном случае всё же необходимо выделение нового объекта.

1
2
3
4
5
6
7
8
9
10
   procedure Detach (Self : in out not null Shared_Data_Access) is
      Old : Shared_Data_Access := Self;
   begin
      if Self = Empty_Shared'Access
        or else not Counters.Is_One (Self.Counter)
      then
         Self := new Shared_Data'(Counter => <>, Value => Old.Value);
         Unreference (Old);
      end if;
   end Detach;

Теперь пришло время привести полный исходные текст спецификации и реализации пакета.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
private with Ada.Finalization;
private with Counters;

generic
   type T is private;
package Holders is
   pragma Preelaborate;

   type Holder is private;
   pragma Preelaborable_Initialization (Holder);

   Empty : constant Holder;

   procedure Set (Self : in out Holder; Value : T);
   function Get (Self : Holder) return T;

private

   type Shared_Data is record
      Counter : aliased Counters.Counter;
      Value   : T;
   end record;

   type Shared_Data_Access is access all Shared_Data;

   procedure Reference (Self : not null Shared_Data_Access);
   procedure Unreference (Self : in out Shared_Data_Access);
   procedure Detach (Self : in out not null Shared_Data_Access);

   Empty_Shared : aliased Shared_Data := (others => <>);

   type Holder is new Ada.Finalization.Controlled with record
      Data : Shared_Data_Access := Empty_Shared'Access;
   end record;

   overriding procedure Adjust (Self : in out Holder);
   overriding procedure Finalize (Self : in out Holder);

   Empty : constant Holder
     := (Ada.Finalization.Controlled with others => <>);
end Holders;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
with Ada.Unchecked_Deallocation;

package body Holders is

   ------------
   -- Adjust --
   ------------

   overriding procedure Adjust (Self : in out Holder) is
   begin
      Reference (Self.Data);
   end Adjust;

   ------------
   -- Detach --
   ------------

   procedure Detach (Self : in out not null Shared_Data_Access) is
      Old : Shared_Data_Access := Self;
   begin
      if Self = Empty_Shared'Access
        or else not Counters.Is_One (Self.Counter)
      then
         Self := new Shared_Data'(Counter => <>, Value => Old.Value);
         Unreference (Old);
      end if;
   end Detach;

   --------------
   -- Finalize --
   --------------

   overriding procedure Finalize (Self : in out Holder) is
   begin
      if Self.Data /= null then
         Unreference (Self.Data);
      end if;
   end Finalize;

   ---------
   -- Get --
   ---------

   function Get (Self : Holder) return T is
   begin
      return Self.Data.Value;
   end Get;

   ---------------
   -- Reference --
   ---------------

   procedure Reference (Self : not null Shared_Data_Access) is
   begin
      if Self /= Empty_Shared'Access then
         Counters.Increment (Self.Counter);
      end if;
   end Reference;

   ---------
   -- Set --
   ---------

   procedure Set (Self : in out Holder; Value : T) is
   begin
      Detach (Self.Data);
      Self.Data.Value := Value;
   end Set;

   -----------------
   -- Unreference --
   -----------------

   procedure Unreference (Self : in out Shared_Data_Access) is
      procedure Free is
        new Ada.Unchecked_Deallocation (Shared_Data, Shared_Data_Access);
   begin
      if Self /= Empty_Shared'Access
        and then Counters.Decrement (Self.Counter'Access)
      then
         Free (Self);
      else
         Self := null;
      end if;
   end Unreference;

end Holders;

И дать ссылку на архив исходных текстов [download id="3"].

Комментарии (2) »