Ускорение операции деления для целочисленного типа

[CRobin]

Здравствуйте. Необходимо разделить число А на число B, при заданом заведомо условии, что А кратно B. Использование оператора div дает производительность такую же как и Trunc(A/B) то есть низкую.

Код: Выделить всё


  SetLength(g, 2000);
  for i:=0 to High(g) do g[i] := Random(1000) * 10;

  j := 0;
  t1 := tsc;
  for i:=0 to High(g) do j := j + g[i] * 10;
  t2 := tsc;

// разница т2 и т1 около 6 мкс

  j := 0;
  t1 := tsc;
  for i:=0 to High(g) do   j := j + g[i] div 10;
  t2 := tsc;   

// разница т2 и т1 около 34 мкс



Есть ли способ избежать избыточной операции отсечения/округления, если заранее известно что результат деления может быть только целочисленным?

Добавлено спустя 7 минут 15 секунд:
К слову, на С# оба цикла выполняются за примерно 12мкс. Стало быть технологических ограничений у компьютера нет.

[скалогрыз]

таблицу деления составить, если значения А и B ограничены?!

[Pavia]

Заменить деление умножением со сдвигами. Подробнее у http://www.agner.org/optimize/

[CRobin]

Pavia умножение не получается, компилятор не пропускает дробный множитель

[runewalsh]

http://www.codeproject.com/Articles/174 ... ly-Shift-i
Но осторожно, этот способ работает только до тех пор, пока промежуточное произведение не переполняется, т. е. накладывает дополнительные ограничения на диапазон делимого.
Лень смотреть, что делает C#, возможно, он умнее и замечает, что диапазон во всём массиве подходит.

[vada]

Если для x86 то на асме 3 команды. Ну и флаг проверить если надо.
http://www.club155.ru/x86cmdfpu/FIDIV

[Pavia]

Pavia умножение не получается, компилятор не пропускает дробный множитель

Это как? Trunc(A/B) пропускает а 0.333 нет что ли?
Но вообще-то у Агнера арифметика целочисленная.

Код: Выделить всё

const
MaxDivider=65535;
var
     NSignBit_1:array [0..MaxDivider] of int64; // Число значащих бит минус 1
     FasDiv_Add:array [0..MaxDivider] of int64;
     FasDiv_Mul:array [0..MaxDivider] of int64;
     FasDiv_Shr:array [0..MaxDivider] of byte;

// Log2 результат целое наибольшее
function Log2Int(n:Int64):Integer;
Var i:Int64;
begin
  Result:=0;
  i:=1;
  while i<N do
   begin
   i:=i shl 1;
   inc(Result);
   end;
end;


procedure TablesInit;
var c,i,j:Integer;
begin

for i:=0 to MaxDivider do
begin
c:=i;
j:=0;
while c<>0 do
  begin
  c:=c shr 1;
  j:=j+1;
  end;
NSignBit_1[i]:=j-1 ;
end;

FasDiv_Add[0]:=0;
FasDiv_Mul[0]:=1;
FasDiv_Shr[0]:=0;

for i:=1 to MaxDivider do
begin
FasDiv_Shr[i]:=Log2Int(MaxDword)+NSignBit_1[i];
if frac(1 shl FasDiv_Shr[i]/i)<0.5 then FasDiv_Add[i]:=1 else FasDiv_Add[i]:=0;
if i=1 then FasDiv_Add[i]:=0;
FasDiv_Mul[i]:=round((1 shl FasDiv_Shr[i])/i);
end;
end;

// Пример использования

function iDiv(const X: WORD; const Y: Word): WORD;
begin
Result:=(Integer(X)+FasDiv_Add[Y])*FasDiv_Mul[Y] shr FasDiv_Shr[Y];
end;

[bormant]

Код: Выделить всё

{$ASMMODE intel}
function RDTSC: Int64; assembler; register;
asm
  rdtsc
end;

var
  g: array of Longint;
  i, j: Longint;
  t: Int64;
begin
  SetLength(g, 2000);
  for i:=0 to High(g) do g[i] := Random(1000) * 10;

  j := 0; t := rdtsc;
  for i:=0 to High(g) do j := j + g[i] * 10;
  t := rdtsc-t; WriteLn(t);

  j := 0; t := rdtsc;
  for i:=0 to High(g) do   j := j + g[i] div 10;
  t := rdtsc-t; WriteLn(t);   
end.


FPC 3.0

Код: Выделить всё

fpc -O3 ...


Код: Выделить всё

3067
7136


Код: Выделить всё

; [20] for i:=0 to High(g) do   j := j + g[i] div 10;
      mov   eax,dword ptr [U_$P$PROGRAM_$$_G]
      call   fpc_dynarray_high
      mov   ecx,eax
; Var i located in register esi
      mov   esi,0
      cmp   ecx,esi
      jl   @@j64
      sub   esi,1
   ALIGN 4
@@j65:
      add   esi,1
      mov   eax,dword ptr [U_$P$PROGRAM_$$_G]
      mov   edi,dword ptr [eax+esi*4]
      mov   eax,1717986919
      imul   edi
      sar   edx,2
      shr   edi,31
      add   edx,edi
      lea   eax,dword ptr [edx+ebx]
      mov   ebx,eax
      cmp   ecx,esi
      jg   @@j65
@@j64:


Как видите, никакого деления.

[CRobin]

bormant ваш код показывает у меня

Код: Выделить всё

26496
108360


с оптимизацией

Код: Выделить всё

11568
104616


Какой у вас процессор и есть ли дополнительные опции компилятора?

[bormant]

На i7-4510U.
На i3-350M чуть хуже

Код: Выделить всё

6076
9972


Для -O2 и -O3 код генерится полностью идентичный.

В FPC 2.6.4 для -O2 и -O3 код также идентичен, но незначительно отличается от FPC 3.0.0:

Код: Выделить всё

; [20] for i:=0 to High(g) do   j := j + g[i] div 10;
      mov   eax,dword ptr [U_P$PROGRAM_G]
      call   fpc_dynarray_high
      mov   ecx,eax
      mov   esi,0
      cmp   ecx,esi
      jl   @@j56
      dec   esi
   ALIGN 4
@@j57:
      inc   esi
      mov   eax,dword ptr [U_P$PROGRAM_G]
      mov   edi,dword ptr [eax+esi*4]
      mov   eax,1717986919
      imul   edi
      mov   eax,edi
      sar   edx,2
      shr   eax,31
      add   edx,eax
      add   edx,ebx
      mov   ebx,edx
      cmp   ecx,esi
      jg   @@j57
@@j56:


[CRobin]

bormant как вы смотрите асемблерный код? Под Убунту скорость выполнения div выросла в 5 раз по сравнению с виндовс. Настройки компилятора те же, код тот же. За счет чего такой прирост?

[bormant]

fpc -Amasm -al ...
ассемблерный выхлоп имеет расширение .S.

[Kemet]

bormant как вы смотрите асемблерный код? Под Убунту скорость выполнения div выросла в 5 раз по сравнению с виндовс. Настройки компилятора те же, код тот же. За счет чего такой прирост?

В свойствах электропитания поставить "Высокая производительность" и только потом проводить измерения.