Assembler-Code wegen Laufzeit-Optimierung benutzen

hkdd

@Swordfish sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Nimm die memcmp()-Implementierung der cstdlib und sei happy

Das habe ich gemacht, es werden die Puffer mit memcmp vergleichen, falls Differenzen, werden diese im Anschluss mit der for-Schleife ermittelt, im Prinzip, wie mit meiner Ass-Routine. Die Laufzeit von bisher 6'31" sinkt auf "tolle" 6'25" ( mit Delphi+Asm = 49").
Compiliert wird mit Visual Studio 2019 Community Version 16.1.6.
Die Zeiten werden vom Programm selbst ermittelt und protokolliert.
(Start - Ende - Dauer)

Der Taskmanager zeigt eine CPU-Auslastung von knapp 20%.
Wenn gut 2 TB Daten verglichen werden, dann müssen die ja auch von zwei Dateien gelesen werden, also das doppelte etwa 4 TB. Das Lesen von Datei 1 und 2 erfolgt nacheinander.

Block1 lesen - Block2 lesen - Block1+2 vergleichen

Die CPU fällt hauptsächlich beim Vergleichen an.


                FileStream fs1 = new FileStream(Dsn1, FileMode.Open, FileAccess.Read);
                FileStream fs2 = new FileStream(Dsn2, FileMode.Open, FileAccess.Read);

                long VerglRestLen = VerglLenGes;
                long VerglOffset = 0;
                long VerglLen = 0;
                int isDiff = 0;

                ByPu1 = new byte[MaxPufL + 0x1000];
                ByPu2 = new byte[MaxPufL + 0x1000];


            NxtPuVergleich:

                if (VerglRestLen > MaxPufL)
                { VerglLen = MaxPufL; }
                else
                { VerglLen = VerglRestLen; }
                                
                fs1.Seek(VerglOffset, SeekOrigin.Begin);
                fs1.Read(ByPu1, 0, (int)VerglLen);

                fs2.Seek(VerglOffset, SeekOrigin.Begin);
                fs2.Read(ByPu2, 0, (int)VerglLen);

                isDiff = memcmp(ByPu1, ByPu2, VerglLen);
                if (isDiff==0) { goto EndePuVergl; }

                // Puffer mit Differenzen vergleichen
                for (int i = 0; i < VerglLen; i++)
                {
                    if (ByPu1[i] != ByPu2[i]) // ungleiche Bytes gefunden ?
                    {
                        if (AnzDiff == 0) // Erste Differenz dieser Datei ?
                        {
                            sZei = sZei + "- ==> Unterschiede gefunden";
                            if (!Flag_F)
                            {
                                PutListV(sZei);
                            }
                            sZei = "";
                        }
                        rc = 1; // es gibt Differenzen
                        isDiff = 1;
                        AnzDiff++;
                        GesDiff++; // Differenzen (Anzahl Bytes)

                        if (AnzDiff <= Anz_M)
                        {
                            ZeigeDiff(VerglOffset+i, ByPu1[i], ByPu2[i], (int)VerglLen);
                        }
                    }
                } // for (uint i = 0; i < VerglLen; i++)

          EndePuVergl:

                VerglRestLen = VerglRestLen - VerglLen; // neue Restlänge

                GesLen = GesLen + VerglLen;
                GesVglLen = GesVglLen + VerglLen;

                Form1Text = "CompHK " + AllTrim(EdStrLo(GesLen, 15)) + " Bytes " + TxPfad3;

                if (VerglRestLen > 0)
                {
                    VerglOffset = VerglOffset + VerglLen;   // Offset nächster Block
                    goto NxtPuVergleich;
                }

                fs1.Close();
                fs2.Close();

TGGC

@hustbaer sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Als Beispiel: Coffee Lake hat ne Speicherbandbreite von 40 GB/s (Hauptspeicher). Bei 4 GHz Takt entspricht das 10 B/c.

Und? Coffee Lake hat 4 Integer ALUs pro Core, kann also 4 Vergleiche auf einmal machen, d.h. selbst bei int32 wären das 128 Byte Daten die verarbeitet werden. Mit Streaming Instruction und Multicores kann man das noch verzigfachen. Bringt aber nichts, weil man schon weit über der lesbaren Datenmenge ist.

wob

@hkdd Hast du dir in meinem oben geposteten StackOverflow-Link die Antworten angeschaut? Insbesondere die von "Mr Anderson" und mit deinem Vergleich verglichen? Vielleicht kann man den Code auch ändern, sodass statt true/false gleich ein Offset rauskommt?

Wozu sind die Seeks in deinem Code?

