Social Icons

понедельник, 18 февраля 2013 г.

Вопросы производительности в конструкторах динамических массивов

В Delphi Вы можете произвести инициализацию динамического массива двумя способами: вручную или используя "магический" конструктор:
...
type
   TIntegerArray = array of Integer;

procedure Test;
var 
   a : TIntegerArray;
begin
   // "Магический" конструктор
   a := TIntegerArray.Create(1, 2);

   // Инициализация вручную
   SetLength(a, 2);
   a[0] := 1;
   a[1] := 2;
end;
На выходе получаем абсолютно идентичные массивы, но во всем ли эти способы одинаковы?

В чем же разница?
Первый способ более лаконичен, но при этом чуть менее эффективен; в этом можно убедиться, посмотрев в окно CPU:
...
// "Магический" конструктор
TestUnit.pas.32: a := TIntegerArray.Create(1, 2);
00511335 8D45F8           lea eax,[ebp-$08]
00511338 8B15F0125100     mov edx,[$005112f0]
0051133E E89576EFFF       call @DynArrayClear   // кто-нибудь знает, зачем?
00511343 6A02             push $02
00511345 8D45F8           lea eax,[ebp-$08]
00511348 B901000000       mov ecx,$00000001
0051134D 8B15F0125100     mov edx,[$005112f0]
00511353 E87476EFFF       call @DynArraySetLength
00511358 83C404           add esp,$04
0051135B 8B45F8           mov eax,[ebp-$08]
0051135E C70001000000     mov [eax],$00000001
00511364 8B45F8           mov eax,[ebp-$08]
00511367 C7400402000000   mov [eax+$04],$00000002
0051136E 8B55F8           mov edx,[ebp-$08]
00511371 8D45FC           lea eax,[ebp-$04]
00511374 8B0DF0125100     mov ecx,[$005112f0]
0051137A E89576EFFF       call @DynArrayAsg

// Инициализация вручную
TestUnit.pas.35: SetLength(a, 2);
0051137F 6A02             push $02
00511381 8D45FC           lea eax,[ebp-$04]
00511384 B901000000       mov ecx,$00000001
00511389 8B15F0125100     mov edx,[$005112f0]
0051138F E83876EFFF       call @DynArraySetLength
00511394 83C404           add esp,$04
TestUnit.pas.36: a[0] := 1;
00511397 8B45FC           mov eax,[ebp-$04]
0051139A C70001000000     mov [eax],$00000001
TestUnit.pas.37: a[1] := 2;
005113A0 8B45FC           mov eax,[ebp-$04]
005113A3 C7400402000000   mov [eax+$04],$00000002
Перед тем как обвинить во всем компилятор, Вам следует чуть глубже понять разницу в приведенных способах инициализации массивов:
  • в первом случае при создании массива все его элементы инициализируются единовременно, переводя его в определенное состояние;
  • в случае ручной инициализации, массив изменяется в несколько раз, и, соответственно, массив может быть определен не полностью.
Конечно, в нашем примере компилятор мог бы определить, что массив не виден извне процедуры, и сгенерировать меньший код, однако эта оптимизация смогла бы помочь только в случае локальной переменной.
В более общем случае, оптимизация могла бы заключаться в отказе компилятора от создания временных массивов, если инициализируемый массив не используется (таким образом неопределенность не имеет значения), это в свою очередь может стать предпосылкой зарождения идеи подсчета ссылок на массивы.

Больше деталей
Использование "магического" конструктора влечет за собой следующие издержки:
  • вызов DynArrayClear (не понимаю, зачем он здесь), освобождающий блок памяти, выделенный ранее для временного массива;
  • вызов DynArraySetLength, выделяющий новый блок памяти с последующим его обнулением;
  • вызов DynArrayAssign, приводящий к освобождению памяти, занимаемой текущим массивом (если он не пустой), а также локу счетчика ссылок и дополнительным инициализации и финализации временного массива.
В многопоточном приложении подобные дополнительные манипуляции с памятью и локи плачевно повлияют на производительность. Если Вы потестируете наш пример в многопоточной среде, то увидите, что при использовании "магического" конструктора выполнение кода сведется к однопоточному.
При ручной инициализации мы имеем только один вызов DynArraySetLength, и если массив не пустой, это может вообще не привести к выделению нового блока памяти (т.к. просто может быть уменьшен/увеличен существующий). Поэтому, если Вы инициализируете массив не один раз, ручная инициализация обойдется Вам дешевле.

Как сделать инициализатор лучше?
Мы увидели, что "магический" конструктор не является хорошим вариантом, но что если Вы хотите воспользоваться подобным удобным способом инициализации? На помощь приходят открытые массивы:
...
procedure InitializeArray(var a: TIntegerArray; const values: array of Integer);
begin
   SetLength(a, Length(values));
   if Length(values) > 0 then
      Move(values[0], a[0], Length(values)*SizeOf(Integer));
end;
...
InitializeArray(a, [1, 2]);
Указанная функция не будет эффективнее ручной инициализации: внутри будет происходить дополнительное копирование значений элементов. Однако, она убирает дополнительное выделение памяти и установку локов, поэтому больше подойдет для многопоточных приложений, будучи при этом компактной и лаконичной.
Обратите внимание, что для всех managed-типов (строк, интерфейсов и т.д.), которые System.Move не принимает в качестве аргумента, Вам понадобится использовать либо asm-хаки, либо инициализировать массив поэлементно (например, через цикл for-to-do), что во многих случаях сделает данный вариант неконкурентоспособным относительно ручного аналога.

Хотите еще лучше?
В общем случае, все приведенные выше подходы страдают от вызова довольно сложной процедуры SetLength (взгляньте на DynArraySetLength в System.pas и убедитесь), поэтому, если есть шанс, что динамический массив не изменится в размере, Вы можете выиграть сделав так:
...
if Length(a) <> Length(value) then
   SetLength(a, Length(Values));
Что может увеличить производительность до 10 раз.
Упс! А почему RTL этого не делает, спросите Вы?

Ответ прост - не может. Динамические массивы в Delphi - это не смесь простых типов и указателей, и SetLength - то место, где непосредственно проиходит определение, с чем мы имеем дело (для доп. изучения см. {1}, {2} и {3}).
В DWScript, например, динамические массивы - ссылочные типы, имеют больше возможностей, а их инициализация более компактна:
...
a := [1, 2];
А при использовании Smart Pascal в Chrome V8 или node.js Вам все-таки придется воспользоваться рассмотренными советами по оптимизации.

http://delphitools.info/2013/02/18/delphi-array-constructors-performance-or-lack-of/

Поделитесь с друзьями!

 

Подписчики

Статистика