ein paar Designfragen

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.

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;
    }
}