Nummer in String möglichst schnell schreiben

Ahoy, Leute.

Ich schreibe grad an einem Programm, welches zur späteren Indizierung im Dateisystem eine Nummer in einen String schreiben soll, in dezimaler Schreibweise. Weil dies schnell gehen muss und snprintf relativ langsam war, dache ich an eine Routine, die dies schnell erledigen soll.

Das ist mein Ansatz:

/*string beinhaltet den Speicherbereich, in den wir schreiben wollen, string_max, wie viele Bytes wir
**schreiben dürfen, und number den Wert, der in Stringform in string geschrieben werden soll.
**Zurückgeben soll die Routine die Anzahl der geschriebenen Bytes.*/
size_t write_number(char*string,size_t string_max,size_t number)
{
        register size_t bytes_wrote=0;
        register size_t x_pow=1;
        register char pos;

        /*Paramchecker*/
        if(!string || !string_max)
                return 0;

        /*Wir versuchen hier, die größe Potenz von 10 zu ermitteln, die kleiner ist als number, damit wir
        **die verschiedenen Stellen berechnen können.*/
        while(number>x_pow*10)
                x_pow*=10;

        /*Jetzt können wir nacheinander die verschiedenen Stellen berechnen.*/
        while(bytes_wrote<string_max && number)
        {
                pos=number/x_pow;
                string[bytes_wrote]=pos+'0';

                number-=pos*x_pow;
                x_pow/=10;
                ++bytes_wrote;
        }

        /*Wenn noch Platz da ist, Null-Byte schreiben*/
        if(bytes_wrote<string_max)
                string[bytes_wrote]=0;

        return ++bytes_wrote;
}

Auf meiner Testmaschine, einem alten gammeligen Pentium-M-Prozessor, braucht diese Routine ungefähr 700 Cycles, ein snprintf braucht zwischen 21000 und 29000 Cycles:

char xxx[10];

/*In ~ 700 Cycles*/
write_number(xxx,10,123456789);

/*In ~ 21000 - 29000 Cycles*/
snprintf(xxx,10,"%u",123456789);

Ich habe allerdings zwei Probleme mit dem Code:

1. Er basiert darauf, dass es eine Zehnerpotenz gibt, die größer ist als die angegebene Nummer, damit die erste While-Schleife abbricht. Sonst gibt es einen Overflow und die Schleife wird nie verlassen. Ein:

write_number(xxx,10,4294967295LU);

wird auf einem System, wo size_t 32 Bit groß ist, in eine Endlosschleife laufen. Wenn ich x_pow als uint64_t deklariere, läuft die Routine normal durch. snprintf hat keine Probleme mit dem Wert. Es kann ja nicht sein, dass das Schreiben davon abhängig ist, dass es eine Zehnerpotenz über dem Wert, den ich schreiben will, geben muss, damit die Routine funktioniert - ich habe das Gefühl, das Problem kann man eleganter lösen, aber mir will nicht einfallen, wie.

2. Mir sind zu viele Divisionen im Code. Zuerst berechne ich den Wert der Ziffer an Position bytes_wrote durch eine Division, und dann dividiere ich nochmal x_pow durch 10.

Ich habe das Gefühl, ich übersehe hier etwas ... könnte sich jemand den Code anschauen und eventuell auf Logikfehler hinweisen, oder direkt einen besseren Weg aufzeigen ( itoa geht nicht und es muss schneller sein als snprintf ).

Danke für die Aufmerksamkeit.

Kleiner Nachtrag:

bytes_wrote sollte nur dann inkrementiert werden, wenn das Nullbyte geschrieben werden konnte, nicht pauschal beim Return. Mein Fehler, ist bereits notiert.

Nathan

Naiver Ansatz:

char* unsigned_to_str(size_t value, char *buffer_begin, char *buffer_end)
{
    for (;;)
    {
        *--buffer_end = '0' + (value % 10);
        value /= 10;
        if (value == 0)
            break;
        else if (buffer_end == buffer_begin + 1)
            return NULL;
    };

    return buffer_end;
}

Mit Modulo kriegt man nur die letzte Ziffer, deswegen wird rückwärts in einen Buffer geschrieben.
buffer_begin zeigt auf den Anfang eines Buffers, buffer_end eins hinters Ende. Es wird ein Zeiger auf die Startaddresse des Zahlenstring in diesem Buffer zurückgegeben, er geht dann von da aus bis zum Ende bzw. im Fall von Overflow NULL. Der Buffer muss dann ggf. noch in deinen String kopiert werden.
Schnellere Methoden brauchen vermutlich Lookup-Table oder Assemblertricks.

