Custom Allocator fuer std::vector

Hallo,

in meinem Program benutze ich nur std::vectoren mit einfachen Datentypen wie folgt:

std::vector<unsigned int>vec(COUNT);

Die Vectoren koennen sehr gross werden. Dann dauert das allokieren manchmal sehr lange. Jetzt habe ich mir ueberlegt einen Custom Allocator zu schreiben, der mir immer 8 Byte speicher reserviert also einen 64 Bit Datentyp benutzt. Das muesste die Anzahl von Aufrufen von "new" ja halbieren und die Sache schneller machen.

std::vector<unsigned int,MyAlloc<unsigned long long>> v(COUNT);

Ist das sinnvoll oder hat es keinen Vorteil? Oder geht das ueberhaupt nicht?

cooky451

Ehm, wenige große vectoren = wenige Allokationen, also das wird dann wohl eher nicht dein Problem sein. Der allokiert doch nicht jedes byte einzeln, lol.

ChefDerDeutschenBank schrieb:

Dann dauert das allokieren manchmal sehr lange.

Woher weisst du das?
Was heisst sehr lange?

volkard

ChefDerDeutschenBank schrieb:

Die Vectoren koennen sehr gross werden. Dann dauert das allokieren manchmal sehr lange.

Momentchen, was heißt "lange"?

Also zunächst mal muss klar sein, daß der vector geometrisch wächst, mithin die Allokationsaufrufe logarithmisch und sogar die Kopierungen nur amortisiert linear sind. Also er wächst zum Beispiel immer die Größe verdoppelnd.
1 2 4 8 16 32…1024576
Dabei macht er NUR 20 Verdopplungen!
Kopierungen:
1+2+4+8+16+32+524288 = 1024575, genau eins weniger als die nächste Zweierpotenz.

Der vector ist für Dich perfekt. Als ChefDerDeutschenBank nehme ich an, es geht Dir darum, auf Großrechnern die Kundenwertpapierdepots durcheinanderzuwirbeln. Da ist vector perfekt, so, wie er ist.

ChefDerDeutschenBank schrieb:

manchmal sehr lange.

Oder ist das "Ruckeln" gemeint? Klar, wenn er von 1073741824 auf 2147483648 wächst, dann steht die Anwendung für ein Sekündchen. Allein das liegt am Kopieren und hat nüscht mit dem Allokator zu thun. Kannst Dir einen kopierarmen vector basteln mit VirtualAlloc/mmap und einfach mal 16G Adressraum reservieren, ihn bei Bedarf aber erst dem Ram zuordnen.

ChefDerDeutschenBank schrieb:

Jetzt habe ich mir ueberlegt einen Custom Allocator zu schreiben, der mir immer 8 Byte speicher reserviert also einen 64 Bit Datentyp benutzt. Das muesste die Anzahl von Aufrufen von "new" ja halbieren und die Sache schneller machen.

Nein, vector thäte bei 2^30 ints nur 30-mal new machen, Deine Annahme des vectors aber mehr als tausend mal tausend mal.

Will man das Ruckeln auch weghaben, was Dich als ChefDerDeutschenBank w*****einlich nicht betrifft, kann man auch verkettete Listen nehmen. Pro neuem Objekt ein new. Sagen wir mal 50 Takte pro new, schnell 50-mal so lahm wie der vector.
Und das kann man beheben, indem man lauter kleiune Mini-vectoren, von sagen wir mal 8k Größe als Liste verkettet (oder in einem Master-Array/Baum/egal), macht dann pro 2000 ints nur einmal new UND ruckelt nicht. Ist aber wieder über die gesamte Laufzeit ein wenig lahmer als vector. So ein Container ist auch eingebaut, er heißt std::deque.

Du brauchst keinen custom allocator.

volkard schrieb:

w*****einlich

wahrscheinlich
warscheinlich
arsch

Wenn ich einen Vector erstelle weiss ich immer schon genau wie viele Elemente drin sein werden. Die Groesse veraendert sich auch bis zum Programmende nicht. Es wird also kein push_back (und es werden keine Elemente geloescht). Die Daten kommen aus einer Datei, und die groesse weiss ich wenn ich die Datei lese.

std::vector<unsigned int>vec(COUNT);

knivil

Wie gross ist der benoetigte Speicher und was bedeutet lang (in Sekunden bitte)? Mit welcher Frequenz benoetigst du diesen Speicher? Wie gross ist COUNT?