hustbaer

@TGGC sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

@hustbaer sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Als Beispiel: Coffee Lake hat ne Speicherbandbreite von 40 GB/s (Hauptspeicher). Bei 4 GHz Takt entspricht das 10 B/c.

Und? Coffee Lake hat 4 Integer ALUs pro Core, kann also 4 Vergleiche auf einmal machen, d.h. selbst bei int32 wären das 128 Byte Daten die verarbeitet werden.

Nein, es wären 128 Bit. Also 16 Byte. Und das auch nur wenn man entweder Loop-Unrolling macht (also im generierten Maschinencode, nicht was die CPU evtl. selbst macht) oder die CPU von sich aus mehr als einen Schleifendurchlauf pro Zyklus schafft.

Du hast behauptet dass die genaue Implementierung irrelevant ist. Wenn diese Behauptung wahr wäre, dann müsste es auch ohne Loop-Unrolling gehen. Geht aber nicht, weil die CPU nicht mehr als einen Schleifendurchlauf pro Zyklus schafft.

Mit Streaming Instruction und Multicores kann man das noch verzigfachen. Bringt aber nichts, weil man schon weit über der lesbaren Datenmenge ist.

Man braucht weder Streaming Instructions noch mehrere Cores. Man braucht bloss Loop Unrolling und idealerweise breite Register (Vector-Register). Und genau das machen die optimierten memcmp Implementierungen.

TGGC

Die Loop wird bei der Umsetzung in Microops und durch Register Renaming sowieso unrolled.

hustbaer

@TGGC
Äh, nein, der Loop wird nicht unrolled!?!

Alleine schon das Inkrementieren der Induktionsvariable "serialisiert" dir den Loop. Klar kann die CPU auch die Induktionsvariable "renamen", aber das ändert nichts daran dass Schleifendurchlauf 2 eine Dependency auf den Wert von Schleifendurchlauf 1 hat, Schleifendurchlauf 3 eine auf den Wert von Schleifendurchlauf 2 usw. Dadurch kommst du nicht unter 1 Zyklus pro Schleifendurchlauf. Zumindest nicht ohne ganz wilde Klimmzüge, und ich kann mir echt nicht vorstellen dass aktuelle CPUs das können.

Wenn man den Loop dagegen selbst unrolled ist die Induktionsvariable kein Problem, man macht einfach nur ein Update pro Iteration und nicht ein Update pro Element. Genau so kann ein guter Optimizer mit sowas umgehen. Der hat aber im Gegensatz zur CPU auch ausreichend Zeit sich den Code anzusehen und rauszufinden wie er das alles optimal in Maschinencode giessen kann.

hkdd

@wob sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Wozu sind die Seeks in deinem Code?

Bei großen Dateien ( > als max Pufferlänge) lese ich immer nur Blöcke in die Max-Länge ein und einen Restblock, falls erforderlich
Seek beginnt mit 0 und dann immer mit dem Beginn des nächsten Blockes.

                if (VerglRestLen > 0)
                {
                    VerglOffset = VerglOffset + VerglLen;   // Offset nächster Block
                    goto NxtPuVergleich;
                }

hkdd

@wob sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Vielleicht kann man den Code auch ändern, sodass statt true/false gleich ein Offset rauskommt

Die meisten Dateien sind identisch, so dass die Behandlung von evtl. Differenzen unrelevant ist. Wenn eine Differenz auftritt, dann kommt es auf ein paar Sekunden nicht an.
In meinem Test habe ich ja immer die Ordner mit sich selbst verglichen.
Es geht um identische Dateien und die Zeit, um festzustellen, ob sie identisch sind.

Ich habe jetzt ein wirklich funktionierendes Beispiel eines Inline-Assemblers gefunden, da werde ich versuchen meinen Compare-Code für einen Block mit Puffer1+2 auf diese Weise in das Programm einzufügen.
Mit DLLs aus C++ hatte ich keinen Erfolg.
https://stackoverflow.com/questions/3216535/x86-x64-cpuid-in-c-sharp

hustbaer

@hkdd
Hast du es mal mit

[DllImport("ntdll.dll", EntryPoint = "RtlCompareMemory")]  
static extern IntPtr RtlCompareMemory(IntPtr Source1, IntPtr Source2, IntPtr length);

probiert?

Swordfish

@hkdd sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Bei großen Dateien ( > als max Pufferlänge) lese ich immer nur Blöcke in die Max-Länge ein und einen Restblock, falls erforderlich
Seek beginnt mit 0 und dann immer mit dem Beginn des nächsten Blockes.

