Länge einer Zahl in einer angegebenen Basis finden

SeppJ

dachschaden schrieb:

Und das funktioniert, wenn ich den Code auch mit Krüppelcompilern wie Visual Studio kompiliere (muss halt auf beiden Systemen laufen)? Ich habe schon die Krise bekommen, als ich alloca durch ein Präprozessormakro ersetzen musste, weil VS nur _alloca kennt.

_BitScanReverse, bzw. _BitScanReverse64 bei MSVC.
__builtin_clzl für unsigned long, bzw. __builtin_clzll für unsigned long long beim GCC.

Musst du eben weitere Präprozessormakros für definieren. Da es dir ja anscheinend auf jede noch so kleine Optimierung ankommt, ist das doch ein sehr kleiner Preis. Das ist doch noch relativ harmlos, was Mikrooptimierungen angeht.

ABER: Ist das überhaupt die richtige Lösung? Selbst wenn du den Logarithmus der Basis exakt berechnest (oder in einem Lookuptable nachguckst), so kann das Ergebnis doch um 1 ungenau sein:
1100011 -> MSB ist 7 -> Dezimaldarstellung hat 2 Stellen ("99")
1100100 -> MSB ist 7 -> Dezimaldarstellung hat 3 Stellen ("100")

Das kommt halt davon, wenn man bei einem der Zwischenergebnisse die Nachkommastellen abschneidet. Vermutlich wird es sogar irgendwo im Zahlenraum 0 bis 2^64 und im Basenraum 2 bis 36 sogar irgendeinen Fall geben, bei dem selbst long double Logarithmen einen of-by-1-Error ergeben werden. Ich fürchte fast, die einzig 100% zuverlässige Methode ist es, die Anzahl der benötigten Stellen im Nachhinein festzustellen (Umdrehmethode), oder durch eine "abgespeckte" Berechnung im Voraus (also so etwas wie deine erste Methode, aber das ist sicherlich langsamer als das Umdrehen im Nachhinein). Oder immer 1 Byte zur Sicherheit einfügen, wenn das Anwendungsszenario das hergibt.

PS: Mal so aus Neugierde: Ist das überhaupt ein realistisches Anwendungsszenario, an dem du gerade so viel Entwicklungszeit verbringst? Verschiedene Zahlendarstellungen klingen nicht unbedingt nach einem Thema, bei dem es auf Performance ankäme, erst recht nicht auf solche Mikrooptimierungen, wie du sie hier suchst. Einfach, da die Darstellung letztlich für eine Ausgabe bestimmt sein muss (warum sollte man sonst etwas darstellen wollen?) und bei IO ist normalerweise das Gerät der Flaschenhals, nicht die Programmlogik. Also: Bei welchem Anwendungsszenario meinst du, schnelle Zahlendarstellungen zu benötigen?

PPS: Hast du diese (oder eine sehr ähnliche) Frage hier schon einmal gestellt? Dein Thema und dein Stil kommen mir irgendwie bekannt vor, aber es ist schon ein paar Monate her, glaube ich.

Für das Messen der Ticks hab ich damals ein API geschrieben. welches auf Präprozessormarkos beruht, weil die Methode auf verschiedenen Architekturen halt anders ist.
Ich habe eine gute Stunde daran gearbeitet, den Code leserlich zu gestalten und dennoch die Grundstruktur beizubehalten:

/*Kompiliert mit:
**gcc -o geschw_test geschw_test.c -lm -m[32 oder 64]
**Laeuft mit:
**./geschw_test
*/

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

/*Generelles Objekt, welches einen Haufen Speicher beinhaltet.*/
struct my_heap
{
	size_t	my_max;	/*Wie viele Bytes wir reserviert haben*/
	char*	my_mem;	/*Zeiger zum eigentlichen Speicher*/
};

/*****************************************************************************
**Speicher ist gut und schoen, aber wir benoetigen auch etwas, das uns sichert,
**wie weit wir geschrieben haben. Dafuer haben wir einen Streamer.
*****************************************************************************/
struct my_streamer
{
	/*Basisobjekt*/
	struct my_heap my_ih;

