[c++] trage std::string constructor omzeilen?

[Verwijderd]

hallo menschen

ik heb een functie die een string teruggeeft, en die wil ik vervolgens vergelijken met iets, bijv:

C++:

  if (GetValue() == "iets") { .. }

soortgelijke code wordt heel vaak aangeroepen, vooral voor mn properties class. ik heb dan bijv een GetProperty() die een std::string teruggeeft, en die ik dan vergelijk met een bepaalde string.

nu ontdekte ik na wat profilen dat er een fikse bottleneck zit in de std::string constructor, omdat hij voor elke keer dat ik "iets" type wordt aangeroepen (er moet immers een string van worden gemaakt die dan met de uitkomst van GetValue() of GetProperty() wordt vergeleken). en hij is blijkbaar dus nogal traag, die constructor

weet iemand een handige manier om deze constructor te omzeilen, het liefst zonder al teveel aan de code te veranderen? het zit nogal overal in mn project namelijk..

en een fijne sinterklaasavond natuurlijk

[Arjan]

code:

static const std::string iets( "iets");
if (GetValue() == iets ) { .. }

Maar ik betwijfel zeer sterk of dit echt je performance probleem is.. de compiler is ook niet achterlijk natuurlijk..

[RobIII]

Ik ben geen C++ expert maar iets zegt me dat je beter moet meten. Ik geloof er verdomd weinig van dat een string constructor traag zou zijn. Zou het werkelijk zo zijn dan denk ik dat je nog steeds een veel groter probleem hebt; als een 'trage string constructor' al de bottleneck zou zijn dan zijn je problemen, naar ik vermoed, huge.

[Verwijderd]

@arjan
daar heb ik ook aan gedacht, maar dan moet ik voor elk mogelijke woordje een static string maken.. dat haalt de handigheid een beetje weg (dan kan ik beter overstappen naar enums ofzo)..

ik heb overigens ook mn twijfels.. maar volgens kcachegrind is het echt het geval, en nadat ik het tijdelijk had weg-gehacked leek het ook daadwerkelijk sneller..

voor de duidelijkheid, die code wordt ettelijke miljoenen op zn minst duizenden keren per seconde aangeroepen (heb de kcachegrind output ff niet bij de hand, zit in windows)

[ Voor 9% gewijzigd door Verwijderd op 05-12-2011 22:21 ]

[RobIII]

Verwijderd schreef op maandag 05 december 2011 @ 22:18:
@arjan
daar heb ik ook aan gedacht, maar dan moet ik voor elk mogelijke woordje een static string maken.. dat haalt de handigheid een beetje weg (dan kan ik beter overstappen naar enums ofzo)..

Waar Arjan op doelt is dat de compiler dat al (als het goed is) voor je doet...

[Gomez12]

Verwijderd schreef op maandag 05 december 2011 @ 22:18:
voor de duidelijkheid, die code wordt ettelijke miljoenen op zn minst duizenden keren per seconde aangeroepen (heb de kcachegrind output ff niet bij de hand, zit in windows)

Als die code echt duizenden keren per seconde aangeroepen wordt, tja dan is een string trager dan menig ander type.

Duizenden string-comparisons per seconde is niet echt het snelste van het snelste zeg maar.

Maar ben je wel zeker van die duizenden keren aanroepen? Of is dat een schromelijke overdrijving en bedoel je enkel maar dat hij vaak wordt aangeroepen?

[Verwijderd]

nou, mn physics thread draait op 100fps, en binnen die thread worden meerdere recursieve functies aangeroepen die veelal vele keren die functies gebruiken. vandaar mn schatting

maar wat rob zegt, dat is blijkbaar dan toch niet het geval? het klinkt idd wel logisch dat dat automatisch geoptimized zou moeten worden..?

[ Voor 28% gewijzigd door Verwijderd op 05-12-2011 22:45 ]

[Sjonny]