SeppJ

Nathan schrieb:

Schnellere Methoden brauchen vermutlich Lookup-Table oder Assemblertricks.

Man könnte vielleicht noch was rausholen, wenn man statt der Dezimalschreibweise die hexadezimale wählt. Ist denn dezimal wirklich wichtig?

P.S.: Außerdem ldiv, falls der Compiler diese einfache Optimierung nicht selber finden sollte. Und testen, ob es wirklich was bringt (kann nämlich nach hinten losgehen).
P.P.S.: Zwar kein ausführlicher Test, aber beim GCC scheint es nach hinten los zu gehen, da der Funktionsaufruf nicht inlined wird. Also vergiss diesen ganzen Absatz

@SeppJ: Leider muss es dezimal sein. Die meisten Programme sortieren nicht nach Hex, sondern nach Dezimal, und beim Durchgehen der geschriebenen Dateien muss die Reihenfolge unbedingt beibehalten werden.

@Nathan: Die Lösung wäre wirklich klasse - braucht nur die Hälfte der Cycles meiner Routine - aber leider schreibt sie rückwärts. D.h. dass wenn der Buffer nicht vollständig gefüllt wird, steht am Anfang nur Unsinn oder gar nichts (weil Arrays zumindest mit dem gcc) mit 0 initialisiert werden. Wenn ich das fixen will, muss ich da wieder memmove machen und den Rest schiften, oder vorher die richtige Länge ermitteln (Augenblick mal ...), und das ist doof. Sonst wäre der Ansatz echt klasse.

Nathan

Wie sieht denn das genaue Format im string buffer aus?
Kannst du den evtl. ganz rückwärts füllen?
Und so ein memmove sollte aber nicht allzu lahm sein.

Das Format ist wie im Beispielcode beschrieben, sowas wie:

"123456\0"
"777\0"
"42\0"

Das mit memmove kann ich vergessen. Selbst wenn die alloca statt malloc und free verwenden, ist der Zugriff auf den Speicher zu langsam, das geht hoch in die 3000 Cycles.

Wenn ich den ganz rückwärts füllen möchte, muss ich wissen, wo ich anfangen soll zu schreiben. Beim Vorwärtsfüllen ist das klar, in der Speicherzelle, auf die string zeigt. Beim Rückwärtsprüfen muss ich den Wert erst durchpotenzieren, damit ich die Länge habe (und dann habe ich das erste Problem, dass bei 0xFFFF FFFF Endlosschleife is), oder ich mache am Ende memmove, was aber langsam ist ... ich verstehe so langsam, wo die Performance beim snprintf hingeht.

Selbst wenn es ein memcpy wäre (was ich nicht verwenden kann, weil nicht sichergestellt ist, in welche Richtung das kopiert), wäre es vermutlich zu teuer, nach dem Rückwärtsfüllen die Bytes an den Anfang des Bereiches zu setzen. Das lohnt sich nur, wenn die Zahl exakt in den Speicher passt, dann gibt es keine Lücke und damit auch keinen Grund zum Rumshiften.

Ich muss da mal eine Nacht drüber schlafen. Eigentlich will ich die Länge ja angeben, damit es auf keinen Fall zu einem Buffer-Overflow kommt. Kaputte Namen sind immer noch besser als Stack-Corruption ...

Nathan

Was willst du den mit dem String machen?
Wenn du den an eine Funktion übergibst, der Rückgabewert meiner Funktio. zeigt auf den Anfang der Zahl, das kannst du dann übergeben. Sollte eigentlich egal sein, ob der Cfap vorne oder hinten steht. Musst nur ggf. vorher das letzte Zeichen im Buffer nullen.

SeppJ

Dachstuhl schrieb:

Das mit memmove kann ich vergessen. Selbst wenn die alloca statt malloc und free verwenden, ist der Zugriff auf den Speicher zu langsam, das geht hoch in die 3000 Cycles.

Ich glaube, du stellst dir memmove falsch vor. memmove allokiert nichts .Hast du es mal ausprobiert?

Falls da bei dir irgendetwas sehr komisch optimiert wird oder du irgendein ganz komisches memmove hast, dass intern dynamisch Speicher allokiert, dann schreib dir ein eigenes naives memmove und fertig. Das ist möglicherweise sogar noch ein paar Takte flotter als das normale memmove, weil ein normales memmove noch Tests macht, welche Optimierung es benutzen soll. Für eine kleine Zeichenkette sollte aber ein naives 1:1-Verschieben schon recht nahe am Optimum sein (oder eventuell 4:4).

und dann habe ich das erste Problem, dass bei 0xFFFF FFFF Endlosschleife is

