Schnittmenge von mehreren Mengen ermitteln

[Furtbichler]

Hi Panthrax, hättest Du ein Problem damit, deine Testroutine hier zur Verfügung zu stellen?

[Namenloser]

Zitat:

Zitat von Amateurprofi (Beitrag 1156652)

Zitat:

Zitat von NamenLozer (Beitrag 1156646)

Also das in ASM umzusetzen halte ich nicht für sinnvoll. Da geht nur die Wartbarkeit flöten, und die Performance wird sich dadurch kein bisschen okay, kaum verbessern, da die Festplatte der Flaschenhals ist, nicht die CPU.

Hallo NamenLozer,
ich sehe das ganz anders.
Auch wenn mein Flug nach Neuseeland 36 Stunden dauert, laufe ich nicht zu Fuß zum Flughafen sondern versuche eine schnellere Lösung zu finden. Zudem ging es hier um den speziellen Fall, daß sich die Daten bereits im RAM befinden. Den Flaschenhals Festplatte gab es hier also nicht.

Ja, im Test gab es den nicht, da man sonst die Algorithmen unmöglich vergleichen könnte. In der Praxis wird es den Flaschenhals Festplatte aber dennoch geben. Ich will deinen Code auf keinen Fall schlechtreden, der eigentliche Vergleiche-Teil ist schon erheblich schneller :thumb:. Die Frage ist nur, ob es sich lohnt, hier 200ms zu sparen, wenn das Laden an sich schon mehrere Sekunden dauert.

[Furtbichler]

Zitat:

Zitat von NamenLozer (Beitrag 1156781)

Die Frage ist nur, ob es sich lohnt...

Du musst das sportlich sehen. ;-)

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1156792)

Zitat:

Zitat von NamenLozer (Beitrag 1156781)

Die Frage ist nur, ob es sich lohnt...

Du musst das sportlich sehen. ;-)

Klar, für einen „Wettbewerb“ kann man das schon mal machen ;). Aber im Produktivsystem würde ich die Pascal-Variante trotzdem vorziehen.

[Panthrax]

Code:

11 Messungen:
function Intersect(var Left: TSampleArray; const Right: TSampleArray);
* mit Length(Left) = Length(Right) = N = 10000000 // 10 Mio.
* mit denselben Daten für jede Routine
* mit zufällig generierten Daten für jede Messung
* in Millisekunden

             Messung  #19, Pascal  #39, Pascal  #45, Pascal  #35, Assembler
                   1      242          224          160              64
                   2      246          221          161              62
                   3      244          224          159              63
                   4      248          221          161              67
                   5      247          246          174              64
                   6      252          221          172              61
                   7      249          222          168              62
                   8      251          227          161              60
                   9      261          231          160              61
                  10      263          236          160              62
                  11      255          221          157              61

          Mittelwert      250,727      226,727      163,000          62,455
  Standardabweichung        6,665        8,026        5,639           1,968

Anmerkungen:

• Testsystem: Intel i7, Windows 7
• Den Mittelwert und die Standardabweichung füge ich mit Excel hinzu.
• Verglichene Implementierungen:
  #19 (Pascal, Furtbichler) ist der erste Vorschlag;
  #39 (Pascal, Furtbichler) ist eine korrigierte und verbesserte Variante von #19;
  #45 (Pascal, Panthrax) ist eine verbesserte Variante von #37;
  #35 (Assembler, Amateurprofi).

[Horst_]

Hallo,

ich habe mal das Programm geändert und einfach ein Testfeld mit Zahlen gleichen Abstandes gefüllt habe ( sehr großer Abstand) und anschließend in diesem diese Feld zufällige Werte um 1 oder mehr vergrößert habe.
Dies mehrfach hintereinander.
Versuch[i]= verändertere(Versuch[i-1])

Es war mir nicht geheuer, immer nur die gleiche Datei mit sich selbst zu vergleichen, da werden keine Daten bewegt.

Hier mal die Messungen mit 16 Feldern mit 1e7 = 10 Mio Werten.
Temp ist das Ausgangs und Intersectfeld
Einmal Intersect(Temp,versuch[i]) mit i von 0..15
und einmal rückwärts
Intersect(Temp,versuch[i]) mit i von 15..0
type
tData = int64;
Als Ergbenis:

Code:

   Messung
  #19, Pascal
   9999999   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244659   4916458   4608947   4321049   4050708   3796820

   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820
   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820

Zeit in ms :     4606
  #39, Pascal
  10000000   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244659   4916458   4608947   4321049   4050708   3796820

   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820
   3796820   3796820   3796820   3796820   3796820   3796820   3796820   3796820

Zeit in ms :         3829
  #45, Pascal
  10000000   9375981   8790215   8240652   7725057   7242124   6788731   6363882
   5967006   5594037   5244658   4916456   4608944   4321045   4050703   3796814

   3796820   3796819   3796818   3796817   3796816   3796815   3796814   3796813
   3796812   3796811   3796810   3796809   3796808   3796807   3796806   3796805

Zeit in ms :         2971
  #35, Assembler
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000

  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000
  10000000  10000000  10000000  10000000  10000000  10000000  10000000  10000000

Zeit in ms :             993

Fertig.

Version #19 verzählt an der höchsten Stelle
Version #39 funktioniert
Version #45 verkleinert scheinbar das intersect um 1 zuviel ( aber nicht immer, besonders auffällig bei rueckwaerts.
Mit tdata = longint, war es richtig :?: )
Version #35 funktioniert überhaupt nicht ( kann eigentlich nur bei tData= 32bit funktionieren, oder? Aber vielleicht übergibt freepascal die Register anders)

Version #45 War in der ursprünglichen Verson mit tdata = longint schneller als die Assembler Version 70 / 80 ms

Gruß Horst

[Panthrax]

Mein Algorithmus hatte einen Fehler. Er hatte einige Treffer überprungen, daher die kleinere Schnittmenge. Hier die Korrektur:

Delphi-Quellcode:

procedure Intersect47(var Left: TSampleArray; const Right: TSampleArray);
type
{$PointerMath On}
  PInt64 = ^Int64;
{$PointerMath Off}
var
  L, R, LeftEnd, RightEnd: PInt64;
  N: NativeInt;
begin
  N := 0;
  L := @Left[0];
  R := @Right[0];
  LeftEnd := @Left[Length(Left)];
  RightEnd := @Right[Length(Right)];

  if (L < LeftEnd) and (R < RightEnd) then
    repeat
      if L^ = R^ then
      begin
        Left[N] := L^;
        Inc(N);
      end;

      repeat
        Inc(L);
      until (L^ >= R^) or (L >= LeftEnd);

      if L >= LeftEnd then
        Break;
{+}
{+}   if L^ = R^ then
{+}   begin
{+}     Left[N] := L^;
{+}     Inc(N);
{+}   end;

      repeat
        Inc(R);
      until (L^ <= R^) or (R >= RightEnd);

      if R >= RightEnd then
        Break;
    until False;

  SetLength(Left, N);
