Другой цикл

Июнь 9, 2012 — Шарахов А.П.

С целью оптимизации времени выполнения кода, написанного на Delphi, можно успешно применять развертывание циклов. Рассмотрим это на примере задачи подсчета ненулевых битов в массиве целых чисел.

Таблицы

Самое быстрое решение нашей задачи – табличное. Обычно в таблицах хранят предварительно вычисленные результаты для всех 8-битных или 16-битных чисел. А вдруг истина посередине? Давайте запасем еще одну таблицу для 11-битных чисел.

Какой тип данных использовать для элементов таблицы? Чтобы не ошибиться, попробуем оба: Integer и ShortInt. Первый сократит количество ассемблерных команд в программе, но увеличит память, занятую таблицей. Второй увеличит количество операций, но уменьшит размер таблицы и позволит компилятору Delphi использовать весьма эффективную команду movsx.

Таким образом, для экспериментов мы должны сгенерировать 6 таблиц:

var
  Table8: array[0..255] of ShortInt;
  Table11: array[0..2047] of ShortInt;
  Table16: array[0..65535] of ShortInt;
  Table8i: array[0..255] of integer;
  Table11i: array[0..2047] of integer;
  Table16i: array[0..65535] of integer;
 
procedure InitTables;
var
  i, j, k: integer;
begin;
  for i:=0 to 255 do begin;
    j:=i;
    k:=0;
    while j<>0 do begin;
      j:=j and (j-1);
      inc(k);
      end;
    Table8[i]:=k;
    Table8i[i]:=k;
    end;
  for j:=0 to 7 do for i:=0 to 255 do begin;
    k:=j*256+i;
    Table11[k]:=Table8[j]+Table8[i];
    Table11i[k]:=Table11[k];
    end;
  for j:=0 to 255 do for i:=0 to 255 do begin;
    k:=j*256+i;
    Table16[k]:=Table8[j]+Table8[i];
    Table16i[k]:=Table16[k];
    end;
  end;

Почти идеальный код

В качестве функции, которую будем оптимизировать возьмем следующую:

function Count8(First: PIntegerArray; Count: integer): integer;
var
  Val: integer;
begin;
  Result:=0;
  if Count>0 then repeat;
    Val:=First[0];
    inc(Result, Table8i[Val and 255]);
    inc(Result, Table8i[Val shr 24]);
    inc(Result, Table8i[Val shr 8 and 255]);
    inc(Result, Table8i[Val shr 16 and 255]);
    dec(Count);
    inc(PInteger(First));
    until Count<=0;
  end;

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

function Count11(First: PIntegerArray; Count: integer): integer;
var
  Val: integer;
begin;
  Result:=0;
  if Count>0 then repeat;
    Val:=First[0];
    inc(Result, Table11i[Val and 2047]);
    inc(Result, Table11i[Val shr 22]);
    inc(Result, Table11i[Val shr 11 and 2047]);
    dec(Count);
    inc(PInteger(First));
    until Count<=0;
  end;
 
function Count16(First: PIntegerArray; Count: integer): integer;
var
  Val: integer;
begin;
  Result:=0;
  if Count>0 then repeat;
    Val:=First[0];
    inc(Result, Table16i[Val and 65535]);
    inc(Result, Table16i[Val shr 16]);
    dec(Count);
    inc(PInteger(First));
    until Count<=0;
  end;

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

В-третьих, можно развернуть цикл.

Отложим на завтра

Развертывание цикла помимо экономии на переходах и на организации цикла дает нам чудесную возможность инициировать операцию чтения следующей порции данных до начала обработки текущей, благодаря чему обеспечивается лучшее совмещение вычислений.

function Count8i(First: PIntegerArray; Count: integer): integer;
var
  Val, Tmp, Sum: integer;
