Länge einer Zahl in einer angegebenen Basis finden
-
dachschaden schrieb:
Ich habe eine gute Stunde daran gearbeitet, den Code leserlich zu gestalten
-
function printUmdreh needs 62 ticks
function printAlt needs 64 ticks
function printLog needs 118 ticks
function printSprintf needs 210 ticksHm. Hm, hm, hm.
Vor allem habe ich das Gefühl, dass das Ergebnis des Logarithmus im Cache gehalten wird, da muss der das dann nicht berechnen.
Ich werd mir printUmdreh gleich noch mal genauer anschauen. Danke jedenfalls für den Code, der ist sehr aufschlussreich.
volkard schrieb:
dachschaden schrieb:
Ich habe eine gute Stunde daran gearbeitet, den Code leserlich zu gestalten
Das hört sich so böse an ...
-
|1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| function printUmdreh needs 732 ticks function printAlt needs 1112 ticks function printLog needs 800 ticks function _ui64toa needs 564 ticksDie Win-CRT bietet seit (mind.) VC6 Zeiten auch "_ui64toa" an, und liefert brauchbare Ergebnisse, s.o.
Den Quellcode kannst du dir ja mal zu Gemüte führen.
-
Wutz schrieb:
|1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| function printUmdreh needs 732 ticks function printAlt needs 1112 ticks function printLog needs 800 ticks function _ui64toa needs 564 ticksDie Win-CRT bietet seit (mind.) VC6 Zeiten auch "_ui64toa" an, und liefert brauchbare Ergebnisse, s.o.
Den Quellcode kannst du dir ja mal zu Gemüte führen.Interessant.
Kannste den ASM-Code von _ui64toa mal zeigen?
Ich wollte ja schon immer mal die Ziffern vorwärts rauströpfeln lassen. Bin gerade dran und drauf und schau mir den ASM-Code erst an, wenn ich durch bin.
-
Hm, Volkard, ich glaube, damit wirst du nicht glücklich.
Ich habe mal hier Code von geborgt und das hier gebaut:uint64_t _ui64toa(uint64_t n) { char*__string=theOutputBuffer; uint64_t __value=n; char buf2[68] ; int len = 0, pos = 0 ; while (__value) { buf2[len++] = __value %10; __value /=10; } while (len) { int ch = buf2[--len] ; ch+= '0' ; __string[pos++] = ch ; } __string[pos] = 0 ; }Und dann ausgeführt:
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
function printUmdreh needs 112 ticks
function printAlt needs 140 ticks
function printLog needs 248 ticks
function printSprintf needs 218 ticks
function _ui64toa needs 320 ticksAuch mit -O2 ist es klar:
function printUmdreh needs 60 ticks
function printAlt needs 64 ticks
function printLog needs 118 ticks
function printSprintf needs 212 ticks
function _ui64toa needs 96 ticks, dass deine Funktion für das unlimitierte Schreiben das schnellste ist, dicht gefolgt von meinem Code.
Allerdings stört mich da noch irgendwas ... ich kann auch nicht mit dem Finger daraufzeigen, aber etwas stört mich daran.
-
Nachtrag:
Habe jetzt auch noch einmal von WINE Code geborgt:uint64_t wine_ui64toa(uint64_t value) { char buffer[65]; char *pos; int digit; pos = &buffer[64]; *pos = '\0'; do { digit = value % 10; value = value / 10; if (digit < 10) { *--pos = '0' + digit; } else { *--pos = 'a' + digit - 10; } /* if */ } while (value != 0L); memcpy(theOutputBuffer, pos, &buffer[64] - pos + 1); }function printUmdreh needs 62 ticks
function printAlt needs 64 ticks
function printLog needs 118 ticks
function printSprintf needs 216 ticks
function _ui64toa needs 96 ticks
function wine_ui64toa needs 60 ticksAber das ist mit -O2. -O0 generiert:
function printUmdreh needs 114 ticks
function printAlt needs 140 ticks
function printLog needs 248 ticks
function printSprintf needs 216 ticks
function _ui64toa needs 320 ticks
function wine_ui64toa needs 218 ticks
-
dachschaden schrieb:
Hm, Volkard, ich glaube, damit wirst du nicht glücklich.
Ich habe mal hier Code von geborgt und das hier gebaut:uint64_t _ui64toa(uint64_t n) { char*__string=theOutputBuffer; uint64_t __value=n; char buf2[68] ; int len = 0, pos = 0 ; while (__value) { buf2[len++] = __value %10; __value /=10; } while (len) { int ch = buf2[--len] ; ch+= '0' ; __string[pos++] = ch ; } __string[pos] = 0 ; }Nee, wirklich nicht.
Der ganze Trick war, nicht inplace swappen zu müssen. Das passt auch fast zu den Messwerten von Wutz. So ebbes besser war es. Nee, nicht ganz!!! MS hat einen besseren Trick, denn wenn ich bei mir das Umdrehen ganz ausschalte, dann ist MS immernoch schneller (falls ich Eure Messwerte hochrechnen darf). Wir müssen den MS-Code anschauen, keine noch so gute Kopie. Jemand mit Windows möge sich erbarmen. Äh, Du natürlich, hast ja vorhin geschrieben. daß es auch auf Win drehen muss.Mir scheint, "asm fbstp" führt zu keinem Sieg. Unglaublich lecker, klar. Aber dann den BCD-Code zu interpretieren? Ich weiß ja nicht…
Andererseits, 64Bit sind ne Menge Holz. Was kümmern einen da ein paar Konvertierungen, wenns danach flutscht? Evtl mit if(n>10000…) ne Sonderregel.dachschaden schrieb:
Auch mit -O2 ist es klar:
Sorry, ich nehme nur -O3.
dachschaden schrieb:
, dass deine Funktion für das unlimitierte Schreiben das schnellste ist, dicht gefolgt von meinem Code.
Allerdings stört mich da noch irgendwas ... ich kann auch nicht mit dem Finger daraufzeigen, aber etwas stört mich daran.Ich kanns ahnen. Du bist vielleicht auch im Geiste ein Progger, der triviale Hardware denkt. Ich hab mit nem ZX81 angefangen, 1k RAM und so. Es ist einfach voll unsinnig, zuerst voll viel Speicher zu schreiben und dann nochmal alles umzuwerfen. Ist halt nicht so, der Prozessor ist sowas von schnell, was ganz einfache Sachen angeht, aber Divisionen kosten endlos. Und die 64Byte sind im Prozessorcache, so schnell wie Register. Verrückte Welt.
Und nu kommt die Bescherung:
#include <stdint.h> #include <stdlib.h> #include <stdio.h> #include <math.h> /***************************************************************************** **Jetzt das Makro zum Sichern der Ticks. Auf 32-Bit-Systemen kann man ueber **rdtsc die gegenwaertigen Ticks auslesen, indem man die Adresse einer **64-Bit-Zahl angibt. Auf 64-Bit-Systemen muss man Adressen zu zwei **32-Bit-Zahlen angeben. ***************************************************************************** #ifdef __x86_64__ #define SAVE_TICKS(x) \ asm("rdtsc": "=a"(*(uint32_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end)), \ "=d"(*(uint32_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end+4))); #else #define SAVE_TICKS(x) \ asm("rdtsc": "=A"(*(uint64_t*)((my_cycle_counter_##x.my_ih.my_mem)+my_cycle_counter_##x.my_end))); #endif*/ //geborgt von http://stackoverflow.com/questions/9887839/clock-cycle-count-wth-gcc static __inline__ unsigned long long rdtsc(void) { unsigned hi, lo; __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi)); return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 ); } #define MY_NUMBER 0x1100100010001fffULL //#define MY_NUMBER 42ULL //Die ganzen print-Funktionen und Messungen vom Speicherbesorgen befreien. //Macht außerdem anscheinend genug OptimierMichNichtHanzWeg. char theOutputBuffer[64]; uint64_t tt=17; uint64_t printUmdreh(uint64_t n){ char* out=theOutputBuffer; do{ tt*=17; *out++=n%10+'0'; n/=10; }while(n!=0); *out='\0'; //r soll mal in ein eigenes Register hüpfen wollen, mag out nicht mehr. for(char *l=theOutputBuffer,*r=out-1;l<r;++l,--r){ char tmp=*l; *l=*r; *r=tmp; } } /*Bisheriger naiver Ansatz*/ uint64_t get_number_length_base10(const uint64_t value) { register uint64_t length=1; register uint64_t rvalue=value; while(rvalue>=10) { //rvalue-=rvalue%10;UNFUG!!! rvalue/=10; ++length; } return length; } uint64_t printAlt(uint64_t n){ char* out=theOutputBuffer+get_number_length_base10(n); *out='\0'; do{ *--out=n%10+'0'; n/=10; }while(n!=0); } /*Neuer Ansatz mit Logarithmus.*/ uint64_t get_new_length_log2(const uint64_t value) { return (uint64_t)(log2(value)/log2(10))+1; } uint64_t printLog(uint64_t n){ char* out=theOutputBuffer+get_new_length_log2(n); *out='\0'; do{ *--out=n%10+'0'; n/=10; }while(n!=0); } uint64_t printSprintf(uint64_t n){ sprintf(theOutputBuffer,"%llu",n); } char* vorwaerts_print9Digits(uint32_t n,char* dst){ //assert(n<1000000000);//handles only 8 digits correctly uint64_t x=11529215046.06846976+1;//2^60/10^8 uint64_t r=n*x; for(int i=0;i<9;++i){ *dst++=((r)>>60)+'0'; r&=0x0fffffffffffffff; r*=10; } return dst; } char* vorwaerts_printMax9Digits(uint32_t n,char* dst){ //assert(n<1000000000);//handles only 8 digits correctly uint64_t x=11529215046.06846976+1;//2^60/10^8 uint64_t r=n*x; int i=0; for(;i<9;++i){ if(((r)>>60)!=0) break; r&=0x0fffffffffffffff; r*=10; } for(;i<9;++i){ *dst++=((r)>>60)+'0'; r&=0x0fffffffffffffff; r*=10; } return dst; } char* vorwaerts_printDigits(uint64_t n,char* dst){ if(n>=10000000000000000000){ *dst++='0'+n/10000000000000000000; n%=10000000000000000000; *dst++='0'+n/1000000000000000000; n%=1000000000000000000; dst=vorwaerts_print9Digits(n/1000000000,dst); dst=vorwaerts_print9Digits(n%1000000000,dst); return dst; } else if(n>=1000000000000000000){ *dst++='0'+n/1000000000000000000; n%=1000000000000000000; dst=vorwaerts_print9Digits(n/1000000000,dst); dst=vorwaerts_print9Digits(n%1000000000,dst); return dst; } else if(n>=1000000000){ dst=vorwaerts_printMax9Digits(n/1000000000,dst); dst=vorwaerts_print9Digits(n%1000000000,dst); return dst; } else{ dst=vorwaerts_printMax9Digits(n,dst); return dst; } } char* printVorwaerts(uint64_t n){ *vorwaerts_printDigits(n,theOutputBuffer)='\0'; } uint64_t measure(char const* fName,uint64_t (*f)(uint64_t)){ //Nur der schnellste Laug zählt! int const maxLeft=1000000; int left=maxLeft; uint64_t minTime=(uint64_t)-1; while(left!=0){ uint64_t time=-rdtsc(); f(MY_NUMBER); time+=rdtsc(); if(time<minTime){ // printf("%lld\n",time); minTime=time; left=maxLeft; } --left; } printf("function %s needs %lld ticks\n",fName,minTime); return minTime; } #define MEASURE(f) measure(#f,f) int main(void){ memset(theOutputBuffer,0,64); printf("|%lld|\n",MY_NUMBER); memset(theOutputBuffer,0,64); printUmdreh(MY_NUMBER); printf("|%s|\n",theOutputBuffer); memset(theOutputBuffer,0,64); printAlt(MY_NUMBER); printf("|%s|\n",theOutputBuffer); memset(theOutputBuffer,0,64); printLog(MY_NUMBER); printf("|%s|\n",theOutputBuffer); memset(theOutputBuffer,0,64); printSprintf(MY_NUMBER); printf("|%s|\n",theOutputBuffer); memset(theOutputBuffer,0,64); printVorwaerts(MY_NUMBER); printf("|%s|\n",theOutputBuffer); MEASURE(printUmdreh); MEASURE(printAlt); MEASURE(printLog); MEASURE(printSprintf); MEASURE(printVorwaerts); return 17; }|1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| function printUmdreh needs 169 ticks function printAlt needs 184 ticks function printLog needs 199 ticks function printSprintf needs 359 ticks function printVorwaerts needs 48 ticks //BOOM!Das hätte ich auch nicht gedacht. Uih!
Wie gesagt, ich wollte schon immer mal die Ziffern vorwärts rauströpfeln lassen; es war mir immer zu kompliziert und die alte Version war ja auch ganz gut. Irrelevant, weil die Ausgabe viel länger dauert. Dabei ist es gar nicht schwierig:
Man stellt die Zahl n=1234 einfach dar als Fixkommazahl r=1,234.
Aber binär! Trotzdem ist vor dem Komma binär die gesuchte Ziffer und dahinter der Rest.Naja, ich freue mich so, daß ich's nochmal wiederholen muss:
function printVorwaerts needs 48 ticks //BOOM!
-
edit: ungetestet ob die 0 recht ausgegeben wird.
-
volkard schrieb:
Wir müssen den MS-Code anschauen, keine noch so gute Kopie. Jemand mit Windows möge sich erbarmen. Äh, Du natürlich, hast ja vorhin geschrieben. daß es auch auf Win drehen muss.
Jau. Kann aber ne Weile dauern. nm und objdump sehen da keine Symbole, aber ich kenne die DLL, die ich disassemblieren muss, Windows/System32/msvcrt.dll. Bumms. Und dann auch nur 64-Bit, also muss ich noch was anderes als IDA nehmen. Doppelbums.
volkard schrieb:
Mir scheint, "asm fbstp" führt zu keinem Sieg. Unglaublich lecker, klar. Aber dann den BCD-Code zu interpretieren? Ich weiß ja nicht…
Andererseits, 64Bit sind ne Menge Holz. Was kümmern einen da ein paar Konvertierungen, wenns danach flutscht? Evtl mit if(n>10000…) ne Sonderregel.Dann kann ich genauso gut:
uint64_t printDumm(uint64_t n) { register char* out=theOutputBuffer; register uint64_t pn=n; register uint64_t l=1; register char*r; if(pn>=10000000000000000000ULL) ++l; if(pn>=1000000000000000000ULL) ++l; if(pn>=100000000000000000ULL) ++l; if(pn>=10000000000000000ULL) ++l; if(pn>=1000000000000000ULL) ++l; if(pn>=100000000000000ULL) ++l; if(pn>=10000000000000ULL) ++l; if(pn>=1000000000000ULL) ++l; if(pn>=100000000000ULL) ++l; if(pn>=10000000000ULL) ++l; if(pn>=1000000000ULL) ++l; if(pn>=100000000ULL) ++l; if(pn>=10000000ULL) ++l; if(pn>=1000000ULL) ++l; if(pn>=100000ULL) ++l; if(pn>=10000ULL) ++l; if(pn>=1000ULL) ++l; if(pn>=100ULL) ++l; if(pn>=10ULL) ++l; r=out+l; do { *--r=pn%10+'0'; pn/=10; } while(pn); }machen ...
function printUmdreh needs 62 ticks
function printAlt needs 64 ticks
function printLog needs 118 ticks
function printSprintf needs 214 ticks
function _ui64toa needs 98 ticks
function wine_ui64toa needs 60 ticks
function printDumm needs 46 ticks //Ja klar, das ist überhaupt nicht bescheuert ... m(volkard schrieb:
Ich kanns ahnen. Du bist vielleicht auch im Geiste ein Progger, der triviale Hardware denkt.
Exakt.
volkard schrieb:
Das hätte ich auch nicht gedacht. Uih!
Wie gesagt, ich wollte schon immer mal die Ziffern vorwärts rauströpfeln lassen; es war mir immer zu kompliziert und die alte Version war ja auch ganz gut. Irrelevant, weil die Ausgabe viel länger dauert. Dabei ist es gar nicht schwierig:
Man stellt die Zahl n=1234 einfach dar als Fixkommazahl r=1,234.
Aber binär! Trotzdem ist vor dem Komma binär die gesuchte Ziffer und dahinter der Rest.Das muss ich mir noch mal in Ruhe anschauen - ist dann doch ein bisschen viel auf einmal.
Ich schau mir jetzt erst einmal den Maschinencode von _ui64toa an, vielleicht finde ich den Schlüssel.
-
Hier hast du das, was mir der DLL-Viewer rausgespuckt hat, bis zum ersten NOP. Allerdings ist mein Assembler zu eingerostet, um da effektiv was rauslesen zu können.
Einmal in AT&T-Syntax:
7ff756a4370: 48 8b c1 mov %rcx,%rax 7ff756a4373: 4c 8b da mov %rdx,%r11 7ff756a4376: 4c 8b ca mov %rdx,%r9 7ff756a4379: 41 8b c8 mov %r8d,%ecx 7ff756a437c: 4c 8b d2 mov %rdx,%r10 7ff756a437f: 33 d2 xor %edx,%edx 7ff756a4381: 48 f7 f1 div %rcx 7ff756a4384: 83 fa 09 cmp $0x9,%edx 7ff756a4387: 77 2f ja 0x7ff756a43b8 7ff756a4389: 80 c2 30 add $0x30,%dl 7ff756a438c: 41 88 11 mov %dl,(%r9) 7ff756a438f: 49 ff c1 inc %r9 7ff756a4392: 48 85 c0 test %rax,%rax 7ff756a4395: 75 e8 jne 0x7ff756a437f 7ff756a4397: 41 88 01 mov %al,(%r9) 7ff756a439a: 49 ff c9 dec %r9 7ff756a439d: 41 8a 02 mov (%r10),%al 7ff756a43a0: 41 8a 09 mov (%r9),%cl 7ff756a43a3: 41 88 01 mov %al,(%r9) 7ff756a43a6: 41 88 0a mov %cl,(%r10) 7ff756a43a9: 49 ff c2 inc %r10 7ff756a43ac: 49 ff c9 dec %r9 7ff756a43af: 4d 3b d1 cmp %r9,%r10 7ff756a43b2: 72 e9 jb 0x7ff756a439d 7ff756a43b4: 49 8b c3 mov %r11,%rax 7ff756a43b7: c3 retq 7ff756a43b8: 80 c2 57 add $0x57,%dl 7ff756a43bb: eb cf jmp 0x7ff756a438cund einmal in Intel-Syntax
7ff756a4370: 48 8b c1 mov rax,rcx 7ff756a4373: 4c 8b da mov r11,rdx 7ff756a4376: 4c 8b ca mov r9,rdx 7ff756a4379: 41 8b c8 mov ecx,r8d 7ff756a437c: 4c 8b d2 mov r10,rdx 7ff756a437f: 33 d2 xor edx,edx 7ff756a4381: 48 f7 f1 div rcx 7ff756a4384: 83 fa 09 cmp edx,0x9 7ff756a4387: 77 2f ja 0x7ff756a43b8 7ff756a4389: 80 c2 30 add dl,0x30 7ff756a438c: 41 88 11 mov BYTE PTR [r9],dl 7ff756a438f: 49 ff c1 inc r9 7ff756a4392: 48 85 c0 test rax,rax 7ff756a4395: 75 e8 jne 0x7ff756a437f 7ff756a4397: 41 88 01 mov BYTE PTR [r9],al 7ff756a439a: 49 ff c9 dec r9 7ff756a439d: 41 8a 02 mov al,BYTE PTR [r10] 7ff756a43a0: 41 8a 09 mov cl,BYTE PTR [r9] 7ff756a43a3: 41 88 01 mov BYTE PTR [r9],al 7ff756a43a6: 41 88 0a mov BYTE PTR [r10],cl 7ff756a43a9: 49 ff c2 inc r10 7ff756a43ac: 49 ff c9 dec r9 7ff756a43af: 4d 3b d1 cmp r10,r9 7ff756a43b2: 72 e9 jb 0x7ff756a439d 7ff756a43b4: 49 8b c3 mov rax,r11 7ff756a43b7: c3 ret 7ff756a43b8: 80 c2 57 add dl,0x57 7ff756a43bb: eb cf jmp 0x7ff756a438cIch hoffe nur, ich habe jetzt nicht irgendein Copyright gebrochen oder so ...
-
OK, Volkard, Ich glaube, ich verstehe langsam, was du da gemacht hast.
Schlüssel ist die Konstante 11529215047 (260/108), welche das Verhältnis darstellt zwischen einer 9-stelligen Dezimalzahl und dem 60-Bit-Speicherraum, mit dem wir arbeiten wollen. Wir rechnen den Wert, den wir damit haben wollen, auf diesen Speicherraum hoch. Da wir uns auf 9-Stellige Dezimalwerte beschränken, vermeiden wir den Werteüberlauf - relativ knapp. Viel wichtiger ist aber, dass wir hierdurch die Zahl in ihrer Nibbledarstellung im Speicher haben - im ersten Nibble haben wir dann den gesuchten Wert in Dezimaldarstellung.
Wir gehen also alle Nibble durch, multiplizieren immer mit 10, um die nächste Zehnerstelle zu bekommen, die im letzten Nibble steht, und schreiben diesen dezimalen Wert ohne weitere Konvertierung bis auf ASCII in den String. Und weil wir von Vorne nach Hinten alles durchgehen, brauchen wir nichts umdrehen, nichts dividieren.
Bei
vorwaerts_printMax9Digitshaben wir eventuell nicht genug Nibbles mit Werten, die wir befüllen können. Deswegen schieben wir die Nibbles weiter, bis wir anfangen können mit dem Schreiben.Beeindruckender Code, das will ich sagen. Aber da stören mich noch ein paar Sachen ... darauf werde ich jetzt aber noch nicht eingehen, ich muss erst noch ein bisschen schlafen und dann ein paar Tests mit dem Code machen. Wenn ich was finales Abgeben kann, werde ich es posten.
Vielen, vielen Dank für die Hilfe.
-
Wutz schrieb:
|1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| function printUmdreh needs 732 ticks function printAlt needs 1112 ticks function printLog needs 800 ticks function _ui64toa needs 564 ticksDie Win-CRT bietet seit (mind.) VC6 Zeiten auch "_ui64toa" an, und liefert brauchbare Ergebnisse, s.o.
Den Quellcode kannst du dir ja mal zu Gemüte führen.Deine Messungen sind so … anders.
Optimierungen waren alle an?
-
Ich habe nur die Ersetzung
#include <math.h> #include <string.h> ... uint64_t printSprintf(uint64_t n){ //sprintf(theOutputBuffer,"%llu",n); _ui64toa(n,theOutputBuffer,10); }und dann jeweils mit MinGW/gcc 4.7.1 + 4.8.1 32Bit und Win7 64Bit und -O1,-O2,-O3 im Release-Modus jeweils die gleichen relativen Ergebnisse auf zwei unterschiedlichen PC erreicht:
mingw32-gcc.exe -Wall -std=c99 -O2 -c \GCC\utoa\main.c -o obj\Release\main.o|1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| |1224996691099262975| function printUmdreh needs 1953 ticks function printAlt needs 2952 ticks function printLog needs 2052 ticks function printSprintf needs 1323 ticksDie Sourcen der WinCRT sind unauffällig, und entsprechen weitgehend dem <printUmdreh>.
Wenn ich den Quelltext mit VStudio2013 übersetze, (rdtsc() muss durch __rdtsc() ersetzt werden), kommt der Unterschied nicht zustande, _ui64toa liegt immer auf Niveau von printUmdreh.
Probiere selber:
https://www.cubbyusercontent.com/pli/utoa.exe/_df8752037ade43559216f10da4198a9c
https://www.cubbyusercontent.com/pli/main.c/_96390fbc63e9408c99f52126c6753bab
https://www.cubbyusercontent.com/pli/main.s/_00aca2abfcfe4fd3b98b53999b60a616Das asm liefert nichts Überraschendes:
_printSprintf: pushl %ebp movl %esp, %ebp subl $40, %esp movl 8(%ebp), %eax movl %eax, -16(%ebp) movl 12(%ebp), %eax movl %eax, -12(%ebp) movl $10, 12(%esp) movl $_theOutputBuffer, 8(%esp) movl -16(%ebp), %eax movl -12(%ebp), %edx movl %eax, (%esp) movl %edx, 4(%esp) call __ui64toa leave retWen es interessiert, hier die WinCRT-Quelle: (den Secure+Unicode Müll habe ich mal entsorgt)
/*** *xtoa.c - convert integers/longs to ASCII string * * Copyright (c) Microsoft Corporation. All rights reserved. * *Purpose: * The module has code to convert integers/longs to ASCII strings. See * *******************************************************************************/ static void __fastcall x64tox (/* stdcall is faster and smaller... Might as well use it for the helper. */ unsigned __int64 val, char *buf, unsigned radix, int is_neg ) { char *p; /* pointer to traverse string */ char *firstdig; /* pointer to first digit */ char temp; /* temp char */ unsigned digval; /* value of digit */ p = buf; if ( is_neg ) { *p++ = '-'; /* negative, so output '-' and negate */ val = (unsigned __int64)(-(__int64)val); } firstdig = p; /* save pointer to first digit */ do { digval = (unsigned) (val % radix); val /= radix; /* get next digit */ /* convert to ascii and store */ if (digval > 9) *p++ = (char) (digval - 10 + 'a'); /* a letter */ else *p++ = (char) (digval + '0'); /* a digit */ } while (val > 0); /* We now have the digit of the number in the buffer, but in reverse order. Thus we reverse them now. */ *p-- = '\0'; /* terminate string; p points to last digit */ do { temp = *p; *p = *firstdig; *firstdig = temp; /* swap *p and *firstdig */ --p; ++firstdig; /* advance to next two digits */ } while (firstdig < p); /* repeat until halfway */ }Ist wie gesagt nichts Besonderes bei, irgendwas müssen die MinGW-Leute noch dazu gebacken haben, damit der Aufruf derselben CRT-Funktion merklich viel schneller abläuft, als beim 'Original' MS.
-
OK, ich habe noch ein bisschen an dem Code rumgehackt:
#include <stdint.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <math.h> //geborgt von http://stackoverflow.com/questions/9887839/clock-cycle-count-wth-gcc static __inline__ unsigned long long rdtsc(void) { unsigned hi, lo; __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi)); return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 ); } //Die ganzen print-Funktionen und Messungen vom Speicherbesorgen befreien. //Macht außerdem anscheinend genug OptimierMichNichtHanzWeg. char theOutputBuffer[64]; typedef uint64_t LONGEST_SUPPORTED_INTEGER; char*printUmdreh(LONGEST_SUPPORTED_INTEGER n) { register char* out=theOutputBuffer; do { *out++=n%10+'0'; n/=10; } while(n); *out='\0'; //r soll mal in ein eigenes Register hüpfen wollen, mag out nicht mehr. register char*l,*r; for(l=theOutputBuffer,r=out-1;l<r;++l,--r){ char tmp=*l; *l=*r; *r=tmp; } } /*Bisheriger naiver Ansatz*/ uint64_t get_number_length_base10(const LONGEST_SUPPORTED_INTEGER value) { register uint64_t length=1; register LONGEST_SUPPORTED_INTEGER rvalue=value; while(rvalue>=10) { //rvalue-=rvalue%10;UNFUG!!! rvalue/=10; ++length; } return length; } char* printAlt(LONGEST_SUPPORTED_INTEGER n) { register char* out=theOutputBuffer+get_number_length_base10(n); *out='\0'; do { *--out=n%10+'0'; n/=10; } while(n); } char* printSprintf(uint64_t n) { sprintf(theOutputBuffer,"%lu",n); } /*Immer vier. Einer weniger, und wir kriegen nicht mehr alle Ziffern im **Dezimalsystem dargestellt.*/ #define BITS_RESERVED_FOR_LAST_DEC_POSITION (4) /*Beinhaltet den Wert, mit dem man sämtliche Zahlen verrechnen muss, damit man **eine rein binaere Representation des Wertes im Speicher erhaelt. Dieser ist: ** 2 ^ (sizeof(LONGEST_SUPPORTED_INTEGER) - ** BITS_RESERVED_FOR_LAST_DEC_POSITION) ** / 10 ^ (Anzahl der Dezimalstellen, die man maximal mit dem Typen minus ** BITS_RESERVED_FOR_LAST_DEC_POSITION schreiben kann). Dies muss **zusätzlich noch aufgerundet werden. ***/ #define DEC_TO_BIN_REPRESENTATION(x) ((x)*11529215047) #define GET_LAST_NIBBLE(x) ((x)>>sizeof(LONGEST_SUPPORTED_INTEGER)*8-BITS_RESERVED_FOR_LAST_DEC_POSITION) #define GET_NEXT_DEC_POSITION(x) ((((x)<<BITS_RESERVED_FOR_LAST_DEC_POSITION)>>BITS_RESERVED_FOR_LAST_DEC_POSITION)*10) char* vorwaerts_print9Digits(uint32_t n,char* pdst) { /*register*/ LONGEST_SUPPORTED_INTEGER r=DEC_TO_BIN_REPRESENTATION(n); /*register*/ char*dst=pdst; /*Scheife ausgefahren.*/ *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); *dst++=GET_LAST_NIBBLE(r)+'0'; return dst; } char* vorwaerts_printMax9Digits(uint32_t n,char* dst) { register LONGEST_SUPPORTED_INTEGER r=DEC_TO_BIN_REPRESENTATION(n); register int i=0; /*Schleife koennen wir hier nicht ausfahren, weil wir die Anzahl der **bisherigen Iterationen benoetigen.*/ while(i<9) { /*Sobald wir genug Stellen vorgeschoben haben, damit wir einen **Wert haben, konnen wir mit dem Schreiben anfangen.*/ if(GET_LAST_NIBBLE(r)) break; r=GET_NEXT_DEC_POSITION(r); ++i; } while(i<9) { *dst++=GET_LAST_NIBBLE(r)+'0'; r=GET_NEXT_DEC_POSITION(r); ++i; } return dst; } #define MY_NUMBER 0xFFFF000012341234ULL /* 123891380ULL*/ /*0xf100100010001fffULL*/ #define BIG_20 10000000000000000000ULL #define BIG_19 1000000000000000000ULL #define BIG_10 1000000000ULL char* vorwaerts_printDigits(LONGEST_SUPPORTED_INTEGER pn,char* pdst) { register LONGEST_SUPPORTED_INTEGER n=pn; register char*dst=pdst; /*Ganz grosse Zahl.*/ if(n>=BIG_19) { /*GAAAAAAAAAAAAAANZ grosse Zahl. Bei dieser machen wir zweimal **die Konvertierung manuell sodass 18 Ziffern übrigbleiben, **und dann schreiben wir mit zwei Calls den String.*/ if(n>=BIG_20) { *dst++='0'+n/BIG_20; n%=BIG_20; } *dst++='0'+n/BIG_19; n%=BIG_19; dst=vorwaerts_print9Digits(n/BIG_10,dst); dst=vorwaerts_print9Digits(n%BIG_10,dst); return dst; } /*Nicht ganz so große Zahl. Hier kann es sein, dass wir beim ersten **Mal nur 1 Stelle schreiben, daber danach schreiben wir wieder volle **9 Stellen.*/ else if(n>=BIG_10) { dst=vorwaerts_printMax9Digits(n/BIG_10,dst); dst=vorwaerts_print9Digits(n%BIG_10,dst); return dst; } /*OK, kleine Zahl im Bereich von unter einer Millarde.*/ else if(n) { dst=vorwaerts_printMax9Digits(n,dst); return dst; } /*Sonderfall 0*/ dst[0]='0'; return dst+1; } char* printVorwaerts(uint64_t n) { *vorwaerts_printDigits(n,theOutputBuffer)='\0'; } uint64_t measure(char const* fName,char* (*f)(LONGEST_SUPPORTED_INTEGER)) { //Nur der schnellste Laug zählt! int const maxLeft=1000000; int left=maxLeft; uint64_t minTime=(uint64_t)-1; while(left!=0) { uint64_t time=-rdtsc(); f(MY_NUMBER); time+=rdtsc(); if(time<minTime) { minTime=time; left=maxLeft; } --left; } printf("function %s needs %lu ticks\n",fName,minTime); return minTime; } #define MEASURE(f) measure(#f,f) int main(void) { memset(theOutputBuffer,0,64); printf("|%llu|\n",MY_NUMBER); memset(theOutputBuffer,0,64); printUmdreh(MY_NUMBER); printf("|%s|\n",theOutputBuffer); memset(theOutputBuffer,0,64); printAlt(MY_NUMBER); printf("|%s|\n",theOutputBuffer); memset(theOutputBuffer,0,64); printSprintf(MY_NUMBER); printf("|%s|\n",theOutputBuffer); memset(theOutputBuffer,0,64); printVorwaerts(MY_NUMBER); printf("|%s|\n",theOutputBuffer); MEASURE(printUmdreh); MEASURE(printAlt); MEASURE(printSprintf); MEASURE(printVorwaerts); return 0; }Ausgabe:
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
|18446462599038243380|
function printUmdreh needs 78 ticks
function printAlt needs 96 ticks
function printSprintf needs 212 ticks
function printVorwaerts needs 28 ticks //Buyakascha
-
dachschaden schrieb:
OK, ich habe noch ein bisschen an dem Code rumgehackt:
An ziemlich genau diese Tricks dachte ich auch.
Aber bei mir bringen Deine Hacks leider 3 Ticks an Langsamkeit dazu.
function printVorwaerts needs 48 ticks //BOOM! function printVorwaerts needs 51 ticks //Buyakascha
-
Verrückt. Wieder mit -O3 kompiliert?
$ gcc -o volk_boom volk_boom.c -O2 $ ./volk_boom |18446462599038243380| |18446462599038243380| |18446462599038243380| |18446462599038243380| |18446462599038243380| function printUmdreh needs 78 ticks function printAlt needs 96 ticks function printSprintf needs 212 ticks function printVorwaerts needs 32 ticks $ gcc -o volk_boom volk_boom.c -O3 $ ./volk_boom |18446462599038243380| |18446462599038243380| |18446462599038243380| |18446462599038243380| |18446462599038243380| function printUmdreh needs 64 ticks function printAlt needs 96 ticks function printSprintf needs 212 ticks function printVorwaerts needs 28 ticksAnsonsten wüsste ich jetzt auch nicht, was das Problem sein könnte - es ist exakt der gleiche Code wie gepostet.
-
dachschaden schrieb:
Verrückt. Wieder mit -O3 kompiliert?
Klar.
Aber um die Vergleichbarkeit zu alten Messungen zu bewahren, hab ich mit der alten Zahl gemessen.
#define MY_NUMBER 0x1100100010001fffULLMit der neuen Zahl sind bei mir beide Versionen gleich schnell.
Hab nicht ins Compilat geschaut, vielleicht macht -O3 das Loop-Unrollig ja selber.
-
volkard schrieb:
Aber um die Vergleichbarkeit zu alten Messungen zu bewahren, hab ich mit der alten Zahl gemessen.
Mit der neuen Zahl sind bei mir beide Versionen gleich schnell.Okee ... bei mir macht die alte Zahl gar keinen Unterschied. Sind immer noch die gleichen Werte bei -O2 und -O3.
volkard schrieb:
Hab nicht ins Compilat geschaut, vielleicht macht -O3 das Loop-Unrollig ja selber.
Hättest das mal lieber gemacht.
Die -O2-Variante hat gar keinen Unterschied invorwaerts_print9Digitszu -O3. Unrolling passiert zwar beivorwaerts_printMax9Digits- das erkenne ich trotz madigen Assemblerkenntnissen deutlich - aber bei so großen Zahlen wirdvorwaerts_printMax9Digitsgar nicht mehr ausgeführt.Ich gebe zu, ich bin mit meinem Latein ein wenig am Ende.
-
dachschaden schrieb:
Ich gebe zu, ich bin mit meinem Latein ein wenig am Ende.
Ich sehe das Problem nicht. Bei Dir ist die Version mit den Hacks um 4 Ticks schneller, wenn ich das richtig sehe. Ist doch ok.
Bei mir ist sie um 3 Ticks langsamer. Ist auch voll ok. Kein Grund mehr, hier viel zu optimieren. Dreimal so schnell wie die alte Version.
-
Gut, wenn du meinst.
Vielen, vielen Dank für die Hilfestellung noch einmal, Leute. Besonders dir, Volkard. Durch diesen Thread habe ich einiges gelernt, was wir jetzt einbauen werden.
