Länge einer Zahl in einer angegebenen Basis finden

[volkard]

dachschaden schrieb:

Dazu muss ich die Länge der Zahl in der jeweiligen Basis kennen (sonst habe ich mit dem bisher verwendeten Algorithmus Padding-Probleme, weil ich nur am Ende, nicht am Anfang schreiben kann, und kann auch nicht exakt zu der Zahl passenden Speicher reservieren).

Warum den String nicht nachher umdrehen?

[dachschaden]

@volkard : Weil ich dann am Ende wieder mehr Zeit benötige - bis zu 3000 Ticks, wenn mein Gedächtnis mich nicht trügt (hatte vor einigen Monaten bereits Tests gemacht, den alten Code beim Durchsehen die Woche aber angewiedert weggeworfen). Mit der bisherigen Längenberechnung bin ich bei 220 (kleine Zahl) bis 4700 (61-Bit Zahl) Ticks, mit der Abkürzung für Binär/Hexdezimalzahlen bei 100 (kleine Zahl) bis 250 (61-Bit Zahl) Ticks. Mit memcpy/memmove kann ich dann genausogut snprintf verwenden.

@dot: Danke für den Hinweis. Ja, es handelt sich um die Logarithmusfunktion, da habe ich jetzt gar nicht daran gedacht, weil ich so sehr in Bitmustern gedacht habe.

[volkard]

dachschaden schrieb:

@volkard : Weil ich dann am Ende wieder mehr Zeit benötige - bis zu 3000 Ticks, wenn mein Gedächtnis mich nicht trügt

3000 Ticks für eine Schleife mit 30 Durchläufen, das kann nicht sein. Da haste ja genug Zeit, um ein malloc/free pro Durchlauf zu machen.

[dachschaden]

volkard schrieb:

3000 Ticks für eine Schleife mit 30 Durchläufen, das kann nicht sein. Da haste ja genug Zeit, um ein malloc/free pro Durchlauf zu machen.

Ich kann nachher noch mal den Test machen, aber das war damals die Zahl, die stehen geblieben ist.

@dot: Besser als in meinen kühnsten Träumen.

const size_t rvalue=0x1100100010001fffULL,radix=10;
printf("%llu\n",(size_t)(log10(rvalue)/log10(radix))+1);

Benötigt auch nur 24 - 160 Ticks, das ist generell schneller als mein Code.
Danke dir.

[dot]

Kannst auch mal probieren, mit dem ln oder ld (log zur Basis 2) zu arbeiten, ka welcher am schnellsten sein wird. Mit dem ld könnte es genügen, das höchstwertige Bit zu bestimmen, wofür es auf vielen CPUs eigene Instructions und entsprechende Compilerintrinsics gibt (http://en.wikipedia.org/wiki/Find_first_set) und du die int-float-Conversions loswerden könntest...

[dachschaden]

Hm, ich habe gerade noch mal einen Test gemacht. Scheinbar hat der Compilter nur optimiert.

Nachdem ich den Call in eine eigene Funktion gepackt habe, die der Compiler nicht mehr optimieren konnte, benötigte er auf einmal -lm als Flag (Mathematik-Lib einlinken). Und plötzlich benötigt das Program 43800 Ticks im jeweiligen Abschnitt.

Ich glaube, ich bleibe erst einmal bei meinem Code.

[dachschaden]

dot schrieb:

Kannst auch mal probieren, mit dem ln oder ld (log zur Basis 2) zu arbeiten, ka welcher am schnellsten sein wird. Mit dem ld könnte es genügen, das höchstwertige Bit zu bestimmen, wofür es auf vielen CPUs eigene Instructions und entsprechende Compilerintrinsics gibt (http://en.wikipedia.org/wiki/Find_first_set) und du die int-float-Conversions loswerden könntest...

log2 ist ein wenig schneller (30000 Ticks), aber immer noch vollkommen übertrieben. Und da dachte ich heute mal, dass die Leute von der Standardbibliothek mich doch mal geschlagen haben ...
Natürlicher Logarithmus dauert 32000 Ticks.

Und mit Inlineassembler möchte ich erst einmal nichts zu tun haben - ich sehe es bereits als Schande an, dass ich den verwenden musste, um mir schnell die Ticks holen zu können.

[dot]

dachschaden schrieb:

Und mit Inlineassembler möchte ich erst einmal nichts zu tun haben [...]

Sollst du ja auch nicht, Stichwort Intrinsic. Unter GCC z.B. __builtin_clz()

[dachschaden]

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.

Oder anders: Ich werde es mir später anschauen, aber ich will mir jetzt nicht wieder zusätzliche Baustellen schaffen.

[dachschaden]

Außerdem hat es für den von dir beschriebenen Weg keine 64-Bit-Versionen, zumindest nicht für den GCC. Meh. Aber dennoch vielen Dank für den Hinweis - selbst, wenn es mich dem Ziel nicht näher bringt, lerne ich dennoch was.

Also, Frage vom ersten Post besteht weiterhin.

[SeppJ]

Kannst du mal ein Testprogramm geben? Ich habe selber ein bisschen rumgespielt und überrascht festgestellt, dass die Umdrehmethode von volkard tatsächlich langsamer ist, selbst als der Logarithmus aus der lm (Von ~100ns mit Logarithmus auf ~140 ns mit Umdrehen, bei kleinen Zahlen.) Das heißt, man könnte wohl wirklich was machen, wenn man diesen Teil optimiert. Aber ich habe keine Ahnung, wie deine Anforderungen sind (ich habe einmal mit nutzergegebenen, festen Arrays gearbeitet und einmal mit dynamischen. Hat zwar keinen Unterschied gemacht, aber wäre trotzdem gut zu wissen, was gewollt ist) oder wie genau du deine Ticks misst oder was ein Tick bei dir ist. Oder wie du überhaupt deine Umrechnungen vornimmst. Ich habe bloß die ganz naive Methode mit Schleife, Modulo und Division genommen, ohne Mikrooptimierungen.

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

[dachschaden]

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

[dachschaden]

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

[dachschaden]

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.

[dachschaden]

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.