Wieso ist das eigentlich ein Problem?

size_t get_decimal_string_length(size_t value)
{
  if (value < UL10) return 2;
  if (value < UL100) return 3;
  if (value < UL1000) return 4;
  if (value < UL10000) return 5;
  // usw.... 2^64 ist ganz schön groß
  if (value < UL1000000000000000000) return 20;
  return 21;
}

(Obiger Code optimiert für kleine Zahlen. Wenn die Zahlen eher die vollen 64-Bit nutzen, dann macht man es umgekehrt.)

Man kann auch noch Bithacks nutzen, um den log2 ein bisschen schneller zu berechnen und dann auf den log10 umrechnen, aber ich schätze, wesentlich schneller wird es dadurch nicht werden. Vielleicht nochmal Faktor 2.
Siehe: http://graphics.stanford.edu/~seander/bithacks.html

Das alles ist aber sicher wesentlich aufwändiger als ein memmove.

@SeppJ: Ich würde einfach mal sagen, mir sagt die Manpage, dass memmove Speicher reserviert (nicht mit memcpy verwechseln).

The memory areas may overlap: copying takes place as though the bytes in src are first copied into a
temporary array that does not overlap src or dest, and the bytes are then copied  from the temporary
array to dest.

Duh! Und natürlich habe ich es ausprobiert - oder denkst du, ich habe mir die 3000 aus dem Nichts herbeigezaubert?

Alles andere würde auch keinen Sinn ergeben. Nehmen wir mal an, ich sage memmove , dass es jetzt 64 MB verschieben soll. Die müssen gecacht werden, vor dem Schreiben. Das geht nicht mit Speicher auf dem Stack, der platzt sonst, selbst wenn es so intelligent sein sollte und erkennt, dass die Speicherbereiche sich eigentlich nicht in die Querre kommen und nur ein gewisser Teil wirklich gecacht werden muss. Und dann muss malloc und free verwendet werden. Und das ist auch der Grund, warum die damals nicht memcpy mit memmove überschreiben wollten.

@Nathan: Ich habe mir gerade noch mal den alten Code angeschaut. In einigen Situationen könnte ich tatsächlich die Rückwärtsroutine verwenden, aber nicht für alle. Seufz. Naja, besser als nichts.

Jedenfalls Danke für die Hilfe an euch beide! Eventuell kann ich auch noch was aus dem Artikel extrahieren. Ich werde mich melden und die Routine pasten, wenn ich weitergekommen bin.

as though

Zwei wichtige Worte. Wenn Englisch nicht so deine Stärke ist, gibt es doch noch den Quelltext in C!

https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memmove.c;hb=HEAD
http://git.musl-libc.org/cgit/musl/tree/src/string/memmove.c
http://anoncvs.estpak.ee/cgi-bin/cgit/openbsd-src/tree/lib/libc/string/bcopy.c
https://github.com/freebsd/freebsd/blob/master/lib/libc/string/bcopy.c
https://github.com/brho/plan9/blob/master/sys/src/libc/port/memmove.c
%VCINSTALLDIR%\crt\src\memmove.c (Visual Studio)

@Dachstuhlgang: Das ist der Originaltext aus der Manpage, Copy+Paste. Abgetippt hab ich den nicht.

Und was den Code angeht: das ist in der Tat höchst interessant. Die Routine erkennt selbstständig, ob es zu einem Überschneiden kommen könnte, und verwendet dann entweder Rückwärts- oder Vorwärtskopie. In diesem Fall muss dann nicht kopiert werden - ich fresse meinen Hut, da habe ich Quatsch erzählt. Danke!

Leider ändert das nichts am Problem selbst, dass memmove langsam ist. Hier ist der Code, den ich jetzt eingecheckt habe:

size_t write_number_reverse(char*string,size_t string_max,size_t value)
{
        register size_t end=string_max;
        register size_t rvalue=value;

        if(!string || !end)
                return 0;

        do
        {
                string[--end]='0'+rvalue%10;
                rvalue/=10;
        }
        while(rvalue && end);

        if(end)
                memmove(&string[0],&string[end],string_max-end);

        return (string_max-end);
}

Aufgerufen mit:

char xxx[11];
write_number_reverse(xxx,9,123456789LU);

Solange end 0 ist, wenn er mit dem Schreiben fertig ist, ist alles kein Problem, hier haben ich sowas wie 200 Cycles. Sollte der Buffer aber größer sein, sind wir plötzlich bei 3500 Cycles. Zwar besser als snprintf , aber trotzdem ...

Das hier ist nur ein bisschen langsamer, aber konstant (300 Cycles):

