Текущий архив: 2008.08.10;
Скачать: CL | DM;

Вниз

Количество элементов в множестве   Найти похожие ветки 

← →
Sapersky   (2008-07-07 22:05) [40]

На P3-700 табличный метод быстрее:
ElementCountForSetOfChar3 - 2564
ElementCountForSetOfChar4 - 2210
(ms, замерял QPC)

---

← →
Sha ©   (2008-07-08 01:15) [41]

> Leonid Troyanovsky ©   (07.07.08 18:11) [38]
> Интерференцию не наблюл.

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

> Докладываю результаты с дом.комп:
> AMD Athlon XP 1500+ 1.29 GHz 512 MB RAM:
> Параллельный метод - 6084
> Табличный метод - 11756 (!)

Если мне не изменяет память, у АМД оба юнита умеют сдвигать, у Интела - только один. Отсюда увеличение скорости параллельного метода.
Пока это только гипотеза, могу ошибаться.

> Sapersky   (07.07.08 22:05) [40]
> На P3-700 табличный метод быстрее:
> ElementCountForSetOfChar3 - 2564
> ElementCountForSetOfChar4 - 2210

Опять же, ЕМНИП, оно так потому, что у P3 сдвиги реализованы хуже, чем у P4.

Тоже докладываю:
На моем 6850 также, как и на P4, параллельный метод быстрее на 11-12%.

Для тех, кому интересно проверить работу обоих методов на своей машине далее приводится код.
На форме мемо, кнопка и таймер (интервал 5-10сек (см. выше))
Я знаю, что использованный метод измерения производительности не оптимален,
если вы тоже так считаете, используйте тот, который вам нравится больше :)


unit BitCount;

interface

uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, StdCtrls, ExtCtrls;

type
 TForm1 = class(TForm)
   Memo1: TMemo;
   Button1: TButton;
   Timer1: TTimer;
   procedure Button1Click(Sender: TObject);
   procedure Timer1Timer(Sender: TObject);
 private
   { Private declarations }
 public
   { Public declarations }
 end;

var
 Form1: TForm1;

implementation

{$R *.dfm}

const
 BitCnt: array[0..255] of byte = (
 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8);

function ElementCount1(pSet: PByte; ByteSize: integer): integer;
var
 n: integer;
begin;
 Result:=0;
 for n:=0 to ByteSize-1 do begin;
   Inc(Result, BitCnt[pSet^]);
   Inc(pSet);
   end;
 end;

function ElementCount4(pSet : PByteArray; ByteSize : Integer): Integer;
begin
Result := 0;
While (ByteSize >= 4) do begin
Inc(Result, BitCnt[pSet[0]] + BitCnt[pSet[1]] + BitCnt[pSet[2]] + BitCnt[pSet[3]]);
Inc(PByte(pSet), 4);
Dec(ByteSize, 4);
end;
If (ByteSize >= 2) then begin
Inc(Result, BitCnt[pSet[0]] + BitCnt[pSet[1]]);
Inc(PByte(pSet), 2);
Dec(ByteSize, 2);
end;
If (ByteSize = 1) then
Inc(Result, BitCnt[pSet[0]]);
end;

function ElementCount2(pSet: pIntegerArray; Bound: integer): integer;
var
 v, i: integer;
begin;
 Result:=0;
 i:=Bound shr 2;
 if Bound and 3<>0 then begin;
   v:=0;
   if Bound and 1<>0 then v:=pByte(integer(pSet) + Bound - 1)^;
   if Bound and 2<>0 then v:=v shl 16 + pWord(@pSet[i])^;
   v:=v - v shr 1 and $55555555;
   v:=v and $33333333 + v shr 2 and $33333333;
   Result:=(v + v shr 4) and $0F0F0F0F;
   end;
 while i>0 do begin;
   v:=pSet[i-1];
   v:=v - v shr 1 and $55555555;
   v:=v and $33333333 + v shr 2 and $33333333;
   Result:=Result + (v + v shr 4) and $0F0F0F0F;
   dec(i);
   end;
 Result:=(Result + Result shr 8) and $00FF00FF;
 Result:=(Result + Result shr 16) and $1FF;
 end;

function ElementCountForSetOfChar4(pSet: PByteArray): Integer;
var
 i: integer;
begin;
 Result:=0;
 i:=32;
 repeat;
   Result:=Result + BitCnt[pSet[i-1]];
   Result:=Result + BitCnt[pSet[i-2]];
   Result:=Result + BitCnt[pSet[i-3]];
   Result:=Result + BitCnt[pSet[i-4]];
   Result:=Result + BitCnt[pSet[i-5]];
   Result:=Result + BitCnt[pSet[i-6]];
   Result:=Result + BitCnt[pSet[i-7]];
   Result:=Result + BitCnt[pSet[i-8]];
   i:=i-8;
   until i=0;
 end;

