Nummer in String möglichst schnell schreiben

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.

Dachstuhl schrieb:

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

Dachstuhl schrieb:

Ne, bei mir erreicht der Code nur 450 Cycles.

Welche Testwerte nimmst du?

Wutz

**xxx[write_number_reverse(xxx,8,12345678LU)]=0;

Da solltest du aber aufpassen, dass du '\0' nicht in undefinierten Speicher schreibst, weil dein xxx evtl. nicht ausreicht.
Ich würde auch bei

while(rvalue && end);

auf end verzichten, und lieber zuvor sinnvolle Größen mittels assert absichern, denn size_t sollte nicht mehr als 20 Dezimalstellen benötigen.
Auch kannst du dir den ganzen Shift-Kram sparen, indem du den Beginnstring zurückgibst und im aufrufenden Kontext einfach wiederverwendest.

const char *write_number_reverse(char*string,size_t string_max,size_t value)
{
  static const char dezimal[]="0123456789";
  char *p=string+string_max;
  assert(string_max>20);

  *--p=0; /* Stringende absichern */
  do *--p=dezimal[value%10]; while(value/=10);

  return p;
}

Aufrufen dann einfach mit:

char s[30];
puts( write_number_reverse(s,30,1234567890LU) );

Nathan

@Wutz: Genau dasselbe hatte ich auch schon in der ersten Antwort gepostet, nur nicht nullterminiert.