end;

Code:

             Messung  #19, Pascal  #39, Pascal  #47, Pascal  #35, Assembler
                   1      251          236          200              66
                   2      267          227          199              63
                   3      277          227          200              64
                   4      268          228          199              64
                   5      257          226          198              66
                   6      264          222          199              65
                   7      253          227          200              64
                   8      253          247          202              63
                   9      253          222          197              66
                  10      250          232          197              63
                  11      247          230          200              65

          Mittelwert      258,182      229,455      199,182          64,455
  Standardabweichung        9,421        7,076        1,471           1,214

Die Zeit-Messwerte aus dem Testprogramm von Horst kann ich nicht zuverlässig ermitteln, wegen der Prozessortaktanpassung bei Hitzeentwicklung. Die Ergebnisse von #39 und #47 zeigen dort jetzt aber die gleiche Schnittmengengröße in der "Vorwärtsrichtung". In der "Rückwärtsrichtung" und für #47 stimmt die Schnittmengengröße beim ersten Mal, dann verkleinert sich die Schnittmengengröße um 1. Ich habe bei meinem ersten Blick nicht verstanden wie die Testdaten erzeugt werden und wie genau getestet wird, und was das für einen Einfluss das auf das "Vorwärts" und "Rückwärts" hat. Vielleicht habe ich auch immer noch Fehler in meinem Algorithmus?

[Horst_]

Hallo,

ich hatte bei #45 übersehen, dass setlength garnicht genutzt wird, dann stimmt die assembler Version für 32 Bit Datentypen.

Delphi-Quellcode:

procedure _Intersect35ASM(var Left: TSampleArray; const Right: TSampleArray);
var
  R: TSampleArray;
begin
  R := Right;
  setlength(Left,Intersect35ASM(Left, R, Length(Left)));
end;

Meine Funktionen, um ein Testfeld zu erzeugen und anschliessend immer mehr zu verfremden.

Delphi-Quellcode:

type
  tData = longint;
  TSampleArray = Array of tData;
  tVersuch = array[0..15] of TSampleArray;
const 
//  MAXDATCOUNT = 1000;
  MAXDATCOUNT = 10*1000*1000;
  delta  = High(tData) div MAXDATCOUNT-1; 

procedure FillArray(var A:TSampleArray);  
//Fuellt A mit Werten von 0 bis MAXDATCOUNT*Delta
// im Abstand delta also, 0,delta,2*delta,3*delta...
var
  i : integer;
  d : tData;
begin 
  i := High(A);
  d := delta * MAXDATCOUNT;
  For i := i downto 0 do
    begin
    d := d-delta;    
    A[i] := d;
    end;
end;

procedure RandomiseArray(out   A:TSampleArray;
                         const B:TSampleArray;
                         Step   :tData;// mittlerer Abstand
                         diff   :tData);// Aenderungswert  
// Veränderte zufällige Werte im durchschnittlichen Abstand Step
var
  cnt: longInt;
  i : longint;
begin 
  A := copy(B);
  i := High(A);
  cnt := 0;
  repeat
    inc(cnt);
    inc(A[i],diff);
    dec(i,random(2*Step-1)+1);
  until (i< 0);
end;
..Im Hauptprogramm
...
  setlength(TestFeld,MAXDATCOUNT);
  FillArray(TestFeld);
  Versuch[low(tVersuch)] := copy(TestFeld);
  //Zufaellige Werte verändern
  For i := low(tVersuch)+1 to High(tVersuch) do
    RandomiseArray(Versuch[i],Versuch[i-1],16,i);

[Panthrax]

Die Testdatenerstellung finde ich etwas umständlich. Das ist aber unwichtig, solange die erzeugten Daten gültig sind: Array[I] < Array[J] mit I < J und I, J: Low(Array)..High(Array). Als Mensch erschwert es mir aber die Testdaten bewerten zu können.

Ja, ich hatte für die Assemblerroutine einen separaten Aufruf geschrieben, weil der Typ von den anderen Routinen abwich.

So auf die Schnelle werde ich den Fehler bei mir wohl nicht finden... Vielleicht hat Furtbichler ja noch eine Idee?

[Amateurprofi]

Zitat:

Zitat von Horst_ (Beitrag 1157022)

Version #35 funktioniert überhaupt nicht ( kann eigentlich nur bei tData= 32bit funktionieren, oder? Aber vielleicht übergibt freepascal die Register anders)

Hallo Horst,
das ist 'ne 32 Bit - Version.
Mir war schon klar, dass in #1 über 64 Bit Daten gesprochen wurde.
Aber ich hatte ja gegen #19 geschrieben aus der leider nicht hervorging ob TSampleArray 32 oder 64 Bit ist.
Aus #28

Zitat:

Ich weiss nur, das das Einlesen einer Zahl genauso lange dauert, wie 2000 (Systempage = 8k, 4Byte=eine Zahl) Also wieso sollte ich einzelne Zahlen einlesen und wie soll das gehen? Ich will ja nicht eine Zahl finden, sondern die Schnittmenge über alle Zahlen. Also muss ich auch alle einlesen (nun ja, bis MAX(Bisherige-Schnittmenge))

hatte ich dann geschlossen, dass #19 mit 32 Bit arbeitet.
Dummerweise habe dann aber auch ich die Definition von TSampleArray nicht explizit angegeben.

[Horst_]

Hallo,

@Amateruprofi,

kann es sein, dass die Assemblerversion in http://www.delphipraxis.net/1156992-post45.html bei gleichen Feldern ein Feld zu wenig zählt.

@panthrax
Ich habe habe Deine Version #45 zu #51 mit while-Schleifen umgebaut, die zählt scheinbar richtig.
Anbei ein Testprogramm.
Bei -1 wird Testfeld gegen Testfeld getestet und die Schnittmenge sollte die gleiche Länge besitzen, was Pascal #19 und Assembler nicht tuen.
Bei 0 werden 12 Felder die jeweile eine Modifikation vom Testfeld sind miteinander "geschnitten"
Bei 1 werden 12 Felder die jeweile eine Modifikation vom VorgängerFeld sind miteinander "geschnitten"
Die Ausgabe in µsec bei meinem Rechner, aber es geht ja nur um relative Beziehung als Assembler ist ~doppelt so schnell wie Pascal #19.

Code:

Pascal #19:Pascal #39:Pascal #39p:Pascal #45:Pascal #51:Assem  #35:
-1      -1:    470313:     388363:    475693:    371294:        -1:
 0  593633:    492619:     441995:    456582:    420622:    267954:
 1  638382:    521710:     459289:    462909:    451294:    296262:
 0  594878:    493216:     445630:    456969:    425607:    240649:
 1  638515:    520117:     461448:    457467:    447657:    302612:
 0  594142:    494672:     442169:    460931:    424432:    241258:
 1  641827:    519991:     459252:        -1:    449344:    298184:
 0  594625:    492036:     441968:        -1:    421176:    241215:
 1  640879:    519695:     459175:    462514:    452662:    296423:
 0  596518:    492056:     445751:    456175:    426792:    238062:
 1  636715:    519495:     458919:        -1:    452807:    301079:
 0  597456:    494035:     442330:    456586:    420898:    236698:
 1  643358:    520896:     462224:    458345:    449333:    294667:
Fertig.

Gruß Horst

[Amateurprofi]

Zitat:

Zitat von Horst_ (Beitrag 1157195)

Hallo,

@Amateruprofi,

kann es sein, dass die Assemblerversion in http://www.delphipraxis.net/1156992-post45.html bei gleichen Feldern ein Feld zu wenig zählt.

Gruß Horst

Eigentlich kann das gar nicht angehen….
Aber vom Brand von Hamburg hatten auch alle gedacht, er könne nicht angehen.
Und dann ist er doch angegangen – und wie!
Das war am 5. Mai 1842, und die haben damals ziemlich dumm geguckt.

So wie ich eben!

Die Funktion ist für Arrays ausgelegt, die keine Zahlen mehrfach enthalten und aufsteigend sortiert sind. Eine weitere Einschränkung ist, dass die als Intersect bezeichnete Menge nicht mehr Elemente enthält, als die als Data bezeichnete.

Wenn wir 2 Arrays haben mit den Zahlen
1 4 4 4 4 7 und
4 4 4
Wie sollte dann die Schnittmenge aussehen?
4 4 4 (weil das die ursprüngliche Anzahl der 4en in der kleineren Menge ist)
oder
4 4 4 4 (weil ja auch die vierte 4 der größeren Menge in der kleineren gefunden wird)
oder
4 4 4 4 4 4 4 4 4 4 4 4 (weil jede 4 der kleineren Menge 4 Mal in der größeren Menge gefunden wird)
oder
4 (weil in Mengen keine Elemente doppelt vorkommen sollten)

Wenn ich in Delphi mit Mengen arbeite, dann kenne ich das so, dass Elemente in Mengen vorkommen oder auch nicht. Es kann aber nicht ein Element mehrfach vorkommen.
Also tendiere ich zur letztgenannten Lösung.

Vielleicht sollte mal jemand ein paar Testdaten (mit nicht mehr als 10 Zahlen in einem Array) zusammenstellen und es sollte auch festgesetzt werden, ob Elemente mehrfach vorkommen dürfen, und wie dann zu verfahren ist.
Und wenn dann mehrere Routinen korrekte Ergebnisse liefern kann man mit großen Mengen die Performance testen.
So wie es jetzt ist, macht das einfach keinen Sinn.

[Laser]

Moin,

Zitat:

Zitat von Amateurprofi (Beitrag 1157272)

Wenn wir 2 Arrays haben mit den Zahlen
1 4 4 4 4 7 und
4 4 4
Wie sollte dann die Schnittmenge aussehen?
4 4 4 (weil das die ursprüngliche Anzahl der 4en in der kleineren Menge ist)
oder
4 4 4 4 (weil ja auch die vierte 4 der größeren Menge in der kleineren gefunden wird)
oder
4 4 4 4 4 4 4 4 4 4 4 4 (weil jede 4 der kleineren Menge 4 Mal in der größeren Menge gefunden wird)
oder
4 (weil in Mengen keine Elemente doppelt vorkommen sollten)

Wenn ich in Delphi mit Mengen arbeite, dann kenne ich das so, dass Elemente in Mengen vorkommen oder auch nicht. Es kann aber nicht ein Element mehrfach vorkommen.
Also tendiere ich zur letztgenannten Lösung.

Vielleicht sollte mal jemand ein paar Testdaten (mit nicht mehr als 10 Zahlen in einem Array) zusammenstellen und es sollte auch festgesetzt werden, ob Elemente mehrfach vorkommen dürfen, und wie dann zu verfahren ist.
Und wenn dann mehrere Routinen korrekte Ergebnisse liefern kann man mit großen Mengen die Performance testen.
So wie es jetzt ist, macht das einfach keinen Sinn.

innerhalb der jeweiligen Menge kommen einzelne Elemente 0 bis 1 mal vor aber nicht mehrfach.

Für das Verständnis sollten diese Testdaten reichen:

Code:

Testdaten:
N1: 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
N2: 02 06 08 12 14 16 18 20 22 24 26 28 30 32
N3: 03 06 09 15 18 24

Schnittmenge:
N0: 06 18

Der Festplattenzugriff ist für die Performance entscheidend. Daher habe ich mich noch nicht ganz vom "Rumgehüpfe" verabschiedet. Der Ansatz ist jetzt:

Code:

UntereSchwelle = größtes erstes Element aus Datei N1.. N3 = 03
ObereSchwelle = kleinstes letztes Element aus Datei N1..N3 = 20
vorzeitig beenden, falls  sich leere Schnittmenge ergibt
jeweils Anzahl Elemente in N1..N3 feststellen
Mit kleinster Datei starten für alle Dateien
  kleine Dateien komplett lesen (Grenze z.B. 4 KB)
  große Dateien nach UntererSchwelle und ObereSchwelle binär durchsuchen
  große Datei von UntererSchwelle bis ObereSchwelle komplett lesen
  Schnittmenge von 2 Dateien erzeugen
  vorzeitig beenden, falls  sich leere Schnittmenge ergibt

Angesichts der goßen Datenmengen, die von der Platte (nicht aus dem Puffer) gelesen werden müssen, wird dieser mit wenig Aufwand eingegrenzt und dann nur noch ein Teil der Daten von HDD gelesen.

Unter Linux kann man den Festplattenpuffer so löschen:

Code:

echo 3 | sudo tee /proc/sys/vm/drop_caches

Quelle: http://www.linuxatemyram.com/play.html

Weiß jemand, wie das unter Windows XP und 7 geht? Notfalls muss man rebooten.

[BUG]

Warum willst du den Puffer nochmal löschen? Dadurch kann es nur langsamer werden :gruebel:

[Furtbichler]

Nein, er will reproduzierbare Tests.

Na, teste mal dein Rumgehüpfe. Ich denke, der Zeitgewinn, wenn überhaupt, wird marginal sein.

Ich weiss nicht, wo die Dateien herkommen, aber wenn sie vor kurzem auf dem System gelandet sind, sind Teile davon bestimmt noch im RAM.

Dessenungeachtet würde ich wirklich mal mit TMappedFile experimentieren, das wird dir das Rumhüpfen verleiden. Das geht wirklich saumäßig schnell.

