c-funktion laufzeit bzw. geschwindigkeit
-
hola leute
bissl komischer titel, aber mir ist nix messeres eingefallen.
ist zwar ne C funktion, aber ich glaube das ich hier doch am besten aufgehoben bin.folgendes:
bin grad am nachbau der itoa-funktion und bin grad am raetseln was die zeitliche dauer der funktion betrifft:
funktion:
inline void TFMain::ctoi(char *t_buffer,unsigned int t_value) { char buffer[16]; unsigned int uih; unsigned int uil; unsigned int uihh; unsigned int uihl; unsigned int uilh; unsigned int uill; unsigned int temp; uih = t_value / 10000; uil = t_value % 10000; temp = t_value / 10000; // (1) }die funktion, ja ich weiß, das sie derzeit nix macht, braucht fuer 1000 aufrufe ueber eine for-schleife rund 48000 ticks(gemessen mit rdtsc).
wenn ich die zeile (1) weg lasse, nur noch rund 9000 ticks.hat jemand ne idee woran das liegen koennte ?
Meep Meep
-
Und was verwendest du da für einen Dreckscompiler?
Ich würde allerdings das % durch eine Multiplikation und eine Subtraktion ersetzen, das ist mit großer Wahrscheinlichkeit schneller - nur dann nicht, wenn ein besonders schlauer Compiler draufkommt, dass der idiv-Befehl auf Intel nicht nur das Divisionsergebnis sondern auch gleich den Rest liefert. Tut aber glaub ich keiner.
-
bist du sicher, dass du alle optimierungen eingeschaltet hast? dann dürfte die funktion nähmlich gar keine zeit verbrauchen. / und % sind ohne seiteneffekte und das ergebnis wird nie gebraucht...
wenn das wirklich alles ist, was dein compiler (welchen benutzt du denn?) liefert dann ab auf den müll damit.
vorzeitiges optimieren an unfertigen funktionen ist sowieso zwecklos.
-
hola
mein dreckscompiler: von borland. optimierungen sind alle aktiv.
ob ich da den modulo operator gegen div und minus autausche is derzeit eigendlich egal.die funtion ist ueberigens fertig. aber mir dauerte sie einfach zulange, deshalb wollt ic mal nachgucken, was da am meisten zeit verbaucht. so kam ich dann auf die nutzlose funktion. warum braucht jetz eigendlich die verson mit der zeile (1) mehr als m mal so lange wie die andere ?
Meep Meep
-
Weil der Borland ein Dreckscompiler ist
Ich hab auch gesagt, du sollst es durch mul und minus ersetzen, nicht durch div und minus.
-
Ringding schrieb:
Ich würde allerdings das % durch eine Multiplikation und eine Subtraktion ersetzen, das ist mit großer Wahrscheinlichkeit schneller - nur dann nicht, wenn ein besonders schlauer Compiler draufkommt, dass der idiv-Befehl auf Intel nicht nur das Divisionsergebnis sondern auch gleich den Rest liefert. Tut aber glaub ich keiner.
Aber klar doch. gcc-3.4.3:
int foo(int a, int b) { return (a / b) + (a % b); }wird mit -O3 zu (vorsicht AT&T-Syntax
foo: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax cltd idivl 12(%ebp) popl %ebp addl %edx, %eax retUnd das ist definitiv optimaler als Subtraktion/Division
-
na gut. hab jetz mal modulo ersetzt.
derzeit:
inline void TFMain::ctoi(char *t_buffer,unsigned int t_value) { char buffer[16]; unsigned int uih; unsigned int uil; unsigned int uihh; unsigned int uihl; unsigned int uilh; unsigned int uill; unsigned int temp; uih = t_value / 10000; uil = t_value - (10000 * uih); temp = t_value / 10000; // (1) }jetzt braucht er mit und ohne zeile (1) ca. 48000 ticks.
ohne (1) und mit modulo braucht er aber nur 1/5 der zeit.
also wie jetz weiter ? ;o)ich glaub, das mit dem modulo koennen wir jetz mal ruhen lassen.
warum nun der grosse zeitunterschied mit und ohne (1) ?Meep Meep
-
@TriPhoenix: Not bad! Auf non-x86 ist vermutlich trotzdem mul/minus ratsamer.
-
Du solltest wirklich mal die Funktion fertigmachen. Da kann sich noch hundertmal was am Laufzeitverhalten ändern. Richtig beurteilen kannst du es erst, wenn du ganz fertig bist. Leider ist halt der Borland-Compiler echt mies. Das ist so ziemlich der einzige halbwegs aktuelle Compiler, den sogar ein Assembler-Anfänger in der Ausführungsgeschwindigkeit schlägt.
-
re
also jetz mal die gesammte funktion
// globales array char array[] = {"00010203040506070809101112131415161718192021222324252627282930313233343536373839" "40414243444546474849505152535455565758596061626364656667686970717273747576777879" "8081828384858687888990919293949596979899"}; // die funktion inline void TFMain::ctoi(char *t_buffer,unsigned int t_value) { char buffer[16]; unsigned int uih; unsigned int uil; unsigned int uihh; unsigned int uihl; unsigned int uilh; unsigned int uill; unsigned int temp; uih = t_value / 10000; uil = t_value - (uih * 10000); uihh = uih / 100; uihl = uih - (uihh * 100); uilh = uil / 100; uill = uil - (uilh * 100);; short int *p = (short int*) buffer; short int *q = (short int*) array; p[0] = q[uihh]; p[1] = q[uihl]; p[2] = q[uilh]; p[3] = q[uill]; buffer[8] = '\0'; char *c = buffer; char *tc = t_buffer; while(*c == '0') ++c; while(*c) *(tc++) = *(c++); }derzeit braucht die funktion fuer die ersten 10000 zahlen rund 1,92 mio. ticks.
waere fein wenn man da noch was drann drehen koennte.
kann man da noch was mit parallelitaet machen ?deshalb hatte ich zuerst auch den modulo dabei ,weil ich dachte, das er die division und modulo parallel ausfuehren kann. so geht das ja schwerlich, weil er auch das ergebnis der division warten muss.
Meep Meep
-
versuch mal das zu messen:
inline void TFMain::ctoi(char* t_buffer, unsigned t_value) { t_buffer += t_value >= 100 ? t_value >= 10000 ? 6 : t_value >= 1000 ? 5 : 4 : t_value >= 10 ? 3 : 2; *--t_buffer = '\0'; do { *--t_buffer = '0' + t_value % 10; } while( t_value /= 10 ); }wenn er / und % nicht zusammenfassen kann, gibt es leider kaum etwas, um den compiler zu heilen.
-
hallo camper
also mit dem bcb compiliert, ist deine funktion nur minimal schneller als atoi vom bcb selbst.
messung fuer die ersten 1 millionen zahlen:
atoi : 556 mio. ticks
deine : 551 mio. ticksmeine alte vresion hab ich nun etwas umgeschrieben und komme jetz
auf 172 mio. ticks. also ungefaehr 3 mal so schnell.
leider hab ich keinen anderen compiler da, damit ich das mal wo anders testen kann. vielleicht waere deine version schneller als meine und der borland macht nur mistcode drauss.koennte mal jemand vielleicht atoi mit 1 bis 1000000 durchlaufen lassen, mit nem guten compiler, und das mit rdtsc messen ?
damit ich mal nen anhaltspunkt habe ?
sollte man auch dazu schreiben, auf welchem prozi das getestet wurde.
ich test grad auf nem AMD64 schleppicermy
Meep Meep
-
#include <memory> char smallNums[10000][6] = { 0 }; char NullNums[10000][5] = { 0 }; char const* const init_smallNums() { for( int i = 0; i < 10000; ++i ) { int v = i; char* buf = &smallNums[i][0]; char x = v >= 100 ? v >= 1000 ? 4 : 3 : v >= 10 ? 2 : 1; buf[ 5 ] = x; buf += x; do { *--buf = '0' + v % 10; } while( v /= 10 ); } for( int i = 0; i < 10000; ++i ) { int v = i; char* buf = &NullNums[i][0]; for( int j = 3; j >= 0; --j ) { buf[j] = '0' + v % 10; v /= 10; } } return smallNums[0]; } char const* const init_smallNums_v = init_smallNums(); inline void ctoi(char* t_buffer, unsigned t_value) { static char const n10000[] = "10000"; static char const n100000000[] = "100000000"; if( t_value < 100000000 ) { if( t_value <= 10000 ) { if( t_value < 10000 ) { memcpy( t_buffer, smallNums[ t_value ], smallNums[ t_value ][ 5 ] + 1 ); } else { memcpy( t_buffer, n10000, sizeof( n10000 ) ); } } else { unsigned v = t_value / 10000; t_value %= 10000; memcpy( t_buffer, smallNums[ v ], smallNums[ v ][ 5 ] ); memcpy( t_buffer + smallNums[ v ][ 5 ], NullNums[ t_value ], 5 ); } } else { if( t_value != 100000000 ) { unsigned v = t_value / 100000000; t_value %= 100000000; char x; memcpy( t_buffer, smallNums[ v ], x = smallNums[ v ][ 5 ] ); v = t_value / 10000; t_value %= 10000; memcpy( t_buffer += x, NullNums[ v ], 4 ); memcpy( t_buffer + 4, NullNums[ t_value ], 5 ); } else { memcpy( t_buffer, n100000000, sizeof( n100000000 ) ); } } } #include <iostream> typedef unsigned long long u64; inline u64 rdtsc() { __asm rdtsc; } int main() { u64 gtime; char xyz[10] = ""; gtime = rdtsc(); for( unsigned i = 0; i < 10000000; ++i ) { ctoi(xyz,i); } gtime = rdtsc() - gtime; std::cout << gtime << '\t' << double(gtime)/10000000.0 << std::endl; char y; std::cin >> y; return 0; }mal zum spass mit p4 und vc++ ergibt ungefähr 150 ticks pro zahl. allerdings benutzt vc auch rep mosb (ugh!) - dabei hab ich die anzahl der zeichen extra als konstante angegeben um aggresivere optimierung zu erlauben. man könnte versucht sein, das ganze irgendwie mit FBSTP zu machen... allerdings ist dessen performance grauenvoll ( 172 takte bei amd )
-
Was magst du jetzt? Zahl zu String oder String zu Zahl? Du redest ständig von atoi (also String zu Zahl), deine Funktion macht aber das Umgekehrte.
-
re
meinte natuerlich itoa. bin scho etwas durcheinander heute.
@camper:
du baust da ja ne ganz schoen grosse table auf. so grosse tables wollte ich jedoch vermeiden. is zwar im gesammten gesehen nicht viel speicher, aber fuer meinen geschmack etwas zu gross. vorallem wenn der code durch nicht wirklich viel schneller ist.inzwischen bin ich auch schon auf 167 ticks pro zahl runter gekommen.
gibts dafuer eigendlich nicht vielleicht schon ne asm optimierte version ?
koennte man ja fast meinen, da sowas doch recht haeufig gebraucht wird.
denk ich mal so.Meep Meep
-
ich teste auf p4, du auf amd64... rechne besser mal damit, dass es bei dir nur ungefähr 2/3 soviele takte braucht
-
Ich wundere mich gerade, warum in der GNU libc-Doku nirgends itoa erwähnt wird...
-
Also die Methode von camper braucht auf einem 2GHz Athlon XP mit gcc-3.4.3 unter Linux 55 Zyklen, auf einem Xeon 2.8GHz 155.
Der Unterschied dürfte aber auch daran liegen, dass ersterer eine bessere memcpy-Implementierung hat. Der Athlon XP läuft mit Debian, der Xeon mit RedHat 9.
-
re
messt doch mal einer von euch meinen zusammen geschusterten code aus, fallse wer lust hat.
static inline __fastcall void TFMain::func(char *t_buffer, unsigned int t_value) { char buffer[15]; unsigned int v[5]={0,0,0,0,0}; if(t_value >= 100000000) { v[0] = t_value / 100000000; t_value -= v[0] * 100000000; } if(t_value >= 1000000) { v[1] = t_value / 1000000; t_value -= v[1] * 1000000; } if(t_value >= 10000) { v[2] = t_value / 10000; t_value -= v[2] * 10000; } if(t_value >= 100) { v[3] = t_value / 100; t_value -= v[3] * 100; } v[4] = t_value; short int *p = (short int*) buffer; //unsigned int *p = (unsigned int*) buffer; short int *si1 = (short int*) array; short int *si2 = (short int*) array; short int *q = (short int*) t_buffer; p[0] = si1[v[0]]; p[1] = si1[v[1]]; p[2] = si1[v[2]]; p[3] = si1[v[3]]; p[4] = si1[v[4]]; buffer[10] = '\0'; char *c = buffer; char *d = t_buffer; while(*c == '0') ++c; while(*c) *(d++) = *(c++); *d = '\0'; }55 ticks is aber ein sehr guter wert. wird wahrscheinlich am xeon liegen schaetz ich mal.
koenntest mal dein teil disassemblieren und nachgucken oder posten was der da macht ? vielleicht kann man das ja irgendiwe gebrauchen. hab leider keinen xeon bei der hand. ausser bei meiner freundin im auto die xeonlampen. aber das duerfte doch was anderes sein ;o)Meep Meep
-
aus
while(*c) *(d++) = *(c++); *d = '\0';machst du besser
while(*d++=*c++);oder
strcpy(d,c);was besser ist, hängt hier wirklich vom compiler ab, i.allg. ist letzteres zu empfehlen.
ich habs mal ein mit inline assembler probiert, es ist nicht gänzlich optimal aber gut genug (selbes framework wie zuvor, nur die funktion hat sich geändert)inline void ctoi(char* t_buffer, unsigned t_value) { unsigned static const n10000 = 10000; unsigned static const n100000000 = 100000000; __asm { mov eax, t_value mov ecx, t_buffer xor edx, edx cmp eax, 100000000 jae ae100000000 cmp eax, 10000 jae ae10000 mov edx, smallNums[ eax + eax * 4 ] mov [ ecx ], edx mov byte ptr [ ecx + 4 ], 0 jmp getout ae10000:div n10000 mov ebx, smallNums[ eax + eax * 4 ] movzx eax, smallNums[ eax + eax * 4 + 4 ] mov edx, NullNums[ edx * 4 ] mov [ ecx ], ebx mov [ ecx + eax ], edx mov byte ptr [ ecx + eax + 4 ], 0 jmp getout ae100000000: div n100000000 mov ebx, smallNums[ eax + eax * 4 ] movzx eax, smallNums[ eax + eax * 4 + 4 ] mov [ ecx ], ebx add ecx, eax mov eax, edx xor edx, edx div n10000 mov eax, NullNums[ eax * 4 ] mov edx, NullNums[ edx * 4 ] mov [ ecx ], eax mov [ ecx + 4 ], edx mov byte ptr [ ecx + 8 ], 0 getout: } }ist ungefähr doppelt so schnell wie zuvor. allerdings sind das ja auch keine realistischen messungen. im grunde ist es sowieso nur spielerei.
bei borland musst du die speicherzugriffe evtl so schreiben:
movzx eax, smallNums[ eax + eax * 4 + 4 ] mov byte ptr [ ecx + 8 ], 0wird zu
movzx eax, [ smallNums + eax + eax * 4 + 4 ] mov [ byte ptr ecx + 8 ], 0oder so.