Форум: "Основная";
Текущий архив: 2004.06.06;
Скачать: [xml.tar.bz2];

Вниз

Перестановка битов в байте - результаты   Найти похожие ветки 

← →
Sha ©   (2004-05-18 16:08) [0]

Похоже, оригинальная ветка потеряна из-за сбоя сервера.

Как обещал, результаты измерения в попугаях (т.е. тиках CPU) на P4/1500/SDRAM

Одиночный вызов:
----------------
240  Jack128
176  Guav
084  SwapBits_APP
096  Default
048  SwapBits_Verg
028  Achtung
028  SwapBits2
028  CombSwap
020  nikkie
020  nikkie2
020  Sha2
016  nikkie_tbl

Вызов 10 раз в цикле:
---------------------
2080  Jack128
1584  Guav
792  SwapBits_APP
588  Default
144  SwapBits_Verg
168  Achtung
164  SwapBits2
084  CombSwap
120  nikkie
084  nikkie2
068  Sha2
040  nikkie_tbl

Процедура Achtung была исправлена (замена bl->dl) и чуть ускорена (замена ah->cl).

Чем измеряли:

{$DEFINE LOOP}
unit Unit1;

interface

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

type
 TForm1 = class(TForm)
   SpeedButton1: TSpeedButton;
   Memo1: TMemo;
   procedure SpeedButton1Click(Sender: TObject);
 end;

var
 Form1: TForm1;

implementation

{$R *.dfm}

function Default(B: Byte): Byte;
asm

     PUSH   EBX
     MOV    EDX, 1
     XOR    EBX, EBX
     MOV    ECX, 8
@@Loop:
     DEC    ECX
     SHR    AL, 1
     JNC    @@Go
     SHL    EDX, CL
     OR     EBX, EDX
     SHR    EDX, CL
@@Go:
     TEST   ECX, ECX
     JNZ    @@Loop
     MOV    AL, BL
     POP    EBX
end;

function GuAV(b: byte): byte;
asm // отсюда убрал строку за ненадобностью
 MOV ECX,8
 SUB AH,AH
 @@1:
 MOV DH,80h
 SHR DH,CL
 SUB DL,DL
 TEST AL,DH
 JZ @@2
 INC DL
 @@2:
 SHL DL,CL
 ADD AH,DL
 LOOP @@1
 TEST AL,80h
 JZ @@3
 INC AH
 @@3:
 MOV AL,AH // сюда добавил
end;

function Jack128(b: byte): byte;

function GetBit(b: byte; Index: Integer): boolean;
begin
Result := (b and (1 shl Index)) <> 0;
end;

procedure SetBit(var b: byte; Index: Integer; Value: boolean);
begin
if not value then
 b := b and not (1 shl Index)
else
 b := b or (1 shl Index);
end;

var
i: integer;
Temp: boolean;
begin
Result := b;
for i := 0 to 3 do
begin
  Temp := GetBit(Result, i);
  SetBit(Result, i, GetBit(Result, 7 - i));
  SetBit(Result, 7 - i, Temp);
end;
end;

function SwapBits_APP(Value: Byte): Byte;
asm
 MOV ECX,8
 MOV AH, AL
@1:
 RCL AH, 1
 RCR AL, 1
 DEC ECX
 JNZ @1
end;

function nikkie(B: Byte): Byte;
begin
Result :=
  ((B and $01) shl 7) xor
  ((B and $02) shl 5) xor
  ((B and $04) shl 3) xor
  ((B and $08) shl 1) xor
  ((B and $10) shr 1) xor
  ((B and $20) shr 3) xor
  ((B and $40) shr 5) xor
  ((B and $80) shr 7);
end;

function SwapBits_Verg(B: byte): byte;
asm
 mov  edx, eax
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 shr edx,1
 rcl eax,1
 and eax,$FF
end;

---

← →
Sha ©   (2004-05-18 16:09) [1]

function SwapBits2(B: byte): byte;
asm
 xor edx,edx;   test al,  1;   setnz dl;   xor ecx,ecx;
 add edx,edx;   test al,  2;   setnz cl;   add edx,ecx;
 add edx,edx;   test al,  4;   setnz cl;   add edx,ecx;
 add edx,edx;   test al,  8;   setnz cl;   add edx,ecx;
 add edx,edx;   test al, 16;   setnz cl;   add edx,ecx;
 add edx,edx;   test al, 32;   setnz cl;   add edx,ecx;
 add edx,edx;   test al, 64;   setnz cl;   add edx,ecx;
 add edx,edx;   test al,128;   setnz cl;   add edx,ecx;
 mov eax,edx;
