[C++] std::string direct buffer write-access?

[Olaf van der Spek]

Is het mogelijk direct de 'inhoud' van een string te editen?
Dus bijvoorbeeld:

code:

std::string s;
s.reserve(1 << 10);
char* w = s.data();

En dan met die w de buffer vullen?

[Verwijderd]

ik denk dat de compiler error die je krijgt op dit stukje code het antwoord al verraad niet?

code:

error C2440: 'initializing' : cannot convert from 'const char *' to 'char *'

[ Voor 11% gewijzigd door Verwijderd op 22-11-2002 19:25 ]

[Verwijderd]

nee. Wat jij doet mag al niet eens, de .data() returned namelijk een const char *, geen char *.

Je kan de inhoud van de string wel modificeren met de member functies van basic_string, zoals append(), replace(), erase(), =, insert(), etc.
Wat jij wilt is een gewone character pointer. Sterker nog, de hele string class is er juist voor om dit soort grappen te voorkomen...

[Verwijderd]

overigens : waarom bouw je niet eerst je string op in een character array, en contstueer je vervolgens van daar af je string object?

dus

C++:

char sz[256];
snprintf(sz,256,"%s %s\n","hello","world");
std::string str(sz);

[Olaf van der Spek]

Dat het zo niet werkt weet ik, het was ook maar een voorbeeld van hoe het zou werken.

Verwijderd schreef op 22 November 2002 @ 19:29:
overigens : waarom bouw je niet eerst je string op in een character array, en contstueer je vervolgens van daar af je string object?

dus

C++:

char sz[256];
snprintf(sz,256,"%s %s\n","hello","world");
std::string str(sz);

Dat is een redelijke oplossing met een nadeel: je kopieert de data onnodig in std::string str(sz).

[Verwijderd]

Wellicht moet je iets beter uitleggen wat je wil bereiken?

[Olaf van der Spek]

Ik wil dus in feite in een functie die een string returned die string opbouwen zonder die onnodige kopie en zonder de overhead van de string functies.

[Verwijderd]

De overhead van de string functies is minimaal (nl. de functioncall). Als je echt zo efficient mogelijk wilt proggen zal je naar basis C terug moeten. Gewoon zelf doen dan dus. Het is gewoon een afweging die je moet maken. Ik denk dat tegenwoordig in het merendeel van de gevallen geld dat de huidige PC's snel zat zijn en dat beetje overhead niet opweegt tegen de betere maintainability/reusability van je code.

edit:

Overigens wordt het op deze manier natuurlijk nooit echt efficient. Omdat je iets met de ge-returnde string wilt gaan doen (assignen aan variabele?) wordt die alsnog in z'n geheel gekopieerd...

[ Voor 22% gewijzigd door Verwijderd op 22-11-2002 19:52 ]

[MSalters]

std::string::reserve( ), dan is append( ) daarna goedkoop.

[Olaf van der Spek]

Verwijderd schreef op 22 November 2002 @ 19:50:
De overhead van de string functies is minimaal (nl. de functioncall). Als je echt zo efficient mogelijk wilt proggen zal je naar basis C terug moeten. Gewoon zelf doen dan dus. Het is gewoon een afweging die je moet maken. Ik denk dat tegenwoordig in het merendeel van de gevallen geld dat de huidige PC's snel zat zijn en dat beetje overhead niet opweegt tegen de betere maintainability/reusability van je code.

Het gaat om wat functies in een forum. Dat kan bijna nooit snel genoeg zijn. Deze functies worden soms wel tig-duizend keer aangeroepen.

edit:

Overigens wordt het op deze manier natuurlijk nooit echt efficient. Omdat je iets met de ge-returnde string wilt gaan doen (assignen aan variabele?) wordt die alsnog in z'n geheel gekopieerd...

Als je hem assigned kan dat gewoon by-reference (in VC6).
Maar wat je ook doet, die laatste kopie in de constructor is onnodig.

[Olaf van der Spek]

MSalters schreef op 22 November 2002 @ 19:51:
std::string::reserve( ), dan is append( ) daarna goedkoop.