	/*Und die Information wo im Heap definierte Werte anfangen und wo
	**aufhoeren.*/
	size_t my_begin;
	size_t my_end;
};

/*****************************************************************************
**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

/*****************************************************************************
**Groesse eines Eintrages im Stream. Ein Eintrag sind immer 8-Byte fuer die
**Anzahl der Ticks selbst plus die Adresse des Strings, der im statischen
**Speicher der Anwendund steht, gross (auf 32-Bit Systemen 4 Byte, auf
**64-Bit-Systemen 8 Byte).
*****************************************************************************/
#define CYCLE_COUNTER_ENTRY_SIZE (sizeof(uint64_t)+sizeof(size_t))

/*Streamer deklarieren*/
#define CYCLE_COUNTER_INIT(x) struct my_streamer my_cycle_counter_##x

/*Makro zum Hinzufuegen eines Markers im Streamer.*/
#define CYCLE_COUNTER_ADD_MARKER(x,y) \
{ \
	SAVE_TICKS(x) \
	*(size_t*)(my_cycle_counter_##x.my_ih.my_mem+my_cycle_counter_##x.my_end+sizeof(uint64_t))=(size_t)&y; \
	my_cycle_counter_##x.my_end+=CYCLE_COUNTER_ENTRY_SIZE; \
}
/*Ende des Makros.*/

/*Streamer initialisieren.*/
#define CYCLE_COUNTER_ALLOC(x) \
{ \
	my_cycle_counter_##x.my_begin=0; \
	my_cycle_counter_##x.my_end=0; \
	\
	/*********************************************************************
	**Wir machen hier einfach eine statische Initialisierung, alles andere
	**wuerde den Rahmen des Programmes sprengen.
	**********************************************************************/ \
	my_cycle_counter_##x.my_ih.my_max=4096; \
	my_cycle_counter_##x.my_ih.my_mem=malloc(my_cycle_counter_##x.my_ih.my_max); \
	CYCLE_COUNTER_ADD_MARKER(x,"(Intern start)"); \
}
/*Ende des Makros.*/

/*Auf verschiedenen Systemen erwartet printf verschiedene Konstanten
**fuer einen size_t. Mit diesem Makro loesen wir das auf.*/
#ifdef __x86_64__
#define UINT64_T_PRINTF		"%lu"
#define HEX64_PRINTF		"%lx"
#else
#define UINT64_T_PRINTF		"%llu"
#define HEX64_PRINTF		"%llx"
#endif

/*Alle Marker im Streamer ausgeben.*/
#define CYCLE_COUNTER_PRINTOUT(x) \
{ \
	/*********************************************************************
	**"tmp" beinhaltet die Bytes bis zum gegenwaertigen Marker, "first"
	**die Ticks des ersten und "last" die Ticks des letzten Markers.
	**
	**Ausgabenformat ist folgendes:
	**[<Name des Objektes>|<Gegenwaertige Ticks in Hexdec>|<Gleiches in Dec>
	** |<Unterschied zum letzten Marker in Hexdec>|<Gleiches in Dec>
	** |Markerstring
	**********************************************************************/ \
	size_t tmp=0; \
	uint64_t first=*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem),last=0; \
	while(tmp<my_cycle_counter_##x.my_end) \
	{ \
		printf("[" #x "|" \
			"0x" HEX64_PRINTF "|" \
			UINT64_T_PRINTF "|" \
			"0x" HEX64_PRINTF "|" \
			UINT64_T_PRINTF "|" \
			 "\"%s\"" "]\n", \
			*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp), \
			*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp), \
			*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp)-last, \
			*(uint64_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp)-last, \
			(char*)*(size_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp+sizeof(uint64_t))); \
		last=*(size_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp); \
		tmp+=CYCLE_COUNTER_ENTRY_SIZE; \
		\
	} \
	/*Finale Ausgabe mit der Anzahl der Ticks zwischen erstem und letzten
	**Marker.*/ \
	printf("[" #x "|" \
		"0x" HEX64_PRINTF "|" \
		UINT64_T_PRINTF "|" \
		"\"%s\"" "]\n", \
		last-first, \
		last-first, \
		"(Overall)"); \
}
/*Ende des Makros.*/