end;

function CombSwap(x: byte): byte;
begin
 x:=((x and $55) shl 1) or ((x shr 1) and $55);
 x:=((x and $33) shl 2) or ((x shr 2) and $33);
 Result:=((x and $F) shl 4) or ((x shr 4) and $0F);
end;

function Sha2(b: byte): byte;
asm
    mov   edx, eax
    shl   eax, 8
    and   edx, $00F0
    or    eax, edx

    mov   edx, eax
    shl   eax, 4
    and   edx, $0CC0
    and   eax, $3300
    or    eax, edx

    mov   edx, eax
    shl   eax, 2
    and   edx, $2A80
    and   eax, $5500
    or    eax, edx

    shr   eax, 7
end;

function nikkie2(B: Byte): Byte;
begin
B := (B and $F0) shr 4 xor
     (B and $0F) shl 4;
Result := (B and $88) shr 3 xor
     (B and $44) shr 1 xor
     (B and $22) shl 1 xor
     (B and $11) shl 3;
end;

function nikkie_tbl(B: Byte): Byte;
const a:array[0..15] of Byte=
($00,$80,$40,$C0,$20,$A0,$60,$E0,$10,$90,$50,$D0,$30,$B0,$70,$F0);
begin
Result := a[B and $0F] xor (a[(B and $F0) shr 4] shr 4);
end;

function Achtung(input: byte): byte;
asm
  mov dl, al
  mov al, 0
  mov cl , dl
  and cl, 10001000B
  rol cl, 1
  or al, cl

  mov cl, dl
  and cl, 00010001B
  ror cl, 1
  or al, cl

  mov cl, dl
  and cl, 00100010B
  ror cl, 3
  or al, cl

  mov cl, dl
  and cl, 01000100B
  rol cl, 3
  or al, cl
end;

//----------------------------

function Dummy(Prm: byte): byte;
asm
 nop
 end;

function GetCPUTick: int64;
asm
 push ebx
 xor eax, eax
 cpuid
 pop ebx
 rdtsc
 cld
 nop; nop; nop; nop;
 nop; nop; nop; nop;
 end;

type
 TFun= function(Prm: byte): byte;

function Measure(Prm: byte; Fun: TFun): integer;
const
 Skip= 1024;
 LoopCount= 1024;
var
 i, j, Tick: integer;
begin;
 Result:=MaxInt;
 for i:=0 to Skip+LoopCount-1 do begin;
   Tick:=GetCPUTick;
{$IFDEF LOOP}
   for j:=1 to 10 do Fun(Prm);
{$ELSE}
   Fun(Prm);
{$ENDIF}
   Tick:=GetCPUTick-Tick;
   if (Result>Tick) and (i>=Skip) then Result:=Tick;
   end;
 end;

const
 MaxCount= 20;
type
 TName= string[15];
 TData= record
   Tick: integer;
   Name: TName;
   end;
 TDataArray= array[0..MaxCount-1] of TData;

procedure TForm1.SpeedButton1Click(Sender: TObject);
var
 Count: integer;
 Data: TDataArray;

procedure CollectData(Name: TName; Fun: TFun);
const
 Prm= 255;
begin;
 if Count<MaxCount then begin;
   Data[Count].Name:=Name;
   Data[Count].Tick:=Measure(Prm, Fun);
   inc(Count);
   end;
 end;

begin;
 Application.ProcessMessages;
 sleep(1000);
 Application.ProcessMessages;

 Count:=0;
 CollectData("Dummy", @Dummy);
 CollectData("nikkie_tbl", @nikkie_tbl);
 CollectData("Sha2", @Sha2);
 CollectData("nikkie2", @nikkie2);
 CollectData("nikkie", @nikkie);
 CollectData("CombSwap", @CombSwap);
 CollectData("SwapBits2", @SwapBits2);
 CollectData("Achtung", @Achtung);
 CollectData("SwapBits_Verg", @SwapBits_Verg);
 CollectData("Default", @Default);
 CollectData("SwapBits_APP", @SwapBits_APP);
 CollectData("Guav", @Guav);
 CollectData("Jack128", @Jack128);

 Memo1.Clear;
 while Count>0 do begin;
   dec(Count);
   Memo1.Lines.Add(Format("%.3d  %s",[Data[Count].Tick-Data[0].Tick,Data[Count].Name]));
   end;
 end;

end.

---

← →
Romkin ©   (2004-05-18 16:09) [2]

Чего переставляли-то?

---

← →
Sha ©   (2004-05-18 16:13) [3]

