heap zu langsam

Janjan

Und warum dauert es länger? Weil der Speicher erst vom Betriebssystem beantragt werden muss...

Bei der Variante 2 wird lediglich intern der Stackpointer verschoben - also Speicher auf dem Stack reserviert, welcher bereits zu deinem Programm gehört.

möglicherweise ist es schon zu spät und ich bin nicht mehr so aufnahmefähig, aber das reservieren des speichers wird beim messen der benötigten zeit überhaupt nicht erfasst. der speicher wird schon VORHER reserviert. nur der zugriff darauf in der letzten schleife wird gemessen.

volkard

Was gibt denn

for(int o=0;o<100;++o){
    for (uint32 i = 0; i < tableSize; ++i) {
        buffer[table[i]] = 255;
    }
}

für Zeiten?

Hintergrund: new muß nicht unbedingt den Speicher wirklich besorgen. Es könnte sein, daß nur virtueller Speicher reserviert wird, der beim ersten Zugriff erst durch physikalischen Speicher gedeckt wird. Das wirkt dann, als würde das erste Schreiben lahm sein, dabei wurden nur 20ms, die eigentlich new zu zahlen hätte, nach hinten verschoben.

Athar

In deinem Beispiel liegt es daran, dass die Schleife nie ausgeführt wird. Der Compiler sieht, dass buffer am Ende wieder gelöscht wird ohne dass der Inhalt je genutzt wird. Also kann er den gesamten Code wegoptimieren. Lass mal am Ende z.B. buffer[0] ausgeben und das ändert sich.

new[] und delete[] darf ein Compiler dagegen nicht einfach wegoptimieren (leider). Du könntest ja ein eigenes new[] geschrieben haben, dass sich den angeforderten Speicherbereich merkt oder ähnliches. Ein fehlender Aufruf von malloc (o.ä.) wäre ebenfalls eine Veränderung des Programmverhaltens, darf der Compiler also nicht.

volkard

Athar schrieb:

new[] und delete[] darf ein Compiler dagegen nicht einfach wegoptimieren (leider).

Der MSVC tut's aber mindestens seit Version 6.1. Das hat mich bei einer Messung mal ganz schön durcheinander gebracht. Seitdem gebe ich immer neben der Meßzeit auch Berechnungsergebnisse auf den Bildschirm aus.

Athar

volkard schrieb:

Der MSVC tut's aber mindestens seit Version 6.1. Das hat mich bei einer Messung mal ganz schön durcheinander gebracht. Seitdem gebe ich immer neben der Meßzeit auch Berechnungsergebnisse auf den Bildschirm aus.

Das ist eine feine Sache, ich hoffe dass man das beim GCC als optionale Optimierungsmöglichkeit auch noch einbaut. Ich denke, dass besonders beim Hantieren mit std::string (z.B. str + str2 + ...) ein großes Optimierungspotential besteht, wenn der Compiler new[]/delete[]-Paare wegoptimieren darf.

@Athar: danke, daran lag es... darauf muß man erstmal kommen ^^

ich gehe jetzt schlafen, scheinbar habe ich es nötig

volkard

Athar schrieb:

volkard schrieb:

Der MSVC tut's aber mindestens seit Version 6.1. Das hat mich bei einer Messung mal ganz schön durcheinander gebracht. Seitdem gebe ich immer neben der Meßzeit auch Berechnungsergebnisse auf den Bildschirm aus.

Das ist eine feine Sache, ich hoffe dass man das beim GCC als optionale Optimierungsmöglichkeit auch noch einbaut. Ich denke, dass besonders beim Hantieren mit std::string (z.B. str + str2 + ...) ein großes Optimierungspotential besteht, wenn der Compiler new[]/delete[]-Paare wegoptimieren darf.

Uih, das wäre ein Ding!
Nee, MSVC schaffts nur, wenn new/delete nicht überladen ist und der Code offensichtlich wirkungslos bleibt wie hier beim Stack.

str+str2+...
sollte eigentlich normal gelöst werden mit Expression-Templates, vermute ich.

In meinem Beispiel war lustigerweise die Heap Variante etwas schneller (3 Messungen pro Variante)