/*Streamer freigeben. Das heisst im Grunde, den Speicher von malloc wieder
**freigeben (duh).*/
#define CYCLE_COUNTER_FREE(x) free(my_cycle_counter_##x.my_ih.my_mem)

/*Ende des APIs. Jetzt koennen wir uns um richtigen Code kuemmern.*/

#include <math.h>

/*Bisheriger naiver Ansatz*/
uint64_t get_number_length(const uint64_t value,const uint8_t radix)
{
	register uint64_t length=1;
	register uint64_t rvalue=value;

	while(rvalue>=radix)
	{
		rvalue-=rvalue%radix;
		rvalue/=radix;
		++length;
	}

	return length;
}

/*Neuer Ansatz fuer Basis 16.
**Habe ich drin gelasen, damit man diese Funktionen gleich direkt mittesten
**kann.*/
uint64_t get_new_length_base16(const uint64_t value)
{
	register uint64_t rvalue=value,nibbles=sizeof(uint64_t)*2;
	do
	{
		--nibbles;
		if(rvalue&(0xFULL<<nibbles*4))return nibbles+1;
	}
	while(nibbles-1);
	return 1;

}

/*Neuer Ansatz fuer Basis 2.*/
uint64_t get_new_length_base2(const uint64_t value)
{
	register uint64_t rvalue=value,nibbles=sizeof(uint64_t)*2,temp;
	do
	{
		if(!(temp=(rvalue>>--nibbles*4)&0xFULL))
			continue;
		if(temp&8)return nibbles*4+4;
		if(temp&4)return nibbles*4+3;
		if(temp&2)return nibbles*4+2;
		return nibbles*4+1;
	}
	while(nibbles);
	return 1;
}

/*Neuer Ansatz mit Logarithmus.*/
uint64_t get_new_length_log2(const uint64_t value)
{
	return (uint64_t)(log2(value)/log2(10))+1;
}

/*Nummer, die fuer alle Calls verwendet werden soll, damit wir ja einheitliche
**Ergebnisse haben.*/
#define MY_NUMBER 0x1100100010001fffULL

int main(void)
{
	/*Streamer deklarieren.*/
	CYCLE_COUNTER_INIT(example_1);
	CYCLE_COUNTER_INIT(example_2);
	CYCLE_COUNTER_INIT(example_3);

	uint64_t first_length;
	uint64_t second_length;
	uint64_t third_length;

	printf("Wert fuer Berechnung: %llu\n",MY_NUMBER);

	/*Streamer alloziiieren.*/
	CYCLE_COUNTER_ALLOC(example_1);
	CYCLE_COUNTER_ALLOC(example_2);
	CYCLE_COUNTER_ALLOC(example_3);

	/*Erster Call, beinhaltet meinen damaligen "naiven" Ansatz.*/	
	CYCLE_COUNTER_ADD_MARKER(example_1,"get_number_length begin");
	first_length=get_number_length(MY_NUMBER,10);
	CYCLE_COUNTER_ADD_MARKER(example_1,"get_number_length end");

	/*Zweiter Call, beinhaltet die Berechnung mit log2, wird allerdings
	**- zumindest bei mir - vom Compiler weitestgehen optimiert.*/
	CYCLE_COUNTER_ADD_MARKER(example_2,"log2 begin");
	second_length=(uint64_t)(log2(MY_NUMBER)/log2(10))+1;
	CYCLE_COUNTER_ADD_MARKER(example_2,"log2 end");

	/*Dritter Call, wieder Logarithmus, aber diesmal in eine exportierte
	**Funktion, hier darf der Compiler nichts wegoptimieren.*/
	CYCLE_COUNTER_ADD_MARKER(example_3,"get_new_length_log2 begin");
	third_length=get_new_length_log2(MY_NUMBER);
	CYCLE_COUNTER_ADD_MARKER(example_3,"get_new_length_log2 end");

#define SEPARATOR "===========================================================================================\n"
	/*Ausgabe*/
	printf(SEPARATOR);
	CYCLE_COUNTER_PRINTOUT(example_1);
	printf(SEPARATOR);
	CYCLE_COUNTER_PRINTOUT(example_2);
	printf(SEPARATOR);
	CYCLE_COUNTER_PRINTOUT(example_3);
	printf(SEPARATOR);

	/*Aufraeumen*/
	CYCLE_COUNTER_FREE(example_1);
	CYCLE_COUNTER_FREE(example_2);
	CYCLE_COUNTER_FREE(example_3);

	/*Kontrolle, ob die Ergebnisse alle gleich sind.*/
	printf("Laengenergebnis: [" UINT64_T_PRINTF " == " UINT64_T_PRINTF " == " UINT64_T_PRINTF "]\n",first_length,second_length,third_length);

	/*Ende (duh).*/
	return 0;
}

