std::string Optimierungen

Hi, ich lese immer wieder, dass die stdlibc++ sehr gut optimiert ist. Aus Interesse habe ich dann auch mal in den Quelltext von std::string bzw. std::basic_string geschaut. Aber ehrlicherweise muss ich sagen, dass ich da nicht ganz durchblicke. Was ich aber meine rausgelesen zu haben ist, dass mehrere std::string auf den gleichen String im Speicher zeigen können und dies mit ref-counts gehandhabt wird. Ist das richtig oder lese ich da Sachenr ein, die gar nicht da sind.

Gruß Peter

EOutOfResources

Es ist möglich und Bjarne Stroustrup deutete es auch an.

EDIT: Es ist aber nicht vorgeschrieben. Jede Implementierung der STD muss den Standard erfüllen, der Rest ist egal. Und wie das intern mit dem Kopieren handgehabt wird ist ausserhalb des Bereichs des Standards.

CStoll

Wie genau die STL-Klassen aufgebaut sind, ist Angelegenheit der Compiler-Entwicklers. Und Referenzzählung und Copy-on-Write Semantik ist durchaus konform zum ANSI-Standard (d.h. die Strings kopieren die dahinterliegenden Daten erst, wenn du ihre Daten änderst).

volkard

Herb Sutter schrieb:

Optimizations That Aren't (In a Multithreaded World)

krümelkacker

Peterblub schrieb:

Was ich aber meine rausgelesen zu haben ist, dass mehrere std::string auf den gleichen String im Speicher zeigen können und dies mit ref-counts gehandhabt wird. Ist das richtig [...?]

Ja, das ist richtig. Ich hatte mir das auch mal angeguckt, als ich einen Programmcode sah, der per reinterpret_cast aus einem string* ein char** gemacht hatte. Ich war nämlich ganz schön überrascht, dass das Programm überhaupt funktionierte.

Im Moment sieht die std::string Implementierung der libstdc++-Bibliothek so aus: sizeof(string) = sizeof(char*). Das einzige Datenelement der Klasse ist auch ein char-Zeiger, der auf eine Nullterminierte Char-Sequenz zeigt. Alles andere (Länge, Kapazität und Referenzzähler) steht direkt vor dieser Char-Sequenz im selben Speicherblock. Die genaue Reihenfolge der 3 Ints weiß ich aber nicht mehr. Das Prinzip war folgendes:

struct meta {
  int ref_count;
  int size;
  int capacity;
};

class string {
  ...
  char* ptr; // <-- einizges Datenelement
  ...
  meta& meta_() const
  { assert(ptr); return *(reinterpret_cast<meta*>(ptr)-1);}
  ...
public:
  ...
  string(string const& s)
  : ptr(s.ptr)
  { if (ptr) atomic_increment(meta_().ref_count); }
  ...
  const char* c_str() const
  { return ptr; }
  ...
};

(Angaben ohne Gewähr)

Ich weiß nicht, wie viel Overhead der Synchronisierungsaufwand wirklich ist. Die libstdc++ Entwickler sind anscheinend zufrieden mit ihrer aktuellen Implementierung. Die ist, soweit ich weiß, "lock-free" aber genauso "thread-safe" wie eine normale Implementierung ohne COW. Da der Move-Konstruktor den Referenzzähler gar nicht anfassen muss, sollte zumindest der sehr effizient sein.

Microsoft dagegen macht ein string-Objekt 32 Byte groß, wenn ich mich richtig erinnere. Jedenfalls ohne COW, aber dafür mit SSO

COW = copy-on-write
SSO = small string optimization