function ElementCountForSetOfChar44(pSet: PByteArray): Integer;
var
 i: integer;
begin;
 Result:=0;
 i:=1;
 repeat;
   Result:=Result + BitCnt[pSet[i]];
   Result:=Result + BitCnt[pSet[i+4]];
   Result:=Result + BitCnt[pSet[i+8]];
   Result:=Result + BitCnt[pSet[i+12]];
   Result:=Result + BitCnt[pSet[i+16]];
   Result:=Result + BitCnt[pSet[i+20]];
   Result:=Result + BitCnt[pSet[i+24]];
   Result:=Result + BitCnt[pSet[i+28]];
   Result:=Result + BitCnt[pSet[i+2]];
   Result:=Result + BitCnt[pSet[i+6]];
   Result:=Result + BitCnt[pSet[i+10]];
   Result:=Result + BitCnt[pSet[i+14]];
   Result:=Result + BitCnt[pSet[i+18]];
   Result:=Result + BitCnt[pSet[i+22]];
   Result:=Result + BitCnt[pSet[i+26]];
   Result:=Result + BitCnt[pSet[i+30]];
   i:=i-1;
   until i<0;
 end;



---

← →
Sha ©   (2008-07-08 01:16) [42]


function ElementCountForSetOfChar2(pSet: pIntegerArray): integer;
var
 s, u, v, i: integer;
begin;
 Result:=0;
 i:=8;
 repeat;
   v:=pSet[i-1];
   u:=v;
   v:=v and $AAAAAAAA;
   v:=v shr 1;
   u:=u-v;
   v:=u;
   u:=u and $CCCCCCCC;
   v:=v xor u;
   u:=u shr 2;
   s:=u+v;

   v:=pSet[i-2];
   u:=v;
   v:=v and $AAAAAAAA;
   v:=v shr 1;
   u:=u-v;
   v:=u;
   u:=u and $CCCCCCCC;
   v:=v xor u;
   u:=u shr 2;
   u:=u+v;

   u:=u+s;

   v:=u;
   u:=u and $F0F0F0F0;
   v:=v xor u;
   u:=u shr 4;
   u:=u+v;

   Result:=Result + u;
   i:=i-2;
   until i=0;

 v:=Result;
 Result:=Result and $FF00FF00;
 v:=v xor Result;
 Result:=Result shr 8;
 Result:=Result + v;

 v:=Result;
 Result:=Result shr 16;
 Result:=Result + v;
 Result:=Result and $1FF;
 end;

function ElementCountForSetOfChar3(pSet: pointer): integer;
asm
 push esi
 mov esi, eax
 push edi
 push ebx
 mov edi, 4
 xor eax, eax

@loop:
 mov ebx, [esi]       //  v:=pSet[i-1];
 mov ecx, ebx         //  u:=v;
 and ebx, $AAAAAAAA   //  v:=v and $AAAAAAAA;
 shr ebx, 1           //  v:=v shr 1;
 mov edx, [esi+4]     //  v:=pSet[i-2];         (moved)
 sub ecx, ebx         //  u:=u-v;
 mov ebx, ecx         //  v:=u;
 and ecx, $CCCCCCCC   //  u:=u and $CCCCCCCC;
 xor ebx, ecx         //  v:=v xor u;
 shr ecx, 2           //  u:=u shr 2;
 add esi, 8           //  i:=i-2;               (moved)
 add ebx, ecx         //  s:=u+v;

 mov ecx, edx         //  u:=v;
 and edx, $AAAAAAAA   //  v:=v and $AAAAAAAA;
 shr edx, 1           //  v:=v shr 1;
 sub ecx, edx         //  u:=u-v;
 mov edx, ecx         //  v:=u;
 and ecx, $CCCCCCCC   //  u:=u and $CCCCCCCC;
 xor edx, ecx         //  v:=v xor u;
 shr ecx, 2           //  u:=u shr 2;

 add ebx, edx         //  u:=u+v;
 add ebx, ecx         //  u:=u+s;

 mov edx, ebx         //  v:=u;
 and ebx, $F0F0F0F0   //  u:=u and $F0F0F0F0;
 xor edx, ebx         //  v:=v xor u;
 shr ebx, 4           //  u:=u shr 4;

 add eax, edx         //  u:=u+v;
 add eax, ebx         //  Result:=Result + u;

 sub edi, 1
 jg @loop             //  until i=0;

 mov edx, eax         //  v:=Result;
 and eax, $FF00FF00   //  Result:=Result and $FF00FF00;
 xor edx, eax         //  v:=v xor Result;
 shr eax, 8           //  Result:=Result shr 8;
 add eax, edx         //  Result:=Result + v;

 mov edx, eax         //  v:=Result;
 shr eax, 16          //  Result:=Result shr 16;
 add eax, edx         //  Result:=Result + v;
 and eax, $1FF        //  Result:=Result and $1FF;

 pop ebx
 pop edi
 pop esi
 end;