Führt dann bei mir zur Ausgabe:

Wert fuer Berechnung: 1224996691099262975

[example_1|0x226724e4ee54c|605222335341900|0x226724e4ee54c|605222335341900|"(Intern start)"]
[example_1|0x226724e4efc98|605222335347864|0x174c|5964|"get_number_length begin"]
[example_1|0x226724e4f0290|605222335349392|0x5f8|1528|"get_number_length end"]
[example_1|0x1d44|7492|"(Overall)"]

[example_2|0x226724e4ef1f4|605222335345140|0x226724e4ef1f4|605222335345140|"(Intern start)"]
[example_2|0x226724e4f02ac|605222335349420|0x10b8|4280|"log2 begin"]
[example_2|0x226724e4f02c4|605222335349444|0x18|24|"log2 end"]
[example_2|0x10d0|4304|"(Overall)"]

[example_3|0x226724e4efc7c|605222335347836|0x226724e4efc7c|605222335347836|"(Intern start)"]
[example_3|0x226724e4f0370|605222335349616|0x6f4|1780|"get_new_length_log2 begin"]
[example_3|0x226724e4f7188|605222335377800|0x6e18|28184|"get_new_length_log2 end"]
[example_3|0x750c|29964|"(Overall)"]

Zu den Anforderungen: Das API soll zwei Funktionen exportieren. Einmal eine Version, wo der Nutzer nur einen Zeiger und eine Zahl angeben muss - hier bestimmt die Funktion dann, wie groß die Zahl ist, und übergibt diesen Wert zusammen mit Zeiger und Zahl an die zweite Funktion -> siehe weiter - und eine Version, die die Anzahl der zu schreibenden Zeichen (a.k.a. die Länge der Zahl oder Logarithmus) übernimmt und die Anzahl der Bytes schreibt. Aus Gründen der Performance (hast du ja schon selbst getestet, da brauche ich dann meinen Test nicht hochzuladen) schreibe ich die Werte so in das Array:

pstring[--pstring_length]='0'+pnumber_to_write%10;
pnumber_to_write/=10;

Also von hinten nach vorne. Wenn die Anzahl der zu schreibenden Zeichen nicht exakt passt, fehlen Zahlen am Ende. Deswegen muss ich die erst berechnen.

SeppJ schrieb:

PS: Mal so aus Neugierde: Ist das überhaupt ein realistisches Anwendungsszenario, an dem du gerade so viel Entwicklungszeit verbringst?

Soll ein API für hochskalierbare Systeme werden, bei denen die Programme CPU-bound sind und halt nicht I/O-bound. Und wir haben keine Lust, da immer wieder dran rumzuhacken, deswegen machen wir das einmal richtig und ändern höchstens was am API, nicht mehr an den Algorithmen.

SeppJ schrieb:

Verschiedene Zahlendarstellungen klingen nicht unbedingt nach einem Thema, bei dem es auf Performance ankäme, erst recht nicht auf solche Mikrooptimierungen, wie du sie hier suchst.

