Frage zur Implementierung von std::string::substr(int pos,int npos)

[HostBB]

Danke Hustbear für die gute Antwort.

Ich kenne es nur aus dem Großrechner Umfeld, da die Teile auf Datendurchsatz getrimmt sind haben die direkt Prozessor Befehle die dafür da sind.

Und beim Pc liegt ja der Hauptaugenmerk auf Performance.
Also das wäre für mich eine Antwort für den fehlenden performanten memmove Befehl.
Wenn ich mal mutmaßen darf:)

[hustbaer]

Sehe ich das richtig, dass die CPU probleme damit hat, 64 byte in 4-Byte paketen von einer cache-line in die andere zu schreiben, bevor die nächste Cache-Line aus dem Hauptspeicher ankommt? Wie schnell (alle wieviele Takte) kommen denn so (über den Daumen gepeilt) neue lines aus dem Hauptspeicher an, wenn die CPU erkannt hat dass man sequenziell zugreift und sie dann spekulativ alles folgende einliest?

Pfuh. Erstmal verstehe ich nicht ganz was du mit deiner ersten Frage meinst.
Und dann geht mein Wissen auch nicht *so* tief.

Bei allen normalen Zugriffen wird eine Cache-Line immer zuerst geladen wenn Werte darin geändert werden sollen - auch wenn in Folge dann die gesamte Cache-Line überschrieben wird. Allerdings liest man öfters was davon dass die neueren Intel CPUs (ab Pentium II oder III oder so) Befehle haben mit denen man "non-cached-writes" machen kann. Ob das aber den Effekt hat dass die entsprechende Cache-Line wirklich nichtmehr geladen werden muss, oder ob sie geladen/modifiziert/zurückgeschrieben wird, und nur nicht im Cache abgelegt (bzw. nicht verspätet zurückgeschrieben), das weiss ich einfach nicht. Auch genauere Angaben dazu kenne ich nicht (also z.B. wie gross die "Stücke" sind mit denen man da Daten lesen und/oder schreiben kann etc.) Habe mich damit auch noch nie so genau auseinandergesetzt. Ist auch rein theoretisches Wissen, braucht man einfach nicht
(Also *ich* nicht. Leute die z.B. ein optimales memcpy implementieren sollen brauchen das vielleicht schon - keine Ahnung. Mir aber auch wurst. :D)

Und wie schnell neue Lines geladen werden sobald der Prefetcher mal überrissen hat dass sequentielle Zugriffe erfolgen... so schnell wie die Hardware es kann natürlich
Wenn man eine "gemessene" Speicherbandbreite von ~8-12GB/sec, eine Taktrate von 3GHz und eine Line-Grösse von 64 Byte annimmt, und dann einfach mal ganz naiv rechnet, dann kommt man auf ~~22 Takte/Cache-Line. Das ist aber nicht viel besser als irgendeine Hausnummer. Diese Geschwindigkeit wird z.B. nichtmehr halten sobald die Zugriffe auf den Speicher nichtmehr linear erfolgen, sondern die Adresse sich sprunghaft ändert. Noch schlimmer: wenn immer zwischen Lesen und Schreiben gewechselt wird. Da kommt es dann u.A. enorm darauf an wie "schlau" die CPU ist. Je besser die CPU günstige Bedingungen für den Speicher-Controller schaffen kann, desto schneller wird es im Endeffekt gehen.

PS: Wobei die CPU wahrscheinlich eh einen Befehl hat, eine komplette Cacheline zu kopieren, nur das geht ja nur, wenn die zieladresse um x*64 byte verschoben ist... Brainlag.

Ich gehe nicht davon aus dass eine x86 so einen Befehl hat, da die Cache-Line-Grösse von Modell zu Modell variiert. Ein Befehl mit dem ich auf einem Modell 64 Byte kopiere und auf einem anderen Modell nur 32 Byte, wäre wohl kaum sehr hilfreich.

[Gast]

Danke für die ausführliche Antwort! Du (bzw. die Fragestellung hier auch) hast jetzt in mir das Interesse geweckt, mich mal genauer mit der Maschinensprache und einfachen optimierungen zu beschäftigen... Ist natürlich deprimieren, dass der Compiler eh besser ist als ich, hehehe.

[hustbaer]

Ist natürlich deprimieren, dass der Compiler eh besser ist als ich, hehehe.

Bei "normalem" Code ist das wohl so. Bzw. selbst wenn man es selbst mit viel Aufwand besser hinbekommen würde zahlt es sich einfach nicht aus.

Spezielle Dinge wie eben einen eigenen memcpy Loop, oder Alpha-Blitting-Funktionen, Funktionen zum Bearbeiten von Datenströmen (ala Vertex-Daten, grosse Matritzen, ...) etc. bekommt man aber immernoch selbst schneller hin. Und da kann es sich auch auszahlen, da man oft nur ein paar wenige solche Funktionen irgendwo braucht, wo dann aber gleich 90% der Zeit draufgeht.