function ElementCountForSetOfChar5(pSet: pointer): integer;
asm
 push esi
 push edi
 push ebx
 xor esi, esi
 mov edi, 4

@loop:
 mov ebx, [eax]       //  v:=pSet[i-1];
 mov ecx, ebx         //  u:=v;
 and ebx, $AAAAAAAA   //  v:=v and $AAAAAAAA;
 shr ebx, 1           //  v:=v shr 1;
 mov edx, [eax+4]     //  v:=pSet[i-2];         (moved)
 sub ecx, ebx         //  u:=u-v;
 mov ebx, ecx         //  v:=u;
 and ecx, $CCCCCCCC   //  u:=u and $CCCCCCCC;
 xor ebx, ecx         //  v:=v xor u;
 shr ecx, 2           //  u:=u shr 2;
 add eax, 8           //  i:=i-2;               (moved)
 add ebx, ecx         //  s:=u+v;

 mov ecx, edx         //  u:=v;
 and edx, $AAAAAAAA   //  v:=v and $AAAAAAAA;
 shr edx, 1           //  v:=v shr 1;
 sub ecx, edx         //  u:=u-v;
 mov edx, ecx         //  v:=u;
 and ecx, $CCCCCCCC   //  u:=u and $CCCCCCCC;
 xor edx, ecx         //  v:=v xor u;
 shr ecx, 2           //  u:=u shr 2;

 add ebx, edx         //  u:=u+v;
 add ebx, ecx         //  u:=u+s;

 mov edx, ebx         //  v:=u;
 and ebx, $F0F0F0F0   //  u:=u and $F0F0F0F0;
 xor edx, ebx         //  v:=v xor u;
 shr ebx, 4           //  u:=u shr 4;

 add esi, edx         //  u:=u+v;
 add esi, ebx         //  Result:=Result + u;

 sub edi, 1
 jg @loop             //  until i=0;

 mov eax, esi         //  v:=Result;
 and esi, $FF00FF00   //  Result:=Result and $FF00FF00;
 xor eax, esi         //  v:=v xor Result;
 shr esi, 8           //  Result:=Result shr 8;
 pop ebx              //                        (moved)
 add esi, eax         //  Result:=Result + v;

 mov eax, esi         //  v:=Result;
 shr esi, 16          //  Result:=Result shr 16;
 pop edi              //                        (moved)
 add eax, esi         //  Result:=Result + v;
 and eax, $1FF        //  Result:=Result and $1FF;

 pop esi
 end;

type
 MyBaseType = 0..255;
 MySetType = Set of MyBaseType;
var
 MySet: MySetType;
 TimerCount: integer= 0;

procedure TForm1.Button1Click(Sender: TObject);
begin;
 Randomize;
 TimerCount:=10;
 Memo1.Lines.Clear;
 end;

procedure TForm1.Timer1Timer(Sender: TObject);
var
 t1, t2, t3: cardinal;
 i, c1, c2: integer;
 e: MyBaseType;
begin;
 if TimerCount>0 then begin;
   MySet:=[];
   for e:=Low(MyBaseType) to High(MyBaseType) do begin;
     RandSeed:=RandSeed * $08088405 + 1;
     if RandSeed<0 then include(MySet, e);
     end;
   dec(TimerCount);
   t1:=GetTickCount;
   for i:=1 to 100000000 do c1:=ElementCountForSetOfChar4(@MySet);
   t2:=GetTickCount;
   for i:=1 to 100000000 do c2:=ElementCountForSetOfChar5(@MySet);
   t3:=GetTickCount;
   Memo1.Lines.Add(IntToStr(t2-t1));
   Memo1.Lines.Add(IntToStr(t3-t2));
   if c1<>c2 then Memo1.Lines.Add("ERROR -----------------");
   Memo1.Lines.Add("");
   end;
 end;

end.

---

← →
Leonid Troyanovsky ©   (2008-07-08 11:44) [43]

> Sha ©   (08.07.08 01:15) [41]

> На моем 6850 также, как и на P4, параллельный метод быстрее
> на 11-12%.

На двухпроцессорной (P4) машине:
парал. ~2294, табл. ~2492, т.е. на 8% быстрее табличного.

--
Regards, LVT.

---

← →
Sha ©   (2008-07-08 12:41) [44]

> Sha ©   (08.07.08 01:15) [41]
> Если мне не изменяет память, у АМД оба юнита умеют сдвигать