Eins zum Schluss: Denk mal an KISS ;-)

[Laser]

Moin,

die Dateien liegen auf der Platte. Sie sind vor dem letzten Reboot entstanden. Die Wahrscheinlichkeit, dass sie schon im RAM sind, liegt in der Größenordnung 1:100.000.

Man kann sich das so vorstellen, dass für jedes Wort in einem Buch mit mehreren Millionen Seiten eine Indexdatei vorliegt. Es werden mehrere Schlagwörter benannt und die Schnittmenge enthält die Seiten, auf denen alle Wörter vorkommen.

KISS steht an dieser Stelle nicht im Vordergrund. Es geht um einen zentralen Teil, der die Performance bestimmt.

[Horst_]

Hallo,

@Amateurprofi:
Ich habe nur die Version, die Panthrax eingebaut hat, verwendet, villeicht hat sich dort ein kleiner Fehler eingeschlichen.
Dort ist das Ergebnis, die Anzahl der gemeinsamen Elemente in EAX, zweier gleicher Felder eben ein Element zu wenig, wie es auch bei der Pascal Version #19 der Fall ist.
Die Felder die ich erstellt habe, haben keine doppelten, wie ich auch in http://www.delphipraxis.net/1157082-post48.html schrieb.
Das Ausgangsfeld hat die Werte 0,delta,2*delta...,(N-1)*delta
delta laut Programm

Delphi-Quellcode:

type
   tData = longint;
   TSampleArray = Array of tData;
   tVersuch = array[0..15] of TSampleArray;
const 
// MAXDATCOUNT = 1000;
   MAXDATCOUNT = 10*1000*1000;
   delta = High(tData) div MAXDATCOUNT-1;

also delta = 214
Bei den Versuchsfelder[i] wird das AusgangsFeld/TestFeld an zufälligen Stellen um i erhöht.

@Laser:

Zitat:

Man kann sich das so vorstellen, dass für jedes Wort in einem Buch mit mehreren Millionen Seiten eine Indexdatei vorliegt. Es werden mehrere Schlagwörter benannt und die Schnittmenge enthält die Seiten, auf denen alle Wörter vorkommen.

Zu Beginn ging es um:

Zitat:

gegeben seien n (=1 bis ca. 12) Dateien, in denen jeweils eine Anzahl a (=2 bis ca. 5.000.000) 64-bit Integer-Schlüssel s abgespeichert sind. s liegen jeweils aufsteigend sortiert vor.

Gesucht ist ein möglichst schneller Algorithmus:
Erzeuge eine Datei output der Schlüssel s, die in allen n Dateien vorkommen.

Also maximal 40 Mbyte in einer Datei.Linaer gelesen in etwa 0,5 Sekunden, bei einer nicht so aktuellen Festplatte.
Bei einer mittleren Zugriffszeit von 13 ms entsprechen 0,5 Sekunden 38..39 Schreib/Lese-Kopfpositionierungen.
Binäre Suche in 5 Mio Werten sind trunc(ln(5e6)/ln(2))+1 = 23 Schritte, Du kannst nicht mal zwei veschiedene Werte die einmal in der unterer, das andere Mal in der oberen Hälfte liegen abfragen und die 0,5 Sekunden sind um. { Bei einer SSD wäre das anders.}

Lange Rede, keinen Sinn:
Mit Furtbichlers Pascalversion aus Beitrag #39 sind bei mir 12 Felder mit 10e6 Elemeneten in 0,5 Sekunden durchgemangelt.
Wie schon festgestellt wurde, bleibt nun die Festplatte die Bremse und dort bietet sich Furtbichlers Vorschlag mit TMappedFile an, denn diese arbeiten mit einem Read-ahead den eine untypisierte Datei nicht bieten soll.

Ich halte jetzt nur noch für interessant, ob man wirklich alle 12 Dateien parallel als TMappedFile öffnen sollte oder nicht.

In ~6 Sekunden ist doch alles geschafft.

Gruß Horst

[Iwo Asnet]

Man kann auch overlapped arbeiten (also jeweils die N+1. Datei öffnen, während die N.Datei verarbeitet wird).

Wenn man Multicore ausnutzen möchte, kann man ja jeweils zwei Dateien pro Kern verarbeiten lassen.

Man kann sich fürchterlich einen abbrechen und tage- oder wochenlang nach einer noch besseren Lösung suchen. Aber viel schneller wirds eh nicht.

[Amateurprofi]

Ich habe meine Asm-Version aus #35 noch einmal überarbeitet.
Die nachstehende Funktion arbeitet mit 32 und 64 Bit Daten und ist (auf meinem Rechner) deutlich schneller, als die aus #35.
Mit den von Laser in #53 genannten Testdaten liefert sie korrekte Ergebnisse.

Die Umstellung von 32 auf 64 Bit habe ich so gelöst :

Delphi-Quellcode:

{$DEFINE INT64DATA}
type
   TElement={$IFDEF INT64DATA} int64 {$ELSE} integer {$ENDIF} ;
   TSampleArray=Array of TElement;
   TFiles=Array of TSampleArray;
var
   files:TFiles;

Wenn files die Daten enthält, dann ist der Ablauf so :

Delphi-Quellcode:

var len:integer;
begin
   len:=Length(files[0]);
   for i:=1 to High(files) do
      len:=GetIntersect_5(files[0], files[i],len);
   SetLength(files[0],len);
end;

Danach ist files[0] der Intersect.

Delphi-Quellcode:

FUNCTION GetIntersect_5(var Intersect,Data:TSampleArray; Len:integer):integer;
const f={$IFDEF INT64DATA} 8 {$ELSE} 4 {$ENDIF};
asm
// IN  : EAX=@Intersect, EDX=@Data, ECX=Anzahl der Elemente der bisherigen Schnittmenge
// Out : EAX=Neue Anzahl der Elemente der Schnittmenge
               // Alle Register retten
               pushad // Temp:=ESP; Push EAX,ECX,EDX,EBX,Temp,EBP,ESI,EDI
               // Prüfen ob Data leer
               mov   esi,[edx]         // @Data[0]
               test  esi,esi
               je    @ReturnZero       // Data ist leer
               mov   edi,[eax]         // @Intersect[0]
               test  edi,edi
               je    @ReturnZero       // Intersect leer
               // Zeiger in Intersect und Data hinter jeweils letzten Eintrag
               // stellen und Indizes auf jeweils ersten Eintrag ausrichten
               lea   edi,[edi+ecx*f]   // @Intersect[Len]
               neg   ecx               // i [edi+ecx*4] = Intersect[0]
               je    @ReturnZero       // 0 Elemente in Intersect
               mov   ebp,ecx           // k [edi+ebp*4] = Intersect[0]
               mov   ebx,[esi-4]       // Length(data)
               lea   esi,[esi+ebx*f]   // @Data[Length(data)]
               neg   ebx               // j [esi+edx*4] = Data[0]
               jmp   @Entry

