std::vector::push_back: mit VS. ohne vorausgehendem reserve

IrgendeinName

Stroustrup hat selbst was darüber geschrieben:
http://www2.research.att.com/~bs/bs_faq2.html
(Strg-f nach reserve)

Ethon

Hängt wohl auch davon ab, was gespeichert wird. ein std::vectorstd::string ist da wohl deutlich heftiger bei Reallocations als ein std::vector<int>

TyRoXx

Ethon schrieb:

Hängt wohl auch davon ab, was gespeichert wird. ein std::vectorstd::string ist da wohl deutlich heftiger bei Reallocations als ein std::vector<int>

Eben nicht, Stichwort: Move constructor. string ist billig zu bewegen, aber teuer initial zu konstruieren. int macht da keinen Unterschied.

Die ganzen Speicheranforderungen werden den Unterschied undeutlicher machen (heißt: kleiner als 50%).

TyRoXx schrieb:

Eben nicht, Stichwort: Move constructor

In C++11

krümelkacker

C++03er schrieb:

TyRoXx schrieb:

Eben nicht, Stichwort: Move constructor

In C++11

Jain. Soweit ich weiß, war das schon vorher bei MSVC optimiert. Die haben da irgendwelche Traits, die einem sagen, ob ein Objekt x des Typs T per

T x = ...;
T y;
swap(x,y);

fix nach y "movebar" ist, ohne dass Ausnahmen fliegen (swaptimization). Und in so einem Falle wählt ihre std::vector-Implementierung für ihre eigenen Typen, die genau das können (std::string, std::vector, ...), eine entsprechende "grow"-Funktion aus, die das ausnutzt.

Aber für selbstdefinierte Klassen mit aufwändigeren Kopier-Konstruktoren und ohne Move-Konstruktoren, wird es sicherlich einen größeren Unterschied machen.

Ethon

Wieso nicht einfach per memcpy in den anderen Speicherbereich kopieren, ohne Allocator::destroy auf die alten Daten loszulassen? Ist ja nicht so als würde std::vector mit new/delete herumhantieren, Konstruktoren und Destruktoren werden alle explizit aufgerufen.

Shade Of Mine

Ethon schrieb:

Wieso nicht einfach per memcpy in den anderen Speicherbereich kopieren, ohne Allocator::destroy auf die alten Daten loszulassen?

Weil du vielleicht keine plain Data Objekte hast, sondern komplexe Objekte die Zeiger auf andere Objekte haben. Und wenn du da einfach mal so die Adressen der Objekte aenderst dann kommen Bugs zustande die unmoeglich zu finden sind.

Ethon

Fällt dir ein Szenario ein, in dem ein Objekt sich bei einem Move-Vorgang verändern würde?

Mit std::string oä. wäre memcpy auf jeden Fall kein Problem.

TyRoXx

Ethon schrieb:

Wieso nicht einfach per memcpy in den anderen Speicherbereich kopieren, ohne Allocator::destroy auf die alten Daten loszulassen? Ist ja nicht so als würde std::vector mit new/delete herumhantieren, Konstruktoren und Destruktoren werden alle explizit aufgerufen.

using namespace std;

static void memcpyStrings(string *from, string *to, size_t count)
{
	memcpy(to, from, count * sizeof(*to));
}

static void moveStrings(string *from, string *to, size_t count)
{
	for (size_t i = 0; i < count; ++i)
	{
		//Kopiert 'from' nach 'to' und setzt 'from' in einen Nullzustand.
		//Das Kopieren könnte vom Compiler mit memcpy() optimiert werden.
		//Das Setzen in den Nullzustand kann weggelassen werden, wenn
		//der Optimierer die zweite Schleife berücksichtigt.
		new (to + i) string(std::move(from[i]));
	}
	for (string *i = from + count - 1; i >= from; --i)
	{
		//'from' wird zerstört, was aber im Nullzustand nichts bewirkt.
		//Der Optimierer könnte erkennen, dass der Move-Konstruktor aus
		//der vorherigen Schleife alle Objekte in den Nullzustand versetzt,
		//sodass die zweite Schleife gar nichts tut.
		//Da das Lesen aus zerstörten Objekten undefiniertes Verhalten ist,
		//können alle finalen Schreibvorgänge ohne Seiteneffekte in den Objekten
		//weggelassen werden. Konkret: Das Versetzen in den Nullzustand findet
		//nicht statt, die Zerstörung wird sozusagen zur Compile-Zeit erledigt.
		(i)->~string();
	}

	//Zusammengefasst: Ein schlauer Optimierer kann das alles durch
	//	memcpy(to, from, count * sizeof(*to));
	//ersetzen und ist damit standardkonform.
}

Man könnte diese Optimierung auf der Ebene der Standardbibliothek implementieren, indem man abhängig von gewissen Eigenschaften von T einfach memcpy verwendet. Bei vordefinierten Typen wie std::string könnte das funktionieren.

pumuckl

Ethon schrieb:

Wieso nicht einfach per memcpy in den anderen Speicherbereich kopieren, ohne Allocator::destroy auf die alten Daten loszulassen?

Das geht problemlos bei PODs (Da wirds auch so gemnacht). Außerdem gehts bei Klassen, die gewisse Voraussetzungen haben - im wesentlichen alles, was vergleichsweise simple noexcept move-konstruktoren hat, wo bei den Kopien keine anderen Objekte benachrichtigt werden müssen usw. Nach dem Optimizer mit reordering und Zusammenfassen der einzelnen Kopien von hintereinander liegendem Speicher wird da im Grunde was ähnlich performantes rauskommen wie memcpy.

Es geht aber eben nicht immer, und deshalb kannn mans nicht einfach allgemein so machen sondern muss die Spezialifälle abprüfen und eine passende Behandlung nehmen.