size_t get_decimal_string_length(size_t value)
{
        register size_t rvalue=value;
        if (rvalue < 10UL) return 2;
        if (rvalue < 100UL) return 3;
        if (rvalue < 1000UL) return 4;
        if (rvalue < 10000UL) return 5;
        /*...*/
}

size_t write_number(char*string,size_t string_max,size_t value)
{
        register size_t end=get_decimal_string_length(value)-1;
        register size_t rvalue=value;

        if(string_max<end)
                end=string_max;

        if(!string || !end)
                return 0;

        string_max=end;

        do
        {
                string[end-1]='0'+rvalue%10;
                rvalue/=10;
        }
        while(rvalue && --end);

        return (string_max);
}

Ich werde also zwei Routinen einfügen, eine, wenn man sich sicher ist, dass der Wert exakt in den Speicher reingeht oder bei dem es schlichtweg egal sein kann, und eine, bei der es egal ist, ob der Wert nicht exakt reingeht, die aber ein bisschen langsamer ist. Muss man wohl mit leben ...

P.S: Die Bithacks haben nichts an der Performance geändert, daher verwende ich lieber die statische Routine. Die kann ich wenigstens debuggen.

Danke für die Suggestionen. Ich hoffe, ich konnte auch damit Leuten, die künftig hier vorbeikommen, damit helfen.

Was spricht eigentlich dagegen, führende Leerzeichen zu benutzen?

DirkB schrieb:

Was spricht eigentlich dagegen, führende Leerzeichen zu benutzen?

Wäre nicht gut, weil da Namen für ein Dateisystem geschrieben werden müssen. Leerzeichen müssen für HTTP kodiert werden. Das ganze soll hochskalierbar sein, sonst kann ich es gleich sein lassen.

SeppJ

Hast du auch ganz sicher Optimierungen eingeschaltet? Sonst wird da am Ende noch irgendeine Debugversion von memmove genommen. Falls ja, dann kannst du auch noch versuchen, selber die Zeichen eines nach dem anderen zu verschieben. Diese paar Bytekopien können unmöglich tausende Takte fressen.

Definiere Optimierungen.

Der Source:

#include <stdio.h>
#include <lib_zum_tickmessen.h>

size_t write_number_reverse(char*string,size_t string_max,size_t value)
{
        register size_t end=string_max;
        register size_t rvalue=value;

        if(!string || !end)
                return 0;

        do
        {
                string[--end]='0'+rvalue%10;
                rvalue/=10;
        }
        while(rvalue && end);

        if(end)
                memmove(&string[0],&string[end],string_max-end);

        return (string_max-end);
}

int main(void)
{
        char xxx[12];
        /*Tickmesserinitialisierung, kennste nicht.*/
        /*<...>*/

        /*Schreibung des Wertes.*/
        write_number_reverse(xxx,11,4294967295LU);
        xxx[11]=0;
        /*Erstellen eines Snapshots. Der kostet 50-100 Ticks, die habe ich aber schon eingepreist.*/
        /*<...>*/

        /*Ausgabe des Strings*/
        printf("%s\n",xxx);

        /*Und hier gibt der Tickmesser aus und wird wieder freigegeben.*/
        /*<...>*/

        return 0;
}

Ich verwende zwar eine eigene Bibliothek für die Tickmessung, aber die kostet wie beschrieben nicht viel. Außerdem verwendet sie memcpy , nicht memmove , skaliert O(1) und wurde mit den gleichen Flags wie unten beschrieben kompiliert.

Der Kommandozeilenaufruf (Linux, hier grad auf einem Ubuntu):

gcc write_shite.c -o write_shite.o <Viele tolle Sachen zur Tickmessung> -O2 -march=native -mtune=native -fno-stackprotector

Die Manpage meint, dass der Stackprotektor standardmässig an wäre, deswegen habe ich die Option negiert.

Ausgeben tut mir das Programm:

[0x65f312f10b4c|112094669245260|0x65f312f10b4c|112094669245260|"(Intern start)"]
[0x65f312f11950|112094669248848|0xe04|3588|"Fertig!"]

Der Snapshot wird DIREKT nach dem Funktionsaufruf gemacht, nicht nach dem printf .

Scheiße, erst hinterher wird mir bewusst, dass du mich hinter einer Windows-Maschine und/oder einer IDE vermutest ...

SeppJ

Dachstuhl schrieb:

Scheiße, erst hinterher wird mir bewusst, dass du mich hinter einer Windows-Maschine und/oder einer IDE vermutest ...

Nein, der Gedanke ist mir erst gekommen, als dein memmove so merkwürdig langsam war.

