Anzahl der gesetzten Bits in DWord (Überweisung $15)

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Hallo zusammen

Ich brauche eine schnelle Prozedur um herauszufinden, um wieviele Bits sich zwei DWords unterscheiden.

Beispiel:
DWord1 : 10010...
DWord2 : 11100...
Differenz: 01110...
In diesem kleinen Beispiel waren 3 Bits verschieden.

Meine Implementation
Bisher hatte ich eine Tabelle, wo für jede Zahl zwischen 0 und 255 die Anzahl der gesetzten Bits gespeichert ist. Diese Tabelle wird 4 Mal angewendet um die gesetzten Bits in einem DWord zu erhalten (die beiden DWords wurden zuerst mit XOR zusammengeführt). Vielleicht wäre eine Tabelle mit 65536 Einträgen und zweimaliger Anwendung performanter oder vielleicht gibt es direkte Assemblerbefehle?

Ziel
Das ganze stellt in meinem Programm den Flaschenhals dar und soll nun via Assembler optimiert werden. Dem Autor der finalen Version werde ich 15 USD per PayPal überweisen. Voraussetzung ist jedoch, dass deine Version einwandfrei funktioniert und mind. 4x schneller ist

.

Implementation
Im unteren Konsolen-Projekt einfach FastDistance implementieren

Der Geschwindigkeitsunterschied wird dann ausgegeben.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils, Windows;

const
 DiffCount: 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
  );


// To be implemented
function FastDistance(A, B: PDWord): Integer; inline;
begin
  Result := 0;
end;

// Original function
function Distance(A, B: PDWord): Integer; inline;
var
  AByte, BByte: PByte;
begin
  // DWord in 4 Bytes unterteilen und Byteweise die Differenz in der Tabelle nachschauen

  // Cast zu Bytepointers
  AByte := PByte(A);
  BByte := PByte(B);

  // 1. Byte
  Result := DiffCount[AByte^ xor BByte^];
  inc(AByte);
  inc(BByte);
  // 2. Byte
  inc(Result, DiffCount[AByte^ xor BByte^]);
  inc(AByte);
  inc(BByte);
  // 3. Byte
  inc(Result, DiffCount[AByte^ xor BByte^]);
  inc(AByte);
  inc(BByte);
  // 4. Byte
  inc(Result, DiffCount[AByte^ xor BByte^]);
end;

var
  A, B: DWord;
  I: Integer;
  TimeA, TimeB, Elapsed1, Elapsed2: Int64;

begin
  randomize;
  // mit 100 zufälligen Zahlen auf Korrektheit testen
  for I := 0 to 99 do
  begin
    A := Round(Random * High(DWord));
    B := Round(Random * High(DWord));
    if Distance(@A, @B) <> FastDistance(@A, @B) then
    begin
      Writeln('Test failed.');
      break;
    end;
  end;

  SetPriorityClass(GetCurrentProcess, REALTIME_PRIORITY_CLASS);
  try
    // Geschwindigkeit messen
    A := Round(Random * High(DWord));
    B := Round(Random * High(DWord));
    QueryPerformanceCounter(TimeA);
    for I := 0 to 9999 do
     Distance(@A, @B);
    QueryPerformanceCounter(TimeB);
    Elapsed1 := TimeB-TimeA;
    Writeln('Original: ',Elapsed1);
    QueryPerformanceCounter(TimeA);
    for I := 0 to 9999 do
     FastDistance(@A, @B);
    QueryPerformanceCounter(TimeB);
    Elapsed2 := TimeB-TimeA;
    Writeln('New: ',Elapsed2);
    Writeln(Format('Result: %.2f x faster',[Elapsed1/Elapsed2]));
  finally
    SetPriorityClass(GetCurrentProcess, NORMAL_PRIORITY_CLASS);
  end;

  readln;
end.

Es zählt die Performance-Messung auf meinem PC. Kompiliert wird mit Delphi 2006.

Danke!

Gast Erhaltene Danke: 1

Hi,

hab hier gerade mal drübergelesen und will dir ne schnell Antwort geben (die 15 USD kannste behalten).
Vorneweg, ich habe keine Ahnung, wie man ASM in Delphi einbindet, aber das wirst du bestimmt wissen.
In ASM umfasst dein Problem drei Befehle:

mov eax, var1
mov ecx, var2
xor eax, ecx

Fertig! Dein Ergebnis steht in EAX und ist somit der Returnwert deiner Funktion(Prozedur).
Der Returnwert is Hexadezimal, aber es gibt in Delphi bestimmt eine Funktion Hex2Bin, also eine Umwandlung von Hex in Binär.

Viel Spaß.

silent

JayEff · Beiträge: 2971 Windows Vista Ultimate D7 Enterprise

a) Das Ergebnis ist als Zahlenwert, nicht etwa nur Hexadezimal, zurückgegeben. Als Integer um genau zu sein, es gibt keine Funktion, die eine Zahl in eine Zahl umwandelt.
b) Das Ergebnis entspricht nicht dem, was heraus kommen soll: In seinem Beispiel soll die Funktion (dec)3 zurückliefern, nicht etwa (bin)1110
c) die ersten 2 Parameter einer Funktion werden bei Delphi mit den registern eax und ecx übergeben, die ersten beiden Zeilen sind also überflüssig

(zumindest iirc)

...Die Lösung hätt ich auch zuerst gehabt, aber dann hab ich noch mal genauer gelesen und gemerkt, dass das nicht ganz das ist, was er wollte

Wäre dann übrigens 7,5 mal schneller gewesen

_________________
>+++[>+++[>++++++++<-]<-]<++++[>++++[>>>+++++++<<<-]<-]<<++
[>++[>++[>>++++<<-]<-]<-]>>>>>++++++++++++++++++.+++++++.>++.-.<<.>>--.<+++++..<+.

Horst_H · Verfasst: Do 19.07.07 07:02

Hallo,

Für population count gibt es doch schone Implementierungen.
EDIT jetzt aber richtig..

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

function popcount(A:integer):integer;
begin
A := (A          AND $55555555)+
     ((A shr 1)  AND $55555555);
A := (A          AND $33333333)+
     ((A shr 2)  AND $33333333);
A := (A          AND $0F0F0F0F)+
     ((A shr 4)  AND $0F0F0F0F);
A := (A          AND $00FF00FF)+
     ((A shr 8)  AND $00FF00FF);
A := (A          AND $0000FFFF)+
     (A shr 16);
result := A;
end;
begin..

DiffSum := popcount(A XOR B);
..

Gruß Horst

Reinhard Kern · Beiträge: 591 Erhaltene Danke: 14

delfiphan hat folgendes geschrieben:

Hallo zusammen

Ich brauche eine schnelle Prozedur um herauszufinden, um wieviele Bits sich zwei DWords unterscheiden.
...
Es zählt die Performance-Messung auf meinem PC. Kompiliert wird mit Delphi 2006.

Danke!

Hallo,

ich habe leider kein D2006 sondern nur D7, und musste daher inline streichen, ausserdem habe ich A und B als DWord übergeben und nicht als PDWord, bitte Aufrufe entsprechend ändern. Probier also mal:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

function FastDistance(A, B: DWord): Integer; {inline;}
begin
  {Result := 0;}
      asm
        xor edx,eax
        xor eax,eax
        @more: sal edx,1
        adc al,ah
        or edx,edx
        jnz @more
      end;
end;

Würde mich interessieren, was bei dir rauskommt.

Gruss Reinhard

Horst_H · Verfasst: Do 19.07.07 17:38

Hallo,

www.df.lth.se/~john_e/gems/gem002d.html
oder von etwas neuer:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