je moet ook gewoon de compare function van std::string gebruiken:

C++:

if (GetValue().compare("iets") == 0) {
 // match
}

die gebruikt dan automatisch de const char* versie.
en je moet GetValue een const string reference laten returnen, anders maakt je return value een copy van je string, wat je ook al niet wil:

C++:

const std::string& GetValue() {
  // maar dan hopelijk minder lompe code
  return std::string("hallo");
}

[Verwijderd]

dat laatste deed ik al goed, maar het 1e wist ik niet! dacht dat ie daar dan ook een string van maakte tnx, ik ga het gelijk proberen

just curious trouwens, string::compare heeft oa. deze 2 implementaties:

C++:

int compare ( const string& str ) const;
int compare ( const char* s ) const;

hoe weet je zeker dat hij de 2e gebruikt?

[ Voor 44% gewijzigd door Verwijderd op 05-12-2011 22:54 ]

[Sjonny]

omdat een "blah" per definitie een const char* is.

[Verwijderd]

maar "blah" is ook een std::string.. alleen de char zit zeker dieper in c++ ingebakken ofzo? *noob*

[Bob]

Sjonny schreef op maandag 05 december 2011 @ 22:51:

die gebruikt dan automatisch de const char* versie.
en je moet GetValue een const string reference laten returnen, anders maakt je return value een copy van je string, wat je ook al niet wil:

C++:

const std::string& GetValue() {
  // maar dan hopelijk minder lompe code
  return std::string("hallo");
}

Je returnt hier een reference naar een temporary. Niet echt volgens het boekje VS zou hier een warning moeten geven.

[Verwijderd]

nee, zo werkt het niet.. de properties zitten binnen die class in een vector, dus die zijn niet temporary. nouja, een beetje wellicht

*edit, owja, in zijn voorbeeld idd.. snap wat je bedoelt maar dat is dus niet echt een issue in mijn geval

[ Voor 29% gewijzigd door Verwijderd op 05-12-2011 23:11 ]

[.oisyn]

RobIII schreef op maandag 05 december 2011 @ 22:40:
[...]

Waar Arjan op doelt is dat de compiler dat al (als het goed is) voor je doet...

Wat nonsens is, de compiler gaat niet voor jou bedenken dat het keer op keer constructen van een temporary kan worden geoptimaliseerd door het maar 1 keer creëren van die temporary. De ctor kan allerlei bijeffecten hebben waar de compiler geen zicht op heeft, en dus mag hij het niet optimaliseren.

De compare method is het meest praktisch. Als het gaat om bakken met code die een dergelijke compare doet dan zou je ook kunnen overwegen om een operator==(const std::string &, const char *) (en vice versa) te definieren.

RobIII schreef op maandag 05 december 2011 @ 22:17:
Ik geloof er verdomd weinig van dat een string constructor traag zou zijn.

Hij doet een memory allocation (al heeft MSVC++ een optimize voor strings < 16 tekens) en een string copy. In vergelijking met een simpele string compare is een allocatie een hele dure operatie.

[ Voor 38% gewijzigd door .oisyn op 05-12-2011 23:29 ]

[Verwijderd]

dat klinkt logisch

nou, dan is alles opgehelderd en hopelijk weer lekker snel.. morgen even profilen voor de zekerheid, maar ik geloof het eigenlijk ook gewoon wel

tnx iedereen en natuurlijk een extra pepernoot voor sjonny voor de handigste oplossing

[.oisyn]

Verwijderd schreef op maandag 05 december 2011 @ 23:00:
maar "blah" is ook een std::string..

Nee, een string literal is altijd een const char[n]. Een std::string heeft een non-explicit ctor voor const char*, en daarom kun je een string literal gebruiken waar een std::string temporary acceptabel is (met andere woorden, een const char * is impliciet converteerbaar naar std::string)

[Verwijderd]

ah okay weer wat geleerd.