Verzeihung, dass ich mich nicht damit zufriedengebe, ein Problem zu lösen, dass ich auch in einem Dreißigstel der Zeit lösen könnte.

SeppJ schrieb:

PPS: Hast du diese (oder eine sehr ähnliche) Frage hier schon einmal gestellt? Dein Thema und dein Stil kommen mir irgendwie bekannt vor, aber es ist schon ein paar Monate her, glaube ich.

Tatsächlich habe ich das - naja, nicht exakt diese. Damals ging es um das schnelle Schreiben an sich. Dann haben wir in der Zwischenzit einen neuen HTTP-Stack geschrieben, der an Sicherheit (in der Übertragung) seinesgleichen sucht, aber wir wollen ganz sicher gehen und z.B. beim Lesen und Schreiben von Chunklängen kein Einfallstor hinterlassen. Deswegen habe ich dann das API angefasst, und währenddessen sind mir für unsere meisten anderen Anwendungsfälle (Binär und Hexadezimal) schnellere Lösungen eingefallen. Aber keinem von uns sind schnellere Lösungen für dekadische Logarithmen eingefallen.

SeppJ schrieb:

_BitScanReverse, bzw. _BitScanReverse64 bei MSVC.
__builtin_clzl für unsigned long, bzw. __builtin_clzll für unsigned long long beim GCC.

Ja, hatte ich nach 5 Minuten bereits gelesen. Aber dafür mache ich doch nicht extra einen weiteren Post.

SeppJ schrieb:

Musst du eben weitere Präprozessormakros für definieren. Da es dir ja anscheinend auf jede noch so kleine Optimierung ankommt, ist das doch ein sehr kleiner Preis. Das ist doch noch relativ harmlos, was Mikrooptimierungen angeht.

Hm, jetzt hast du mich neugierig gemacht. Welche anderen Mikrooptimierungen kennst du denn noch?

SeppJ schrieb:

ABER: Ist das überhaupt die richtige Lösung? Selbst wenn du den Logarithmus der Basis exakt berechnest (oder in einem Lookuptable nachguckst), so kann das Ergebnis doch um 1 ungenau sein:
1100011 -> MSB ist 7 -> Dezimaldarstellung hat 2 Stellen ("99")
1100100 -> MSB ist 7 -> Dezimaldarstellung hat 3 Stellen ("100")

Genau das ist das Problem, welchem ich begegnet bin, als ich versucht habe, die Anzahl der Stellen anhand des Bitmusters zu ermitteln. Und wie gesagt, bisher vertraue ich da eher meiner "naiven" Lösung.

Was eine Textwand ...

Und ein kleiner Fehler im Programm ist mir noch aufgefallen: in Zeile 122:

last=*(size_t*)(my_cycle_counter_##x.my_ih.my_mem+tmp); \

Sollte die Umwandlung in einen size_t* eigentlich uint64_t* sein.

volkard

SeppJ schrieb:

Kannst du mal ein Testprogramm geben?

Mal ein Entwurf:

#include <stdint.h>
#include <stdlib.h>
#include <stdio.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 printUmdreh(uint64_t n){
	char* out=theOutputBuffer;
	do{
		*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);
}

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

	MEASURE(printUmdreh);
	MEASURE(printAlt);
	MEASURE(printLog);
	MEASURE(printSprintf);

    return 0;
}

|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
function printUmdreh needs 160 ticks
function printAlt needs 187 ticks
function printLog needs 202 ticks
function printSprintf needs 362 ticks

volkard

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 ticks

Hm. 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 ...

Wutz

|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
|1224996691099262975|
function printUmdreh needs 732 ticks
function printAlt needs 1112 ticks
function printLog needs 800 ticks
function _ui64toa needs 564 ticks

Die 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.

volkard

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 ticks
Die 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 ticks

Auch 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 ticks

Aber 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

volkard

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!

volkard

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.

@volkard:

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    0x7ff756a438c

und 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    0x7ff756a438c

