heap zu langsam

ich habe folgendes problem. vereinfacht ausgedrück habe ich eine liste mit ca. 16 millionen int-werten, durch die iteriert wird. die enthaltenen int-werte stellen indizes eines arrays (buffer) dar, welches eine länge von 30240 hat. alle 16 millionen int-werte haben also einen wert zwischen 0 und 30239;

dieses array (buffer) ist nun der knackpunkt. während der iteration erfolgen 16 millionen schreibzugriffe darauf. dies dauert je nach art der erstellung unterschiedlich lange:

wird das array dynamisch reserviert (also auf dem heap), dauert der vorgang ca 50ms:

byte* buffer = new byte[30240]; // byte ist eine typedef von "unsigned char"

wenn ich das array jetzt aber wie folgt erstelle (stack), dauert das ganze nur 20ms:

byte buffer[30240];

die zweite variante, lässt sich allerdings nur anwenden, wenn die länge der buffers (30240) global konstant ist. leider ist er das nicht, so das eine dynamische speicherreservierung zwingend nötig ist.

warum ist dynaamisch reserierter speicher so merklich langsamer?

hier noch ein paar infos über die laufzeitumgebung:
Linux (amd64-architektur)
amd phenom ii x4
8 gb ram
compiler gcc 4.4 (kompiliert als "release", keine debug-symbole)

ich hoffe das ist einigermaßen verständlich. wer nich mehr infos braucht, einfach schreien

Athar

Sollte eigentlich nicht der Fall sein, sofern du das dynamisch erzeugte Array nicht ständig löschst und wieder neu erstellst. Das kostet schon Zeit, während das auf dem Stack nicht der Fall ist.

Janjan

nezhaa schrieb:

warum ist dynaamisch reserierter speicher so merklich langsamer

Weil du das Betriebssystem nach diesen Speicher fragst. Das Betriebssystem muss erst einmal schauen, wo der Speicher frei ist, muss speichern das dieser jetzt belegt ist und dir noch die Adresse zurück geben.

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.