alternative zu placement new

[Gast]

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

[Gast]

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.

[Gast]

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

[unskilled]

Danke ^^

Die Zeile hätte schon gereicht - den Rest hatte ich auch so verstanden, nur das konnte ich mir nicht so richtig denken ^^

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

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

Hmm... xD Die Idee hätte glatt von mir stammen können... Verdammt ^^ Naja - man lernt ja bei so was wenigstens immer dazu ^^

Kommt bei mir ganz klar 8 dabei raus.

Stimmt - bei mir auch... So gar im x64-Mode oO

bb

[Nexus]

Dravere schrieb:

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

Nene, aber ist gut, dass du meine Gedanken kennst. :p

Aber die ersten beiden Quellen bei Google sagen da etwas Anderes (im Buch hab ich das Wort nicht finden können):

www.duden.de schrieb:

al|lo|kie|ren <zu mlat. allocare>: für einen bestimmten Zweck bereitstellen (bes. Datenv.)

de.wiktionary.org schrieb:

allokieren (Deutsch)

Bedeutungen:
[1] Informatik: (Arbeitsspeicher) belegen

Synonyme:
[1] anfordern, belegen

[Dravere]

Hast du nicht auch die Diskussion auf "de.wiktionary.org" gelesen?
http://de.wiktionary.org/wiki/Diskussion:allokieren

In meinem Duden Zuhause (23. Auflage) befindet sich kein allokieren. Wenn ich im Duden im Web suche, finde ich nur das, was ich schon gesagt habe. Interessanterweise komme ich aber über Goolge auf die Website, welche du per Copy&Paste präsentierst, aber das geht nur über Google

Jedenfalls nach ursprünglicher Bedeutung, macht allozieren deutlich mehr Sinn. Mir ist allerdings nicht klar, ob es so ist, wie in der Dikussion auf Wikitionary erwähnt wird, dass die Informatiker einfach zu dumm waren und das allokieren nun auch in dieser Art in die Sprache aufgenommen wurde.

Naja, wie auch immer, mit allozieren ist man ganz sicher, auf der richtigen Seite

Grüssli

[pumuckl]

gottseidank sind wir keine Compiler die bei nem Tippfehler oder falsch verwendeten Wort einfach aussteigen. Hauptsache ist doch man kann ohne Schwierigkeiten den Text verstehen, und dass keiner hier den armen Speicher trösten will sollte ja bekannt sein
Vllt. kann man sich drauf einigen, neudeutsch "allocieren" zu schreiben - dann kann sich jeder aussuchen wie er das c gern aussprechen möchte.
Oder man verlegt sich aufs englische, so dass die Leute genug damit zu tun haben, ihren eigenen Satzbau zurechtzufrickeln und Kleinigkeiten geduldet werden

[hustbaer]

Decimad schrieb:

aufrufen würde.

Die meisten Implementierungen werden das auch genau so machen.

Aber bedenke folgendes: angenommen T=char, x=1, und die Heap-Implementierung von Compiler Y kann Stücke nicht kleiner als 4 Byte anfordern... Wenn nun der Hersteller von Compiler Y eine Standard-Library Implementierung mitliefert, dann ist es IMO vollkommen OK wenn capacity() nach einem reserve(1) auf einen char-vector als Ergebnis 4 liefert. Grund: es gehen sowieso immer 4 Byte drauf, ob der vector nun nur eins anfordert oder gleich 4. Von daher wäre es ziemlich sinnlos so eine Optimierung zu verbieten. Natürlich könnte man jetzt einwenden dass man ja seinen eigenen allocator an std::vector übergeben könnte (der evtl. problemlos einzelne Bytes allozieren kann ohne Platz zu verschwenden). Allerdings, wenn der Hersteller von Compiler Y schlau ist, dann macht er diese Optimierung auch nur wenn std::allocator verwendet wird

Und nochwas, hätte ich fast vergessen: capacity() darf auch schonmal deswegen nach reserve(x) einen Wert > x melden, weil der vector vor dem reserve(x) ja schon grösser gewesen sein könnte. In diesem Fall schreibt der Standard IIRC sogar vor dass der Speicher NICHT re-alloziert werden soll, die grössere Capacity also erhalten bleiben soll. Das Verhalten was für vector hier vorgeschrieben wird mag zwar seltsam anmuten, ist aber in dem meisten Fällen sehr gut. Natürlich gibt es einige Fälle wo man möchte dass der vector auch mal wieder "schrumpft". In denen muss man dann über diverse Tricks dafür sorgen dass das passiert, z.B. mittels swap(). Das einzige was mir hier abgeht ist eine "shrink" Funktion, so dass man nicht auf umständliche "swap" Tricks angewiesen wäre. Und der Code würde dadurch auch leserlicher (=es wäre einfacher zu sehen was hier passiert, bzw. was der Programmierer bezwecken wollte).

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.

Äh. Nö, wieso sollte man das?

Ja, der Standard erlaubt es an vielen Stellen total praxisfremde und bescheuerte Implementierungen zu machen. Nur heisst das noch lange nicht dass ich als Programmierer Rücksicht auf diese Möglichkeit nehmen muss. Der Standard sieht (implizit, dadurch dass er die Klasse definiert) vor, dass std::vector in realen Programmen verwendet wird. Eine Implementierung die das in der Praxis unmöglich macht (bzw. total "unbrauchbar"), z.B. solche hinrissigen Dinge macht wie den zigtausendfachen Speicher anzufordern, bloss weil es erlaubt ist, ist zwar vielleicht dem Buchstaben des Standards nach konform, aber totaler Schwachsinn.
Ich wiederhole mich jetzt, aber wie gesagt, ich nehme auf sowas keine Rücksicht, und ich halte das für eine äusserst realistische und gute Lösung. Geh einfach davon aus dass eine Implementierung dir nicht zu Fleiss irgendwelche Klötze in den Weg werfen wird.

BTW: die einzige sinnvolle Alternative zu der Formulierung im Standard wäre IMO eine (u.U. ziemlich lange) Liste von Fällen zu presentieren in denen es erlaubt ist mehr Speicher anzufordern als bei reserve() angegeben wird. Das dumme an solchen Listen ist nur dass man Fälle übersehen kann.

Die Forderung eine praxistaugliche und sinnvolle Implementierung zu wählen ist IMO implizit, muss nicht extra hingeschrieben werden, und wird nach Meiner Erfahrung auch von allen Implementierungen respektiert.