Gibt es ein memset() Template?

SeppJ

Meinst du std::fill?

edit: Zu spät.

Der Unterschied zwischen fill und uninitialized_fill ist der, dass fill erwartet, dass dort schon ein Objekt liegt, während uninitialized_fill das Objekt vor Ort konstruiert. Nutze was immer in deinem Fall angebracht ist.

Und dieses Setzen von Konstanten Werten ist der Teil deines Programms, der die Performance negativ beeinflusst?

Falls ja, dann hast du ein Problem, weil schneller als die Transferrate des Arbeitsspeichers wirst du eh nicht. Und das sollte memset schon ausschöpfen.

Falls nein, - und da gehe ich jetzt mal von aus - Premature Optimization ist keine gute Idee.

Tomahawk

ProgChild schrieb:

Und dieses Setzen von Konstanten Werten ist der Teil deines Programms, der die Performance negativ beeinflusst?

Falls ja, dann hast du ein Problem, weil schneller als die Transferrate des Arbeitsspeichers wirst du eh nicht. Und das sollte memset schon ausschöpfen.

Falls nein, - und da gehe ich jetzt mal von aus - Premature Optimization ist keine gute Idee.

Du hast schon recht!
Meine Engine braucht braucht zu lange zum Starten, so dass es eine Verzögerung gibt, bevor der Benutzer arbeiten kann. Und das liegt an der Berechnung von KPK-Bitbases (Schach) und der Initialisierung von Hashspeichern und LUTs.

Ist ausserdem "nur" Feinschliff.

Tomahawk schrieb:

Du hast schon recht!
Meine Engine braucht braucht zu lange zum Starten, so dass es eine Verzögerung gibt, bevor der Benutzer arbeiten kann. Und das liegt an der Berechnung von KPK-Bitbases (Schach) und der Initialisierung von Hashspeichern und LUTs.

Ist ausserdem "nur" Feinschliff.

Und ein Profiler hat die jetzt memset als teuerste Funktion angezeigt? Kommt mir ein wenig seltsam vor, wenn du memset nur einmal für die Initialisierung verwendest. Bei heutigem Arbeitsspeicher kannst du mehr als ein GByte pro Sekunde schreiben.

Bashar

Ach, das soll dasselbe sein wie memset, nur dass der zu schreibende Wert eine Compilezeitkonstante ist? Ich hatte das wohl falsch verstanden.

Es gibt in manchen Umgebungen Funktionen wie bzero (BSD-Welt) oder ZeroMemory (Windows-Welt), die dasselbe wie memset(p, 0, n) machen. Aber ob das wirklich schneller als reines memset ist? Erstens hätte man es dann doch in die Standardlibrary aufgenommen (memzero z.B.), zweitens ist memset für gute Compiler eine intrinsische Funktion, d.h. sie generieren dafür spezielle Codemuster, statt einen Aufruf zu einer Libraryfunktion. Damit sollte memset in den meisten(oder immer?) Fällen schon optimalen Code liefern.

hustbaer

ProgChild schrieb:

weil schneller als die Transferrate des Arbeitsspeichers wirst du eh nicht. Und das sollte memset schon ausschöpfen.

Sollte ja, ist aber nicht immer so
MSVC + "use intrinsics = yes" => rep stosb => auf vielen CPUs relativ langsam

volkard

hustbaer schrieb:

ProgChild schrieb:

weil schneller als die Transferrate des Arbeitsspeichers wirst du eh nicht. Und das sollte memset schon ausschöpfen.

Sollte ja, ist aber nicht immer so
MSVC + "use intrinsics = yes" => rep stosb => auf vielen CPUs relativ langsam

Nimnmt er auch rep, wenn die Größe zur Compilezeit unbekannt ist?

hustbaer

volkard schrieb:

hustbaer schrieb:

ProgChild schrieb:

weil schneller als die Transferrate des Arbeitsspeichers wirst du eh nicht. Und das sollte memset schon ausschöpfen.

Sollte ja, ist aber nicht immer so
MSVC + "use intrinsics = yes" => rep stosb => auf vielen CPUs relativ langsam

Nimnmt er auch rep, wenn die Größe zur Compilezeit unbekannt ist?

Ich glaube ja, müsste ich aber nochmal ausprobieren.

Ich glaube sogar, dass er nichtmal bei sehr grossen konstanten Werten (wo die Setup-Kosten gering im Vergleich zu den Gesamt-Kosten sind) schlau genug war, die Funktionen aufzurufen. Obwohl die bei grossen Werten um ein vielfaches schneller sind als die intrinsics.