Nog steeds relatief duur. Ik heb de volgende functie nu herschreven om een 256 byte buffer te gebruiken indien mogelijk, maar dat is nog steeds niet het beste.
Het gaat om functies als:

C++:

string web_encode(const string& v, bool add_br)
{
    string r;
    int i = 0;
    while (i < v.length())
    {
        char c = v[i++];
        switch (c)
        {
        case '\r':
            break;
        case '\n':
            if (add_br)
                r += "<br>";
            r += '\n';
            break;
        case '<':
            r += "&lt;";
            break;
        case '>':
            r += "&gt;";
            break;
        case '&':
            r += "&amp;";
            break;
        case '"':
            r += "&quot;";
            break;
        default:
            r += c;
        }
    }
    return r;
}

[ Voor 22% gewijzigd door Olaf van der Spek op 22-11-2002 20:16 ]

[Verwijderd]

Als je hem assigned kan dat gewoon by-reference (in VC6).

Wat bedoel je hier precies mee?

C++:

std::string &str = getstring();
doeiets(str);
str = getstring();
doeiets(str);

bovenstaande gaat namelijk niet goed tenzij de = operator voor std::string geimplementeerd is (deze wordt namelijk bij str = ... aangeroepen, en dat was nou juist niet de bedoeling...)

[ Voor 23% gewijzigd door Verwijderd op 22-11-2002 20:38 ]

[Verwijderd]

overigens zou ik de if (add_br) buiten je while() halen, nu wordt daar iedere keer op gechecked...

is het trouwens niet handiger om gewoon een subclass van std::string te deriven die een web_translate method heeft?

[ Voor 43% gewijzigd door Verwijderd op 22-11-2002 20:41 ]

[Olaf van der Spek]

Verwijderd schreef op 22 November 2002 @ 20:37:
[...]

Wat bedoel je hier precies mee?

C++:

std::string &str = getstring();
doeiets(str);
str = getstring();
doeiets(str);

bovenstaande gaat namelijk niet goed tenzij de = operator voor std::string geimplementeerd is (deze wordt namelijk bij str = ... aangeroepen, en dat was nou juist niet de bedoeling...)

Ik bedoel dat als je std::string str(getstring) doet, er geen kopie van de inhoud gemaakt hoeft te worden.

Verwijderd schreef op 22 November 2002 @ 20:39:
overigens zou ik de if (add_br) buiten je while() halen, nu wordt daar iedere keer op gechecked...

is het trouwens niet handiger om gewoon een subclass van std::string te deriven die een web_translate method heeft?

Zo vaak komt \n niet voor, dus dat is niet nodig. Waarom zou dat handiger zijn?

[ Voor 27% gewijzigd door Olaf van der Spek op 22-11-2002 20:54 ]

[.oisyn]

OlafvdSpek schreef op 22 november 2002 @ 20:15:
[...]

Nog steeds relatief duur. Ik heb de volgende functie nu herschreven om een 256 byte buffer te gebruiken indien mogelijk, maar dat is nog steeds niet het beste.
Het gaat om functies als:

C++:

string web_encode(const string& v, bool add_br)
{
    string r;
    int i = 0;
    while (i < v.length())
    {
        char c = v[i++];
        switch (c)
        {
        case '\r':
            break;
        case '\n':
            if (add_br)
                r += "<br>";
            r += '\n';
            break;
        case '<':
            r += "<";
            break;
        case '>':
            r += ">";
            break;
        case '&':
            r += "&";
            break;
        case '"':
            r += """;
            break;
        default:
            r += c;
        }
    }
    return r;
}

dit is niet echt een handige methode. Ik heb zelf zo'n zelfde functie gebruikt in de syntax highlighter die hier nu op GoT draait (even patsen ), maar in plaats van steeds 1 char aan de buffer toe te voegen kijkt ie heerst hoeveel chars er komen die niet een van die chars zijn die je moet aanpassen. Dit was echter een C-functie, met std::string kan dat controleren heel gemakkelijk met std::string::find_first_of ()

dat wordt zoiets:

C++:

string web_encode (const string & s)
{
    string r;
    size_t pos = 0, newpos;

    r.reserve (s.length ());  // iig zoveel chars, kan alleen langer worden
    while ((newpos = s.find_first_of ("\n&<>\"", pos) != string::npos)
    {
        if (pos < newpos)     // er is wat te doen
            r.append (s, pos, newpos - pos);
        switch (s[newpos])
        {
            // hier je switch
        }
        pos = newpos + 1;
    }

    if (pos < s.length ())
        r.append (s, pos, s.length () - pos);

    return r;
}

[Olaf van der Spek]

.oisyn schreef op 22 November 2002 @ 21:21:
dit is niet echt een handige methode. Ik heb zelf zo'n zelfde functie gebruikt in de syntax highlighter die hier nu op GoT draait (even patsen ), maar in plaats van steeds 1 char aan de buffer toe te voegen kijkt ie heerst hoeveel chars er komen die niet een van die chars zijn die je moet aanpassen. Dit was echter een C-functie, met std::string kan dat controleren heel gemakkelijk met std::string::find_first_of ()

Is het forum volledig in C++ geschreven of een combo van talen?
Jouw functie is inderdaad beter dan mijn eerste functie, maar is die ook sneller dan wanneer je inderdaad direct naar std::string kon schrijven?

[.oisyn]

GoT (React) is een php forum, mijn highlighter is een php module gemaakt in C
Hoe bedoel je, "direct naar std::string schrijven"?
Je hebt de buffer niet nodig, met append kun je er gewoon zooi achter zetten. Maar als de buffer van die string niet groot genoeg is, dus moet er een nieuwe aangemaakt worden en dan de contents worden gekopieerd van de oude naar de nieuwe. De ideaalste situatie is als je van tevoren weet hoe groot de nieuwe buffer gaat worden, zodat je die kunt reserveren met reserve ()

Dat is natuurlijk wel te tellen, door al die tekens eerst op te gaan zoeken en dan uitrekenen hoe groot te string wordt als je die tekens vervangt door die html strings. Daarna doe je een reserve () en vervolgens ga je er opnieuw doorheen. Dit lijkt omslachtig, maar het zorgt ervoor dat een hoop buffers alloceren en kopieren niet nodig is, en dus uiteindelijk sneller is bij strings waar veel gereplaced wordt

[MSalters]

OlafvdSpek schreef op 22 november 2002 @ 20:15:
[...]

Nog steeds relatief duur.
[...]
Ik heb de volgende functie nu herschreven om een 256 byte buffer te gebruiken indien mogelijk, maar dat is nog steeds niet het beste.
Het gaat om functies als:

C++:

string web_encode(const string& v, bool add_br)
{
    string r;
    int i = 0;
    while (i < v.length())
    {
        char c = v[i++];
        switch (c)
        {
        case '\r':
            break;
        case '\n':
            if (add_br)
                r += "<br>";
            r += '\n';
            break;
        case '<':
            r += "&lt;";
            break;
        case '>':
            r += "&gt;";
            break;
        case '&':
            r += "&amp;";
            break;
        case '"':
            r += "&quot;";
            break;
        default:
            r += c;
        }
    }
    return r;
}

Dat algoritme is mis. Dit soort conversies wil je inderdaad in een loop doen. Maar hoe lang is die string v? Als die orde-grootte 1K is, dan zou ik in scan 1 via een LUT bepalen hoe lang de return string wordt, die in een keer reserven ( een buffer allocatie, precies genoeg uninitialized geheugen ) en die in scan 2 vullen. Je schrijft alleen naar het geheugen wat je daadwerkelijk gaat retourneren -> 0 copies.

Nu, omdat je niet weet hoe lang de output string is, kopieer je bij de reallocaties elk karakter gemiddeld 1x. Hetzelfde geldt voor je char[256] oplossing, daar zal het toch uit gekopieerd moeten worden.

const char[]s optellen is niet efficient, omdat je elke keer een strlen() moet doen om te bepalen hoe lang dat is. Stop de chars een keer in een std::string, en de size() is beschikbaar in O(1) ipv O(n).

Een andere tip is om de add_br decision te hoisten. Nu branch je v.size() keer, dat hoeft maar 1 keer ( hij verandert niet tijdens de loop ).

Iha is het efficienter om int i en v[i] te vervangen door een string iterator, alhoewel het op de x86 niet uitmaakt.

Kortom, ga er niet van uit dat je weet waar de bottlenecks zitten. Ik heb recent een C programma herschreven in C++, en daarbij de char[]s vervangen door echte strings. Het programma deed niet veel meer dan strings manipuleren. De runtime ging van 16-24 uur naar 1 uur. Waarom? Ik gebruikte een profiler, en verbeterde wat er daadwerkelijk uitmaakte, de ene functie die in m'n eerste probeersel 4 uur duurde.

[Olaf van der Spek]

.oisyn schreef op 22 november 2002 @ 21:58:
Dat is natuurlijk wel te tellen, door al die tekens eerst op te gaan zoeken en dan uitrekenen hoe groot te string wordt als je die tekens vervangt door die html strings. Daarna doe je een reserve () en vervolgens ga je er opnieuw doorheen. Dit lijkt omslachtig, maar het zorgt ervoor dat een hoop buffers alloceren en kopieren niet nodig is, en dus uiteindelijk sneller is bij strings waar veel gereplaced wordt

Maar je blijft met het probleem zitten dat append onnodig controleert of het wel past.

[Olaf van der Spek]

MSalters schreef op 22 November 2002 @ 22:14:
Dat algoritme is mis. Dit soort conversies wil je inderdaad in een loop doen. Maar hoe lang is die string v? Als die orde-grootte 1K is, dan zou ik in scan 1 via een LUT bepalen hoe lang de return string wordt, die in een keer reserven ( een buffer allocatie, precies genoeg uninitialized geheugen ) en die in scan 2 vullen. Je schrijft alleen naar het geheugen wat je daadwerkelijk gaat retourneren -> 0 copies.

De string v is relatief kort (vaak tot 32 chars). Eerst uitrekenen hoe lang die string wordt begrijp ik.

Nu, omdat je niet weet hoe lang de output string is, kopieer je bij de reallocaties elk karakter gemiddeld 1x. Hetzelfde geldt voor je char[256] oplossing, daar zal het toch uit gekopieerd moeten worden.

const char[]s optellen is niet efficient, omdat je elke keer een strlen() moet doen om te bepalen hoe lang dat is. Stop de chars een keer in een std::string, en de size() is beschikbaar in O(1) ipv O(n).

Ik had gehoopt dat de optimizer dat tijdens compile-time zou doen.

Een andere tip is om de add_br decision te hoisten. Nu branch je v.size() keer, dat hoeft maar 1 keer ( hij verandert niet tijdens de loop ).

Je branced alleen als er '\n' in zit, niet bij elk char toch?

Iha is het efficienter om int i en v[i] te vervangen door een string iterator, alhoewel het op de x86 niet uitmaakt.

Kortom, ga er niet van uit dat je weet waar de bottlenecks zitten. Ik heb recent een C programma herschreven in C++, en daarbij de char[]s vervangen door echte strings. Het programma deed niet veel meer dan strings manipuleren. De runtime ging van 16-24 uur naar 1 uur. Waarom? Ik gebruikte een profiler, en verbeterde wat er daadwerkelijk uitmaakte, de ene functie die in m'n eerste probeersel 4 uur duurde.

Ik heb ook geprofiled en deze functie kostte 100 ms totaal (main was 2.200 s). De functie werd geloof ik 1000 x aangeroepen.

[hobbit_be]

als je weet hoe groot de meeste zijn een hoop buffers aannmaken van die grote (32Bytes/64Bytes). Dan gewoon al de tips uitvoeren en dan de pointer doorgeven (wat memory loss neem je er maar bij - ik neem aan dat het om speed gaat?). CString van M$ gebruikt die tricks ook en die is super-snel... Tja ze doen ook sommige dingen deftig

[Olaf van der Spek]

Ik ben nog een ding vergeten: kijken of er uberhaupt wel een edit nodig is. Dat zal wel de belangrijkste optimalisatie zijn.

[.oisyn]

OlafvdSpek schreef op 23 november 2002 @ 11:41:
[...]

Maar je blijft met het probleem zitten dat append onnodig controleert of het wel past.

die check stelt niets voor, een paar clockcycles