Frage zu C++ Primer Übung 4.29 (Zeichenstrings im C-Stil)

Danke für die Antwort. Nur habe ich leider keine Ahnung was du meinst

unskilled

strcpy muss jedes zeichen einzeln kopieren und jedes mal nachprüfen, ob das zeichen jz schon das letzte (also '\0') ist. das kopieren eines strings hab ich jetzt nicht finden können - vll will das noch wer anders machen ^^
aber es wird mit sicherheit mithilfe der länge bewerkstelligt sein und somit entfällt dieses ständige prüfen auf '\0'.

der operator == von string führt das compare aus der string-klasse aus - der ruft wieder traits <value_type>::compare auf - und das sieht so hier aus (zumindest in der stl des MSVC):

int compare(const _Elem *_First1, const _Elem *_First2, size_t _Count)
{	// compare [_First1, _First1 + _Count) with [_First2, ...)
	for (; 0 < _Count; --_Count, ++_First1, ++_First2)
		if (!eq(*_First1, *_First2))
			return (lt(*_First1, *_First2) ? -1 : +1);
	return (0);
}

also muss auch hier nicht jedes mal wieder ein abgleich der aktuellen speicherposition mit '\0' gemacht werden, sondern es existiert gleich ein laufindex mit der länge...

also:

vergleich ist schneller
das kopieren ist schnller
allokation und deallokation wird sich nichts nehmen

bb

Das macht Sinn. Jetzt hab ichs verstanden. Danke!

unskilled

C++Primer schrieb:

Das macht Sinn. Jetzt hab ichs verstanden. Danke!

np ^^
hast du gesehen, dass ichs noch ma geändert habe? die sätze waren teilweise so grässlich geschrieben - war mir dann zu peinlich, dass das jemand liest und sich dann drüber lustig macht und als ichs dann einmal geändert habe, hab ich dann auch nochmal die hälfte geändert (in der hoffnung, dass es noch besser ist, als es davor schon war ^^)

außerdem musste ich noch was schreiben, damit ich 1111 beiträge habe ;o)

bb

volkard

die paar gesparten vergleiche bringens aber nicht. schauen wir doch mal, wie kopiert wird...

basic_string&
      operator=(const basic_string& __str) 
      { return this->assign(__str); }

naja, also assign suchen.

template<typename _CharT, typename _Traits, typename _Alloc>
    basic_string<_CharT, _Traits, _Alloc>&
    basic_string<_CharT, _Traits, _Alloc>::
    assign(const basic_string& __str)
    {
      if (_M_rep() != __str._M_rep())
	{
	  // XXX MT
	  const allocator_type __a = this->get_allocator();
	  _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
	  _M_rep()->_M_dispose(__a);
	  _M_data(__tmp);
	}
      return *this;
    }

aha? anscheinen besorgt _M_grab das kopieren.

_CharT*
	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
	{
	  return (!_M_is_leaked() && __alloc1 == __alloc2)
	          ? _M_refcopy() : _M_clone(__alloc1);
	}

hier ist _M_refcopy interessant

_CharT*
	_M_refcopy() throw()
	{
#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
	  if (__builtin_expect(this != &_S_empty_rep(), false))
#endif
            __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
	  return _M_refdata();
	}  // XXX MT

da passiert nicht mehr als _M_refcount+=1

also es wird gar nix kopiert. beide string-objekte zeigen nach

string str2 = str;

auf den selben speicher und teilen sich den.

unskilled

hmm.. hab ich noch nich gewusst - und im msvc seh ich da auch nicht durch -.-
wenn du mal lange weile hast, kannste das ja da auch mal zeigen!?

wobei mir das gerade sehr komisch vorkommt, weil dann ja jedes mal ne fallunterscheidung gemacht werden muss (op+=, dtor, ...) - also ob man dann jz kopieren(aufräumen) muss oder ob man schon nen eigenen speicherbereich hat...
haste lust, das zu erklären? : >

bb

hustbaer

MSVC 6 hat AFAIK noch eine STL dabei die COW für std::string verwendet.
MSVC 7.1 und 8 haben "normale" std::string Implementierungen, die lediglich die SSO verwenden (small string optimization).

COW für std::string zu implementieren ist kaum sinnvoll möglich. In single-threaded Applikationen würde es in einigen wenigen Fällen etwas bringen. Im multi-threading Applikationen müsste man für den Referenz-Zähler CAS bzw. InterlockedIncrement/InterlockedDecrement verwenden, was einiges kostet. Idealerweise wäre malloc schonmal schneller als ein einziger CAS/InterlockedXxx Aufruf. Wäre deswegen, weil malloc auf Windows/MSVC ziemlich langsam ist - IIRC ca. 2,5 mal langsamer als CAS (auf heutiger Standard-Hardware mit Intel CPU -- AMD hab' ich nie gemessen).

2,5 mal klingt jetzt als ob man damit noch gut was rausholen könnte. Ist aber nicht so. Warum? Weil COW bei std::string eben nahezu unbrauchbar ist. So ziemlich das einzige wo bei einem geCOWten std::string nicht kopiert werden muss, ist den String 1:1 durchzureichen, oder maximal noch size() aufzurufen. Sobald man den String aber z.B. über eine mutable Referenz ausliest, muss kopiert werden. Klingt komisch, is aber so. Grund: die String Klasse kann nicht wissen, dass diverse Zugriffe, die eine mutable Referenz auf die im String gespeicherten chars zurückliefern, nicht wirklich verwendet werden um den String zu manipulieren.

Beispiel:

#include <iostream>
#include <string>

int main()
{
    std::string s1 = "seppdepp";
    std::string s2 = s1; // COW?

    char c = s1[5]; // liest bloss, sieht harmlos aus
    char& ref = s1[5]; // hmmm...
    ref = 'X'; // HMMMMM...

    std::cout << "s1=" << s1 << "\n";
    std::cout << "s2=" << s2 << "\n";
}

std::string kann hier nicht unterscheiden ob der operator [] aufgerufen wird um den String auszulesen, oder um ihn zu verändern. Dasselbe Problem hat man beim Dereferenzieren von Iteratoren. Kurz: bei fast jeder Operation muss der String kopiert werden, um sicherzustellen, dass andere Strings nicht "unabsichtlich" geändert werden könnten.

Zurück zum Thema "ist aber nicht so". COW bringt nix, weil fast jeder String, der über COW "geshared" wird, gleich wieder kopiert werden muss. Wenn man für das "sharen" und "un-sharen" fast nix zahlt, wie eben bei single-threaded Applikationen, kann es trotzdem was bringen, und kaum schaden. Wenn man aber für das sharen & un-sharen ca. 40% des kopierens/freigebens zahlt, dann bringt es eben nixmehr. Bzw. macht die Sache sogar langsamer.

volkard

noch einfacher: in normalen anwendungen wird jeder kopierte string auch verändert, denn nur dazu hat man ihn kopiert. also bringt copy-on-write nix.

was ist CAS?

hustbaer

CAS = compare and swap = InterlockedCompareExchange

noch einfacher: in normalen anwendungen wird jeder kopierte string auch verändert, denn nur dazu hat man ihn kopiert. also bringt copy-on-write nix.

Das würde ich so nicht sagen. An wirklich vielen Stellen werden Strings nur rumgereicht und gelesen. Oft sogar nur durchgereicht. Als Parameter gehts ja noch mit cosnt&, aber doof sind u.a. Returnwerte.

Das Problem ist wirklich nur, dass das Lesen bei std::string auch dazu führt dass die Kuh kopiert werden muss.

Der neue Standard wird dank move-semantics da an vielen Stellen helfen.

Ich wünsche mir aber trotzdem std::const_string

Nexus

hustbaer schrieb:

Ich wünsche mir aber trotzdem std::const_string

Sowas wie der einmal von Shade of Mine vorgeschlagene NonCopy-String?

Ist wahrscheinlich nicht allzu schwierig, sowas zu implementieren... Aber wenns grad im Standard wäre, wäre das natürlich nichts schlecht.

hustbaer

Nexus schrieb:

hustbaer schrieb:

Ich wünsche mir aber trotzdem std::const_string

Sowas wie der einmal von Shade of Mine vorgeschlagene NonCopy-String?

Nö, ein sehrwohl-copy String der aber einfach immutable ist. Der könnte dann nämlich sharen soviel er mag.

Ist wahrscheinlich nicht allzu schwierig, sowas zu implementieren... Aber wenns grad im Standard wäre, wäre das natürlich nichts schlecht.

Jo, solange es nicht in Standard ist ists ziemlich zwecklos.

volkard

hustbaer schrieb:

Nexus schrieb:

hustbaer schrieb:

Ich wünsche mir aber trotzdem std::const_string

Sowas wie der einmal von Shade of Mine vorgeschlagene NonCopy-String?

Nö, ein sehrwohl-copy String der aber einfach immutable ist. Der könnte dann nämlich sharen soviel er mag.

reicht es da nicht einfach schon,

const string appName(string("foo")+bar);

zu schreiben.
der kluge bibliotheksentwickler hat doch sicherlich dran gedacht, daß die

char& operator[](size_t index)

eine kopie erzeugt, aber die

char const& operator[](size_t index) const

sowas nicht macht.

Nexus

hustbaer schrieb:

Nö, ein sehrwohl-copy String der aber einfach immutable ist. Der könnte dann nämlich sharen soviel er mag.

Aber käme man da nicht bereits mit const char* relativ weit? Vielleicht noch leicht gewrappt, dass man sich nicht mehr um die Speicherverwaltung kümmern muss...

hustbaer schrieb:

Jo, solange es nicht in Standard ist ists ziemlich zwecklos.

Ja, es ist dann eben nicht "anerkannt" und die Verbreitung würde sich im Mass halten. Aber innerhalb der eigenen Projekte spricht ja nichts dagegen, sich zusätzliche Utility-Klassen zu basteln...

volkard

Nexus schrieb:

hustbaer schrieb:

Nö, ein sehrwohl-copy String der aber einfach immutable ist. Der könnte dann nämlich sharen soviel er mag.

Aber käme man da nicht bereits mit const char* relativ weit? Vielleicht noch leicht gewrappt, dass man sich nicht mehr um die Speicherverwaltung kümmern muss...

ja, wrapper, referenzzähler rund innendrin ein char const*, voila, ein const_string.

Nexus

volkard schrieb:

ja, wrapper, referenzzähler rund innendrin ein char const*, voila, ein const_string.

boost::shared_array<const char> ?