Ich 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 (2^60/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_printMax9Digits haben 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.

volkard

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 ticks
Die 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?

Wutz

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 ticks

Die 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/_00aca2abfcfe4fd3b98b53999b60a616

Das 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
	ret

Wen 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

volkard

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 ticks

Ansonsten wüsste ich jetzt auch nicht, was das Problem sein könnte - es ist exakt der gleiche Code wie gepostet.

Länge einer Zahl in einer angegebenen Basis finden

Wert fuer Berechnung: 1224996691099262975

[example_1|0x226724e4ee54c|605222335341900|0x226724e4ee54c|605222335341900|"(Intern start)"]
[example_1|0x226724e4efc98|605222335347864|0x174c|5964|"get_number_length begin"]
[example_1|0x226724e4f0290|605222335349392|0x5f8|1528|"get_number_length end"]
[example_1|0x1d44|7492|"(Overall)"]

[example_2|0x226724e4ef1f4|605222335345140|0x226724e4ef1f4|605222335345140|"(Intern start)"]
[example_2|0x226724e4f02ac|605222335349420|0x10b8|4280|"log2 begin"]
[example_2|0x226724e4f02c4|605222335349444|0x18|24|"log2 end"]
[example_2|0x10d0|4304|"(Overall)"]

[example_3|0x226724e4efc7c|605222335347836|0x226724e4efc7c|605222335347836|"(Intern start)"]
[example_3|0x226724e4f0370|605222335349616|0x6f4|1780|"get_new_length_log2 begin"]
[example_3|0x226724e4f7188|605222335377800|0x6e18|28184|"get_new_length_log2 end"]
[example_3|0x750c|29964|"(Overall)"]

Länge einer Zahl in einer angegebenen Basis finden

Wert fuer Berechnung: 1224996691099262975

[example_1|0x226724e4ee54c|605222335341900|0x226724e4ee54c|605222335341900|"(Intern start)"] [example_1|0x226724e4efc98|605222335347864|0x174c|5964|"get_number_length begin"] [example_1|0x226724e4f0290|605222335349392|0x5f8|1528|"get_number_length end"] [example_1|0x1d44|7492|"(Overall)"]

[example_2|0x226724e4ef1f4|605222335345140|0x226724e4ef1f4|605222335345140|"(Intern start)"] [example_2|0x226724e4f02ac|605222335349420|0x10b8|4280|"log2 begin"] [example_2|0x226724e4f02c4|605222335349444|0x18|24|"log2 end"] [example_2|0x10d0|4304|"(Overall)"]

[example_3|0x226724e4efc7c|605222335347836|0x226724e4efc7c|605222335347836|"(Intern start)"] [example_3|0x226724e4f0370|605222335349616|0x6f4|1780|"get_new_length_log2 begin"] [example_3|0x226724e4f7188|605222335377800|0x6e18|28184|"get_new_length_log2 end"] [example_3|0x750c|29964|"(Overall)"]

[example_1|0x226724e4ee54c|605222335341900|0x226724e4ee54c|605222335341900|"(Intern start)"]
[example_1|0x226724e4efc98|605222335347864|0x174c|5964|"get_number_length begin"]
[example_1|0x226724e4f0290|605222335349392|0x5f8|1528|"get_number_length end"]
[example_1|0x1d44|7492|"(Overall)"]

[example_2|0x226724e4ef1f4|605222335345140|0x226724e4ef1f4|605222335345140|"(Intern start)"]
[example_2|0x226724e4f02ac|605222335349420|0x10b8|4280|"log2 begin"]
[example_2|0x226724e4f02c4|605222335349444|0x18|24|"log2 end"]
[example_2|0x10d0|4304|"(Overall)"]

[example_3|0x226724e4efc7c|605222335347836|0x226724e4efc7c|605222335347836|"(Intern start)"]
[example_3|0x226724e4f0370|605222335349616|0x6f4|1780|"get_new_length_log2 begin"]
[example_3|0x226724e4f7188|605222335377800|0x6e18|28184|"get_new_length_log2 end"]
[example_3|0x750c|29964|"(Overall)"]