begin;
  Result:=0;
  if Count>0 then begin;
    Sum:=0;
    Val:=First[0];
    if Count and 1=0 then begin;
      Val:=0;
      dec(PInteger(First));
      end;
    dec(Count);
    if Count>0 then repeat;
      Tmp:=First[1];
      inc(Result, Table8i[Val and 255]);
      inc(Sum, Table8i[Val shr 24]);
      inc(Result, Table8i[Val shr 8 and 255]);
      inc(Sum, Table8i[Val shr 16 and 255]);
      Val:=First[2];
      inc(Result, Table8i[Tmp and 255]);
      inc(Sum, Table8i[Tmp shr 24]);
      inc(Result, Table8i[Tmp shr 8 and 255]);
      inc(Sum, Table8i[Tmp shr 16 and 255]);
      dec(Count,2);
      inc(PInteger(First),2);
      until Count<=0;
    inc(Result, Table8i[Val and 255]);
    inc(Sum, Table8i[Val shr 24]);
    inc(Result, Table8i[Val shr 8 and 255]);
    inc(Sum, Table8i[Val shr 16 and 255]);
    inc(Result,Sum);
    end;
  end;
 
function Count11i(First: PIntegerArray; Count: integer): integer;
var
  Val, Tmp, Sum: integer;
begin;
  Result:=0;
  if Count>0 then begin;
    Sum:=0;
    Val:=First[0];
    if Count and 1=0 then begin;
      Val:=0;
      dec(PInteger(First));
      end;
    dec(Count);
    if Count>0 then repeat;
      Tmp:=First[1];
      inc(Result, Table11i[Val and 2047]);
      inc(Sum, Table11i[Val shr 22]);
      inc(Result, Table11i[Val shr 11 and 2047]);
      Val:=First[2];
      inc(Sum, Table11i[Tmp and 2047]);
      inc(Result, Table11i[Tmp shr 22]);
      inc(Sum, Table11i[Tmp shr 11 and 2047]);
      dec(Count,2);
      inc(PInteger(First),2);
      until Count<=0;
    inc(Result, Table11i[Val and 2047]);
    inc(Sum, Table11i[Val shr 22]);
    inc(Result, Table11i[Val shr 11 and 2047]);
    inc(Result,Sum);
    end;
  end;
 
function Count16i(First: PIntegerArray; Count: integer): integer;
var
  Val, Tmp, Sum: integer;
begin;
  Result:=0;
  if Count>0 then begin;
    Sum:=0;
    Val:=First[0];
    if Count and 1=0 then begin;
      Val:=0;
      dec(PInteger(First));
      end;
    dec(Count);
    if Count>0 then repeat;
      Tmp:=First[1];
      inc(Result, Table16i[Val and 65535]);
      inc(Sum, Table16i[Val shr 16]);
      Val:=First[2];
      inc(Result, Table16i[Tmp and 65535]);
      inc(Sum, Table16i[Tmp shr 16]);
      dec(Count,2);
      inc(PInteger(First),2);
      until Count<=0;
    inc(Result, Table16i[Val and 65535]);
    inc(Sum, Table16i[Val shr 16]);
    inc(Result,Sum);
    end;
  end;

Обмануть хочу

Варианты тех же функций с “короткими” таблицами:

function Count8s(First: PIntegerArray; Count: integer): integer;
var
  Val, Tmp, Sum: integer;
begin;
  Result:=0;
  if Count>0 then begin;
    Sum:=0;
    Val:=First[0];
    if Count and 1=0 then begin;
      Val:=0;
      dec(PInteger(First));
      end;
    dec(Count);
    if Count>0 then repeat;
      Tmp:=First[1];
      inc(Result, Table8[Val and 255]);
      inc(Sum, Table8[Val shr 24]);
      inc(Result, Table8[Val shr 8 and 255]);
      inc(Sum, Table8[Val shr 16 and 255]);
      Val:=First[2];
      inc(Result, Table8[Tmp and 255]);
      inc(Sum, Table8[Tmp shr 24]);
      inc(Result, Table8[Tmp shr 8 and 255]);
      inc(Sum, Table8[Tmp shr 16 and 255]);
      dec(Count,2);
      inc(PInteger(First),2);
      until Count<=0;
    inc(Result, Table8[Val and 255]);
    inc(Sum, Table8[Val shr 24]);
    inc(Result, Table8[Val shr 8 and 255]);
    inc(Sum, Table8[Val shr 16 and 255]);
    inc(Result,Sum);
    end;
  end;
 
function Count11s(First: PIntegerArray; Count: integer): integer;
var
  Val, Tmp, Sum: integer;