#include <fstream>
#include <iostream>
#include <windows.h>
#include <cstddef>

const unsigned int size = 1<<10;

int main()
{
	unsigned int arr[size];                        // STACK: 20406/20500/20453 => 20453ms
	//unsigned int * arr = new unsigned int[size]; // HEAP : 20344/20312/20266 => 20307ms

    //init
	for(unsigned int i = 0; i != size; ++i)
		arr[i] = rand();

	unsigned int StartTime = GetTickCount();

	for(unsigned int a = 0; a != size; ++a)
		for(unsigned int j = 0; j != size; ++j)
			for(unsigned int i = 0; i != size; ++i)
			{
				arr[i] = arr[j] | arr[a] ^ arr[i] & arr[j] ^ arr[a] & arr[i];
				arr[a] = arr[a] | arr[i] ^ arr[j] & arr[i] | arr[j] ^ arr[a];
				arr[j] = arr[i] | arr[j] ^ arr[a] & arr[a] & arr[i] | arr[j];
				arr[i] = arr[j] | arr[a] ^ arr[i] & arr[j] ^ arr[a] | arr[i];
				arr[a] = arr[a] | arr[i] ^ arr[j] & arr[i] ^ arr[j] ^ arr[a];
				arr[j] = arr[i] | arr[j] ^ arr[a] & arr[a] & arr[i] | arr[j];
				arr[j] = arr[j] ^ arr[a] ^ arr[i] & arr[j] ^ arr[a] | arr[i];
				arr[i] = arr[a] & arr[i] ^ arr[j] & arr[i] ^ arr[j] ^ arr[a];
				arr[a] = arr[i] | arr[j] | arr[a] ^ arr[a] & arr[i] | arr[j];
			}

	unsigned int EndTime = GetTickCount() - StartTime;
	std::cout<<EndTime;
	std::ofstream Str("DoNotOptimize");
	for(unsigned int i = 0; i != size; ++i)
		Str<<arr[i];
	//delete [] arr;
}

asdfasd schrieb:

In meinem Beispiel war lustigerweise die Heap Variante etwas schneller (3 Messungen pro Variante)
[/cpp]

Immer mit dem gleichen seed ?

Temporäre Daten sollten aufgrund der besseren Performance auf den Stack,
das ist im Gesamtzusammenhang einfach das schnellste.

Es ist vergleichsweise schwierig den Unterschied Stack vs. Heap,
insbesondere bei größeren Datenmengen isoliert zu betrachten.
Gößere Datenmengen führen auch auf dem Stack erstmal zu Reallocationen.
Das kann isoliert betrachtet genauso viel Zeit kosten wie beim Heap.

Wenn die Datenmengen nicht feststehen,
kann man dennoch dynamisch auf dem Stack allozieieren:
z.B. (win+linux):

void *alloca(size_t size);

std::tr1:array (habe ich selbst gerade erst gelernt ...)

Gruß Frank

volkard

Frank Erdorf schrieb:

Temporäre Daten sollten aufgrund der besseren Performance auf den Stack, das ist im Gesamtzusammenhang einfach das schnellste.

Große Daten gehören nicht auf den Stack, der (noch) auf 1 oder 2 M beschränkt ist.

weerwe fgsfdg schrieb:

asdfasd schrieb:

In meinem Beispiel war lustigerweise die Heap Variante etwas schneller (3 Messungen pro Variante)
[/cpp]

Immer mit dem gleichen seed ?

Miss doch mal nach mit einem konstanten Seed. Würde mich mal interessieren was bei euch so da rauskommt.

knivil

Aussagen im 20ms Bereich sind eh fuer die Katz.

knivil schrieb:

Aussagen im 20ms Bereich sind eh fuer die Katz.

Nicht generell, wenn du z.B. 60 Fps willst, hast du ~17ms pro frame für deine berechnungen...

brotbernd

Dann sollte man die Zeit für 60 Berechnungen messen. Ich denke das meint er.
Bei so kurzen Zeiten ist das Rauschen aufgrund von diversen Einflüssen von aussen einfach zu stark.

knivil

Genau. Kommt mal kurz der Scheduler ..