Ich weiss nur noch sicher, dass ich extra ein #pragma function(memset, memcpy) in ein paar Source-Files reinmachen musste, damit er bei meinen Software-Blitting/Fill Funktionen nicht rep stosb bzw. rep movsb aus memset() bzw. memcpy() macht. Und da dabei die Grösse immer variabel war...

Walli

ProgChild schrieb:

Falls nein, - und da gehe ich jetzt mal von aus - Premature Optimization ist keine gute Idee.

Und wieso nicht? Wenn ich weiß, wie ich effizient Speicherbereiche initialisiere, dann gewöhne ich mir das so an, egal ob es in dem konkreten Fall hier was bringt oder nicht. So lange es nicht umständlicher zu schreiben/lesen ist als was anderes, sehe ich hier kein Problem mit 'premature optimization'. Die ist nämlich nur die 'root of all evil', wenn man unnötigerweise Optimierungen einbaut, die nachher die Erweiterbarkeit und Lesbarkeit des Codes beeinflussen. Aber wenn ich z.B. einmal weiß, dass std::fill doppelt so schnell ist wie eine Schleife (stimmt i.d.R. nicht, nur als Beispiel), dann nehme ich das doch.

Walli schrieb:

Und wieso nicht?

In diesem konkreten Fall, auf den ich mich hier beziehe, ist es keine gute Idee. Bevor ist memset schneller kriege, muss ich so viele plattform-spezifische Details berücksichtigen, dass ich mir sicher sein sollte, dass das wirklich mein Flaschenhals ist.

Mehr sage ich nicht.

Bashar

Das ist mal wieder Theorie vs. Praxis Was hindert den VC++ eigentlich, auch bei intrinsics dword-weise (oder was gerade optimal ist) zu arbeiten?

hustbaer

Bashar schrieb:

Das ist mal wieder Theorie vs. Praxis Was hindert den VC++ eigentlich, auch bei intrinsics dword-weise (oder was gerade optimal ist) zu arbeiten?

Oops
Erstmal die Antwort: nichts hindert ihn, nur VC6 hat es IIRC nicht gemacht.

Ich hätte vermutlich gleich dazuschreiben sollen dass ich das damals mit dem nunmehr sehr betagten VC6 getestet hatte

Gerade eben nochmal mit VC9 getestet, etwas ausführlicher, und VC9 ist viel viel schlauer

* mit #pragma function(memset) macht VC9 wie auch VC6 brav nen Funktionsaufruf

* mit #pragma intrinsic(memset) :
... bei kleinen konstanten Werten wird ein Haufen mov draus (KEIN rep -Dreck mehr!)
... bei grossen konstanten Werten wird trotzdem die Funktion memset aufgerufen
... bei variablen Werten wird *immer* die Funktion memset aufgerufen (auch wenn die variablen Werte immer klein sind und man mit PGO compiliert)

Wobei der VC9 Optimizer auch schlau genug ist, die Intrinsic-Variante zu erzeugen, wenn eine Variable durch Inlining zu einem konstanten Ausdruch wird.

Noch ein paar Details:
* die Grenze scheint bei 10x mov zu liegen. 38 Byte => 9x mov DWORD + 1x mov WORD , 39 Byte => memset, 40 Byte => 10x mov DWORD , 41 Byte => memset
* genau das selbe Verhalten ist beim Initialisieren von Stack-Arrays zu beobachten, nur dass beim Initialisieren von Stack-Arrays das #pragma intrinsic/function keine Rolle zu spielen scheint (d.h. Schwellenwert ist immer 10x mov)

p.S.: bei variablen Werten auch mit intrinsic "optimal" zu arbeiten ist glaube ich schwierig, weil der Code den man dafür brauch (die ganzen Fallunterscheidungen) schnell recht gross wird.

volkard

Jetzt ist die Welt wieder in Ordnung.
Und std::fill mit 0 wandelt er hoffentlich auch in memset um?
Weil das wäre sehr schön, da nicht mehr an Mikrooptimierung denken zu müssen.

hustbaer

jain

std::fill für char/signed char/unsigned char = memset
(keine compiler magic, sondern spezialisierung von _Fill in der std.lib)

std::fill für short/int/... mit kleiner konstanter grösse = unrolled loop als DWORD movs soweit möglich (unabhängig von der variablen-grösse, also auch 8x DWORD mov für 16 shorts)
hier scheinen andere regeln zu gelten wie für intrinsic memset, z.b. macht er da auch bis zu 16x mov vs. nur bis max. 10x mov bei memset. auch greift hier das #pragma function nicht (was ja auch vollkommen OK ist).