Биты в обратном порядке

---

← →
MBo ©   (2004-05-18 16:39) [4]

P3-600

без цикла
247  Jack128
105  Guav
070  SwapBits_APP
049  Default
018  SwapBits_Verg
009  Achtung
017  SwapBits2
018  CombSwapAsm
054  CombSwap
073  nikkie
060  nikkie2
009  Sha2
030  nikkie_tbl
с циклом
2479  Jack128
1058  Guav
729  SwapBits_APP
473  Default
142  SwapBits_Verg
081  Achtung
166  SwapBits2
097  CombSwapAsm
542  CombSwap
761  nikkie
651  nikkie2
071  Sha2
310  nikkie_tbl

function CombSwapAsm(x: byte): byte;
asm
 mov edx,eax
 and eax,$55
 shr edx,1
 shl eax,1
 and edx,$55
 or eax,edx
 mov edx,eax
 and eax,$33
 shr edx,2
 shl eax,2
 and edx,$33
 or eax,edx
 mov edx,eax
 and eax,$F
 shr edx,4
 shl eax,4
 and edx,$F
 or eax,edx
end;



---

← →
pasha_golub ©   (2004-05-18 16:40) [5]

Задача интересная.

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

Мотивировка: манипуляции над TColor, например.

---

← →
Romkin ©   (2004-05-18 16:46) [6]

тут недалеко человек вроде просил слова в обратном порядке ;)

---

← →
MBo ©   (2004-05-18 16:48) [7]

>pasha_golub
1. ассемблерный BSWAP
2. and+сдвиги+or

---

← →
pasha_golub ©   (2004-05-18 16:52) [8]

MBo ©   (18.05.04 16:48) [7]
Я согласен. Но в приведенных выше примерах, использовалось тоже самое, а разница во времени присутствует.

---

← →
GuAV ©   (2004-05-18 17:48) [9]

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

---

← →
Sha ©   (2004-05-18 17:56) [10]

GuAV ©   (18.05.04 17:48) [9]
function GetCPUTick: int64;

---

← →
nikkie ©   (2004-05-18 19:09) [11]

>Sha
а где же функция sha, которую panov написал? она же была абсолютным чемпионом?

>subj
>[4] MBo ©
да... поражает разница в результатах на P4/1500 и P3/600.
особенно удивительно, почему в основном на P3 все отрабатывет не медленнее, Achtung и Sha2 работают даже в 2-3 раза быстрее, а вот CombSwap, nikkie, nikkie2 и nikkie_tbl - на P3 существенно медленнее.

в тесте на P4 смущает вот это
Default       96 588
SwapBits_Verg 48 144
в тестах на P3 более четко видна разница в 10 раз.

---

← →
panov ©   (2004-05-18 19:20) [12]

>nikkie ©   (18.05.04 19:09) [11]
а где же функция sha, которую panov написал? она же была абсолютным чемпионом?

Она не алгоритмическая-)

---

← →
Sha ©   (2004-05-18 19:29) [13]

> nikkie ©   (18.05.04 19:09) [11]
> а где же функция sha, которую panov написал? она же была абсолютным чемпионом?

Потеряна вместе со старой веткой из-за сбоя сервера.
Хотя и так ясно, она будет всегда чемпионом :)

> да... поражает разница в результатах на P4/1500 и P3/600.
> особенно удивительно, почему в основном на P3 все отрабатывет
> не медленнее, Achtung и Sha2 работают даже в 2-3 раза быстрее,
> а вот CombSwap, nikkie, nikkie2 и nikkie_tbl - на P3
> существенно медленнее.

Потому, на P4 операции сдвига имеют большую латентность. И если это является основным тормозом для процедуры на P4, то он исчезает на P3, и в итоге она становится лучше сбалансированной.
Кроме того, на P4 некоторые операции могут выполняться за 1/2 такта, а на P3 таких нет, это служит одной из причин замедления на P3.

> в тесте на P4 смущает вот это
> Default       96 588
> SwapBits_Verg 48 144
> в тестах на P3 более четко видна разница в 10 раз.

На P4 длиннее конвейер, плюс кеш микрокоманд.

---

← →
nikkie ©   (2004-05-18 19:33) [14]

>Потеряна вместе со старой веткой из-за сбоя сервера.
ну если только ы этом дело... :)

[36] panov ©   (17.05.04 10:02)
Реализация идеи от
Sha ©   (17.05.04 07:35) [32]