overigens gebruik ik gcc, weet niet of dat nog iets optimized voor korte strings

[.oisyn]

GCC gebruikt een ranzige copy-on-write string implementatie. Herb Sutter gebruikte dat in 1999 al in een voorbeeld waarom dat performance issues heeft in multithreaded applicaties. En wie linkt er tegenwoordig nou nog tegen singlethreaded libraries... MSVC++ is na VC6 afgestapt van een CoW implementatie.

[ Voor 8% gewijzigd door .oisyn op 06-12-2011 00:00 ]

[Arjan]

Verwijderd schreef op maandag 05 december 2011 @ 22:18:
@arjan
daar heb ik ook aan gedacht, maar dan moet ik voor elk mogelijke woordje een static string maken.. dat haalt de handigheid een beetje weg (dan kan ik beter overstappen naar enums ofzo)..
[...]

Als je echt de mogelijkheid hebt om over te stappen naar enums dan zou ik daar zeker voor gaan en alles in een switch stoppen

.oisyn schreef op maandag 05 december 2011 @ 23:22:
[...]
Wat nonsens is, de compiler gaat niet voor jou bedenken dat het keer op keer constructen van een temporary kan worden geoptimaliseerd door het maar 1 keer creëren van die temporary. De ctor kan allerlei bijeffecten hebben waar de compiler geen zicht op heeft, en dus mag hij het niet optimaliseren.
[...]

De compiler zou in het geval van de std::string iig. moeten weten of er wel/niet bijeffecten zijn. Lijkt me dat wanneer er geen bijeffecten zijn ( wat tegelijkertijd eigenlijk al uitgesloten is met CoW ) dat dit geoptimaliseerd zal worden

[ Voor 42% gewijzigd door Arjan op 06-12-2011 10:03 ]

[RobIII]

.oisyn schreef op maandag 05 december 2011 @ 23:22:
Wat nonsens is, de compiler gaat niet voor jou bedenken dat het keer op keer constructen van een temporary kan worden geoptimaliseerd door het maar 1 keer creëren van die temporary. De ctor kan allerlei bijeffecten hebben waar de compiler geen zicht op heeft, en dus mag hij het niet optimaliseren.

Ow, sorry hoor Zo begreep ik Arjan's post en ik vond 't wel logisch

[Woy]

Arjan schreef op dinsdag 06 december 2011 @ 09:59:
[...]
De compiler zou in het geval van de std::string iig. moeten weten of er wel/niet bijeffecten zijn. Lijkt me dat wanneer er geen bijeffecten zijn ( wat tegelijkertijd eigenlijk al uitgesloten is met CoW ) dat dit geoptimaliseerd zal worden

std::string is natuurlijk geen onderdeel van de compiler, maar van de library. Voor hetzelfde geld link je wel tegen een andere implementatie van de std lib, en dus kan de compiler die aanname niet maken.

In Java en C# zijn dergelijke optimalisaties wel gebruikelijk, maar daar is een string natuurlijk ook gewoon onderdeel van de taal specificatie.

[ Voor 5% gewijzigd door Woy op 06-12-2011 10:32 ]

[Arjan]

Zijn std::string en vrienden niet als een template geïmplementeerd? Daar was ik eigenlijk een beetje vanuit gegaan..

[.oisyn]

Ja, maar hij doet een memory allocatie, dus dat gaat door operator new(). De compiler weet niet wat daarbinnen gebeurt.

[BenoitRoosens]

Ik heb in het verleden gelijkaardige problemen gehad (vooral op Nintendo platformen) en de oplossing was eigenlijk heel simpel indien je gw een hard-coded literal moet returnen vanuit GetValue():

C++:

const char* GetValue() const { return "literal"; }

if(GetValue() == "literal")
{
...
}

[LauPro]

Bovenstaande lijkt mij foutgevoelig. Kan je dan niet beter een wrapper class schrijven die een enum om zet naar string literals?

[BenoitRoosens]

Was puur theoretisch he, ik volg je opmerking compleet en ik heb meestal tevens een enumeration met de bijhorende "string to enum" en "enum to sting" functies...

[.oisyn]

BenoitRoosens schreef op woensdag 07 december 2011 @ 09:11:
Ik heb in het verleden gelijkaardige problemen gehad (vooral op Nintendo platformen) en de oplossing was eigenlijk heel simpel indien je gw een hard-coded literal moet returnen vanuit GetValue():

C++:

const char* GetValue() const { return "literal"; }

if(GetValue() == "literal")
{
...
}

Character arrays kun je natuurlijk niet vergelijken met ==

[ Voor 3% gewijzigd door .oisyn op 07-12-2011 10:32 ]

[MLM]

BenoitRoosens schreef op woensdag 07 december 2011 @ 09:11:
Ik heb in het verleden gelijkaardige problemen gehad (vooral op Nintendo platformen) en de oplossing was eigenlijk heel simpel indien je gw een hard-coded literal moet returnen vanuit GetValue():

C++:

const char* GetValue() const { return "literal"; }

if(GetValue() == "literal")
{
...
}

Dat gaat alleen werken als je linker de string literals merged. Daar kan je niet echt van uit gaan
een compare van const char * en const char * is niet een string compare, dat is een pointer-compare (ie, dat kan een false-negative opleveren).

Niet dat het heel veel uitmaakt, maar je kan ook ipv magische string-constantes gewoon een enum gebruiken. Dan omzeil je het hele string gebeuren in 1x, en is een stuk sneller

[.oisyn]

Oh wat ontzettend stom. Er bestaat gewoon al een operator==(std::string&, const char*) en vice versa (21.3.7.2). Als je alsnog die ctor aangeroepen ziet worden dan suckt je implementatie wel heel erg.

[Soultaker]

Woy schreef op dinsdag 06 december 2011 @ 10:30:
std::string is natuurlijk geen onderdeel van de compiler, maar van de library. Voor hetzelfde geld link je wel tegen een andere implementatie van de std lib, en dus kan de compiler die aanname niet maken.

Ik ben geen C++-expert, maar is het niet zo dat standaardfuncties door de compiler als built-ins behandeld mogen worden?

Voor ANSI C betekent dat dat de compiler in een lus als deze:

C:

void foo(char *s)
{
    for (size_t n = 0; n < strlen(s); ++n) {
         /* blabla */
    }
}

.. de call naar strlen() buiten de lus mag halen omdat 'ie er vanuit mag gaan dat die geen side effects heeft, hoewel dat uit het standaardprototype van strlen() niet valt af te leiden.

(Dat is ook de reden dat calls naar goniometrische functies als sin(), cos() enzovoorts geen function calls opleveren maar direct omgeschreven worden naar instructires als fsin, fcos, enzovoorts. Dat mag de compiler niet doen voor user-defined functies.)