Тут ошибочкв вкралась. У AMD K6/K7 сдвиги реализует толькл один IEU, но с малой латентностью. У Атлона уже три IEU, сколько из них умеют сдвигать, не знаю.

---

← →
Sha ©   (2008-07-08 13:20) [45]

Полезные ссылки:
http://www.agner.org/optimize/optimizing_assembly.pdf
http://www.agner.org/optimize/microarchitecture.pdf

---

← →
JanMihail   (2008-07-08 21:20) [46]

Спасибо!)

---

← →
Sha ©   (2008-07-08 22:23) [47]

> Sapersky   (07.07.08 16:26) [33]
> Ну и 16-битная таблица ещё немного быстрее, впрочем, по использованию памяти это уже ни в какие ворота.

Если нельзя, но очень хочется, то можно :)
Как и следовало ожидать, 16-битная таблица повышает скорость работы табличного метода ровно в 2 раза.
Проверял вот на этом коде (здесь и далее процессор 6850).

function ElementCountForSetOfChar8(pSet: PWordArray): Integer;
var
 i: integer;
begin;
 Result:=0;
 i:=16;
 repeat;
   Result:=Result + BitCnt2[pSet[i-1]];
   Result:=Result + BitCnt2[pSet[i-2]];
   Result:=Result + BitCnt2[pSet[i-3]];
   Result:=Result + BitCnt2[pSet[i-4]];
   Result:=Result + BitCnt2[pSet[i-5]];
   Result:=Result + BitCnt2[pSet[i-6]];
   Result:=Result + BitCnt2[pSet[i-7]];
   Result:=Result + BitCnt2[pSet[i-8]];
   i:=i-8;
   until i=0;
 end;


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

function ElementCountForSetOfChar9(pSet: PWordArray): Integer;
var
 i, w: integer;
begin;
 i:=16;
 Result:=0;
 repeat;
   w:=pSet[i-1];
   Result:=Result + BitCnt[w and 255];
   Result:=Result + BitCnt[w shr 8];
   w:=pSet[i-2];
   Result:=Result + BitCnt[w and 255];
   Result:=Result + BitCnt[w shr 8];
   w:=pSet[i-3];
   Result:=Result + BitCnt[w and 255];
   Result:=Result + BitCnt[w shr 8];
   w:=pSet[i-4];
   Result:=Result + BitCnt[w and 255];
   Result:=Result + BitCnt[w shr 8];
   i:=i-4;
   until i=0;
 end;

Попытки читать по 4 байта или еще немного развернуть цикл к дальнейшему прогрессу не приводят.

Только полное исключение цикла в функциях ElementCountForSetOfChar5 и ElementCountForSetOfChar9 позволяет получить время работы обоих методов на 20% лучше ElementCountForSetOfChar4.

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

Ну, а лидером в заезде становится работающая в 2.36 раза быстрее ElementCountForSetOfChar4 и использующая с 16-битную таблицу

function ElementCountForSetOfChar88(pSet: PIntegerArray): Integer;
var
 i: integer;
begin;
 i:=pSet[0];
 Result:=BitCnt2[i and $FFFF];
 Result:=Result + BitCnt2[i shr 16];
 i:=pSet[1];
 Result:=Result + BitCnt2[i and $FFFF];
 Result:=Result + BitCnt2[i shr 16];
 i:=pSet[2];
 Result:=Result + BitCnt2[i and $FFFF];
 Result:=Result + BitCnt2[i shr 16];
 i:=pSet[3];
 Result:=Result + BitCnt2[i and $FFFF];
 Result:=Result + BitCnt2[i shr 16];
 i:=pSet[4];
 Result:=Result + BitCnt2[i and $FFFF];
 Result:=Result + BitCnt2[i shr 16];
 i:=pSet[5];
 Result:=Result + BitCnt2[i and $FFFF];
 Result:=Result + BitCnt2[i shr 16];
 i:=pSet[6];
 Result:=Result + BitCnt2[i and $FFFF];
 Result:=Result + BitCnt2[i shr 16];
 i:=pSet[7];
 Result:=Result + BitCnt2[i and $FFFF];
 Result:=Result + BitCnt2[i shr 16];
 end;


---

← →
Sha ©   (2008-07-09 08:45) [48]

Очепатка:
Любопытно, что даже в случае исключения цикла в ElementCountForSetOfChar5 параллельный метод занимает меньше памяти, чем любая версия табличного метода.
В частности, поэтому (на 6850) его имеет смысл использовать вместо табличного с 8-битной таблицей, т.к. их скорости равны.

---

Страницы: 1 2 вся ветка

Текущий архив: 2008.08.10;
Скачать: CL | DM;

Наверх

Память: 0.58 MB
Время: 0.007 c