@Store:        mov   [edi+ebp*f],eax   // In neuem Intersect speichern
               {$IFDEF INT64DATA}
               mov   [edi+ebp*f+4],edx // Hi wenn int64
               {$ENDIF};
               add   ebp,1             // Neue Anzahl in Intersect
               add   ecx,1             // Nächster Intersect-Index
               je    @SetRes           // Fertig
               mov   eax,[edi+ecx*f]   // Zahl aus Intersect laden
               {$IFDEF INT64DATA}
               mov   edx,[edi+ecx*f+4] // Hi wenn int64
               {$ENDIF};
@NextData:     add   ebx,1             // Nächster Data-Index
               je    @SetRes           // Fertig
@Compare:      {$IFDEF INT64DATA}
               cmp   edx,[esi+ebx*f+4] // Vergleich Intersect, Data (Hi)
               ja    @NextData         // Intersect>Data. Nur Data-Index erhöhen
               jb    @NextI
               {$ENDIF};
               cmp   eax,[esi+ebx*f]   // Vergleich Intersect, Data
               je    @Store            // Gleich. Speichern und beide Indizes erhöhen
               ja    @NextData         // Intersect>Data. Nur Data-Index erhöhen
@NextI:        add   ecx,1             // Nächster Intersect-Index
               je    @SetRes           // Fertig
@Entry:        mov   eax,[edi+ecx*f]   // Zahl aus Intersect laden
               {$IFDEF INT64DATA}
               mov   edx,[edi+ecx*f+4] // Hi wenn int64
               {$ENDIF};
               jmp   @Compare

@SetRes:       add   ebp,[esp+24]      // Alte Länge addieren (ebp ist <= 0)
               jmp   @StoreRes

@ReturnZero:   xor   ebp,ebp
@StoreRes:     mov   [esp+28],ebp      // von da wird sie in EAX gepopt
               popad
end;

Dass die Performance weitestgehend durch das Einlesen der Daten von der Platte bestimmt wird ist auch mir klar.
Mir geht es hier nur um den Wettbewerb der von Furtbichler ins Leben gerufen wird, mit der Voraussetzung "Daten komplett im RAM".

[Horst_]

Hallo,