Nogmaals, ik weet niet zeker of datzelfde ook geldt voor C++, maar in dat geval zou de compiler wel de aanname mogen doen dat een std::string constructor geen side effects heeft. (Al betekent dat niet per se dat 'ie de constructor weg kan optimaliseren, natuurlijk.)

.oisyn schreef op maandag 05 december 2011 @ 23:47:
GCC gebruikt een ranzige copy-on-write string implementatie.

Dit is waar, maar de C++ standaard (in ieder geval die uit 1998 -- ik ben nog niet helemaal bij wat betreft de laatste versie) geeft sowieso weinig garanties wat betreft de implementatie en performancekarakteristieken van std::string. (Ik meen dat niet eens gegarandeerd is dat de karakters achter elkaar in het geheugen staan?)

De GCC implementatie is overigens niet single threaded; hij doet locking, maar alleen met atomaire operaties op een integer (de reference count). Als ik het juist heb (maar ik heb er maar heel kort naar gekeken) wordt bij het lezen daarvan helemaal niet gesynchroniseert en bij het schrijven alleen een bus lock gedaan; de overhead daarvan valt erg mee en het geheel is sowieso lockfree. Ik denk dat de performance dus wel in orde is.

Voor korte strings is de in-place representatie van MSVC wel handig natuurlijk, maar bij grotere strings levert dat alleen maar overhead op. Het zal een beetje verschillen per applicatie of je daar feitelijk veel profijt van hebt, en dat hangt ook weer samen met de efficiëntie van de heap allocator. (Ik vermoed dat het in het gros van de applicaties weinig nut heeft.)

De moraal van het verhaal is dat als je voorspelbaar geheugenmanagement wil, je beter af bent met een std::vector<char> dan met std::string, zeker als je niet van non-standaard features gebruik wil maken.

edit: met "niet single-threaded" bedoel ik hier dat meerdere threads op verschillende container objecten mogen werken. Verschillende threads op dezelfde container laten werken wordt v.z.i.w. niet ondersteund (in in MSVC ook niet, vermoed ik, aangezien het me onmogelijk lijkt dat te implementeren zonder locking).

---

.oisyn schreef op woensdag 07 december 2011 @ 13:12:
Oh wat ontzettend stom. Er bestaat gewoon al een operator==(std::string&, const char*) en vice versa (21.3.7.2). Als je alsnog die ctor aangeroepen ziet worden dan suckt je implementatie wel heel erg.

Ik heb het even getest, en als ik met GC 4.5.3 deze code compileer:

C++:

const std::string &bar();
bool f() { return bar() == "baz"; }

Dan levert dat deze gegenereerde code op:

GAS:

.LC0:
    .string "baz"

foo():
    subq    $8, %rsp
    call    bar()
    movl    $.LC0, %esi
    movq    %rax, %rdi
    call    std::basic_string<char, std::char_traits<char>, std::allocator<char> >::compare(char const*) const
    testl   %eax, %eax
    sete    %al
    addq    $8, %rsp
    ret

Met andere woorden: er wordt geen std::string geconstrueerd en de vergelijking wordt omgeschreven naar een call naar std::string::compare() (waarschijnlijk door de operator== die je noemt te inlinen). Ik snap dus sowieso niet waarom de TS dit probleem zou hebben, tenzij hij de std::string van bar() niet by reference ontvangt, en er dus een temporary geconstruct wordt.

(Ongerelateerd: ik snap niet waarom de compiler hier 8 bytes op de stack alloceert terwijl die ruimte compleet niet gebruikt te worden. Wat mis ik?)

offtopic:
Dit is echt een situatie waarin ik graag zou mogen multiposten aangezien ik feitelijk drie verschillende reacties aan het typen ben.

[ Voor 61% gewijzigd door Soultaker op 07-12-2011 17:47 ]

[.oisyn]

Soultaker schreef op woensdag 07 december 2011 @ 17:17:
Nogmaals, ik weet niet zeker of datzelfde ook geldt voor C++, maar in dat geval zou de compiler wel de aanname mogen doen dat een std::string constructor geen side effects heeft. (Al betekent dat niet per se dat 'ie de constructor weg kan optimaliseren, natuurlijk.)

Het probleem is dat de string ctor een allocatie doet. De compiler kan niet weten wat voor sideeffects een dergelijke allocatie heeft, zeker niet gezien je operator new[] zelf mag overriden. Ook al zul je er in de praktijk alleen maar van lezen.

Persoonlijk had ik ook liever een immutable string class gezien. Dan had je ook gewoon zo'n string class direct kunnen constructen vanuit een literal zonder enige allocatie.

De GCC implementatie is overigens niet single threaded; hij doet locking, maar alleen met atomaire operaties op een integer (de reference count). Als ik het juist heb (maar ik heb er maar heel kort naar gekeken) wordt bij het lezen daarvan helemaal niet gesynchroniseert en bij het schrijven alleen een bus lock gedaan; de overhead daarvan valt erg mee en het geheel is sowieso lockfree. Ik denk dat de performance dus wel in orde is.

Als je operator[] aanroept op een non-const string dan moet er een non-const reference teruggegeven worden. Hij moet er op dat moment voor zorgdragen dat de buffer die hij gebruikt uniek is.

Overigens, een atomaire memory instructie is dan weliswaar geen volledige lock, maar wel al snel honderden tot soms duizenden cycles. Je kunt een heel hoop string compares doen in die tijd . In dat artikel wat ik net linkte van Herb Sutter stonden een aantal profiles van verschillende implementaties.

edit: met "niet single-threaded" bedoel ik hier dat meerdere threads op verschillende container objecten mogen werken. Verschillende threads op dezelfde container laten werken wordt v.z.i.w. niet ondersteund (in in MSVC ook niet, vermoed ik, aangezien het me onmogelijk lijkt dat te implementeren zonder locking).

Klopt. Het probleem van copy-on-write is dat localiteit niet meer duidelijk is. Multithreaded apps kun je geheel lock free maken door elke thread gewoon zijn eigen data te geven. Bij een copy-on-write string heb je daar geen controle over, want ookal heeft de thread zijn eigen string object, de onderliggende buffer kan mogelijk alsnog geshared zijn, en dus is "locking" (ik gebruik het woord hier wat vrijer, en beschouw atomaire operaties als increment en test-and-set ook als locking) sowieso nodig. Zelfs ook al deelt geen enkele thread in de praktijk daadwerkelijk data. Ik ben dus ook geen fan van een dergelijk paradigma.

(Ongerelateerd: ik snap niet waarom de compiler hier 8 bytes op de stack alloceert terwijl die ruimte compleet niet gebruikt te worden. Wat mis ik?)

Het 16-byte aligned houden van de stack misschien? De stack wordt wel gebruikt voor de returnadressen van de twee calls in de functie. Wellicht dat GCC garandeert dat de stack altijd 16-byte aligned is na de aanroep van elke functie? Wel handig als je daar SSE register van/naar wilt lezen/schrijven.

[ Voor 3% gewijzigd door .oisyn op 07-12-2011 20:34 ]

[Soultaker]

.oisyn schreef op woensdag 07 december 2011 @ 20:32:
Het probleem is dat de string ctor een allocatie doet. De compiler kan niet weten wat voor sideeffects een dergelijke allocatie heeft, zeker niet gezien je operator new[] zelf mag overriden.

Ah, dat is vervelend inderdaad.

Als je operator[] aanroept op een non-const string dan moet er een non-const reference teruggegeven worden. Hij moet er op dat moment voor zorgdragen dat de buffer die hij gebruikt uniek is.

Klopt, maar om dat te checken hoeft 'ie alleen de reference count te lezen (zonder locken, want die read is al atomair, en als de reference count 1 is, is het per definitie onmogelijk dat er een andere thread via een ander object op dezelfde buffer werkt).

Als de buffer shared is moet 'ie eerst gekopieerd worden en dan moet de reference count atomair verlaagd worden met 1. Dat moet met een bus lock (interlocked decrement of iets dergelijks) wat enige overhead kan hebben, maar dit komt maximaal één keer voor per std::string instance (amortized).

De reference count hoeft niet eens volatile te zijn, dus die check is te optimaliseren. Als je een string indexeert in een lusje kan de reference count check gewoon buiten de loop gehaald worden, bijvoorbeeld.

.oisyn schreef op woensdag 07 december 2011 @ 20:32:
Het 16-byte aligned houden van de stack misschien? De stack wordt wel gebruikt voor de returnadressen van de twee calls in de functie.

Ah, dat zal het zijn waarschijnlijk!