FileStream.Read advanced den file-pointer doch sowieso schon. Völlig für die Katz'.

hkdd

@Swordfish sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Völlig für die Katz'.

Da hast Du Recht, es funktioniert genau so ohne Seek.
Ich habe es heraus genommen.
Danke für den Hinweis.

TGGC

@hustbaer sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

@TGGC
Äh, nein, der Loop wird nicht unrolled!?!

Alleine schon das Inkrementieren der Induktionsvariable "serialisiert" dir den Loop. Klar kann die CPU auch die Induktionsvariable "renamen", aber das ändert nichts daran dass Schleifendurchlauf 2 eine Dependency auf den Wert von Schleifendurchlauf 1 hat, Schleifendurchlauf 3 eine auf den Wert von Schleifendurchlauf 2 usw. Dadurch kommst du nicht unter 1 Zyklus pro Schleifendurchlauf. Zumindest nicht ohne ganz wilde Klimmzüge, und ich kann mir echt nicht vorstellen dass aktuelle CPUs das können.

Wenn man den Loop dagegen selbst unrolled ist die Induktionsvariable kein Problem, man macht einfach nur ein Update pro Iteration und nicht ein Update pro Element. Genau so kann ein guter Optimizer mit sowas umgehen. Der hat aber im Gegensatz zur CPU auch ausreichend Zeit sich den Code anzusehen und rauszufinden wie er das alles optimal in Maschinencode giessen kann.

Genau, die bauen in ihre CPUs 6,7 unabhängige Einheiten, die paralell arbeiten könnten aber machen das dann alles nur sequentiell, nur weil du dir das nicht vorstellen kannst...

Informier dich doch mal über Speculative execution.

Swordfish

@hkdd sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Ich habe es heraus genommen.

Und?

hkdd

@hustbaer sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Hast du es

Ja, allerdings habe ich an anderer Stelle den DllImport anders gefunden

        [DllImport("ntdll.dll", EntryPoint = "RtlCompareMemory", SetLastError = false)]
        private static extern ulong RtlCompareMemory(IntPtr Source1, IntPtr Source2, ulong length);



                IntPtr sPtr1 = Marshal.UnsafeAddrOfPinnedArrayElement(ByPu1, 0);
                IntPtr sPtr2 = Marshal.UnsafeAddrOfPinnedArrayElement(ByPu2, 0);

                ulong uLen = Convert.ToUInt64(VerglLen);
                ulong okLen = RtlCompareMemory(sPtr1, sPtr2, uLen);
                ulong uDiff = uLen - okLen;

                if (uDiff > 0)
                { isDiff = 1; } // es gibt Differenzen
                else
                { isDiff = 0; } // es gibt keine Differenzen

Die Laufzeit für die gleichen Daten, wie bisher = 6'44"

Ich denke, alle diese Routinen arbeiten mit der for-Schleife.
Keine nutzt eine effektive Ass-Routine mit REPZ CMPSD

  MOV   ESI,[EBP+16] ; Offset Puffer1
  MOV   EDI,[EBP+12] ; Offset Puffer2
  MOV   ECX,[EBP+08] ; Länge in Bytes 
  SHR   ECX,2        ; Länge / 4 : in DWords 
  CLD
  REPZ  CMPSD        ; DWords vergleichen - den kompletten Puffer
  JNZ   @Diff        ; --> Differenz

hustbaer

@TGGC

Genau, die bauen in ihre CPUs 6,7 unabhängige Einheiten, die paralell arbeiten könnten aber machen das dann alles nur sequentiell, nur weil du dir das nicht vorstellen kannst...

Wenn Dependencies bestehen, dann ja. Man kann das Ergebnis halt einfach nicht berechnen bevor der Input feststeht. Und wenn das Ergebnis dann gleich wieder als Input für die nächste Operation verwendet wird...

Informier dich doch mal über Speculative execution.

Das hat nichts mit Speculative Execution zu tun. Mit Speculative Execution kann man den bedingten Sprung in der Schleife mal testweise ausführen bevor das Ergebnis feststeht. Aber wenn du 1000x hintereinander ein INC RAX hast, da hilft alles Register-Renaming und Speculative Execution nicht dass man das in unter 1000 Zyklen ausgeführt bekommen würde. Und die Sache wird noch schwieriger dadurch dass es nichtmal 1000 INC RAX Befehle hintereinander sind, sondern immer der selbe, nur halt in 1000 aufeinanderfolgenden Schleifendurchläufen.

Vielleicht solltest ja du dich mal etwas näher damit beschäftigen wie moderne CPUs so arbeiten. Anstatt davon auszugehen dass die zaubern können und schon alles richten werden.

firefly

@hkdd Liegt halt daran, dass RtlCompareMemory die Anzahl der gleichen Bytes zurück liefert.
-> Es geht durch den ganzen block durch.

Dein ASM Code bricht, wenn ich das richtig verstanden habe, bei dem ersten unterschied ab.
Und wenn ein unterschied entdeckt wurde, dann wird nochmal durch den block durchgegangen (diesmal komplett, um dann alle Differenzen "anzuzeigen" (was auch immer "anzeigen" bedeutet)

Dadurch sind beide codes nicht vergleichbar!

Der C# Code (mit RtlCOmpareMemory) geht zweimal durch den kompletten block durch (wenn eine Differenz gefunden wurde)
Der ASM code aber nicht immer.

Das zweimal durchgehen durch den ganzen block macht der ASM code, wenn die Differenz sich im letzten byte befindet.

Um eine besser vergleichbarkeit zu haben müsstest der C# folgendes tun:

Den zu prüfenden block in einer schleife durchlaufen und bei der ersten differenz die schleife abbrechen

Das würde deinem ASM code, welche eine Differenz feststellt, am nächsten kommen.

Ansonsten sollte man den durchlauf mit einem profiler messen um festzustellen, wo die meiste Zeit drauf geht

TGGC

@hustbaer Ist doch Quatsch was du erzählst. Wenn man beim ersten Unterschied abbricht, gibts keine Abhängigkeiten. Wenn man eins addiert, wenn der compare ungleich sagt, gibts nur in dem Fall eine Abhängigkeit, der Rest bleibt unabhängig. D.h. die zweite Loop kann lange angefangen werden, bevor die erste fertig ist. Jede aktuelle CPU wird mehre Loopsdurchläufe paralell machen. Der amortisierte Zeitaufwand wird im Bereich 1 Cycle liegen, wenns kein Memory Stall gibt.

hkdd

@firefly sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Dadurch sind beide codes nicht vergleichbar

Das sehe ich auch so.
Ich habe nun eine weitere Frage zu meiner Ass-Routine.
Wenn ich die starte, dann wollen die Befehle natürlich die beiden Pufferinhalte lesen, um zu vergleichen.
Dieses Lesen wird aber verhindert, es kommt sofort die Meldung:

System.AccessViolationException

Es wurde versucht im geschützten Speicher zu lesen oder zu schreiben.

Bei RtlCompareMemory werden diesen beiden Puffer vor dem Aufruf freigegeben.

            IntPtr sPtr1 = Marshal.UnsafeAddrOfPinnedArrayElement(ByPu1, 0);
            IntPtr sPtr2 = Marshal.UnsafeAddrOfPinnedArrayElement(ByPu2, 0);

Meine Routine kann aber mit IntPtr nichts anfangen.
Kann man so eine Freigabe auch derart machen, dass man anschließend einen Pointer auf die byte[] bekommt ?

Swordfish

@hkdd sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:

Ass-Routine

Perversling.

hustbaer

@TGGC

Ist doch Quatsch was du erzählst.

Nein ist es nicht, du verstehst bloss offenbar nicht worauf ich hinaus will.

Wenn man beim ersten Unterschied abbricht, gibts keine Abhängigkeiten.

Doch, natürlich. Und zwar beim Inkrementieren der Induktionsvariable. Wie ich ja schon geschrieben habe. Durch Loop-Unrolling und Renaming wird daraus

...
i2 = i1 + 1
...
i3 = i2 + 1
...
i4 = i3 + 1
...
i5 = i4 + 1
...

Alleine das bremst dich schon auf max. 1 Schleifendurchlauf pro Zyklus aus, weil Berechnungen die jeweils von der vorigen Berechnung abhängen halt nicht parallelisiert werden können. Du kannst i3 = i2 + 1 halt nicht ausrechnen ohne i2 zu kennen. Wenn danach lange genug nichts kommt was den Wert von i3 benötigt, dann wird das halt entsprechend reordered und tut nicht weiter weg. Wenn aber das Ergebnis sofort als Input für die nächste Operation benötigt wird, und das immer und immer wieder, dann staut sich das auf sozusagen.

Dazu kommt dann noch das was die Schleife "eigentlich tut" (das Laden und vergleichen der zwei Streams), und es würde mich sehr wundern wenn man damit nicht mindestens auf 3-4 Zyklen pro Durchlauf kommen würde.

Aber guck mal, ich hab heute Abend Zeit und werde einfach mal ne einfache "ein DWORD pro Durchlauf" Schleife basteln und dann gucken wie die performt, vs. "schlauere" Schleifen.