ein paar Designfragen

freakC++

Eisflamme schrieb:

Keine Ahnung, woraus der int fällt und wieso Du den in einen stringstream schiebst.

Ich habe das Horner-Schema zum Wechseln der Zahlenbasis implementiert. Pro Iterationschritt wird eine Ziffer berechnet und "fällt" quais unten aus der Schleife raus --> bildhaft gesprochen

Eisflamme schrieb:

Ja weißte, dann frag doch einfach im C-Forum nach.

Werde ich machen!

Eisflamme schrieb:

Der stringstream muss jeden int parsen und als String darstellen.

Warum muss ein int geparst werden? Unter Parsen stelle ich mir eine Art Syntaxprüfrung vor. Hat ein int eine Syntax?

Ethon schrieb:

Problematisch kann es höchstens bei 32bit System werden da dort auch der virtuelle Speicher recht limitiert ist.

Jo, es soll aber auch auf 32 Bit Systemen laufen Der Tipp ist aber gut. Danke

Verstehe ich euch richtig, dass ihr zum Erstellen eines Strings nicht stringstream verwenden würdet, wenn der Strinhalts die einzelnen Elemente eines std::vector<int> sind?

Vielen Dank
LG, freakC++

knivil

kaskadierenden Algorithmus ... fällt unten ein "int" raus ... bildhaft gesprochen

Damit kann man echt viel anfangen. Dazu kann ich nur sagen: Nimm blau, dann wirds schoener.

Verstehe ich euch richtig, dass ihr zum Erstellen eines Strings nicht stringstream verwenden würdet, wenn der Strinhalts die einzelnen Elemente eines std::vector<int> sind

Ich verwende std::to_string. Ansonsten: Was soll string.push_back fuer ints sein?

freakC++

knivil schrieb:

Nimm blau, dann wirds schoener.

OK :D. Danke. Das leuchtet auch ein, weil Cola ja besser als aus dem Glas schmeckt!

knivil schrieb:

Ich verwende std::to_string.

und warum muss hier nicht geparst werden? Warum ist es also so viel schneller als die Zahlen in einen stringstream zu schieben?

Danke

knivil

Warum ist string.push_back so viel schneller als ein stringstream?

Welchen Datentyp hat in dieser Aussage das Objekt string ?

und warum muss hier nicht geparst werden?

Wo schreibe ich das?

freakC++

knivil schrieb:

Warum ist string.push_back so viel schneller als ein stringstream?

Welchen Datentyp hat in dieser Aussage das Objekt string ?

?
string

knivil schrieb:

Wo schreibe ich das?

nirgendswo. Aber das schließe ich daraus. Anscheinend ist stringstream ja so langsam, weil die Zahlen zuvor geparst werden. Wenn std::to_string so viel schneller ist, schließe ich daraus, dass hier nicht gepart wird (jaja, sehr gewagt^^). Wo liegt dann der Performancegewinn?

knivil

Wenn std::to_string so viel schneller ist

Wo schreibe ich das? Ich habe keinen Performancevergleich getaetigt.

Aber das schließe ich daraus.

Du gehst von Annahmen aus, die so nicht gegeben sind. Liesst Dinge, die so nicht da sind. Was du schliesst, entbehrt jeder Logik. Hoere auf damit!

?
string

Nun, ich kenne kein string::push_back(int). Diese Methode nimmt fuer gewoehnlich ein char als Parameter.

freakC++

Anscheinend hast Du meinen Punkt nicht verstanden. Mir geht es hier um eine effizientere Lösung für stringstream << int. In einem anderen Thread habe ich erfahren, dass dies nämlich so wegen eines Parsingvorgangs nicht sehr schnell ist.

Wie würdest Du möglichst schnell integer an einen String anfügen?

Du hast von std::to_string gesprochen. Also gehen ich davon aus, dass dies wohl recht flott geht. Mich interessiert warum. Falls dies ebenfalls langsam ist: Warum benutzt Du es?

Vielen Dank
LG, freakC++

knivil

Warum ist string.push_back so viel schneller als ein stringstream? Mir geht es hier um eine effizientere Lösung für stringstream << int.