begin;
  Result:=0;
  if Count>0 then begin;
    Sum:=0;
    Val:=First[0];
    if Count and 1=0 then begin;
      Val:=0;
      dec(PInteger(First));
      end;
    dec(Count);
    if Count>0 then repeat;
      Tmp:=First[1];
      inc(Result, Table11[Val and 2047]);
      inc(Sum, Table11[Val shr 22]);
      inc(Result, Table11[Val shr 11 and 2047]);
      Val:=First[2];
      inc(Sum, Table11[Tmp and 2047]);
      inc(Result, Table11[Tmp shr 22]);
      inc(Sum, Table11[Tmp shr 11 and 2047]);
      dec(Count,2);
      inc(PInteger(First),2);
      until Count<=0;
    inc(Result, Table11[Val and 2047]);
    inc(Sum, Table11[Val shr 22]);
    inc(Result, Table11[Val shr 11 and 2047]);
    inc(Result,Sum);
    end;
  end;
 
function Count16s(First: PIntegerArray; Count: integer): integer;
var
  Val, Tmp, Sum: integer;
begin;
  Result:=0;
  if Count>0 then begin;
    Sum:=0;
    Val:=First[0];
    if Count and 1=0 then begin;
      Val:=0;
      dec(PInteger(First));
      end;
    dec(Count);
    if Count>0 then repeat;
      Tmp:=First[1];
      inc(Result, Table16[Val and 65535]);
      inc(Sum, Table16[Val shr 16]);
      Val:=First[2];
      inc(Result, Table16[Tmp and 65535]);
      inc(Sum, Table16[Tmp shr 16]);
      dec(Count,2);
      inc(PInteger(First),2);
      until Count<=0;
    inc(Result, Table16[Val and 65535]);
    inc(Sum, Table16[Val shr 16]);
    inc(Result,Sum);
    end;
  end;

Итоги

Для определения зависимости времени выполнения от используемой таблицы и развертывания цикла будем использовать процедуру:

procedure TForm1.Button2Click(Sender: TObject);
type
  TCountFunction= function(First: PIntegerArray; Count: integer): integer;
var
  i, j: integer;
  f: array[0..8] of TCountFunction;
  s: array[0..High(f)] of integer;
  t: array[0..High(f)+1] of cardinal;
  a: array of byte;
const
  n: array[0..High(f)] of string=('Count8',  'Count8i',  'Count8s',
                                  'Count11', 'Count11i', 'Count11s',
                                  'Count16', 'Count16i', 'Count16s');
begin;
  Randomize;
  SetLength(a, 1024*1024);
  for i:=0 to Length(a)-1 do a[i]:=Random(256);
 
  InitTables;
 
  f[0]:=@Count8;
  f[1]:=@Count8i;
  f[2]:=@Count8s;
  f[3]:=@Count11;
  f[4]:=@Count11i;
  f[5]:=@Count11s;
  f[6]:=@Count16;
  f[7]:=@Count16i;
  f[8]:=@Count16s;
 
  for i:=0 to High(f) do begin;
    t[i]:=GetTickCount;
    for j:=2047 downto 0 do s[i]:=f[i](PIntegerArray(a), Length(a) div 4);
    end;
  t[High(t)]:=GetTickCount;
 
  Memo1.Lines.Add('');
  for i:=0 to High(f) do Memo1.Lines.Add(Format('%6d %s',[t[i+1]-t[i], n[i]]));
  //for i:=0 to High(f) do Memo1.Lines.Add(Format('%d %6d %s',[s[i], t[i+1]-t[i], n[i]])); //debug
  end;

В таблице приведено сравнительное время обработки 2 Gb данных тестируемыми функциями на различных компьютерах:

 Время (ms)
========================
 E6850 i5-2300  Функция
------------------------
  1250   1216   Count8
   953    967   Count8i
  1016   1077   Count8s
   953    904   Count11
   766    717   Count11i
   797    749   Count11s
  1735   1014   Count16
  1719    936   Count16i
  1156    624   Count16s

Скорость работы исходной функции улучшена почти в 2 раза, достигнута скорость обработки данных 3.2 Gb/s.

на главную