ein paar Designfragen

[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++

[performer]

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.

[performer]

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.

[knivil]

Ich weiss nicht warum immer an eigenen Meinungen festgehalten wird. Nachmessen! Aber die Muehe macht sich niemand bei so Spielzeugbeispielen, da der Flaschenhals meist woanders liegt.

Lookup-Tabellen sind so gut wie immer das Effizienteste

Das haengt auch entscheidend von der Groesse der Tabelle, dem Cache und der Prozessorarchitektur ab.

Was kann verbessert werden: Wird sich auf die Ziffern 0-9 beschraenkt, also Radix = 10, dann verschwindet die Lookuptabelle.

*iter = '0' + (value % Radix);

Falls Radix = 16 ist, so baut man ein if ein. Ob das schneller als ein Speicherzugriff ist, muss gemessen werden. Weiterhin kann die Lookuptabelle bei 64 Bit Architekturen in 2 Registern vorgehalten werden, d.h. Register auswaehlen + shift bleibt dann uebrig.

[Ethon]

knivil schrieb:

Was kann verbessert werden: Wird sich auf die Ziffern 0-9 beschraenkt, also Radix = 10, dann verschwindet die Lookuptabelle.

*iter = '0' + (value % Radix);

Falls Radix = 16 ist, so baut man ein if ein. Ob das schneller als ein Speicherzugriff ist, muss gemessen werden. Weiterhin kann die Lookuptabelle bei 64 Bit Architekturen in 2 Registern vorgehalten werden, d.h. Register auswaehlen + shift bleibt dann uebrig.

Ist langsamer als die Lookup-Tabelle. (gcc 4.7, -03, irgeineine i7 mobile CPU)

[knivil]

Ist langsamer als die Lookup-Tabelle. (gcc 4.7, -03, irgeineine i7 mobile CPU)

Das ist eine sehr vage Aussage. Testprogramm und Ergebnisse fehlen. Auch ist mobile CPU sehr duerftig. Klar kann ich heir meinen STM32F ausbuddeln und dann wird es ganz anderes aussehen.

Aus eigener Erfahrung weiss ich, dass -O3 schlechter sein kann als -O2. Mal schauen, wann ich Zeit fuer deine Herausforderung habe. Es gibt ja noch mehr Moeglichkeiten der Optimierung. Fuer gewoehnlich ist nur die Basis 2, 8, 16 und eben 10 interessant. Fuer 2 8, und 16 kann beispielsweise die Modulo-Operation wegfallen.

Und dann koennen sie gern gegen irgendwas hier antreten: http://stackoverflow.com/questions/4351371/c-performance-challenge-integer-to-stdstring-conversion

@freakC++: google: fastest integer to string conversion c++

Und zu deiner Frage: Ich benutze std::to_string, weil es nur eine Zeile Code ist. Flaschenhaelse treten normalerweise zuerst woanders auf.

[Ethon]

Hmm, die Stacckoverflow-Lösungen machen meine Lösung ziemlich nass.
http://ideone.com/lGkIcy

Edit: Hihi, ich habe mir von der ersten Stackoverflow-Lösung das mit der Größe davor bestimmen um den Buffer zu sparen + die etwas größere Lookuptable geklaut.
Bin jetzt nochmal deutlich schneller als die Stackoverflow-Lösung und das ohne unportables Gehacke.

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

    char const* chars =
        "00010203040506070809"
        "10111213141516171819"
        "20212223242526272829"
        "30313233343536373839"
        "40414243444546474849"
        "50515253545556575859"
        "60616263646566676869"
        "70717273747576777879"
        "80818283848586878889"
        "90919293949596979899"
      ;

    unsigned size;
    if(value >=10000)
    {
        if(value >=10000000)
        {
            if(value >=1000000000)
                size=10;
            else if(value >=100000000)
                size=9;
            else 
                size=8;
        }
        else
        {
            if(value >=1000000)
                size=7;
            else if(value >=100000)
                size=6;
            else
                size=5;
        }
    }
    else 
    {
        if(value >=100)
        {
            if(value >=1000)
                size=4;
            else
                size=3;
        }
        else
        {
            if(value >=10)
                size=2;
            else
                size=1;
        }
    }

    s.resize(s.size() + size);
    std::reverse_iterator<std::string::iterator> iter( (s.end()) );
    while(value >= 100)
    {
        *iter = chars[value % 100 * 2 + 1];
        ++iter;
        *iter = chars[value % 100 * 2];
        value /= 100;
        ++iter;
    }
    if(value >= 10)
    {
        *iter = chars[value * 2];
        ++iter;
        *iter = chars[value * 2 + 1];
        ++iter;
    }
    else
    {
        *iter = '0' + value;
    }
}