Was soll ich sagen, aber es zählt immer noch einen zuwenig, wenn gleiche Felder vorliegen :-(.

Delphi-Quellcode:

  // Ausgangsfeld erzeugen
  setlength(TestFeld,MAXDATCOUNT);
  FillArray(TestFeld);
  writeln('Laenge Ausgangsfeld                        ',length(TestFeld):9);
  writeln('Ausgabe GetINtersect5 bei gleichen Feldern ',GetIntersect_5(TestFeld,TestFeld,length(TestFeld)):9);  
  writeln();

Ergibt:

Code:

Laenge Ausgangsfeld                             1000
Ausgabe GetINtersect5 bei gleichen Feldern       999

Mit freepascal 2.6.0 funktioniert die Konstante f nicht.

Delphi-Quellcode:

function GetIntersect_5(var Intersect, Data: TSampleArray; len:integer): Integer;
asm
// IN : EAX=@Intersect, EDX=@Data, ECX=Anzahl der Elemente der bisherigen Schnittmenge
// Out : EAX=Neue Anzahl der Elemente der Schnittmenge
                // Alle Register retten
                pushad // Temp:=ESP; Push EAX,ECX,EDX,EBX,Temp,EBP,ESI,EDI
                // Prüfen ob Data leer
                mov esi,[edx] // @Data[0]
                test esi,esi
                je @ReturnZero // Data ist leer
                mov edi,[eax] // @Intersect[0]
                test edi,edi
                je @ReturnZero // Intersect leer
                // Zeiger in Intersect und Data hinter jeweils letzten Eintrag
                // stellen und Indizes auf jeweils ersten Eintrag ausrichten
                {$IFDEF INT64DATA}
                lea edi,[edi+ecx*8] // @Intersect[Len]
                {$ELSE}
                lea edi,[edi+ecx*4] // @Intersect[Len]
                {$ENDIF}
                neg ecx // i [edi+ecx*4] = Intersect[0]
                je @ReturnZero // 0 Elemente in Intersect
                mov ebp,ecx // k [edi+ebp*4] = Intersect[0]
                mov ebx,[esi-4] // Length(data)
                {$IFDEF INT64DATA}
                lea esi,[esi+ebx*8]
                {$ELSE}
                lea esi,[esi+ebx*4] // @Intersect[Len]
                {$ENDIF}
                neg ebx // j [esi+edx*4] = Data[0]
                jmp @Entry

 @Store:        
                // In neuem Intersect speichern
                {$IFDEF INT64DATA}
                 mov [edi+ebp*8],eax
                 mov [edi+ebp*8+4],edx // Hi wenn int64
                {$ELSE}
                 mov [edi+ebp*4],eax
                {$ENDIF}
                add ebp,1 // Neue Anzahl in Intersect
                add ecx,1 // Nächster Intersect-Index
                je @SetRes // Fertig
               {$IFDEF INT64DATA}
                mov eax,[edi+ecx*8] // Zahl aus Intersect laden
                mov edx,[edi+ecx*8+4] // Hi wenn int64                
                {$ELSE}
                 mov eax,[edi+ecx*4] 
                {$ENDIF};
 @NextData:     
                add ebx,1 // Nächster Data-Index
                je @SetRes // Fertig
 @Compare:      
                {$IFDEF INT64DATA}
                cmp edx,[esi+ebx*8+4] // Vergleich Intersect, Data (Hi)
                ja @NextData // Intersect>Data. Nur Data-Index erhöhen
                jb @NextI
                cmp eax,[esi+ebx*8] // Vergleich Intersect, Data
                {$ELSE};                
                cmp eax,[esi+ebx*4] // Vergleich Intersect, Data
                {$ENDIF};                
                je @Store // Gleich. Speichern und beide Indizes erhöhen
                ja @NextData // Intersect>Data. Nur Data-Index erhöhen
 @NextI:        
                add ecx,1 // Nächster Intersect-Index
                je @SetRes // Fertig
                 
 @Entry:        
                {$IFDEF INT64DATA}
                mov eax,[edi+ecx*8] // Zahl aus Intersect laden
                mov edx,[edi+ecx*8+4] // Hi wenn int64
                {$ELSE}
                mov eax,[edi+ecx*4]
                {$ENDIF};
                jmp @Compare

 @SetRes:       
                add ebp,[esp+24] // Alte Länge addieren (ebp ist <= 0)
                jmp @StoreRes

 @ReturnZero:   
                xor ebp,ebp
 @StoreRes:     
                mov [esp+28],ebp // von da wird sie in EAX gepopt
                popad
end;

Natürlich ist es rasant viel schneller.
Etwa 60% Laufzeit von meiner Version #51 und 40% von Furtbichlers Version #39.
Hier einmal mit 64Bit Daten:

Code:

Testlauf mit gleichen Feldern
Laenge Ausgangsfeld     5000000

Pascal #19 |            4999999
Pascal #39 |            5000000
Pascal #39p|            5000000
Pascal #45 |            5000000
Pascal #51 |            5000000
Assem  #59 |            4999999

-1 bei falscher Länge
Pascal #19 |Pascal #39 |Pascal #39p|Pascal #45 |Pascal #51 |Assem  #59 |
 0  1032722|     779007|     781494|     682641|     517543|     309627|
 1  1007572|     756619|     746804|         -1|     552682|     340868|
 0  1037553|     779392|     777746|     682334|     516801|     328240|
 1  1008169|     756272|     746638|     631414|     551661|     329541|
 0  1034872|     779641|     777919|     681329|     514093|     304921|
 1  1005277|     755735|     749490|         -1|     560050|     327174|
 0  1033337|     777257|     781387|     682378|     514298|     306631|
 1  1010560|     756301|     749123|         -1|     550271|     345284|
 0  1033724|     780110|     777521|     685260|     514094|     307414|
 1  1010056|     760684|     749326|         -1|     556893|     329527|
 0  1033210|     776339|     777866|     681292|     513723|     306443|
 1  1008153|     757486|     746477|     628156|     556972|     341013|
Fertig.

Bei 32-bit ist der Unterschied größer:

Code:

Testlauf mit gleichen Feldern
Laenge Ausgangsfeld     5000000
Pascal #19 |            4999999
Pascal #39 |            5000000
Pascal #39p|            5000000
Pascal #45 |            5000000
Pascal #51 |            5000000
Assem  #59 |            4999999

-1 bei falscher Länge
Pascal #19 |Pascal #39 |Pascal #39p|Pascal #45 |Pascal #51 |Assem  #59 |
 0   600767|     495126|     460957|     479938|     432181|     175543|
 1   641177|     528338|     477717|     465587|     459524|     248209|
 0   599462|     496682|     460025|         -1|     431155|     186023|
 1   645629|     525119|     477410|     465200|     463242|     248517|
 0   600016|     495281|     460690|     480712|     430214|     182466|
 1   645418|     526174|     478063|         -1|     463148|     248494|
 0   601073|     496591|     460689|         -1|     433332|     186775|
 1   646770|     525318|     477356|         -1|     460146|     231838|
 0   602341|     496265|     459657|     480644|     433047|     184413|
 1   646620|     525649|     477909|         -1|     463296|     248481|
 0   599127|     495659|     460553|     484453|     428845|     173225|
 1   645832|     525271|     476603|     464068|     461602|     248839|
Fertig.

Gruß Horst

[Panthrax]

Code:

11 Messungen:
function Intersect(var Left: TSampleArray; const Right: TSampleArray);
* mit Length(Left) = Length(Right) = N = 10000000 // 10 Mio.
* mit denselben Daten für jede Routine
* mit zufällig generierten Daten für jede Messung
* in Millisekunden

             Messung  #19, Pascal  #39, Pascal  #61, Pascal  #35, Assembler  #59, Assembler
                   1      270          225          209              64              104
                   2      241          220          196              65              105
                   3      249          220          207              64              100
                   4      245          218          206              61              104
                   5      262          226          196              61              102
                   6      241          236          194              61              106
                   7      247          226          196              61              103
                   8      257          216          196              61              105
                   9      258          215          199              61              104
                  10      261          216          196              63              103
                  11      248          218          197              66              103

          Mittelwert      252,636      221,455      199,273          62,545          103,545
  Standardabweichung        9,500        6,283        5,350           1,916            1,635

Mein Algorithmus sollte nun auch fehlerfrei sein.

Das letzte Programm von Horst lässt sich nur mit {$DEFINE INT64DATA} kompilieren. Die Messungen sind aber nicht zuverlässig, weil die Hitzeregulierung mittendrin den Prozessortakt verändert.

Code:

Testlauf mit gleichen Feldern
Laenge Ausgangsfeld     5000000
Pascal #19 |            4999999
Pascal #39 |            5000000
Pascal #39p|            5000000
Pascal #51 |            5000000
Pascal #61 |            5000000
Assem  #59 |            5000000


-1 bei falscher Laenge
Pascal #19 |Pascal #39 |Pascal #39p|Pascal #51 |Pascal #61 |Assem  #59 |
 0  1479473|     942698|     962416|     619718|     869753|     256950|
 1  1237576|     984844|    1067793|     808219|     849550|     333418|
 0  1188971|     970760|     949159|     689957|     896708|     241256|
 1  1248376|     967134|    1073641|     773794|     881661|     332663|
 0  1146181|    1134064|     960496|     604081|    1015837|     277104|
 1  1451410|    1086576|    1069443|     729483|     868560|     328100|
 0  1162970|     977305|     956732|     651758|     916255|     239902|
 1  1234589|    1002855|    1082293|     805464|    1084635|     406615|
 0  1404511|     927632|    1018545|     596848|     904477|     241852|
 1  1235117|     997919|    1076292|     754609|     873866|     366354|
 0  1233630|     970846|     984954|     617806|     920718|     266788|
 1  1223514|    1053170|    1045890|     820487|     914746|     337277|

 Mittelwert
    1251531     1006646     1025931      713864      920638      306484
Standardabweichung
      93849       60489       53601       85766       69511       56339
 
Fertig.

[Horst_]

Hallo,

Da ich kein Unit diagnostics habe, ( Wo gibt es die für freepacal? ) habe ich ein workaround queryperformancecounter oder einfach time unter Linux genommen.

Der Aufruf der Assemblerversion sollte auch Intersect, hier Left, auf die richtige Länge setzen, damit Chancengleichheit herrscht und man den Fehler überhaupt erkennen kann.

Delphi-Quellcode:

procedure _Intersect59ASM(var Left: TSampleArray; const Right: TSampleArray);
var
  R: TSampleArray;
begin
  R := Right;
  //zuvor GetIntersect_5(Left, R, Length(Left)) 
  setlength(left,GetIntersect_5(Left, R, Length(Left)));
end;

Meine Prozedur hatte ich in #51 ja nicht explizit angegeben:

Delphi-Quellcode:

procedure Intersect51(var Left: TSampleArray; const Right: TSampleArray);
// modifiziertes Intersect45 auf while Schleife
type
{$PointerMath On}
  pData = ^tData; // hier ist tData Int64

var
  L, R, LeftEnd, RightEnd: pData;
  N: NativeInt;
begin
  N := 0;
  L := @Left[0];
  R := @Right[0];
  LeftEnd := @Left[Length(Left)];
  RightEnd := @Right[Length(Right)];

  if (L < LeftEnd) and (R < RightEnd) then
    repeat
      while  (L < LeftEnd) and (R < RightEnd) AND (L^ = R^) do
      begin
        Left[N] := L^;
        Inc(N);
        inc(R);
        inc(L);
      end;
      if (L = LeftEnd) OR ( R = RightEnd) then
        Break;
     
      while (L < LeftEnd)  AND (L^ < R^) do
        inc(L);
      while (R < RightEnd) AND (R^ < L^) do
        inc(R);
    until False;

  SetLength(Left, N);
{$PointerMath Off}  
end;

Meine Laufzeiten unter Linux mit freepascal 2.6.0 sind nun mit einem Phenom 955 X4 mit 3,2 Ghz:

Code:

  #61, Pascal  10000000
  #39, Pascal  10000000
  #51, Pascal  10000000
  #59, Assem    9999999

   Messung  #61, Pascal  #39, Pascal  #51, Pascal  #59, Assem 
         1      138          134           76           62
         2      137          133           76           59
         3      137          134           77           59
         4      136          134           77           59
         5      137          134           76           59
         6      137          134           77           64
         7      137          133           77           58
         8      137          135           76           60
         9      138          134           76           59
        10      137          133           76           59
        11      137          134           76           59
Fertig.

Im angehängten Program habe ich als Gag es ein Define Laptop, um die Pause einzubauen.

Gruß Horst

[Panthrax]

Vielen Dank für den Kompilerschalter! Hier meine Messwerte auf einem i7 M640 @ 2,8 GHz, Windows 7 64 Bit:

{$DEFINE INT64DATA}

Code:

  #61, Pascal  10000000
  #39, Pascal  10000000
  #51, Pascal  10000000
  #59, Assem   10000000

   Messung  #61, Pascal  #39, Pascal  #51, Pascal  #59, Assem
         1      218          154           75           38
         2      212          154           73           37
         3      216          148           72           39
         4      214          153           74           39
         5      216          152           71           41
         6      217          152           82           41
         7      221          155           75           39
         8      220          152           72           43
         9      214          160           74           51
        10      213          154           73           41
        11      231          156           73           37

Mittelwert      217,455      153,636       74,000       40,545
Standardabw.      5,298        2,976        2,933        3,934
Fertig.

//{$DEFINE INT64DATA}

Code:

  #61, Pascal  10000000
  #39, Pascal  10000000
  #51, Pascal  10000000
  #59, Assem   10000000

   Messung  #61, Pascal  #39, Pascal  #51, Pascal  #59, Assem
         1      218          158           80           34
         2      219          155           71           34
         3      220          166           77           38
         4      225          159           76           35
         5      217          164           80           40
         6      218          150           72           37
         7      218          161           78           36
         8      220          152           71           35
         9      214          164           76           37
        10      217          152           70           35
        11      231          166           85           38

Mittelwert      219,727      158,818       76,000       36,273
Standardabw.      4,606        5,896        4,690        1,902
Fertig.

Damit ich es kompilieren konnte musste ich einen Schreibfehler korrigieren:

Delphi-Quellcode:

{$Else} // war: eine schließende, eckige Klammer
  {$AppType Console}
{$EndIf}

Das Längesetzen im _Intersect*ASM hätte ich tun sollen. Ich weiß auch nicht, warum ich das immer unterschlagen habe.

Auch wenn es die Unit Diagnostics für FreePascal so nicht zu geben schein. Dein Ersatz ist doch angemessen und gut!

Vielleicht sollte ich noch ein Wort zu den Schleifen sagen. Ich hatte ausprobiert welche schneller sind; und für mein System waren es die Repeat-Until-Schleifen, was den Algorithmus etwas verkompliziert hat. Ich hatte auch erst While-Schleifen, weil sie einfach so viel besser zum Algortihmus passen, wie ein oberflächlicher Vergleich schon zeigt. Interessanterweise zeigen die Zeiten, dass das es dieser Geschwindigkeitsgewinn nicht überall so zu geben scheint.

[Amateurprofi]

Zitat:

Zitat von Horst_ (Beitrag 1157497)

Hallo,

Was soll ich sagen, aber es zählt immer noch einen zuwenig, wenn gleiche Felder vorliegen :-(.

Gruß Horst

Hallo Horst,
sorry, aber bei mir passiert das nicht.
Zumindest dann nicht, wenn ich

Delphi-Quellcode:

tData=integer

deklariere.
Wenn ich, wie du es gemacht hast

Delphi-Quellcode:

tData=cardinal

deklariere, dann wird nicht compiliert, anstatt kommt in der Prozedur FillArray bei der Zeile

Delphi-Quellcode:

d := delta * MAXDATCOUNT;

eine Fehlermeldung :
[DCC Fehler] Intersect_Main.pas(318): E2099 Überlauf bei Konvertierung oder arithmetischer Operation
Die OH sagt hierzu:
Der Compiler hat in einem arithmetischen Ausdruck einen Überlauf entdeckt. Das Ergebnis des Ausdrucks kann wegen seiner Größe nicht in 32 Bits dargestellt werden. Überprüfen Sie die durchgeführten Berechnungen, und stellen Sie sicher, dass die Ergebnisse von der Hardware des Computers dargestellt werden können.

Und wenn ich mit der Maus auf die Konstante "delta" zeige dann kommt der Hinweis
delta = null - Erroneous Type

Wenn ich aber nun die Konstante delta explizit als cardinal deklariere, also

Delphi-Quellcode:

delta:cardinal= High(TData) div maxdatcount-1;

dann wird compiliert und die Asm-Funktion liefert korrekte Ergebnisse.

Ich vermute, dass es daran liegt….

Delphi-Quellcode:

type
   TData=cardinal;

const
   maxdatcount=5000000;
//   delta=High(TData) div maxdatcount-1; // so wird nicht compiliert
     delta:cardinal=High(TData) div maxdatcount-1; // so funktioniert es

procedure FillArray(var A:TSampleArray);
var
  i : integer;
  d : tData;
begin
  i := High(A);
  d := delta * MAXDATCOUNT;
  For i := i downto 0 do
    begin
    d := d-delta;
    A[i] := d;
    end;
end;

procedure TMain.Button1Click(Sender: TObject);
var intersect,data:TSampleArray; 
begin
   SetLength(data,maxdatcount);
   FillArray(data);
   intersect:=copy(data);
   SetLength(intersect,GetIntersect_5(intersect,data,Length(intersect)));
   meRes.Lines.Add(inttostr(Length(intersect)));
end;

[Horst_]

Hallo,

Ach Herr je,
da will man clever sein und fällt wieder auf die Nase ;-)
Weil bei mir PrepareSamples wegen random in freepascal so ewig dauerte, kam ich auf die Idee, für eine neue Runde Left aus Right zu kopieren und anschliessend nur PrepareSamples(Right) aufzurufen.
Dämlicherweise habe ich dies nicht ans Ende der repetitions-Schleife getan sondern noch in der Schleife für die Varianten.
Deshalb hatten die Nicht-Ersten Varianten immer gleiche Felder zu untersuchen, was rasend schnell ist.
Dies habe ich nun geändert.

@Amateurprofi:
Ich benutze seit der letzten Version für die Belegung der Testfelder die Version von Panthrax.
Ich weiß nicht, ob freepascal statt length, high abspeichert und deshalb das Programm das letzte Element des array nicht mehr testet

Delphi-Quellcode:

asm

...
mov edi,[eax] // @Intersect[0]
              // Zeiger in Intersect und Data hinter jeweils letzten Eintrag
              // stellen und Indizes auf jeweils ersten Eintrag ausrichten
lea edi,[edi+ecx*8] // @Intersect[Len] // Offset berechnen damit
neg ecx             // [edi+ecx*8] = Intersect[0]

..
mov esi,[edx] // @Data[0]
..
mov ebx,[esi-4] // Length(Data) oder High(Data)?
...
add ecx,1 // Nächster Intersect-Index
je @SetRes // Fertig
end;

Deshalb hab ich die Vorbelegung derart geändert, das im letzten Element im High(TData) steht.

Delphi-Quellcode:

procedure PrepareSamples(out Value: TSampleArray; const N: NativeInt = 10000000; const S: NativeInt = 5);
var
  I: NativeInt;
begin
  SetLength(Value, N);
  Value[0] := Random(S);
  for I := 1 to N - 2 do
    Value[I] := Value[I - 1] + Random(S) + 1;
  Value[N-1] := High(TData);
end;

Dann habe ich die Ausgabe wie im Kommentar von Panthrax gemacht, also die Ausgabe von Länge der Schnittmenge und Laufzeit,aber mit Komma getrennt ( csv )
Mit Freepascal ergibt sich:

Code:

  #39, Pascal  10000000
  #51, Pascal  10000000
  #61, Pascal  10000000
  #59, Assem    9999999

   Messung  #39, Pascal  #51, Pascal  #61, Pascal  #59, Assem
         1,3332223,125 ,3332223,116 ,3332223,111  ,3332222,76
         2,3333764,129 ,3333764,121 ,3333764,118  ,3333763,70
         3,3338301,123 ,3338301,117 ,3338301,112  ,3338300,69
         4,3334825,123 ,3334825,115 ,3334825,111  ,3334824,68
         5,3330696,123 ,3330696,115 ,3330696,112  ,3330695,68
         6,3333988,124 ,3333988,119 ,3333988,111  ,3333987,71
         7,3333174,123 ,3333174,117 ,3333174,111  ,3333173,76
         8,3333983,123 ,3333983,118 ,3333983,111  ,3333982,68
         9,3335054,125 ,3335054,117 ,3335054,112  ,3335053,74
        10,3333229,123 ,3333229,117 ,3333229,111  ,3333228,71
        11,3332975,123 ,3332975,115 ,3332975,111  ,3332974,70
Fertig.

Hier hat die Assembler Version immer ein Element zu wenig.

Gruß Horst

EDIT:
Der Test mit Freepascal ergab:

Delphi-Quellcode:

  L := @Left[0];
  R := @Right[0];
  DEC(R); writeln(R^);INC(R);
  DEC(L); writeln(L^);INC(L);
...
Ausgabe
9999999
9999999

Also speichert freepascal High(DynArray) statt Length(DynArray)

Böse Falle das!

[Panthrax]

{$DEFINE INT64DATA}
{$DEFINE LAPTOP}

Code:

 #39, Pascal  10000000
 #51, Pascal  10000000
 #61, Pascal  10000000
 #59, Assem   10000000

  Messung  #39, Pascal  #51, Pascal  #61, Pascal  #59, Assem
        1,3333535,239 ,3333535,238 ,3333535,217 ,3333535,138
        2,3332769,223 ,3332769,223 ,3332769,210 ,3332769,129
        3,3332354,223 ,3332354,218 ,3332354,202 ,3332354,124
        4,3335244,219 ,3335244,221 ,3335244,200 ,3335244,129
        5,3330107,222 ,3330107,220 ,3330107,204 ,3330107,128
        6,3333308,219 ,3333308,222 ,3333308,208 ,3333308,128
        7,3330565,226 ,3330565,220 ,3330565,202 ,3330565,128
        8,3331374,252 ,3331374,245 ,3331374,206 ,3331374,129
        9,3332415,220 ,3332415,221 ,3332415,206 ,3332415,141
       10,3333225,223 ,3333225,216 ,3333225,219 ,3333225,128
       11,3333172,221 ,3333172,221 ,3333172,217 ,3333172,127
Mittelwert
          226,091      224,091      208,273      129,909
Standardabweichung
           10,232        8,949        6,680        4,989

//{$DEFINE INT64DATA}
{$DEFINE LAPTOP}

Code:

 #39, Pascal  10000000
 #51, Pascal  10000000
 #61, Pascal  10000000
 #59, Assem   10000000

  Messung  #39, Pascal  #51, Pascal  #61, Pascal  #59, Assem
         1,3333535,206 ,3333535,193 ,3333535,176 ,3333535,116
         2,3332769,188 ,3332769,179 ,3332769,166 ,3332769,104
         3,3332354,194 ,3332354,181 ,3332354,165 ,3332354,108
         4,3335244,219 ,3335244,194 ,3335244,183 ,3335244,120
         5,3330107,201 ,3330107,181 ,3330107,166 ,3330107,100
         6,3333308,198 ,3333308,189 ,3333308,171 ,3333308,102
         7,3330565,195 ,3330565,179 ,3330565,165 ,3330565,106
         8,3331374,195 ,3331374,177 ,3331374,166 ,3331374,104
         9,3332415,199 ,3332415,180 ,3332415,163 ,3332415,105
        10,3333225,207 ,3333225,182 ,3333225,167 ,3333225,107
        11,3333172,220 ,3333172,179 ,3333172,163 ,3333172,102
Mittelwert
           202,000      183,091      168,273      106,727
Standardabweichung
            10,188        5,991        6,150        6,101

[Horst_]

Hallo,

dann liegt es wohl an Freepascal und deren Speicherung dynamischer Felder.
Was mich wundert, dass Panthrax mit Win64 das kompiliert bekommt.
Freepascal 2.7.1. für Linux64 meckert über jede Zeile.
Die Pascalversionen sind dann aber für Int64 (etwas mehr) und Int32 ( ein wenig) schneller, weil dann viel mehr Register benutzt werden können, aber kein Vergelich zu den Assemblerversionen.

Gruß Horst