Zur Performancemessung: Ich hätte da einfach gprof genommen, da kann man auch ziemlich sicher sein, dass es kein Fehler in der Zeitmessung an sich ist. Oder noch einfacher ein time bei der Ausführung der Executable, wobei gprof den Vorteil hat, dass es einem sagt, was wie viel Zeit braucht. So kann man feststellen, ob es wirklich am memmove liegt.

Hast du mal probiert, das memmove durch ein:

if (anfang_des_buffers != anfang_der_ziffernfolge)
  do
   *anfang_des_buffers++ = *anfang_der_ziffernfolge;
  while(*anfang_der_ziffernfolge++);

zu ersetzen? Das können unmöglich 3000 Takte sein, eine handvoll Zeichen so zu kopieren. (Der Code oben ist eben schnell hier im Foreneditor getippt, ohne Test. Eventuelle Syntax- und Logikfehler dienen der Übung des Lesers )

Mit Optimierung meinte ich schon so etwas wie die O-Stufen des GCC. Manche Leute haben die verrückte Idee, die Performance auf O0 zu testen. Wollte nur sicher sein, dass du nicht dazu zählst.

Dein Vertrauen in meine Fähigkeiten berührt mich.

size_t write_number_reverse(char*string,size_t string_max,size_t value)
{
        register size_t end=string_max;
        register size_t rvalue=value;
        register size_t res;

        /*Prüfung auf ungültige Werte*/
        if(!string || !end)
                return 0;

        /*Vom Ende her die Zahl bauen ...*/
        do
        {
                string[--end]='0'+rvalue%10;
                rvalue/=10;
        }
        /*... solange wir noch Wert und Platz haben.*/
        while(rvalue && end);

        /*Wieviel haben wir NICHT gebraucht? Das steht dann in res, und wenn es einen Unterschied gibt,
        **müssen wir ihn korrigieren.*/
        res=string_max-end;
        if(end)
        { 
                rvalue=0;
                /*What would memmove do? Vorwärtskopie ...*/
                do string[rvalue]=string[rvalue+end];
                /*... solange wir noch was zu schiften haben.*/
                while(++rvalue<res);
        }

        /*Und hier die Rückgabe, damit man so Sachen wie
        **xxx[write_number_reverse(xxx,8,12345678LU)]=0; machen kann*/
        return res;
}

Braucht zwischen 180 und 250 Cycles, auch wenn zu viel Buffer verwendet wurde. Auch noch mal Danke für den Anstoß - anscheinend sollte ich mich nicht blind darauf verlassen, dass die glibc-Funktionen immer schneller sind als das, was ich aus den Fingern ergieße ... was merkwürdig ist, denn meine memmem -Routine war immer einige Cycle langsamer. Aber das ist eine andere Geschichte ...

Erstaunlich, wie man zwei Seiten mit einem so trivialen Thema füllen kann. Damit wäre meine Variante jetzt gut 100 schneller als snprintf - das kann sich sehen lassen.

Vielen, vielen Dank an alle!

Nachschlag:

gprof zeigt mir an, dass no time accumulated wurde. Seitdem verwende ich mein eigenes API zur Cyclemessung - da weiß man, was man hat.

Wie wäre es den die Division durch eine Multiplikation zu ersetzen? Würde man uint32_t statt size_t verwenden, könnet man es mit fixed-point Arithmetik machen:

int uint32_to_sz(uint32_t value,char (*string)[11]) {
	char* psz = (char*)string;
	char *p = psz+9;
	int len=0;
	register uint32_t v = value;
	do {
		union {
			uint64_t full;
			struct {
				uint32_t low;
				uint32_t high;
			} part;
		} quad;

		/**
		 *  quotient = Floor( ( value * Round(2**32/10 * 2**3) * 2**(-3) ) * 2**(-32))
		 *  modulo = value - quotient*10
		 */
		quad.full = (uint64_t)v * 0xCCCCCCCDULL;
		register uint32_t r2, r = quad.part.high;
		r2 = r = r >> 3;
		r = v - r*10 + '0';
		*p-- = (char)r;
		v = r2;
		len++;
	} while( v );
	p++;
	for(int i=len; i; i--) {
		*psz++ = *p++;
	}
	*psz=0;
	return len;
}

Hab ich seinerzeit für alle Werte von value getestet.

Dass du dich traust, so ein Gewusel zu veröffentlichen ...

Ne, bei mir erreicht der Code nur 450 Cycles. Das ist zwar immer noch schneller als die erste Routine, aber kommt an mein letztes Ergebnis (200 Cycles) nicht ran.