heap zu langsam

unskilled

wie auch athar schon sagte, sollte es nur unterschiede bei der geschwindigkeiten im beschaffen des speichers geben - der rest sollte haargenau gleichschnell sein

evtl versuchst du mal ein compilerbares-minimal-bsp zu posten, was das stück enthält und wo die eine variante trotzdem viel langsamer ist als die andere.

das das ganze aber schneller sein _kann_, wenn du den wert als konstante irgendwo hast, sollte klar sein.

also beim new-test mal auch mit der konstante arbeiten. evtl. kann der compiler da irgendwelche schleifen optimieren oder was auch immer

bb

der speicher wird nur einmal beim programmstart reserviert und bleibt dann so wie er ist. und die größe des buffers ist eigentlich ein systemweiter programmparameter und ist deswegen zur kompilezeit umbekannt.

ein kompilierbares beispiel dürfte schwierig werden, aber ich schau mal, was ich machen kann. es hängen ein haufen klassen da mit drann und eine 60mb große lookup-tabelle die zur laufzeit eingelsene wird (die 16 millionen werte und so). eventuell kann ich eine ähnlich situation simulieren...

hier ist mal ein beispiel:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <sys/time.h> // NUR LINUX

typedef __u_char byte;
typedef __uint32_t uint32;
typedef __uint64_t uint64;

uint64 currentMilliSeconds() {
	timeval t;

	gettimeofday(&t, NULL); // NUR LINUX
	return ((uint64)t.tv_sec) * 1000ull + (t.tv_usec / 1000ull);
}

int main(int argc, char* argv[]) {
	const uint32 tableSize = 16234314;
	const uint32 bufferSize = 30240;
	std::vector<uint32> table(tableSize);

//	byte* buffer = new byte[bufferSize]; // Variante #1
	byte buffer[bufferSize];             // Variante #2

	srand(time(NULL));

	for (int i = 0; i < table.size(); ++i) {
		table[i] = rand() % bufferSize;
	}

	uint64 start = currentMilliSeconds();

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

	std::cout << (currentMilliSeconds() - start) << std::endl;

	return 0;
}

variante #1 benötig knapp 30 ms bei mir.
variante #2 nahezu 0 ms.

ANMERKUNG: der include <sys/time.h> und die daraus stammende methode gettimeofday existiert glaube ich nur unter linux. ich hab leider keiner ahnung, wie man unter windows die zeit in millisekunden messen kann.

kann ich den schreibzugriff auf den dynamisch erzeugten speicher irgendwie beschleunigen?

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