Deine falsche Vorstellung von Geschwindigkeit ruehrt vielleicht daher, dass du string::push_back falsch benutzt hast. Bitte korrigiere diese Vorstellung oder begruende mit aussagekraeftigen Zahlen oder Verweisen.

Wie würdest Du möglichst schnell integer an einen String anfügen?

mein_string += std::to_string(mein_int);

freakC++

knivil schrieb:

schreibe ich das? Ich habe keinen Performancevergleich getaetigt.

Ich aber!

knivil schrieb:

Was du schliesst, entbehrt jeder Logik. Hoere auf damit!

is ja gut...dafür hättest Du deinen Beitrag nicht änder müssen. char puhh[8] = {67,72,73,76,76,77,65,76};

Nathan

freakC++ schrieb:

Anscheinend hast Du meinen Punkt nicht verstanden. Mir geht es hier um eine effizientere Lösung für stringstream << int. In einem anderen Thread habe ich erfahren, dass dies nämlich so wegen eines Parsingvorgangs nicht sehr schnell ist.

Jein. std::stringstream ist lahm, weil im Hintergrund wegen Formatierung und Fehlerprüfung und generellem Overhead da total viel passiert.

Du hast von std::to_string gesprochen. Also gehen ich davon aus, dass dies wohl recht flott geht. Mich interessiert warum. Falls dies ebenfalls langsam ist: Warum benutzt Du es?

Weil std::to_string() sich den ganzen Stress mit Formatierung spaart, das Ergebnis nicht buffert und geringen Overhead hat.

freakC++

knivil schrieb:

mein_string += std::to_string(mein_int);

Gut. Danke! Mich interessiert, warum dies schnell ist. Dies ist ja deine Antwort auf meine Frage, wie "Du möglichst schnell integer an einen String anfügen" würdest. Ist dies schneller als stringstream << int? Wenn ja, warum?

knivil schrieb:

vielleicht daher, dass du string::push_back falsch benutzt hast.

Ich benutze diese Methode gar nicht, sondern habe ich aus einem anderen Thread. Bis jetzt geht es bei mir nur um die Nutzung von stringstream und eventuell um deine Art.

Danke dir

knivil

Ich aber!

Dann stelle dein Testprogramm und deren Ergebnisse zur Diskussion. Wenn dein Programm string::push_back verwendet ... gute Nacht.

diese Methode gar nicht, sondern habe ich aus einem anderen Thread

Dann sag doch mal mit was du verglichen hast.

Ethon

Wenn das schnell sein muss: Selber basteln! stringstreams haben viel overhead und auch to_string legt eine unnötige Kopie an.

void append(std::string& s, int value, int radix=10)
{
    if(value < 0)
    {
        s.push_back('-');
        value = -value;
    }

    assert(radix > 1 && radix < 17);
    char const* chars = "0123456789abcdef";

    char buffer[sizeof(int) * CHAR_BIT];
    char* iter = buffer;
    while(value >= radix)
    {
        *iter = chars[value % radix];
        value /= radix;
        ++iter;
    }
    *iter = chars[value];

    s.append(std::reverse_iterator<char*>(iter + 1), std::reverse_iterator<char*>(buffer));
}

Ziemlich optimal so.

knivil

char buffer[sizeof(int) * CHAR_BIT];

Sehr kryptische Groessenangabe. Warum genau so, wenn fuer 32 Bit, Stellen ausreichen 11 Stellen ausreichen und fuer 64 Bit eben 21 Stellen genuegen? Klar, wenns binar sein soll, aber das ist nicht die Anforderung. Deswegen bezweifle ich, dass es ziemlich optimal ist, weil eben generalisiert wurde.

Schaut man sich andere Implementierungen so fuellen sie den Buffer gleich von hinten und kopieren mit memcpy und Co.

freakC++

Der Code gefällt mir. Man könnte es noch effizienter machen, wenn man das ganze über eine Loopup-Tabelle regelt:

char const* chars[90] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35};

LG, freakC++

freakC++ schrieb:

Der Code gefällt mir. Man könnte es noch effizienter machen, wenn man das ganze über eine Loopup-Tabelle regelt:

1. Low-Level-Code != effizient
2. "gefallen" ist subjektiv, Performance muss man messen!
3. Jedes vnprintf ist schneller als das Gehacke von Ethon.
4. Dein Vorschlag ist Quatsch.

Ethon

knivil schrieb:

char buffer[sizeof(int) * CHAR_BIT];

Sehr kryptische Groessenangabe. Warum genau so, wenn fuer 32 Bit, Stellen ausreichen 11 Stellen ausreichen und fuer 64 Bit eben 21 Stellen genuegen? Klar, wenns binar sein soll, aber das ist nicht die Anforderung. Deswegen bezweifle ich, dass es ziemlich optimal ist, weil eben generalisiert wurde.

Schaut man sich andere Implementierungen so fuellen sie den Buffer gleich von hinten und kopieren mit memcpy und Co.

Stackspeicher zu verschwenden ist doch ziemlich egal.
In welche Richtung man den Buffer befüllt ist auch egal.
Und memcpy bringt bei solchen kleinen Eingabemengen wohl reichlich wenig, mit Pech wird's sogar langsamer.

Ich würde am ehesten kritisieren dass nicht direkt in den String geschrieben wird. Müsste man eben den String zuerst vergrößern. Bezweifle aber dass sich das lohnt.

Ethon schrieb:

In welche Richtung man den Buffer befüllt ist auch egal.
Und memcpy bringt bei solchen kleinen Eingabemengen wohl reichlich wenig, mit Pech wird's sogar langsamer.

Irrtum. Wenns gleich in der richtigen Reihenfolge wäre, könnte man alles als uint64_t kopieren.

So muss aus dem Array jeder einzelne char extrahiert werden (char extrahieren ist teurer als int extrahieren) und ausserdem muss 4x so häufig kopiert werden.

Wer ganz klug ist, speichert gleich alle Zahlentripel in der Tabelle vor ("000", "001", ..., "999") und macht tripel[zahl%1000].

Weisst du, wer so klug ist? vnprintf! Das ist ein Compiler-Builtin, das gleich in den schnellstmöglichen Code der jeweiligen Plattform umgesetzt wird.

Ethon

performer schrieb:

Ethon schrieb:

In welche Richtung man den Buffer befüllt ist auch egal.
Und memcpy bringt bei solchen kleinen Eingabemengen wohl reichlich wenig, mit Pech wird's sogar langsamer.

Irrtum. Wenns gleich in der richtigen Reihenfolge wäre, könnte man alles als uint64_t kopieren.

So muss aus dem Array jeder einzelne char extrahiert werden (char extrahieren ist teurer als int extrahieren) und ausserdem muss 4x so häufig kopiert werden

Kommt nun darauf an wie groß eine durchschnittliche Zahl ist. Wenn man es mit 64bit Integern macht dann kommen noch Conditionals dazu. Solange man keinen Test schreibt kann man nur raten.
Allerdings sehe ich nicht warum man nicht auch rückwärts ganze Wörter anstatt Bytes schreiben können sollte.

performer schrieb:

Wer ganz klug ist, speichert gleich alle Zahlentripel in der Tabelle vor ("000", "001", ..., "999") und macht tripel[zahl%1000].

Weisst du, wer so klug ist? vnprintf! Das ist ein Compiler-Builtin, das gleich in den schnellstmöglichen Code der jeweiligen Plattform umgesetzt wird.

Denkst du das ist so klug? 1000 * sizeof(char*) sind allein schon 4k/8k Bytes - dann noch die Strings, die möglicherweise woanders im statischen Speicher liegen ... klingt nicht sehr optimal, lieber ein paar Schleifendurchläufe extra als nen Cachemiss zu riskieren.

3. Jedes vnprintf ist schneller als das Gehacke von Ethon.

Zeig mal Beispielscode. Google spuckt zu vnprintf nichts aus.

Eisflamme

1. Low-Level-Code != effizient

Lookup-Tabellen sind so gut wie immer das Effizienteste, wenn sie eben möglich sind. Somit stimme ich hier absolut zu, das ist an Performance kaum zu schlagen.