function sha(B: Byte): Byte;
const a:array[byte] of Byte=
($00,$80,$40,$C0,$20,$A0,$60,$E0,$10,$90,$50,$D0,$30,$B0,$70,$F0,
$08,$88,$48,$C8,$28,$A8,$68,$E8,$18,$98,$58,$D8,$38,$B8,$78,$F8,
$04,$84,$44,$C4,$24,$A4,$64,$E4,$14,$94,$54,$D4,$34,$B4,$74,$F4,
$0C,$8C,$4C,$CC,$2C,$AC,$6C,$EC,$1C,$9C,$5C,$DC,$3C,$BC,$7C,$FC,
$02,$82,$42,$C2,$22,$A2,$62,$E2,$12,$92,$52,$D2,$32,$B2,$72,$F2,
$0A,$8A,$4A,$CA,$2A,$AA,$6A,$EA,$1A,$9A,$5A,$DA,$3A,$BA,$7A,$FA,
$06,$86,$46,$C6,$26,$A6,$66,$E6,$16,$96,$56,$D6,$36,$B6,$76,$F6,
$0E,$8E,$4E,$CE,$2E,$AE,$6E,$EE,$1E,$9E,$5E,$DE,$3E,$BE,$7E,$FE,
$01,$81,$41,$C1,$21,$A1,$61,$E1,$11,$91,$51,$D1,$31,$B1,$71,$F1,
$09,$89,$49,$C9,$29,$A9,$69,$E9,$19,$99,$59,$D9,$39,$B9,$79,$F9,
$05,$85,$45,$C5,$25,$A5,$65,$E5,$15,$95,$55,$D5,$35,$B5,$75,$F5,
$0D,$8D,$4D,$CD,$2D,$AD,$6D,$ED,$1D,$9D,$5D,$DD,$3D,$BD,$7D,$FD,
$03,$83,$43,$C3,$23,$A3,$63,$E3,$13,$93,$53,$D3,$33,$B3,$73,$F3,
$0B,$8B,$4B,$CB,$2B,$AB,$6B,$EB,$1B,$9B,$5B,$DB,$3B,$BB,$7B,$FB,
$07,$87,$47,$C7,$27,$A7,$67,$E7,$17,$97,$57,$D7,$37,$B7,$77,$F7,
$0F,$8F,$4F,$CF,$2F,$AF,$6F,$EF,$1F,$9F,$5F,$DF,$3F,$BF,$7F,$FF);
begin
Result := (a[B]);
end;

---

← →
vertal   (2004-05-18 19:38) [15]

Не могу удержаться от предложения своего варианта. Может ,  он будет помедленнее ассемблерных решений , но зато понятнее и легко модифицируем под разные целые типы(до Int64 - достаточно поменять тип в объявлении функции - приминаемого значения и результата)

Function ReverseBits(source:Byte):byte;overload;
Var
 i:shortint;
Begin
 Result:=0;
 For i:=(SizeOf(Result)shl 3)-1 downto 0 do
 Begin
   Result:=Result shl 1;
   Result:=Result or (source and 1);
   source:=source shr 1;
 End;
End;


---

← →
vertal   (2004-05-18 19:39) [16]

Не могу удержаться от предложения своего варианта. Может ,  он будет помедленнее ассемблерных решений , но зато понятнее и легко модифицируем под разные целые типы(до Int64 - достаточно поменять тип в объявлении функции - приминаемого значения и результата)

Function ReverseBits(source:Byte):byte;overload;
Var
 i:shortint;
Begin
 Result:=0;
 For i:=(SizeOf(Result)shl 3)-1 downto 0 do
 Begin
   Result:=Result shl 1;
   Result:=Result or (source and 1);
   source:=source shr 1;
 End;
End;


---

← →
Sha ©   (2004-05-18 19:58) [17]

P4/1500/SDRAM (дополнено)

Одиночный вызов:
----------------

260  Jack128
176  Guav
168  ReverseBits
080  SwapBits_APP
096  Default
048  SwapBits_Verg
028  Achtung
028  SwapBits2
028  CombSwap
024  CombSwapAsm
020  nikkie
020  nikkie2
020  Sha2
016  nikkie_tbl
008  Sha

Вызов 10 раз в цикле:
---------------------
2080  Jack128
1592  Guav
1340  ReverseBits
792  SwapBits_APP
588  Default
144  SwapBits_Verg
168  Achtung
176  SwapBits2
104  CombSwap
072  CombSwapAsm
120  nikkie
084  nikkie2
068  Sha2
040  nikkie_tbl
020  Sha

---

← →
Pa5ha   (2004-05-18 21:29) [18]

А я тоже себе копурайт хочу красный, как у panov-a!!!