function popcount(v :integer) :integer; assembler;
begin
asm
      mov  edx, eax          ;// v
      shr  eax, 1            ;// v >> 1
      and  eax, 055555555h   ;// (v >> 1) & 0x55555555
      sub  edx, eax          ;// w = v - ((v >> 1) & 0x55555555)
      mov  eax, edx          ;// w
      shr  edx, 2            ;// w >> 2
      and  eax, 033333333h   ;// w & 0x33333333
      and  edx, 033333333h   ;// (w >> 2)  & 0x33333333
      add  eax, edx          ;// x = (w & 0x33333333) + ((w >> 2) &
                             ;//  0x33333333)
      mov  edx, eax          ;// x
      shr  eax, 4            ;// x >> 4
      add  eax, edx          ;// x + (x >> 4)
      and  eax, 00F0F0F0Fh   ;// y = (x + (x >> 4) & 0x0F0F0F0F)
      imul eax, 001010101h   ;// y * 0x01010101 //Hier ist Pentium IV langsam
      shr  eax, 24           ;// population count = (y *
                              //  0x01010101) >> 24
      mov result,EAX                        
end;
end;

Gruß Horst
EDIT:
Laufzeiten für N = 10.000.000-1;

Original: 776190
FastDistance : 1632971 //Reinhard Kern Verwion ist abhängig davon, ob es viele Nullen es im oberen Bereich gibt
Result: 0,48 x faster //war auch schon 0.35 also noch langsamer (A XOR B =$FFFFFFFF wäre der schlimmste Fall
PopCount1 : 457914 // Pascal Version
Result: 1,70 x faster
PopCount2 : 405931
Result: 1,91 x faster //Assembler ohne Multiplizieren
PopCount : 331202
Result: 2,34 x faster //Assembler mit Multiplizieren

Einloggen, um Attachments anzusehen!

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Herzlichen Dank für eure Beiträge :zustimm:

Wie es scheint gibt es ein Problem mit dem inline-Statement. Um den Prozeduraufruf zu vermeiden, werde ich den Code natürlich direkt reinkopieren, ohne Funktionsaufruf - etwas schade, da die Übersichtlichkeit drunter leidet.

Ich habe jetzt noch eine Variante mit einem 16-bit Lookup-Table gemacht (siehe Anhang). Hier die Auswertung:

markieren

Quelltext

1:
2:
3:
4:
5:

8 bit lookup table (Reference): 1.00x
16 bit lookup table           : 2.13x
Horst_H                       : 1.01x
Horst_H2                      : 2.14x
Reinhard Kern                 : 0.13x

Somit ist der Code von Horst_H2 bislang am besten. Die 4x-Schwelle ist noch nicht erreicht - vielleicht ist es auch gar nicht möglich. Ich lasse den Thread noch ein wenig offen und werde dann entscheiden, an wem die $15 gehen

Im Internet nach Lösungen suchen ist selbstverständlich erlaubt

Was für mein Projekt noch sinnvoll wäre ist noch eine Funktion, die dasselbe auf einen beliebig langen Bytestream anwendet (Size ist jeweils durch 4 teilbar).

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

function Distance(A, B: PByte; Size: Integer): Integer;
var
 I: Integer;
begin
  Result := 0;
  for I := 0 to Size-1 do
  begin
   inc(Result, DiffCount[A^ xor B^]);
   inc(A);
   inc(B);
  end;
end;

Falls jemand einen SpeedUp von 2x hinkriegt, gibt's $5 (Einzahlung per PayPal).

Einloggen, um Attachments anzusehen!

Horst_H · Verfasst: Fr 20.07.07 18:33

Hallo,

was für einen Rechner hast Du?
Auf meinen AMD64 3000 (1800 Mhz) sind die Laufzeiten Deines Programmes mit inlinen der Funktionen und Nutzung von delphi7:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

Enter dr³cken um Testrunde zu starten

Result = 10000000
8 bit lookup table (Reference): 1387042

Result = 10000000
16 bit lookup table: 661488
Result: 2,10 x faster

Result = 10000000
Horst_H: 676891
Result: 2,05 x faster

Result = 10000000
Horst_H2: 300833
Result: 4,61 x faster

Result = 10000015 ?????????????
Reinhard Kern: 1767346
Result: 0,78 x faster

Man sieht, dass mein Code-Schnipsel von AMD kommt ;-)

und das der AMD die Shift's besser abkann (Reinhard Kern) , als der Pentium M des Notebook, den ich davor nutzte.

Gruß Horst
P.S.
Es gibt auch MMX Varianten, die direkt 64 Bit verarbeiten, mit SSE? könnten doch mittlerweile 128 Bit möglich sein?

EDIT:

Reinhard Kern Variante wurde falsch übernommen!

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

■ Free Pascal IDE Version 1.0.10 [2007/05/11]
■ Compiler Version 2.1.4
■ GBD Version GDB 6.2.1
■ Cygwin "C:\fpc\2.1.4\bin\i386-win32\cygwin1.dll" version 1005.18.0.0
Running "???????????\popcount.exe "
Enter dr³cken um Testrunde zu starten

Result = 30000000
8 bit lookup table (Reference): 1567620

Result = 30000000
16 bit lookup table: 841997
Result: 1,86 x faster

Result = 30000000
Horst_H: 321073
Result: 4,88 x faster

Result = 30000000
Horst_H2: 290995
Result: 5,39 x faster

Result = 30000000
Reinhard Kern: 2128622
Result: 0,74 x faster

Wieso ist Freepascal so viel schneller, bei beiden Versionen die ich angegeben habe ?????
O.K. das ist schon ein Grund
Freepascal
8 bit lookup table (Reference): 1567620
Delphi
8 bit lookup table (Reference): 1387042

, aber absolut
Freepascal
Horst_H: 321073
Delphi
Horst_H: 676891
ist doch sehr erstaunlich.

Und überhaupt, bei
Delphi Result = 10000000
freepascal Result = 30000000

Einloggen, um Attachments anzusehen!

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Ich habe einen Intel Dual Core. Wie dem auch sei, die $$$ hast du zu gut :-D

. Kannst mir deine Emailadresse per PM schicken dann zahl ich's dir ein

Die zweite Funktion wäre dann der zweite Flaschenhals. Size ist in meinem Algorithmus eine Konstante und ist momentan gleich 256, also in jedem Fall durch 4, 8 oder sogar 16 teilbar, falls das jemand in MMX schreiben will. Ich geb hierfür nochmals $5 raus

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

function Distance(A, B: PByte; Size: Integer): Integer;  
var  
 I: Integer;  
begin  
  Result := 0;  
  for I := 0 to Size-1 do  
  begin  
   inc(Result, DiffCount[A^ xor B^]);  
   inc(A);  
   inc(B);  
  end;  
end;

Horst_H · Verfasst: Sa 21.07.07 06:32

Hallo,

führ Dir dies bmagic.sourceforge.net/bmsse2opt.html zu Gemüte und schreibe es für Delphi um.
Oder wartze auf die nächste CPU-Generation: www.heise.de/newsticker/meldung/78804 ;-)

Gruß Horst
P.S.:
www.koders.com/assem...55372.aspx?s=hamdist

freimatz · Hält's aus hier Beiträge: 13

delfiphan hat folgendes geschrieben:

Ich habe jetzt noch eine Variante mit einem 16-bit Lookup-Table gemacht (siehe Anhang).

Bedenkt auch noch, dass die Größe des Cache eine Rolle spielt. Wenn du einen Stream damit bahandelst muss der Cache immer neu gefüllt werden.

OlafSt · Verfasst: Di 24.07.07 16:10

Horst_H hat folgendes geschrieben:

Hallo,

führ Dir dies bmagic.sourceforge.net/bmsse2opt.html zu Gemüte und schreibe es für Delphi um.

Die dort benutzten Intrinsincs lassen sich in Delphi wie folgt benutzen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

     asm
          movdqu xmm1,DQWORD PTR Data  //_mm_load_si128
          movdqu DQWORD PTR Data, xmm1 //_mm_store_si128
          andpd xmm1,xmm2              //_mm_and_si128
          xorpd xmm1,xmm2              //_mm_xor_si128
          psrlw xmm1,1                 //_mm_srli
          addpd xmm1,xmm2              //_mm_add_epi32
     end;

Funzt aber IIRC nur mit D2006+, da erst hier SSE2 in den Inline-Assembler implementiert wurde. Durch das movdqu muß der Bereich auch nicht 16-Byte-Aligned sein (ist aber auch entsprechend etwas langsamer).

Also. Du hast 7 XMM-Register (XMM0 bis XMM7). Tob dich aus

_________________
Lies, was da steht. Denk dann drüber nach. Dann erst fragen.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme