Assembler-Code wegen Laufzeit-Optimierung benutzen
-
@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 CMPSDMOV 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
-
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 1000INC 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.
-
@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
-
@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.
-
@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 ?
-
-
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 ohnei2
zu kennen. Wenn danach lange genug nichts kommt was den Wert voni3
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.
-
Die Induktionsvariable ist aber von nichts weiter abhänging und daher braucht das erhöhen eben auch nur 1 Cycle. Es ist immer +1, egal woher der Speicher geladen wird oder der Vergleich ausgeht. Die Inkrements können daher als Microps alle direkt hintereinander unrolled werden. Das Erhöhen der Variable bremst die Schleife also nie, sie wird lange bevor der Speicher antwortet schon für die nächsten 5-6 Durchläufe berechnet.
-
Sorry @hustbaer, aber 1:0 für den Tetrisspieler.
-
@hkdd sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:
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 ?IntPtr ist vereinfacht gesagt nichts anderes als in C ein void pointer (Zeigen auf eine Speicherstelle).
Die ersten beiden Parameter von RtlCompareMemory sind VOID pointer, die in C# als IntPtr abgebildet werden.https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/content/wdm/nf-wdm-rtlcomparememory
Man kan den inptr aber auch in ein void pointer konvertieren:
https://docs.microsoft.com/en-US/dotnet/api/system.intptr.topointer
-
@firefly sagte in Assembler-Code wegen Laufzeit-Optimierung benutzen:
Man kan den inptr aber auch in ein void pointer konvertieren:
Es kommt weiterhin dieser Fehler, sicherlich habe ich etwas falsch codiert...
namespace CompHK { using System; using System.Globalization; using System.Linq; using System.Reflection; using System.Runtime.InteropServices; using System.Text; public partial class Form1 { [Flags] private enum AllocationTypes : uint { Commit = 0x1000, Reserve = 0x2000, Reset = 0x80000, LargePages = 0x20000000, Physical = 0x400000, TopDown = 0x100000, WriteWatch = 0x200000 } [Flags] private enum MemoryProtections : uint { Execute = 0x10, ExecuteRead = 0x20, ExecuteReadWrite = 0x40, ExecuteWriteCopy = 0x80, NoAccess = 0x01, ReadOnly = 0x02, ReadWrite = 0x04, WriteCopy = 0x08, GuartModifierflag = 0x100, NoCacheModifierflag = 0x200, WriteCombineModifierflag = 0x400 } [Flags] private enum FreeTypes : uint { Decommit = 0x4000, Release = 0x8000 } [UnmanagedFunctionPointerAttribute(CallingConvention.Cdecl)] public unsafe delegate bool CompBytArrDelegate(byte* Puff1, byte* Puff2, int PuLen); private static unsafe bool CompBytArr(byte[] Puffer1, byte[] Puffer2, int PuffLen) { bool rCode = false; IntPtr p = NativeMethods.VirtualAlloc( IntPtr.Zero, new UIntPtr((uint)CompBytArrCode.Length), AllocationTypes.Commit | AllocationTypes.Reserve, MemoryProtections.ExecuteReadWrite); try { unsafe { Marshal.Copy(CompBytArrCode, 0, p, CompBytArrCode.Length); // Asm-Code => p CompBytArrDelegate delAsmCode = (CompBytArrDelegate)Marshal.GetDelegateForFunctionPointer (p, typeof(CompBytArrDelegate)); IntPtr sPtr1 = Marshal.UnsafeAddrOfPinnedArrayElement(Puffer1, 0); IntPtr sPtr2 = Marshal.UnsafeAddrOfPinnedArrayElement(Puffer2, 0); rCode = delAsmCode((byte*)sPtr1, (byte*)sPtr2, PuffLen); } } finally { NativeMethods.VirtualFree(p, 0, FreeTypes.Release); } return rCode; } #region ASM private static readonly byte[] CompBytArrCode = new byte[] { // .CODE // Start: 0x55, // PUSH EBP 0x8B, 0xEC, // MOV EBP,ESP 0x56, // PUSH ESI 0x57, // PUSH EDI 0x53, // PUSH EBX 0x51, // PUSH ECX 0x33, 0xDB, // XOR EBX,EBX ; EBX löschen 0x8B, 0x75, 0x10, // MOV ESI,[EBP+16] ; Offset Puffer1 0x8B, 0x7D, 0x0C, // MOV EDI,[EBP+12] ; Offset Puffer2 0x8B, 0x4D, 0x08, // MOV ECX,[EBP+08] ; Länge in Bytes 0x8A, 0xD9, // MOV BL,CL ; Bit 0+1 in BL retten = Restlänge 0xC1, 0xE9, 0x02, // SHR ECX,2 ; Länge / 4 : in DWords 0x80, 0xE3, 0x03, // AND BL,3 ; Restlänge in BL = 0 ? 0x74, 0x11, // JZ @CmpDW ; --> ja, nur DWords vergleichen 0xFC, // CLD 0xF3, 0xA7, // REPZ CMPSD ; DWords vergleichen 0x75, 0x07, // JNZ @Diff ; --> Differenz 0x8B, 0xCB, // MOV ECX,EBX ; Restlänge 1..3 0xFC, // CLD 0xF3, 0xA6, // REPZ CMPSB ; Restlänge in Bytes vergleichen 0x74, 0x0A, // JZ @EndeOK ; --> keine Differenz // @Diff: 0x33, 0xC0, // XOR EAX,EAX ; true : Differenz 0x48, // DEC EAX ; EAX = FFFFFFFF 0xEB, 0x07, // JMP @Ende ; --> RCode = true : Differenz // @CmpDW: 0xFC, // CLD 0xF3, 0xA7, // REPZ CMPSD ; DWords vergleichen 0x75, 0xF6, // JNZ @Diff ; --> Differenz // @EndeOK: 0x33, 0xC0, // XOR EAX,EAX ; RCode = false : keine Differenz // @Ende: 0x59, // POP ECX 0x5B, // POP EBX 0x5F, // POP EDI 0x5E, // POP ESI 0x8B, 0xE5, // MOV ESP,EBP 0x5D // POP EBP }; // END Start #endregion } // public partial class Form1 } // namespace CompHK
-
@hkdd sagte in [Assembler-Code wegen Laufzeit-Optimierung benutzen]
Es kommt weiterhin dieser Fehler
aha.
-
Dieser Beitrag wurde gelöscht!
-
So, hoffe das ist ein passendes Beispiel:
int test(int64_t* ptr1, int64_t* ptr2, size_t length) { auto end = ptr1 + length; while (ptr1 < end) { IACA_START if (*ptr1 != *ptr2) { return 1; } ptr1++; ptr2++; } IACA_END return 0; }
Block Throughput: 1.00 Cycles Throughput Bottleneck: Dependency chains Loop Count: 22 Port Binding In Cycles Per Iteration: -------------------------------------------------------------------------------------------------- | Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | -------------------------------------------------------------------------------------------------- | Cycles | 0.5 0.0 | 0.5 | 1.0 1.0 | 1.0 1.0 | 0.0 | 0.5 | 0.5 | 0.0 | -------------------------------------------------------------------------------------------------- DV - Divider pipe (on port 0) D - Data fetch pipe (on ports 2 and 3) F - Macro Fusion with the previous instruction occurred * - instruction micro-ops not bound to a port ^ - Micro Fusion occurred # - ESP Tracking sync uop was issued @ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected X - instruction not supported, was not accounted in Analysis | Num Of | Ports pressure in cycles | | | Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | ----------------------------------------------------------------------------------------- | 1 | | | 1.0 1.0 | | | | | | mov rax, qword ptr [rdx+rcx*1] | 2^ | 0.5 | | | 1.0 1.0 | | 0.5 | | | cmp qword ptr [rcx], rax | 0*F | | | | | | | | | jnz 0x16 | 1 | | 0.5 | | | | | 0.5 | | add rcx, 0x8 | 1* | | | | | | | | | cmp rcx, r8 | 0*F | | | | | | | | | jb 0xffffffffffffffe7 Total Num Of Uops: 5
it|in|Dissasembly :012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 0| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 0| 0| TYPE_LOAD (1 uops) :s---deeeew----R-------p | | | | | | | | | | | | 0| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 0| 1| TYPE_LOAD (1 uops) :s---deeeew----R-------p | | | | | | | | | | | | 0| 1| TYPE_OP (1 uops) :A--------dw----R-------p | | | | | | | | | | | | 0| 2|jnz 0x16 : | | | | | | | | | | | | | | 0| 2| TYPE_OP (0 uops) :w--------------R-------p | | | | | | | | | | | | 0| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 0| 3| TYPE_OP (1 uops) :sdw------------R-------p | | | | | | | | | | | | 0| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 0| 4| TYPE_OP (1 uops) : Adw-----------R-------p | | | | | | | | | | | | 0| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 0| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 1| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 1| 0| TYPE_LOAD (1 uops) : As--deeeew-----R-------p | | | | | | | | | | | | 1| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 1| 1| TYPE_LOAD (1 uops) : As--deeeew-----R-------p | | | | | | | | | | | | 1| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | | 1| 2|jnz 0x16 : | | | | | | | | | | | | | | 1| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 1| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 1| 3| TYPE_OP (1 uops) : Adw------------R-------p | | | | | | | | | | | | 1| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 1| 4| TYPE_OP (1 uops) : Aw------------R-------p | | | | | | | | | | | | 1| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 1| 5| TYPE_OP (0 uops) : w-------------R-------p | | | | | | | | | | | | 2| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 2| 0| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 2| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 2| 1| TYPE_LOAD (1 uops) : As--deeeew-----R-------p | | | | | | | | | | | | 2| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | | 2| 2|jnz 0x16 : | | | | | | | | | | | | | | 2| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 2| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 2| 3| TYPE_OP (1 uops) : Adw------------R-------p | | | | | | | | | | | | 2| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 2| 4| TYPE_OP (1 uops) : A-w------------R-------p | | | | | | | | | | | | 2| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 2| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 3| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 3| 0| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 3| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 3| 1| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 3| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | | 3| 2|jnz 0x16 : | | | | | | | | | | | | | | 3| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 3| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 3| 3| TYPE_OP (1 uops) : Adw------------R-------p | | | | | | | | | | | | 3| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 3| 4| TYPE_OP (1 uops) : A-w------------R-------p | | | | | | | | | | | | 3| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 3| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 4| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 4| 0| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 4| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 4| 1| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 4| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | | 4| 2|jnz 0x16 : | | | | | | | | | | | | | | 4| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 4| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 4| 3| TYPE_OP (1 uops) : Adw------------R-------p | | | | | | | | | | | | 4| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 4| 4| TYPE_OP (1 uops) : A-w------------R-------p | | | | | | | | | | | | 4| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 4| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 5| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 5| 0| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 5| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 5| 1| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 5| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | | 5| 2|jnz 0x16 : | | | | | | | | | | | | | | 5| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 5| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 5| 3| TYPE_OP (1 uops) : Adw------------R-------p | | | | | | | | | | | | 5| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 5| 4| TYPE_OP (1 uops) : A-w------------R-------p | | | | | | | | | | | | 5| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 5| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | | 6| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 6| 0| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 6| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 6| 1| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | | 6| 1| TYPE_OP (1 uops) : A--------dw----R-------p| | | | | | | | | | | | 6| 2|jnz 0x16 : | | | | | | | | | | | | | | 6| 2| TYPE_OP (0 uops) : w--------------R-------p| | | | | | | | | | | | 6| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 6| 3| TYPE_OP (1 uops) : Adw------------R-------p| | | | | | | | | | | | 6| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 6| 4| TYPE_OP (1 uops) : A-w------------R-------p| | | | | | | | | | | | 6| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 6| 5| TYPE_OP (0 uops) : w--------------R-------p| | | | | | | | | | | | 7| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 7| 0| TYPE_LOAD (1 uops) : As--deeeew----R-------p| | | | | | | | | | | | 7| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 7| 1| TYPE_LOAD (1 uops) : As--deeeew----R-------p| | | | | | | | | | | | 7| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | 7| 2|jnz 0x16 : | | | | | | | | | | | | | | 7| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | 7| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 7| 3| TYPE_OP (1 uops) : Adw------------R-------p | | | | | | | | | | | 7| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 7| 4| TYPE_OP (1 uops) : A-w------------R-------p | | | | | | | | | | | 7| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 7| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | 8| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 8| 0| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | 8| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 8| 1| TYPE_LOAD (1 uops) : As--deeeew----R-------p | | | | | | | | | | | 8| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | 8| 2|jnz 0x16 : | | | | | | | | | | | | | | 8| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | 8| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 8| 3| TYPE_OP (1 uops) : Acdw-----------R-------p | | | | | | | | | | | 8| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 8| 4| TYPE_OP (1 uops) : A--w-----------R-------p | | | | | | | | | | | 8| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 8| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | 9| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 9| 0| TYPE_LOAD (1 uops) : A-s-deeeew----R-------p | | | | | | | | | | | 9| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 9| 1| TYPE_LOAD (1 uops) : A-s-deeeew----R-------p | | | | | | | | | | | 9| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | 9| 2|jnz 0x16 : | | | | | | | | | | | | | | 9| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | 9| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 9| 3| TYPE_OP (1 uops) : A-dw-----------R-------p | | | | | | | | | | | 9| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 9| 4| TYPE_OP (1 uops) : A--w-----------R-------p | | | | | | | | | | | 9| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 9| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | 10| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 10| 0| TYPE_LOAD (1 uops) : A-s-deeeew----R-------p | | | | | | | | | | | 10| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 10| 1| TYPE_LOAD (1 uops) : A-s-deeeew----R-------p | | | | | | | | | | | 10| 1| TYPE_OP (1 uops) : A--------dw----R-------p | | | | | | | | | | | 10| 2|jnz 0x16 : | | | | | | | | | | | | | | 10| 2| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | 10| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 10| 3| TYPE_OP (1 uops) : A-dw-----------R-------p | | | | | | | | | | | 10| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 10| 4| TYPE_OP (1 uops) : A--w-----------R-------p | | | | | | | | | | | 10| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 10| 5| TYPE_OP (0 uops) : w--------------R-------p | | | | | | | | | | | 11| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 11| 0| TYPE_LOAD (1 uops) : |A-s-deeeew----R-------p | | | | | | | | | | | 11| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 11| 1| TYPE_LOAD (1 uops) : |A-s-deeeew----R-------p | | | | | | | | | | | 11| 1| TYPE_OP (1 uops) : |A--------dw----R-------p | | | | | | | | | | | 11| 2|jnz 0x16 : | | | | | | | | | | | | | | 11| 2| TYPE_OP (0 uops) : |w--------------R-------p | | | | | | | | | | | 11| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 11| 3| TYPE_OP (1 uops) : |A-dw-----------R-------p | | | | | | | | | | | 11| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 11| 4| TYPE_OP (1 uops) : |A--w-----------R-------p | | | | | | | | | | | 11| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 11| 5| TYPE_OP (0 uops) : |w--------------R-------p | | | | | | | | | | | 12| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 12| 0| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 12| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 12| 1| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 12| 1| TYPE_OP (1 uops) : | A--------dw----R-------p | | | | | | | | | | | 12| 2|jnz 0x16 : | | | | | | | | | | | | | | 12| 2| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | | 12| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 12| 3| TYPE_OP (1 uops) : | A-dw-----------R-------p | | | | | | | | | | | 12| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 12| 4| TYPE_OP (1 uops) : | A--w-----------R-------p | | | | | | | | | | | 12| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 12| 5| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | | 13| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 13| 0| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 13| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 13| 1| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 13| 1| TYPE_OP (1 uops) : | A--------dw----R-------p | | | | | | | | | | | 13| 2|jnz 0x16 : | | | | | | | | | | | | | | 13| 2| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | | 13| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 13| 3| TYPE_OP (1 uops) : | A-dw-----------R-------p | | | | | | | | | | | 13| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 13| 4| TYPE_OP (1 uops) : | A--w-----------R-------p | | | | | | | | | | | 13| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 13| 5| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | | 14| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 14| 0| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 14| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 14| 1| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 14| 1| TYPE_OP (1 uops) : | A--------dw----R-------p | | | | | | | | | | | 14| 2|jnz 0x16 : | | | | | | | | | | | | | | 14| 2| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | | 14| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 14| 3| TYPE_OP (1 uops) : | A-dw-----------R-------p | | | | | | | | | | | 14| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 14| 4| TYPE_OP (1 uops) : | A--w-----------R-------p | | | | | | | | | | | 14| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 14| 5| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | | 15| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 15| 0| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 15| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 15| 1| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 15| 1| TYPE_OP (1 uops) : | A--------dw----R-------p | | | | | | | | | | | 15| 2|jnz 0x16 : | | | | | | | | | | | | | | 15| 2| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | | 15| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 15| 3| TYPE_OP (1 uops) : | A-dw-----------R-------p | | | | | | | | | | | 15| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 15| 4| TYPE_OP (1 uops) : | A--w-----------R-------p | | | | | | | | | | | 15| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 15| 5| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | | 16| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 16| 0| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 16| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 16| 1| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | | 16| 1| TYPE_OP (1 uops) : | A--------dw----R-------p| | | | | | | | | | | 16| 2|jnz 0x16 : | | | | | | | | | | | | | | 16| 2| TYPE_OP (0 uops) : | w--------------R-------p| | | | | | | | | | | 16| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 16| 3| TYPE_OP (1 uops) : | A-dw-----------R-------p| | | | | | | | | | | 16| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 16| 4| TYPE_OP (1 uops) : | A--w-----------R-------p| | | | | | | | | | | 16| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 16| 5| TYPE_OP (0 uops) : | w--------------R-------p| | | | | | | | | | | 17| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 17| 0| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p| | | | | | | | | | | 17| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 17| 1| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p| | | | | | | | | | | 17| 1| TYPE_OP (1 uops) : | A--------dw----R-------p | | | | | | | | | | 17| 2|jnz 0x16 : | | | | | | | | | | | | | | 17| 2| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | 17| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 17| 3| TYPE_OP (1 uops) : | A-dw-----------R-------p | | | | | | | | | | 17| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 17| 4| TYPE_OP (1 uops) : | A--w-----------R-------p | | | | | | | | | | 17| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 17| 5| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | 18| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 18| 0| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | 18| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 18| 1| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | 18| 1| TYPE_OP (1 uops) : | A--------dw----R-------p | | | | | | | | | | 18| 2|jnz 0x16 : | | | | | | | | | | | | | | 18| 2| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | 18| 3|add rcx, 0x8 : | | | | | | | | | | | | | | 18| 3| TYPE_OP (1 uops) : | A-dw-----------R-------p | | | | | | | | | | 18| 4|cmp rcx, r8 : | | | | | | | | | | | | | | 18| 4| TYPE_OP (1 uops) : | A--w-----------R-------p | | | | | | | | | | 18| 5|jb 0xffffffffffffffe7 : | | | | | | | | | | | | | | 18| 5| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | | 19| 0|mov rax, qword ptr [rdx+rcx*1] : | | | | | | | | | | | | | | 19| 0| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | 19| 1|cmp qword ptr [rcx], rax : | | | | | | | | | | | | | | 19| 1| TYPE_LOAD (1 uops) : | A-s-deeeew----R-------p | | | | | | | | | | 19| 1| TYPE_OP (1 uops) : | A--------dw----R-------p | | | | | | | | | | 19| 2|jnz 0x16 : | | | | | | | | | | | | | | 19| 2| TYPE_OP (0 uops) : | w--------------R-------p | | | | | | | | | |
Ergebnis: 22 Loops parallel auf einer CPU ohne manuelles Unroll. Bezweifle das da irgendein Haupspeicher mitkommen würde. Wenn die Schleife kurz und alles im Cache, passiert natürlich was Anderes. Für weiter Info empfehle ich mal ccpCon going nowhere googeln.
-
@Swordfish Das wird sich weisen.
-
@hustbaer Wieso? Willst Du zum Tetrisspielen anfangen?
-
Ergebnis: 22 Loops parallel auf einer CPU ohne manuelles Unroll. Bezweifle das da irgendein Haupspeicher mitkommen würde.
Sollte sich knapp ausgehen. Wichtig ist hier doch bloss "Block Throughput: 1.00 Cycles", right? D.h. die CPU schafft im Schnitt einen Durchlauf pro Zyklus abzuschliessen ("retire") -- egal wie viele Durchläufe gleichzeitig "in flight" sind. Ein Durchlauf macht einen Vergleich und lädt dafür zwei Werte. Bei DWORD heisst das 2x4=8 Byte, also knapp am theoretischen Maximum von ~10 Byte/Zyklus. Bei Byte-Vergleichen bist du dann schon weit darunter.
(EDIT: Ich hab' erst jetzt gesehen dass du den Typ auf int64 geändert hast. Damit geht es sich mit dem Hauptspeicher dann nicht mehr aus, ja. Nur genau an dieser Änderung sehen wir auch dass die Implementierung eben genau nicht egal ist. Denn wenn sie so egal wäre, dann könnten wir auch gleich
unsigned char
verwenden -- bzw. hätten eben bei int32 bleiben können.)Und wenn...
Wenn die Schleife kurz und alles im Cache, passiert natürlich was Anderes.
...dann bist du selbst bei DWORD Vergleichen weit darunter.
D.h. für mich: nein, die Implementierung ist nicht egal. Sie ist weniger wichtig als ich ursprünglich dachte, aber es ist lange noch nicht so dass eine einfache Schleife die z.B. byteweise vergleicht die volle Speicherbandbreite ausreizen könnte.
-
Die oben gezeigte Schleife auf einer 64Bit CPU lädt 16 Byte pro Cycle. Das ist soweit ich weis das theoretische Maximum aus dem 1st Level Cache. Das ist überhaupt das Maximum für normalen 64Bit Instruktionen auf aktuellen Maschinen, da beide Load Ports (2/3 in der Tabelle) zu 100% beschäftigt sind. Andere Ports haben noch Luft und könnten möglicherweile den "Fehlerzähler" noch nebenbei berechenen, ohne das es länger dauert.
Bei einem kompletten Cachemiss würde ich das Penalty auf mindestens eine Größenordnung schätzen, d.h. wenn einzelne Bytes verglichen werden kommt es möglicherweise irgendwann wieder auf den genauen Code an - das man sowas optimiert war aber wohl von Post #1 klar?
-
Also hier https://en.wikichip.org/wiki/intel/microarchitectures/coffee_lake steht "64 B/cycle load bandwidth" für den L1D Cache. (Bei Haswell übrigens auch schon, was gut ist, weil ich hab nur nen alten Haswell zu Hause stehen.)
Das ginge, wenn jeder Load Port 32 Byte auf einmal laden kann. Das wären 256 Bit, also AVX Registerbreite. Klingt für mich jetzt nicht unvernünftig. Aber da ich noch nicht zu Hause bin hatte ich noch keine Zeit auszuprobieren wie viel
memcmp
,RtlCompareMemory
bzw. auch einfach ein von GCC mit -O3 unrolled Loop wirklich schaffen.d.h. wenn einzelne Bytes verglichen werden kommt es möglicherweise irgendwann wieder auf den genauen Code an - das man sowas optimiert war aber wohl von Post #1 klar?
Das war mir nicht von Anfang an klar. Du hast geschrieben
Der Code macht 2% ALU Auslastung und 100% Speicherauslastung. Die genaue Implementation ist daher irrelevant, solange das Prefetchen erkannt werden kann. Die CPU wird ja sogar die effektive Schleife bei der Ausführung umschreiben durch Register Renaming etc. so das selbst der genaue Assemblercode gar nicht in dem Sinne befolgt wird.
Ich hab das als "ist egal, die CPU ist eh immer schneller als der Speicher, da muss man gar nix optimieren" verstanden . Der OP hatte davor Code gezeigt der 32 Bit Werte lädt. Natürlich hab ich deine Aussage dann darauf bezogen. Und mich daher dann zu dem Thema gemeldet, da es halt nicht stimmt.
-
Und das ist genau was ich sagte mit 64Bit Instruktionen. Wie schon viel weiter oben gesagt wurde: mit SSE/AVX wirds noch schneller, nur eben das Lesen ausm Speicher bremst das trotzdem aus, sobald der Cache alle ist und bei 2 GByte ist halt der Grossteil nicht im Cache. Überleg dir einfach mal wie schnell das fertig sein sollte, wenn es nur ansatzweise an der Vergleichsschleife liegen würde (Sekundenbruchteile) und wie lange es dauert. Diese Vergleichsschleife macht irgendwie 2% aus vom ganzen Programm - irgendwas fertiges aufrufen und fertig. Ansonsten schnellere Speichermedien kaufen.
Ich seh auch bei http://quick-bench.com kaum Unterschied zwischen 64Bit und 32Bit Schritten oder memcmp.
Genau das Gleiche bei den verlinkten Benchmarks von unterschiedlichen Implementation auf Stack Overflow, bei hinreichender Größe sind alle Algorithmen gleich schnell, wo sie am Anfang 3-4x Faktor Unterschiede hatten.
Ich sagte auch nicht jede Implementation, sondern eine die den Speicher schnell genug anfordert. Selbst 22x vorher schon das Byte anfordern reicht vermutlich nicht, das die nächste Cacheline immer früh genug da ist. Also extra dumm anstellen darf man sich nicht. Aber versuchen extra schlau sein mit selbstgebasteltem Assembler ist auch Unsinn.