---

← →
MBo ©   (2004-05-19 07:39) [19]

А вот что с Athlon XP 1900+

без цикла
001  Sha
003  nikkie_tbl
004  Achtung
004  CombSwapAsm
004  Sha2
005  SwapBits_Verg
006  CombSwap
008  nikkie2
011  nikkie
012  SwapBits2
044  Default
048  SwapBits_APP
060  Guav
101  ReverseBits
131  Jack128

с циклом
011  Sha
041  nikkie_tbl
047  Sha2
064  CombSwapAsm
066  SwapBits_Verg
078  Achtung
104  CombSwap
114  nikkie2
124  nikkie
142  SwapBits2
352  Default
539  SwapBits_APP
695  Guav
839  ReverseBits
1294  Jack128

добавлена сортировка:

function CompareFunc(List: TStringList; Index1, Index2: Integer): Integer;
var
 i1,i2:Integer;
 s1,s2:string;
begin
 Result:=0;
 s1:=List[Index1];
 s2:=List[Index2];
 i1:=StrToIntDef(Copy(s1,1,Pos(" ",s1)-1),0);
 i2:=StrToIntDef(Copy(s2,1,Pos(" ",s2)-1),0);
 if i1>i2 then
   Result:=1
 else if i1<i2 then
   Result:=-1;
end;

//модификация SpeedButton1Click

SL:=TStringList.Create;
Memo1.Clear;
while Count>0 do begin
  dec(Count);
  SL.Add(Format("%.3d  %s",[Data[Count].Tick-Data[0].Tick,Data[Count].Name]));
  end;
SL.CustomSort(CompareFunc);
Memo1.Lines.Assign(SL);
SL.Free;



---

← →
Sha ©   (2004-05-19 10:11) [20]

Я тоже планировал сделать сортировку :)

Еще хорошо бы в начало SpeedButton1Click добавить
SpeedButton1.Enabled:=false;
а в конец
SpeedButton1.Enabled:=true;

---

← →
Sha ©   (2004-05-19 14:12) [21]

Скажем скромно: это шедевр (тики на P4: 016 / 060).
Алгоритм допускает обобщение на word и dword.

function ReverseBits_Sha(b: byte): byte;
asm
    rol   al,  1

    mov   dl, al
    rol   al, 2
    and   dl, $55
    and   al, $AA
    or    al, dl

    mov   dl, al
    rol   al, 4
    and   dl, $33
    and   al, $CC
    or    al, dl
end;

function ReverseBitsSha2(b: byte): byte;
asm
    mov   dl, al
    rol   al, 4
    and   dl, $CC
    and   al, $33
    or    al, dl

    mov   dl, al
    rol   al, 2
    and   dl, $AA
    and   al, $55
    or    al, dl

    rol   al, 1
end;

---

← →
MBo ©   (2004-05-19 14:35) [22]

Кусочек для AXP1900

000  Sha
002  ReverseBitsSha2
002  ReverseBits_Sha
003  nikkie_tbl
004  Achtung
004  CombSwapAsm
004  Sha2

loop:
011  Sha
032  ReverseBitsSha2
034  ReverseBits_Sha
040  nikkie_tbl
054  Sha2

---

← →
8ung ©   (2004-05-19 20:09) [23]

ИМХО swapbits - app - Классное решение. До такого даже не додумался.

---

← →
default ©   (2004-05-21 06:39) [24]

вот ещё вариант


function Default(B: Byte): Byte;
asm

     MOVZX   EAX, AL

     MOV     EDX, EAX
     AND     EDX, 81H
     JZ      @@Go1
     XOR     EDX, 81H
     JZ      @@Go1
     XOR     EAX, 81H
@@Go1:
     MOV     EDX, EAX
     AND     EDX, 42H
     JZ      @@Go2
     XOR     EDX, 42H
     JZ      @@Go2
     XOR     EAX, 42H
@@Go2:
     MOV     EDX, EAX
     AND     EDX, 24H
     JZ      @@Go3
     XOR     EDX, 24H
     JZ      @@Go3
     XOR     EAX, 24H
@@Go3:
     MOV     EDX, EAX
     AND     EDX, 18H
     JZ      @@Go4
     XOR     EDX, 18H
     JZ      @@Go4
     XOR     EAX, 18H
@@Go4:

end;


---

← →
Sha ©   (2004-05-21 10:26) [25]

default ©   (21.05.04 06:39) [24]

на P4: 016 / 172

---

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

Форум: "Основная";
Текущий архив: 2004.06.06;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.54 MB
Время: 0.03 c