Die Daten kommen aus einer Datei

Kann es sein, dass das Lesen der Datei lange dauert nicht die Speicherallokation? Wie misst du die Zeit? Was misst du?

volkard

Ok, kann noch ein Problemchen geben. Dein vector ist viel größer als das RAM und liegt zu großen Teilen in der Auslagerungsdatei. Ist das so? Dann ist:

Da haste bei der Konstruktion des vectors für das bloße Besorgen des Speichers auch noch keine Kosten, aber der vector ist so bescheuert, daß er alle seine Elemente erstmal initialisiert, im falle von vector<unsigned int>, meint er, die alle erstmal mit 0 beschreiben zu müssen. Du hättest nur dieses Problem zu beheben, nimm vielleicht einfach mal testhalber rohen Speicher und vergleiche.

Nexus

Oder nimm reserve() .

Klaus82

ChefDerDeutschenBank schrieb:

Die Groesse veraendert sich auch bis zum Programmende nicht. Es wird also kein push_back (und es werden keine Elemente geloescht).

Warum nimmst du dann nicht den seit C++11 etablierten Array?

Gruß,
-- Klaus.

Klaus82 schrieb:

Warum nimmst du dann nicht den seit C++11 etablierten Array?

ChefDerDeutschenBank schrieb:

Die Daten kommen aus einer Datei, und die groesse weiss ich wenn ich die Datei lese.

compile-time fstream 4tw!

Klaus82

Desdemona schrieb:

compile-time fstream 4tw!

Und auf Deutsch?

Gruß,
-- Klaus.

knivil

Klaus82 schrieb:

Warum nimmst du dann nicht den seit C++11 etablierten Array?

Das gibts schon seit TR1.

Klaus82 schrieb:

Und auf Deutsch?

std::array hat eine Größe, die zur Compilezeit feststehen muss. Die Größe wird aber erst zur Laufzeit aus der Datei gelesen. Daher kann std::array nicht verwendet werden.

Klaus82

knivil schrieb:

Klaus82 schrieb:

Warum nimmst du dann nicht den seit C++11 etablierten Array?

Das gibts schon seit TR1.

Jo,
aber jetzt lässt es sich einfach so verwenden, ohne ein zusätzliches Fass aufzumachen.

nwp3 schrieb:

std::array hat eine Größe, die zur Compilezeit feststehen muss. Die Größe wird aber erst zur Laufzeit aus der Datei gelesen. Daher kann std::array nicht verwendet werden.

Also folgendes funktioniert bei mir, geht also auch zur Laufzeit.

#include <array>
#include <iostream>

int main()
{
	// das Einlesen der Datei sagt, dass 10 Elemente benötigt werden
	unsigned int const n = 10;

	std::array<double,n> arr;

	arr[0] = 1.5;

	std::cout << arr[0] << std::endl;

	return 0;
}

Gruß,
-- Klaus.

Dann lass mal das const beim n weg.

Klaus82

manni66 schrieb:

Dann lass mal das const beim n weg.

Ja schon klar, dann funktioniert es nicht.

Aber nachdem ich eben schreiben kann

int const n = funktionDieMirDieNoetigeZahlAnElementenAusDateiLiefert();

ist doch alles in Butter - zur Laufzeit.

Gruß,
-- Klaus.

Nathan

Klaus82 schrieb:

ist doch alles in Butter - zur Laufzeit.

Ja, zur Laufzeit.
Templateparameter sind aber Teil des Typen und Typen werden zur COMPILE-Zeit bestimmt. Da kannst du keine Laufzeitvariable hin tun.

KN4CK3R

Klaus82 schrieb:

manni66 schrieb:

Dann lass mal das const beim n weg.

Ja schon klar, dann funktioniert es nicht.

Aber nachdem ich eben schreiben kann
int const n = funktionDieMirDieNoetigeZahlAnElementenAusDateiLiefert();
ist doch alles in Butter - zur Laufzeit.

Gruß,
-- Klaus.

Da ist beim Array nichts in Butter... Laufzeitkonstant reicht bei Templates nicht.

Klaus82

Nathan schrieb:

Klaus82 schrieb:

ist doch alles in Butter - zur Laufzeit.

Ja, zur Laufzeit.
Templateparameter sind aber Teil des Typen und Typen werden zur COMPILE-Zeit bestimmt. Da kannst du keine Laufzeitvariable hin tun.

Also ist diese const Definition ein workaround?

Gruß,
-- Klaus.