std::fill für short/int/... mit grosser konstanter grösse = rep stos (bäh)

std::fill für short/int/... mit variabler grösse = einfacher loop (aber inlined)

p.S.: ob std::fill mit wert == 0 oder wert != 0 aufgerufen wird hat bei meinen versuchen keinen unterschied gemacht. z.B. std::fill für short wird entweder zu nem haufen DWORD movs oder zu nem rep stosw oder zu nem normalen movw loop. ganz egal ob wert == 0 oder wert == 1 oder wert == 0x0101.

p.p.S.: alles in allem würde ich sagen, dass man wohl trotzdem auf mikro-optimierungen verzichten kann. der code ist zwar nicht in jedem fall optimal, aber IMO gut genug für fast alle anwendungen.

p.p.p.S.: würde mich interessieren was GCC 4.x aus memset/std::fill macht

volkard

Vielen Dank.

Ich habe versucht, den relevaten Code zu finden und zu pasten. Hoffentlich habe ich getroffen.

std::fill für short/int/... mit grosser konstanter grösse = rep stos (bäh)

int main()
{
	int arr[4096];
	cout<<arr[5]<<'\n';
	fill(arr,arr+4096,0);
	cout<<arr[5]<<'\n';
}

Die cout sind nur, um den Nutzcode zu finden. Fast. Ohne das zweite wird alles wegoptimiert.

pxor	%xmm0, %xmm0
	leal	16(%esp), %eax
	leal	16400(%esp), %edx
	.p2align 4,,7
L3:
	movaps	%xmm0, (%eax)
	addl	$16, %eax
	cmpl	%edx, %eax
	jne	L3

Der scheint da mit mmx zu spielen. Ich glaube, das ist gut.

int main()
{
	int arr[4096];
	int i;
	cin>>i;
	cout<<arr[5]<<'\n';
	fill(arr,arr+i,0);
	cout<<arr[5]<<'\n';
}

wird zu

pxor	%xmm0, %xmm0
	xorl	%eax, %eax
	.p2align 4,,7
L5:
	movl	%eax, %edx
	incl	%eax
	sall	$4, %edx
	cmpl	%esi, %eax
	movaps	%xmm0, (%ecx,%edx)
	jb	L5

struct Foo{
	virtual ~Foo(){
	}
};

int main()
{
	cout<<5<<'\n';
	Foo arr[4096];
	cout<<5<<'\n';
	cout<<&arr<<'\n';
}

wird zu

movl	%ebx, %eax
	.p2align 4,,7
L8:
	movl	$__ZTV3Foo+8, (%eax)
	movl	$__ZTV3Foo+8, 4(%eax)
	movl	$__ZTV3Foo+8, 8(%eax)
	movl	$__ZTV3Foo+8, 12(%eax)
	addl	$16, %eax
	cmpl	%esi, %eax
	jne	L8

Vierfaches unwinding.

struct Foo{
	int bar;
	Foo(){
		bar=3;
	}
	virtual ~Foo(){
	}
};

int main()
{
	cout<<5<<'\n';
	Foo arr[4096];
	cout<<5<<'\n';
	cout<<&arr<<'\n';
}

wird zu

movl	%ebx, %eax
	.p2align 4,,7
L8:
	movl	$__ZTV3Foo+8, (%eax)
	movl	$3, 4(%eax)
	addl	$8, %eax
	cmpl	%esi, %eax
	jne	L8

Und jetzt char[variabel]:

int main()
{
	char arr[4096];
	int i;
	cin>>i;
	cout<<arr[5]<<'\n';
	fill(arr,arr+i,0);
	cout<<arr[5]<<'\n';
}

wird zu

pxor	%xmm0, %xmm0
	xorl	%eax, %eax
	.p2align 4,,7
L5:
	movl	%eax, %edx
	incl	%eax
	sall	$4, %edx
	cmpl	%eax, %edi
	movaps	%xmm0, (%ecx,%edx)
	ja	L5
	addl	24(%esp), %ecx
	movl	24(%esp), %edx
	cmpl	%edx, 28(%esp)
	je	L6
	.p2align 4,,7
L9:
	movb	$0, (%ecx)
	incl	%ecx
	cmpl	%ecx, %esi
	jne	L9
L6:

Mir scheint, es gibt GCC-Leute, die daran viel Spaß haben und Sachen machen, die normalerweise kein Arbeitgeber bezahllen würde.

Ups, memset vergessen hab.

int main()
{
	char arr[4096];
	int i;
	cin>>i;
	memset(arr,0,i);
	cout<<arr[5]<<'\n';
}

wird zu

call	_memset

int main()
{
	char arr[4096];
	memset(arr,0,4096);
	cout<<arr[5]<<'\n';
}

wird zu

call	_memset

memset(arr,0,8);

wird zu

movl	$0, 23(%esp)
	movl	$0, 27(%esp)
	movb	$0, 31(%esp)
	movl	$1, 8(%esp)

memset(arr,0,32);

wird zu

movl	%edx, %ecx
	xorl	%eax, %eax
	shrl	$2, %ecx
	testb	$2, %dl
	rep stosl
	je	L5
	movw	$0, (%edi)
	addl	$2, %edi
L5:
	andl	$1, %edx
	je	L6
	movb	$0, (%edi)
L6:

Oh. Er entscheiden anhand der Größe, welcher Inline-Code reingeknallt werden soll. Hier sieht man, daß er gar nicht bemerkt hat, daß am Ende das movw und movb nicht nötig gewesen wären. Ab 2049 ints nimmt er call memset.

Mir scheint, memset zu nehmen ist kontraproduktiv! Der memset-Speicher wird nur noch als Byte-Speicher gesehen. Durch memset verliert er Alignment-Informationen und die Größenteilbarekeit auch. Verliert mmx.

hustbaer

memset(arr,i,0)

memset(ptr, value, size), nicht umgekehrt

BTW: ich verwende gerne derartige hilfsfunktionen um bestimmte optimierungen zu verhindern:
(und gleichzeitig bestimmte stellen zu markieren)

void __declspec(noinline) observe(void* ptr)
{
    char dummy[123] = {};
    void** pp = reinterpret_cast<void**>(&dummy[0]);
    pp[1] = ptr; // dank der führenden nullen in dummy erzeugt das OutputDebugStringA unten keine ausgabe
    ::OutputDebugStringA(dummy); // jetzt muss der compiler annehmen dass es einen alias für "ptr" gibt
}

Alternativ könnte man das vermutlich auch so schreiben:

volatile void* volatile g_ovservable_dummy = 0;

void __declspec(noinline) observe(void* ptr)
{
    g_ovservable_dummy = ptr;
    g_ovservable_dummy = 0;
}

Walli

ProgChild schrieb:

Walli schrieb:

Und wieso nicht?

In diesem konkreten Fall, auf den ich mich hier beziehe, ist es keine gute Idee. Bevor ist memset schneller kriege, muss ich so viele plattform-spezifische Details berücksichtigen, dass ich mir sicher sein sollte, dass das wirklich mein Flaschenhals ist.

Es geht mir doch gerade in keiner Weise drum ob es ein Flaschenhals ist. Aber, wenn man den 'premature optimization'-Spruch bringt, dann doch am besten in Situationen, wo er angebracht ist. Also wenn jemand 200 statt 2 Zeilen schreibt um 3 Takte unnötigerweise (da kein Flaschenhals) zu sparen. Ob std::fill, memset oder Schleife ist von der Komplexität her für jemanden, der den Code noch einmal anpacken muss, letztlich egal. Von daher nehme ich doch das, was schöner ist und ggf. sogar vielleicht netterweise auf vielen Plattformen einen Tacken schneller. Sicher wird er mit diesen 'Optimierungen' keinen Blumentopf gewinnen, aber er wird sich auch nicht großartig damit den Code verhunzen. Außerdem sagte er doch nachher selber, dass es sich hier um 'Feinschliff' handelt.

Walli schrieb:

Von daher nehme ich doch das, was schöner ist und ggf. sogar vielleicht netterweise auf vielen Plattformen einen Tacken schneller. Sicher wird er mit diesen 'Optimierungen' keinen Blumentopf gewinnen, aber er wird sich auch nicht großartig damit den Code verhunzen. Außerdem sagte er doch nachher selber, dass es sich hier um 'Feinschliff' handelt.

Wenn er nur ein ein memset durch ein fill ersetzt, dann würde ich dir zustimmen. Aber wer sagt denn, dass das die Lösung ist? Ihm ist sein Programm zu langsam und wenn die Initialisierung des Speichers wirklich der Flaschenhals ist, kann man sich durchaus ein paar Techniken überlegen, die ein paar Zeilen Code mehr verursachen.