Assembler-Code wegen Laufzeit-Optimierung benutzen
-
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 charverwenden -- 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,RtlCompareMemorybzw. 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.
-
@hustbaer Er weiß
zur Abwechslungwovon er redet. 2:0 für den Tetrisspieler.
-
@Swordfish Aber er drückt sich nicht immer sehr verständlich aus.
Selbst 22x vorher schon das Byte anfordern reicht vermutlich nicht, das die nächste Cacheline immer früh genug da ist.
Das Problem bei einer Schleife die Bytes lädt und vergleicht ist weniger das Prefetching als dass es eben nicht schneller als 1 Durchlauf/Zyklus geht, wegen der schon mehrfach erwähnten Dependency auf der Induktionsvariable. Damit bist du auf ~2x4 GB/s limitiert, und das schafft sogar der Hauptspeicher.
Die Limitierung durch die von dir erwähnten Load-Ports kommt dann noch zusätzlich hinzu.Das Prefetching selbst funktioniert nach meiner Erfahrung aber sehr zuverlässig.
Also extra dumm anstellen darf man sich nicht. Aber versuchen extra schlau sein mit selbstgebasteltem Assembler ist auch Unsinn.
Es in Assembler zu schreiben macht vermutlich wirklich kaum Sinn. Und wenn dann nur wenn man auch alle Register zieht -- also z.B. AVX Register verwendet.
Ich hatte deine Aussage einfach falsch verstanden. Worauf ich hinaus wollte ist lediglich dass man nicht glauben sollte der Speicher wäre so langsam bzw. die CPU so schnell, dass man mit einfachen Schleifen die Byteweise Datenströme abackern die Speicherbandbreite ausreizen könnte.
-
Du kannst das gern optimieren und unrollen etc. Fakt ist das ich in der Realität keinen Unterschied von memcmp, oder einer simplen Loop mit int* oder int64* sehe. Alles quasi gleich schnell. Und zwar so extrem schnell das ich den Fall mit "einmal lesen" kaum sinnvoll messen kann. Es kann nicht daran liegen und ich bezweifle stark das die Vergleichsschleife irgendwie substantiell schneller wird. Und Ich stelle es mir schwer vor die Schleife so umzuschreiben, das die ALU so voll ist, das nicht mehr jeden oder fast Cycle die maximale Anzahl loads gemacht wird - ausser man macht das absichtlich schlecht. Nur zur Erinnerung hast du vorhin noch behauptet das wegen irgendwelchen Dependencies ja nur aller 2-3 Cycle ein Load wäre.
