alternative zu placement new

[Nexus]

unskilled schrieb:

Und nein, std::vector möchte ich nicht nehmen, da es ein 2D Array ist und der Speicherverbrauch ja dann expotentiell höher ist als der, der genutzt wird (da vector immer mehr alloziert)

Wieso exponentiell? In den gängigen Implementierungen wird bei einer Reallokation doppelt soviel Speicher allokiert. Also im zweidimensionalen Fall hast du im Worst Case 25% des angeforderten Speichers belegt.

unskilled schrieb:

Ein C-Array und sämtliche Wrapper fallen leider auch flach(Stack ist zu begrentzt und Größe steht nicht zur Compilezeit fest).

Wieso schreibst du dir nicht eine eigene Containerklasse, die genau deinen Bedürfnissen angepasst ist? Ich hab auch einmal ein Table -Klassentemplate für zweidimensionale Felder geschrieben.

pumuckl schrieb:

[..] uninitialisierten Speicher, so wie er z.B. von malloc() geliefert wird oder von der alloc()-Routine des von dir benutzen Allokators

[...] und den Speicher dann mit free() wieder freigeben.

Dafür kann man auch einfach operator new und operator delete aufrufen, aber mit der expliziten Schreibweise:

void* Memory = operator new(245);  // Allokiert 245 Bytes.
operator Delete(Memory);   // Deallokiert den Speicherbereich.

unskilled schrieb:

zur not muss ich es halt über eine nachträgliche zuweisung machen - aber das muss doch auch anders gehen!? ^^

Eben, gerade wenn du es komfortabel handhaben willst, würde ich zur eigenen Klasse raten. Ansonsten kannst du wie gesagt reinen Speicher mit operator new anfordern und Placement New belegen. Beim Freigeben musst du zuerst den Destruktor und anschliessend operator delete aufrufen. Aber wenn dir Speicher nicht so extrem wichtig ist, solltest du doch besser std::vector verwenden. Oder std::deque , da ist die Speicherverwaltung meist günstiger.

Decimad schrieb:

Warum sollte ein vector, dem man mit reserve genau gesagt hat, wieviel man haben will, sein Feld aufplustern, bevir man dann auf einmal über die reservierte Grenze hinausschießt?

std::vector::reserve() kann auch mehr anfordern als gewünscht. Bei einer Reallokation wird der Speicher normalerweise verdoppelt. Die Speicherverschwendung von std::vector ist schon ziemlich gross, was sich gerade bei grossen Matrizen (möglicherweise mit nicht skalaren Typen) auswirken kann.

[Guest]

Das wäre doch wohl oberbeknackt. Der Programmierer muss sich doch mit dem reserve was gedacht haben, warum sollte er denn nur halb so viel reservieren, wie er am Ende braucht? Oo

Ausschnitt aus Dimkumware's reserve:

else if (capacity() < _Count)
{	// not enough room, reallocate
    pointer _Ptr = this->_Alval.allocate(_Count);

Das sieht für mich irgendwie schlüssig aus.

Dann wieder aus ner Doku:

This informs the vector of a planned increase in size, although notice that the parameter n informs of a minimum, so the resulting capacity may be any capacity equal or larger than this.

Ich beginne an der Intelligenz der Leute vom Standard zu zweifeln. Der einzige Grund, der mir überhaupt nur einfiele wäre derjenige, dass man nur Blöcke mit einer bestimmten Größe größer als sizeof( typ ) allozieren kann. Aber dann käme man ja mit oder ohne vector nicht darum herum.

[sothis_]

verdammt nochmal, das heißt 'allozieren', allo-z-ieren!

[unskilled]

Nexus schrieb:

unskilled schrieb:

Und nein, std::vector möchte ich nicht nehmen, da es ein 2D Array ist und der Speicherverbrauch ja dann expotentiell höher ist als der, der genutzt wird (da vector immer mehr alloziert)

Wieso exponentiell? In den gängigen Implementierungen wird bei einer Reallokation doppelt soviel Speicher allokiert. Also im zweidimensionalen Fall hast du im Worst Case 25% des angeforderten Speichers belegt.

gut - auf 25% kommt man, wenn man für nur eine dimension nen vector nutzt und für die andere nen pointer-array?!

weil:

benötigterSpeicher = row_count * line_count * sizeof(T)

vector:

worstCase = row_count*2 * line_count*2 * sizeof(T)
bestCase = row_count * line_count * sizeof(T)

also im Durchschnitt:

(worstCase + bestCase)/2
------------------------
   benötigterSpeicher

row_count*2 * line_count*2 * sizeof(T) + row_count * line_count * sizeof(T)
---------------------------------------------------------------------------
                2  *  row_count * line_count * sizeof(T)

row_count*2 * line_count*2 + row_count * line_count
---------------------------------------------------
          2 * row_count * line_count

row_count * line_count (4 + 1)
------------------------------
row_count * line_count * 2

 5
---    =   2,5
 2

also komm ich auf 150% mehr Speicher - im Durchschnitt
und nicht auf 25% im worstcase ^^

wenn man eine dimension durch pointer ersetzt bekommt man (2*1+1)/2 also 1,5 raus. Beduetet also noch immer 50% Speicherverschwendung - und wir reden noch immer vom Durchschnitt... Das wird vll klarer, wenn man sich das ganze mal vorstellt - aber die Rechnung sollte jz nicht so unlogisch sein ^^

Und selbst 10% würde ich schon für die Obergrenze halten - weil ja z.bsp. beim Determinaten berechnen sehr viele determinanten (n! falls man nur nach dem Laplace`schen Entwicklungssatz geht ohne vorher die Matrix umzuformen) gebraucht werden...

Das wäre doch wohl oberbeknackt. Der Programmierer muss sich doch mit dem reserve was gedacht haben, warum sollte er denn nur halb so viel reservieren, wie er am Ende braucht

Die Aussage verstehe ich nicht ganz xD

Nachvollziehen kann ich das mit der bis zu doppelt so großen Länge auf jeden Fall - auch sehr hilfreich - nur eben nicht, wenns um mehrere Dimensionnen geht, deren Größe an sich sich relativ selten (bis nie) ändert ^^

bb

edit: da war ne zahl falsch ^^

[Nexus]

Decimad schrieb:

Ich beginne an der Intelligenz der Leute vom Standard zu zweifeln.

Naja, manchmal frag ich mich auch ein wenig. Obwohl ich nicht glaube, dass es an der Intelligenz der Leute liegt...

Decimad schrieb:

This informs the vector of a planned increase in size, although notice that the parameter n informs of a minimum, so the resulting capacity may be any capacity equal or larger than this.

Eben, dort steht ja extra ein Satz mit "although". Ich kann mir vorstellen, dass man in den meisten Fällen mit reserve() nicht gross Speicher verschwendet haben wird, aber man sollte sich nicht darauf verlassen.

unskilled schrieb:

gut - auf 25% kommt man, wenn man für nur eine dimension nen vector nutzt und für die andere nen pointer-array?!

Keine Ahnung, was du so kompliziert machst.

Also, du hast einen std::vector . Nehmen wir an, dass er sich mit doppelter Kapazität reallokiert, wenn diese nicht mehr ausreicht. Nach der Reallokation wird nur 50% des Speichers verwendet (eigentlich ein bisschen mehr, aber vernachlässigen wir das) - also ist die Hälfte des angeforderten Speichers belegt.

Wenn du nun das Ganze in zwei Dimensionen machst, besteht jeder Vector aus einigen Vectoren. Im Worst Case wird von denen wiederum nur 50% benötigt.

Ein zu 50% ausgelasteter Vector, dessen Elemente wiederum nur zu 50% ausgelastet sind, führt zu einer effektiven Nutzung des angeforderten Speichers von 25%.

[Guest]

Hat jemand andere verbreitete STL-Implementationen angeschaut? Wie gesagt, Visual C++ 2008's STL alloziert mit reserve auf das Byte genau.

[pumuckl]

ihr redet mit euren Prozenten aneinander vorbei
der eine redet davon, wieviel Prozent des angeforderten Speichers tatsächlich genutzt werden (~25% im worst case), der andere redet davon, wieviel Prozent des benötigten Speichers angefordert werden (~400% im worst case)

Decimad schrieb:

Ich beginne an der Intelligenz der Leute vom Standard zu zweifeln. Der einzige Grund, der mir überhaupt nur einfiele wäre derjenige, dass man nur Blöcke mit einer bestimmten Größe größer als sizeof( typ ) allozieren kann.

Dass die Standardler das so ausdrücken, liegt einfach daran, dass sie die Implementatoren nicht zu weit einschränken wollen. Stell dir vor, jemand hat ein Speicherverwaltungstool, in dem tatsächlich nur Blöcke bestimmter Größe angefordert werden können. Oder irgendein OS besteht darauf dass der Speicher entsprechend unterteilt wird. Auf der anderen Seite stünde im Standard "vector alloziert genau so viel Speicher wie angegeben wurde. Aus die Maus mit dem templateparameter Allocator, weil nicht jede Speicherverwaltung es dem vector ermöglicht, exakt den Speicher zu reservieren der angegeben wird. Und aus die Maus mit Portabilität, weil der Standard durch unsinnige Restriktionen verhindern würde, dass vector auf dem BigMemBlock-OS implementiert werden kann.

std::vector<char> vc;
vc.reserve(41);
std::cout << vc.capacity() << std::endl;

Was da wohl rauskommt? ich würde mal schätzen, da kommt 42, 44 oder 48
raus, je nachdem ob das OS den Speicher in 16 bit, 32 bit oder 64 bit Blöcke unterteilt

[Nexus]

pumuckl schrieb:

alloziert

Vorher hätte ich sothis_ beinahe geantwortet, aber seine Trollposts sind mir oft einfach zu blöde.

Nur weil er hier spammt, brauchst du dich nicht beeinflussen zu lassen. "Allokieren" ist genauso ein deutsches Wort.

[unskilled]

stimmt - hatte es wohl unzureichend gelesen und deshalb

was kommt denn bei dir raus?

also bei mir kommt 41 raus...
(MS VC 2008 Prof, Vista 64bit)

bei folgendem code

std::vector<char> vc; 
std::cout << vc.capacity() << std::endl;
vc.reserve(22);
std::cout << vc.capacity() << std::endl;
for (char i(0); i != 41; ++i)
{
	vc.push_back (i);
	std::cout << vc.capacity() << std::endl;
}

kommt bei mir 0 / 22 / 33 / 49 raus (nat. jeweils mehr als einmal ^^)

wobei ich es trotzdem sehr sinnvoll finde doppelt so viel zu reservieren wie benötigt wird... stellt euch so was mal vor:

std::vector <int> r;
for (size_t i(0); i != 100; ++i)
  r.push_back(i);

das würde also zu 100 mal umkopieren führen(was man aber eigtl super mit nem reserve unterbinden könnte - aber soll ja auch fälle geben, wo man nicht weiß, wie viele elemente in dem vector platz brauchen werden) - oder man reserviert immer ein wenig mehr ram (und was ist schon doppelt so viel - wenn man 100 elemente speichert, kann man imho auch für 200 platz in anspruch nehmen - ob es bei verschachtelten vectoren dann net mehr so toll ist, kommt ja auch auf das anwendungsgebiet an)...
davon abgesehen ist pumuckl´s begründung wahrscheinlich die wichtigere/bessere/...

bb

[Guest]

Na klar, ich find das auch ok, dass der vector beim IMPLIZITEN vergrößern "großzügig" ist. Aber ich finde es NICHT ok, wenn der vector das auch noch macht, wenn ich ihn explizit (reserve) darauf hinweise, dass es genau so groß sein soll (aber es ist okay, dass er dann nicht noch extra schrumpft).

Ich erwarte folgendes:

std::vector<int> v;
v.reserve( 10 );
for( int i=0; i<10; ++i ) v.push_back( i );
assert( v.capacity() == 10 );

Alles andere ist mir eigentlich egal.

[Guest]

aufrufen würde. Aber der Standard ist da so frei, dass der vector durchaus auf ein reserve(1) mit einer Kapazität von 20k antworten kann... Und ab da kann sich ja ein standardkonformer Programmierer direkt ausklinken und alle semidynamischen Felder wieder selber kodieren.

[Nexus]

Ich fände, eine Art Flag oder globales Makro wäre angebracht, um die Grosszügigkeit seiner Vector-Implementierung einzuschränken. Ähnlich wie das Makro zur Abschaltung der Sicherheitsabfragen.

Damit könnte man z.B. auch push_back() begrenzen. Aber naja, da kommt man auch einer eigenen Klasse näher, schlussendlich wirds auf eigenes Coden hinauslaufen...

[unskilled]

Jopp - ich hab dann aber doch wieder ne Frage:

values = static_cast <ValueType*> (operator new (sizeof(ValueType) * row_count));

kann ich davon ausgehen, dass padding/... hier berücksichtigt wird bzw. wie sollte man das besser lösen?

bb

[pumuckl]

Ich denke mal dass k(aum )ein Implementor der Standardbibliothek sich dazu erdreistet hat bei einem reserve() dem OS unnötig viel Speicher abzutrotzen. Ich würd mich in erster Linie drauf verlassen, dass vector das schon ganz richtig macht und erst wenn es Performanceprobleme gibt und mein Profiler mir sagt dass vector schuld ist überleg ich mir Alternativen. Alles andere ist PMO
Außerdem gibts die gleiche Situation beim int (!): Der Standard schreibt nicht vor wie groß er sein soll. Nur dass er größer als short und char ist. Genauso wie der vector beim reserve also einige Megabyte sinnlosen Speicher reservieren darf, ists dem Compilerhersteller auch nicht verboten, einen int auf 200MB Größe festzulegen. Trotzdem kommt keiner auf die Idee da was eigenes zu implementieren

/edit:

unskilled schrieb:

bzw. wie sollte man das besser lösen?

mit operator new[]

[unskilled]

pumuckl schrieb:

/edit:

unskilled schrieb:

bzw. wie sollte man das besser lösen?

mit operator new[]

Oo
Vll hätte ich den Zusammenhang mit posten sollen (das war das new statt malloc)

values = static_cast <ValueType*> (operator new (sizeof(ValueType) * row_count));

SizeType index = SizeType();
try
{
	for (; index != row_count; ++index)
	{
		ValueType *tmp = value[index];
		tmp = new (tmp) ValueType (fill_with);
	}
}
catch (...)
{
	Destruct(index);
	throw;
}

Oder gibt es einen operator new[], der uninitialisierten Speicher hinterlässt? ^^

bb

edit:
analog dazu das löschen:

for (ValueType *iter = values, *end = values+length; iter != end; ++iter)
{
	if(iter)
		iter->~ValueType();
}

operator delete (values);
values = nullptr;

[Nexus]

unskilled schrieb:

Oder gibt es einen operator new[], der uninitialisierten Speicher hinterlässt? ^^

Ja, genau analog zu operator new .

[unskilled]

und hier kann ich mir dann sicher sein, dass er alignment und padding beachtet:

values = static_cast <ValueType*> (operator new [sizeof(ValueType) * row_count]);

//operator delete[] (values);

?

Falls nicht, sehe ich keinen Unterschied in der Lösung und der davor (abgesehen vom optischen ^^). Falls ich jz iwas falsch verstanden habe, mach ma pls nen kurzes Bsp

bb

[Nexus]

Vielleicht nochmals zusammenfassend:

T* ptr = operator new(sizeof(T));
T* ptr = operator new[](5*sizeof(T));

Hiermit wird Speicher allokiert und nicht initialisiert.

new (ptr) T;

Das Placement New initialisiert den Speicher ptr , indem eine Instanz an dieser Speicherstelle konstruiert wird. Es können auch Konstruktorargumente für T übergeben werden.

ptr->~T();

Der explizite Destruktoraufruf ist erforderlich, wenn Zerstörung und Deallokation separat behandelt werden.

operator delete(ptr);
operator delete[](ptr);

Der operator delete bzw. operator delete[] gibt den Speicher an der Speicherstelle ptr frei. Hier muss man darauf achten, dass die korrekte Version aufgerufen wird.

[Nexus]

unskilled schrieb:

und hier kann ich mir dann sicher sein, dass er alignment und padding beachtet:

values = static_cast <ValueType*> (operator new [sizeof(ValueType) * row_count]);

So kannst du operator new[] gar nicht aufrufen (siehe mein letzter Post). Eigentlich brauchst du nur operator new .

Also so:

values = static_cast<ValueType*>(operator new(sizeof(ValueType) * row_count);

Hier sollte kein Problem wegen Alignment entstehen.

Aber du kannst auch einfach den std::allocator verwenden.

[Dravere]

@unskilled,
sizeof berücksichtig padding und co. Kannst es auch selber testen:

struct Foo
{
  int a;
  char b;
};

int main()
{
  std::cout << sizeof(Foo) << std::endl;
  return 0;
}

Kommt bei mir ganz klar 8 dabei raus.

@Nexus,

<?xml version="1.0" ?>
<off-topic operation="klugscheiss">
  <talk-to name="Nexus">
    <definition-of value="allokieren">anreden, trösten</definitin-of>
    <definition-of value="allozieren">zuweisen, bereitstellen</definition-of>
    <reference type="url">http://faql.de/fremdwort.html#allocate</reference>
    <commenct>sothis_ hat es zwar nicht nett gesagt, aber recht hat er.</comment>
  </talk-to>
</off-topic>

Und ich will jetzt kein "Nerd" oder ähnliches hören.

Grüssli