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

Hallo zusammen,

ich habe eine Grundsätzliche Frage zur Implementierung der Methode
"

std::string::substr(int pos,int npos)

".

Die Frage ist ob, Sie den neuen String entweder mit einem rutsch erzeugt
(Beispielsweise mit einer Prozessor Direktive) oder ob sie den neuen
String einfach Zeichen für Zeichen mit append aufbaut.

Was meint ihr ?

Gruß der Gast

devkid

Also am einfachsten würd ich mir das so vorstellen:

std::string std::string::substr (int pos, int n)
{
    return std::string (*this, pos, n);
}

Siehe die verschiedenen Konstruktoren der Klasse...

Das beantwortet nicht meine Frage^^ aber denoch danke:)

Ich wollte wissen, wie er die Characters von A nach B verschiebt.
Mich interesiert ob er das in einzel Schritten tut oder
ob er das auf einmal tut zum Beispiel mit einer Assembler direktive.

Das wäre jetzt Schrittweise nach meiner Definition:

std::string std::string::substr (int pos, int n)
{   
    std::string neuerString;
    for(int i = pos;i<(pos+n);i++)
       neuerString.append(this->operator[](i)); 

    return neuerString;
}

Wie ist das nun implementiert ?

Nexus

aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:

Das beantwortet nicht meine Frage^^ aber denoch danke:)
[...]
Wie ist das nun implementiert ?

Wieso schaust du dir die Implementierung nicht einfach an? Diese muss sowieso nicht bei jedem Compiler gleich aussehen.

Das ist nicht festgelegt. Du kannst aber davon ausgehen, dass sich die Schreiber der einzelnen Bibliotheken bestimmt Gedanken machen, wie das auf der entsprechenden Plattform am effizientesten zu bewerkstelligen ist. Schau doch einfach selbst die Implementation an... Sind doch alles Templates, drum muss der Quellcode deiner Bibliothek doch dabei sein Und nimm bitte mal einen vernünftigen Namen hier O.O

Also habe mal eine Weile lang nach dem Source der Standard C++ Bibliothek gesucht finde sie net.
Oder hat jemand den Link vor mir gefunden;) ?

... Bibliotheken bestimmt Gedanken machen, wie das auf der entsprechenden Plattform am effizientesten zu bewerkstelligen ist ....

Ich glaube mal das ihr alle auf einer 386 Architektur arbeitet von daher^^
Sollte das alles die selbe Suppe sein:)

Da könnten ja noch so sachen wie die Unicode repräsentation im OS und so reinspielen, wer weiß. Hast du dich mal gefragt, was #include <string> bedeutet? Dann wirst du relativ schnell den Source auf deiner Festplatte finden.

Nexus

aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:

Also habe mal eine Weile lang nach dem Source der Standard C++ Bibliothek gesucht finde sie net.
Oder hat jemand den Link vor mir gefunden;) ?

Würdest du eine moderne IDE verwenden, könntest du per Rechtsklick die Definition anzeigen lassen.

Ansonsten halt mal in den <string> -Header reinschauen und die dort eingebundenen Header überprüfen. Bei mir (MSVC++) ist std::string::substr() in <xstring> definiert (wobei es intern wieder Dinge aus anderen Header benötigt).

aaaaaaaaaaaaaaaaaaaaaaaaa schrieb:

Ich glaube mal das ihr alle auf einer 386 Architektur arbeitet von daher^^
Sollte das alles die selbe Suppe sein:)

Wie gesagt, kann das von Compiler zu Compiler anders sein. Architektur spielt hier nicht die wesentliche Rolle...

Und wie Nexus schon sagt, DIE C++ Standard-Bibliothek gibt es nur als Interface-Beschreibung. Jeder Compiler kann entsprechend der Spezifikation eine eigene Implementierung davon verwenden. Dinkumware stellt zB. eine her (Wird in MSVC++ verwendet), dann gibts noch STLport und bestimmt dutzende andere Implementierungen

Wie gesagt, kann das von Compiler zu Compiler anders sein. Architektur spielt hier nicht die wesentliche Rolle...

Dabei handelt es sich um optimierungen mehr nicht der Content ist der gleiche:)

Würdest du eine moderne IDE verwenden, könntest du per Rechtsklick die Definition anzeigen lassen.

Ansonsten halt mal in den <string>-Header reinschauen und die dort eingebundenen Header überprüfen. Bei mir (MSVC++) ist std::string::substr() in <xstring> definiert (wobei es intern wieder Dinge aus anderen Header benötigt).

Ich benutze eine moderne IDE, aber wenn 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:)

Aber gut ich glaube ich bin schneller wenn ich mir ... die lib disassembliere:)
Wollte doch nur ne Kurze antwort^^

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.

Nexus

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:)

Nexus

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.

Braunstein

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!

Braunstein

Das war jetzt Ironie, nicht?
Diese Spezialisierungen gibt es natürlich auch. Hier kommen dann wmemcpy und memcpy zum Einsatz. Beides auch in iosfwd.

hustbaer

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,
Michael

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.