Frage zur Implementierung von std::string::substr(int pos,int npos)
-
Du wirst in den Headern aber alles finden, was du benötigst (alles von Speicherallozierung bis zu einem void* cast und nem memcpy und was weiß ich noch).
Wenn du keine spezifische Frage stellst, kannst du auch keine spezifische Antwort erwarten. Daraus, dass du keine spezifische Frage gestellt hast (wie ist das in der stl von vc++ implementiert beispielsweise), hast du eher den Eindruck erweckt, dass du keine Ahnung hast, damit musst du halt rechnen. Wenn du dann noch etwas unfreundlich antwortest, machst du dir auch nicht mehr Freunde.
-
aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:
Dabei handelt es sich um optimierungen mehr nicht der Content ist der gleiche:)
Woher willst du das wissen, wenn du die Implementierung noch nie gesehen hast?
aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:
ich mir die Definition kann ich mir auch ansehen aber dort sehe ich nur die Deklaration des ganzen:)
Die genaue Definition oder Implementierung steht in diversen Libs die wie du sagtest durch Header eingebunden werden:)Definition != Deklaration.
Aber wenn dich die Implementierung wirklich interessiert, kommst du da nicht darum herum. Folge doch einfach den Headern. Vielleicht findest du ja im Internet jemanden, der sich die Zeit genommen hat, das zu entschlüsseln - wobei du dir da wieder nicht sicher sein kannst, dass es genau deiner Implementierung entspricht.aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:
Aber gut ich glaube ich bin schneller wenn ich mir ... die lib disassembliere:)
Ah bestimmt. Da ja Maschinencode 1:1 den C++-Code repräsentiert, wirst du auch haargenau den Sourcecode bekommen...
aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:
Wollte doch nur ne Kurze antwort^^
Ich hab ja in meiner ersten Antwort bereits gesagt, dass das implementierungsspezifisch ist. Wenn du mir das nicht glaubst, ist das deine Sache.
-
Tut mir leid wenn es unfreundlich rüber kamm:)
Ich entschuldige mich vllt nochmal in aller Form es kann sein das es in euren IDE so ist das der gesamte Source der Bibliothek dabei ist:) Kann ja sein
Darum geht es nicht:)Das was ich hier mit über haupt bezwecken wollte... war zu erfahren was schneller
ist wenn ich jedes Byte einzeln verschiebe oder wennn ich mehrer Bytes aufeinmal verschiebe?Und das bezogen auf die Klasse std::Klasse String auf einem Windows Betriebsystem auf einem x386 Architektur.Ich weiß nicht wollen wir uns hier nur streiten...Nexus ich will nicht den C++
Code ich will wissen was auf der Prozessor ebene geschieht.Um genau zu sein:)
-
aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:
Nexus ich will nicht den C++
Code ich will wissen was auf der Prozessor ebene geschieht.Um genau zu sein:)Okay, dann habe ich dich falsch verstanden.
Schreib doch mal eine kleine Anwendung mit
substr(), und schau dir das zugehörige Disassembly an.
-
Also, ich gehe davon aus, dass für nicht-"alignte" am Anfang bzw. Ende des String Bytes byte um byte kopiert wird, bzw. halt Teile des gelesen weggeschmissen werden bis man ganze Maschinenworte lesen kann, also zB. 4 oder 8 Bytes. Wenn man das dann wieder auf ner ganzen Cache line macht, könnte ich mir vorstellen, dass am Ende ganze cache-lines kopiert werden (von außerhalb des Prozessors gesehen). Das ganze natürlich nur bei entsprechend langen Substrings. Du findest bestimmt irgendwo optimierte Assembler-Listings für Memcpy's unter bestimmten Bedingungen. Intel und AMD bieten da bestimmt was an, ob das ist, wie deine Lib implementiert wurde, steht natürlich auf einem anderen Blatt.
Aber eines muss klar sein, die Bibliothek muss alle Fälle irgendwie halbwegs effizient behandeln können. Darum kann zB. ein ansonsten suboptimaler Algorithmus effizienter sein, weil man davon ausgehen kann, dass man es oft nur mit kurzen Strings zu tun hat und der Ovearhead durch irgendwelche cleveren Berechnungen dann zu stark ins Gewicht fallen würde.
-
Ich habe bei mir mal nachgeschaut (dinkumware).
substr (in xstring) ruft, wie devkid schon geschrieben hat, einfach nur einen passenden Konstruktor auf.
Dieser Konstruktor (in xstring) ruft wieder eine passende Version von assign auf.
Dieses assign (in xstring) ruft neben anderen Dingen _Traits::copy auf.
_Traits dürfte wohl meist char_traits sein.
Dieses habe ich in iosfwd gefunden. Darin steht dann auch die copy-Funktion. Das ist dort eine simple for-Schleife.
Diese Header sollten immer vorhanden sein und nicht in irgendwelchen libs, da es sich ja hier immer um Templates handelt.
-
Ich hätte jetzt irgendwie optimierte spezialisierungen für char und wchar erwartet, die memcpy verwenden, was dann ja sehr wohl in ner Bibliothek stecken darf O.o Wie können sie nur!
-
Das war jetzt Ironie, nicht?
Diese Spezialisierungen gibt es natürlich auch. Hier kommen dann wmemcpy und memcpy zum Einsatz. Beides auch in iosfwd.
-
Decimad schrieb:
Ich hätte jetzt irgendwie optimierte spezialisierungen für char und wchar erwartet, die memcpy verwenden, was dann ja sehr wohl in ner Bibliothek stecken darf O.o Wie können sie nur!
Für std::basic_string werden vermutlich keine Spezialisierungen nötig sein, da std::basic_string vermutlich std::copy und ähnliches verwenden wird.
std::copy wird dann oft für primitive Typen (char, int, short, ...) spezialisiert sein.
Wenn ein Compiler-Hersteller aber z.B. weiss dass sein Compiler die Kopierschleife in std::copy zuverlässig erkennt, und mit einem memcpy Aufruf ersetzt, dann kann er genausogut die nunmehr sinnlosen Spezialisierungen weglassen, ohne dass es was ausmachen würde.Ich weiss zumindest dass es Compiler gibt die schlau genug sind solche einfachen Kopierschleifen durch memcpy zu ersetzen.
---
aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:
Das was ich hier mit über haupt bezwecken wollte... war zu erfahren was schneller
ist wenn ich jedes Byte einzeln verschiebe oder wennn ich mehrer Bytes aufeinmal verschiebe?Und das bezogen auf die Klasse std::Klasse String auf einem Windows Betriebsystem auf einem x386 Architektur.Natürlich ist es besser wenn man mehrere Bytes auf einmal kopieren kann. Mit einer "ein byte pro durchlauf" Schleife kann man oft schon nichtmal mehr die Bandbreite des Hauptspeichers voll auslasten, von der der Caches ganz zu schweigen.
Die Frage ist nur wieviel Byte man auf einmal kopieren *kann*. 4 gehen immer (DWORD Zugriffe dürfen auf beliebige Adressen erfolgen - aber siehe EDIT2 unten). Bei 16 muss aber das Alignment passen (EDIT: OK, falsch, anscheinend gibt's nen MMX/SSE Befehl wo das Alignment selbst für 16 Byte Loads/Stores egal ist /EDIT), d.h. Source und Destination müssen gleich aligned sein. Wenn das nicht der Fall ist müsste man recht komplizierte Kopierschleifen verwenden, wobei ich nicht weiss ob sich das dann noch auszahlt. Vor allem wird der Overhead den man pro memcpy Aufruf hat wieder grösser. Für grosse Blöcke ist das egal, bei ganz kleinen Blöcken schadet es dann aber wieder.EDIT2: ich beziehe mich hier (in diesem ganzen Posting) auf x86/i386 CPUs, weil das die Fragestellung war. Es gibt genug CPUs auf denen auch 4 Byte breite Zugriffe aligned sein müssen, d.h. nicht auf beliebige Adressen erfolgen dürfen. Nur damit das keiner falsch versteht der vielleicht nicht alle Beiträge gelesen hat. /EDIT2
Decimad schrieb:
Wenn man das dann wieder auf ner ganzen Cache line macht, könnte ich mir vorstellen, dass am Ende ganze cache-lines kopiert werden (von außerhalb des Prozessors gesehen)
"Von ausserhalb des Prozessors gesehen" werden immer ganze Cache-Lines gelesen/geschrieben. Darum gehts aber nicht, sondern darum dass die CPU einfach zu langsam ist wenn man Byte für Byte kopiert.
----
Ich frage mich auch schon lange wieso CPUs nicht einen (performanten) "memcpy" Befehl haben. Die CPU sollte schliesslich am besten wissen wie sie die Rumkopiererei am schnellsten hinbekommt. Klar gibt's "rep movsb" (und movsd, movsq), aber das ist schnarchlangsam (verglichen mit Kopierschleifen die MMX/SSE/... Befehle verwenden), und daher eigentlich nur für ganz kurze Strings brauchbar.
Wenn man moderne Betriebssysteme verwendet, moderne Sprachen und moderne Programmiertechniken, dann werden Daten wahnsinnig oft nur blöd durch die Gegend geschoben. Oft genug dass es sich IMO auszahlen würde da mal CPU-Seitig was zu machen.
-
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? Ich habe mich selber nie sooo genau mit Maschinenlevel beschäftigt... Weißt Du das?
Danke im Voraus,
MichaelPS: 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.
-
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:)
-
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.
-
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.
-
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.
