Schnittmenge von mehreren Mengen ermitteln

[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".