С целью оптимизации времени выполнения кода, написанного на 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.