[c++] vector & geheugen vrijgeven

[CyBoB]

ik ben hier nu al een paar dagen mee bezig geweest, maar ik kom er gewoon echt niet meer uit. het kan zijn dat mijn ontwerp gewoon niet goed is maar ik doe het volgende.

ik heb ergens een vector die pointers naar een Entry class bevat:

C++:

std::vector<Entry*> m_entries;

de vector wordt gevuld door een Parser die voor elke regel die hij leest uit een file bepaalde gegevens bijhoud die ik gedurende de hele applicatie nodig heb, tenzij:

a) de applicatie afsluit ... resources vrijgeven
b) de parser opdracht krijgt een nieuwe file te lezen... ook resources vrijgeven en daarna wordt de vector weer opnieuw gebruikt.

wanneer ik dus die resources wil vrijgeven wil ik dus al die Entry's delete'en. dit lukt alleen op een vrij baggere en zeer langzame manier en ik zie door de bomen het bos niet meer. wat ik heb geprobeert is gewoon de vector doorlopen en telkens delete aanroepen op de huidige pointer.... werkt wel, maar heeel langzaam.

C++:

//dit kost heel veel tijd en helemaal niet netje naar mijn id
for(int i = 0; i < m_entries.size(); i++){
    delete m_entries[i];
}

//de vector doorlopen met een iterator werkt ook niet, hetzelfde probleem
for(std::vector<Entry*>::iterator it = m_entries.begin() ; it < m_entries.end(); it++){
    delete (*it);
}

//toen dacht ik, he vector is gewoon een wrapper om een array heen, misschien kan ik wel gewoon delete[] erop aanroepen
delete[] m_entries; //genereert error C2440, wat duidelijk is natuurlijk

m_entries.erase(m_entries.begin(), m_entries.end()); //dit maakt de vector leeg, duidelijk, maar geeft niet de resources vrij

//hetzelfde met clear();
m_entries.clear(); //blaat

code:

//toch ff nog de error
error C2440: 'delete' cannot convert 'std::vector<_Ty>' to 'void *'   with   [    _Ty=Entry*    ]

hoop dat het duidelijk is.

waar zit mijn denkfout? is het wel mogelijk? moet ik een andere stuctuur gebruiken?

[koli-man]

Volgens mij hoef je toch niet door de vector te lopen?

Als je zorgt dat je voor Entry een goede destructor hebt, dan doet de destructor van std::vector de rest voor jou. Het is toch een template functie die de destructor van de in dit geval Entry aanroept.

[Robtimus]

Het zijn pointers naar Entry's. Daar ben je als programmeur zelf verantwoordelijk voor. Bij gewone Entry's zou je gelijk hebben, maar met pointers raakt alleen de pointer out of scope (dus deconstruction van alleen de pointer), en niet het object op de heap. Gevolg: memleak.

[CyBoB]

IceManX schreef op 12 mei 2004 @ 16:09:
Het zijn pointers naar Entry's. Daar ben je als programmeur zelf verantwoordelijk voor. Bij gewone Entry's zou je gelijk hebben, maar met pointers raakt alleen de pointer out of scope (dus deconstruction van alleen de pointer), en niet het object op de heap. Gevolg: memleak.

idd dat was mijn conclusie ook en die memleak is best enorm als ik een file van 100mb open dus er moet toch een manier zijn om dat geheugen weer vrij te kunnen geven?

ik vrees trouwens dat wanneer ik door de vector heen loop en delete aanroep er op de achtergrond steeds weer een nieuw indexering plaatsvind van de vector waardoor het zo ongelovelijk lang duurt. zelfs als ik van achter naar voren loop (lijkt me logisch dat er dan geen nieuwe indexering plaatsvind) is het rete langzaam.

[.oisyn]

CyBoB schreef op 12 mei 2004 @ 15:59:
wanneer ik dus die resources wil vrijgeven wil ik dus al die Entry's delete'en. dit lukt alleen op een vrij baggere en zeer langzame manier en ik zie door de bomen het bos niet meer.

Hoeveel entries staan er dan wel niet in zo'n vector? Je gebruik van vector is het probleem niet, ik denk dat de destructor van een Entry gewoonweg teveel tijd kost. Ik vermoed dat je hetzelfde probleem hebt als je geen vector gebruikte maar gewoon een Entry **

Overigens

C++:

delete[] m_entries; //genereert error C2440, wat duidelijk is natuurlijk 

Je denkwijze was: vector is een array van Entry *, dus eigenlijk een Entry **. Natuurlijk lukt het niet zo, maar al zou je een delete[] op een Entry ** aanroepen dan delete ie alleen maar de array van Entry * elementen, en dus niet de Entries zelf (gevolg: memleak)

[.oisyn]

CyBoB schreef op 12 mei 2004 @ 16:13:
ik vrees trouwens dat wanneer ik door de vector heen loop en delete aanroep er op de achtergrond steeds weer een nieuw indexering plaatsvind van de vector waardoor het zo ongelovelijk lang duurt. zelfs als ik van achter naar voren loop (lijkt me logisch dat er dan geen nieuwe indexering plaatsvind) is het rete langzaam.

Nee, je roept een delete aan op een Entry *. De waarde in de vector blijft echter bestaan, dus de vector blijft gevuld. Een delete van een Entry * zal niet ineens zorgen dat de betreffende Entry * uit de vector gehaald wordt. Je moet dus alsnog achteraf een clear () doen.

[ Voor 4% gewijzigd door .oisyn op 12-05-2004 16:17 ]

[curry684]

Even heel kort door de bocht: lees nog eens even bij op wat een pointer nu eigenlijk fysiek is en wat zijn inhoud is, want dat heb je er duidelijk nog niet goed inzitten. Denk eens na over de achterliggende structuur op geheugenniveau, dan zie je vanzelf waarom je hier de mist in gaat

[CyBoB]

.oisyn schreef op 12 mei 2004 @ 16:15:
[...]


Hoeveel entries staan er dan wel niet in zo'n vector? ...enz

veel!!

ik moet voor elke regel die ik parse bepaalde info bijhouden. nu kunnen het aantal regels varieren van enkele 10 tallen tot gerust 600 000 + regels.

[.oisyn]

Dan is dat je probleem, en niet zozeer het gebruik van een vector
Je zou een std::deque<Entry> kunnen gebruiken (ja dat lees je goed, geen pointer, maar het object zelf). Dan wordt er geen geheugen gealloceerd per Entry, en hoeven al die kleine blokjes dus ook niet vrijgegeven te worden. Bijkomend voordeel is dat je nu gewoon de deque kan destructen, en al je Entries verdwijnen ook automatisch

De reden voor een deque tov een vector is dat een vector een contiguous memory block gebruikt, die steeds langer gemaakt moet worden als ie vol zit en er meer Entries bij moeten. Dat resulteert in een nieuwe allocatie van de grootte van de vorige plus een beetje, een kopie van de oude naar de nieuwe buffer, en dan het verwijderen van de oude buffer. Een deque heeft hier minder last van, omdat ie een lijst van buffers gebruikt

[ Voor 87% gewijzigd door .oisyn op 12-05-2004 16:29 ]

[curry684]

CyBoB schreef op 12 mei 2004 @ 16:25:
[...]


veel!!

ik moet voor elke regel die ik parse bepaalde info bijhouden. nu kunnen het aantal regels varieren van enkele 10 tallen tot gerust 600 000 + regels.

En wat zit er in die entry? Gebruik je random access op de regels of itereer je altijd? Moet je er wel eens in zoeken? Waarom gebruik je een vector van pointers ipv een vector van objects?

edit:
tipje als je zelf tekstfiles splitst: tel vantevoren het aantal newlines en alloceer in 1 klap voldoende Entries die je vervolgens hardpointered zelf opsplitst om je app 10 keer sneller te maken... en/of manually replace the newlines met nullen zodat je hardpointered de read-buffer in kunt wijzen, nog een factor 10 oid

[ Voor 28% gewijzigd door curry684 op 12-05-2004 16:30 ]

[Verwijderd]

Je geeft hem goed vrij. Je vector wordt niet opnieuw geindexeerd als je een delete doet.
Je doet alles goed, maar het zou wel eens een beetje met de destructor van je entry te maken kunnen hebben, en met de aantallen.
Probeer eens bij elke 1000 of 10000 een stipje op het scherm te printen.
Probeer eens gewoon met een iterator door die vector heen te lopen en te kijken hoe snel dat dan gaat.

G.

[CyBoB]

curry684 schreef op 12 mei 2004 @ 16:28:
[...]

En wat zit er in die entry? Gebruik je random access op de regels of itereer je altijd? Moet je er wel eens in zoeken? Waarom gebruik je een vector van pointers ipv een vector van objects?

edit:
tipje als je zelf tekstfiles splitst: tel vantevoren het aantal newlines en alloceer in 1 klap voldoende Entries die je vervolgens hardpointered zelf opsplitst om je app 10 keer sneller te maken... en/of manually replace the newlines met nullen zodat je hardpointered de read-buffer in kunt wijzen, nog een factor 10 oid

Entry is niks meer dan een data object dat een stuk of 6 integer waardes bijhoud en een pointer naar een string (welke 99.9% van de gevallen gewoon NULL blijft). de destructor van Entry doet verder niks meer dan wanneer deze string != NULL is delete'en.

verder access ik de vector op index volledig random. ik had voor een vector gekozen omdat ik niet eerst door de hele file wil lezen om het aantal regels te bepalen en zo een array te creeeren en daarna nog een keer de file te lezen om het array te vullen. met files van +-100mb is dat niet echt leuk.

..ik ga je tip nog een bekijken, snap niet helemaal wat je bedoelt

Verwijderd schreef op 12 mei 2004 @ 16:29:
Je geeft hem goed vrij. Je vector wordt niet opnieuw geindexeerd als je een delete doet.
Je doet alles goed, maar het zou wel eens een beetje met de destructor van je entry te maken kunnen hebben, en met de aantallen.
Probeer eens bij elke 1000 of 10000 een stipje op het scherm te printen.
Probeer eens gewoon met een iterator door die vector heen te lopen en te kijken hoe snel dat dan gaat.

G.

gewoon door de vector itereren werk vliegensvlug 60000 regels is hij zo doorheen... pas als ik het "delete (*it);" gaat het berg afwaarts.

[curry684]

CyBoB schreef op 12 mei 2004 @ 16:39:
[...]


Entry is niks meer dan een data object dat een stuk of 6 integer waardes bijhoud en een pointer naar een string (welke 99.9% van de gevallen gewoon NULL blijft). de destructor van Entry doet verder niks meer dan wanneer deze string != NULL is delete'en.

Waarom gebruik je geen std::vector<Entry> dan maar doe je moeilijk met die pointers? Iedere implementatie van vector doet namelijk 'batch allocates' waardoor je maar ongeveer 20 news en deletes doet ipv 600000...

[ Voor 3% gewijzigd door curry684 op 12-05-2004 16:47 . Reden: html-rechten... :| ]

[.oisyn]

Heb je mijn vorige post nog gelezen?
[rml].oisyn in "[ c++] vector & geheugen vrijgeven"[/rml]

.edit: als een Entry idd maar zo weinig is kun je net zo goed een vector gebruiken ja, ipv de deque die ik voorstelde (wel een goede copyconstructor implementeren!)

[ Voor 40% gewijzigd door .oisyn op 12-05-2004 16:46 ]

[CyBoB]

ik weet ondertussen ook alweer waarom ik gekozen had voor een vector van pointers ipv.. euh objecten? iig ik std::vector<Entry*> ipv std::vector<Entry>. ik wil namelijk Entry objecten die in de vector staan kunnen muteren. als ik dan std::vector<Entry> gebruik dan krijg ik steeds een copy terug van m_entries.at(); en das lastig.


ps. sorry als we misschien een beetje langs elkaar heen praten, maar ik probeer alle reacties ff te verwerken

[.oisyn]

Uhm, je krijgt geen kopie terug maar een referentie, en bovendien is de [] operator sneller (maar minder veilig omdat die geen range check doet). Als je een kopie terug kreeg had een vector weinig nut als container

[ Voor 22% gewijzigd door .oisyn op 12-05-2004 16:52 ]

[CyBoB]

.oisyn schreef op 12 mei 2004 @ 16:51:
Uhm, je krijgt geen kopie terug maar een referentie, en bovendien is de [] operator sneller (maar minder veilig omdat die geen range check doet). Als je een kopie terug kreeg had een vector weinig nut als container

hmm... begin me hier nu een beetje dom te voelen :\

ik denk dat ik maar eens ga kijken wat er eerst dan fout ging met het gebruik van Entry objecten ipv pointers. moet echter nu eerst naar huis. ik laat nog weten wanneer ik eruit ben

[MSalters]

curry684 schreef op 12 mei 2004 @ 16:28:
[...]

edit:
tipje als je zelf tekstfiles splitst: tel vantevoren het aantal newlines en alloceer in 1 klap voldoende Entries die je vervolgens hardpointered zelf opsplitst om je app 10 keer sneller te maken... en/of manually replace the newlines met nullen zodat je hardpointered de read-buffer in kunt wijzen, nog een factor 10 oid

Valt in de praktijk best tegen, omdat de allocatie van een groot blok veel langzamer kan zijn dan N kleinere blokken. Dat wordt netjes opgelost door een std::deque<Entry>.

[MSalters]

CyBoB schreef op 12 mei 2004 @ 16:39:
[...]


Entry is niks meer dan een data object dat een stuk of 6 integer waardes bijhoud en een pointer naar een string (welke 99.9% van de gevallen gewoon NULL blijft). de destructor van Entry doet verder niks meer dan wanneer deze string != NULL is delete'en.

Eerste optimalisatie: delete NULL; is volledig veilig. Dump de if(ptr!=NULL) check, zijn weer 600,000 if statements. Scheelt misschien wel 10 ms.

verder access ik de vector op index volledig random. ik had voor een vector gekozen omdat ik niet eerst door de hele file wil lezen om het aantal regels te bepalen en zo een array te creeeren en daarna nog een keer de file te lezen om het array te vullen. met files van +-100mb is dat niet echt leuk.

..ik ga je tip nog een bekijken, snap niet helemaal wat je bedoelt

[...]

gewoon door de vector itereren werk vliegensvlug 60000 regels is hij zo doorheen... pas als ik het "delete (*it);" gaat het berg afwaarts.

600,000 heap objects maakt de zaak erg duur. Als je alleen in deze context Entry objecten dynamisch aanmaakt zou je een pool allocator kunnen gebruiken voor Entry::operator new(). Dan zijn de delete's goedkoop, want no-ops. Het enige wat je doet is na de 600,000 deletes in een keer alle memory weggooien. Dat scheelt ook nog eens de extra bytes aan overhead die nodig zijn om individuele Entry objecten weg te gooien. Nog makkelijker is natuurlijk std::deque<Entry>, als dat voor je werkt. Dat zijn maar een paar honderd heap objects, in plaats van een paar honderd duizend.

[Soultaker]

MSalters schreef op 12 mei 2004 @ 17:19:
Valt in de praktijk best tegen, omdat de allocatie van een groot blok veel langzamer kan zijn dan N kleinere blokken. Dat wordt netjes opgelost door een std::deque<Entry>.

Gegeven was dat er veel random accesses gedaan werden naar de elementen en daarvoor is een vector wel het snelste; de kans is aanwezig dat dat opweegt tegen de iets hogere allocatiekosten. Daarbij is het dealloceren van een groot blok geheugen een stuk efficiënter dan het dealloceren van meerdere stukken.

[curry684]

MSalters schreef op 12 mei 2004 @ 17:19:
[...]

Valt in de praktijk best tegen, omdat de allocatie van een groot blok veel langzamer kan zijn dan N kleinere blokken.

1 tegen 600000 kan ik je echt uit ervaring melden dat dat onder NT enorme factoren scheelt. Dat het geen 600000 is zei ik ook al en claimde ik niet, maar enkele tientallen gegarandeerd (op de pure memory-overhead that is).

[CyBoB]

ik heb er vandaag weer naar gekeken en heb het probleem opgelost op de volgende manier:

ik heb in eerste instantie toch gekozen voor

C++:

std::vector<Entry> m_entries; //dus geen pointers meer

en voor de rest heb ik de Entry class een beetje aangepast zodat ik nu gebruik maakt van een std::string om wat text bij te houden ipv een TCHAR * (array dus). dit omdat er steeds wat fout ging met de copy constructor (welke naar mijn idee helemaal goed was ) en met std::string niet meer.

ik moet zeggen dat het nu aardig snel is. geheugen vrijgeven met

C++:

m_entries.clear();

is in een factie van een seconden gedaan met een grote van 600000 Entry's

[.oisyn]

CyBoB schreef op 13 mei 2004 @ 11:50:
dit omdat er steeds wat fout ging met de copy constructor (welke naar mijn idee helemaal goed was ) en met std::string niet meer.

Kun je je code van die copy-ctor eens posten? Ik vermoed namelijk dat je gewoon een assignment doet, en geen kopie maakt van de char buffer van de andere instantie. Je hebt dan 2 instanties die wijzen naar dezelfde buffer, en als een van die 2 wordt gedestruct, dan verdwijnt de buffer ook. Maar de ander gebruikt die nog, en dat gaat natuurlijk fout.

---

Je kunt het trouwens nog verder optimaliseren door een reference-counted string te gebruiken. Het punt van std::string is dat het zich gedraagt als een value-type. Als je die dus kopieert, dan wordt de interne buffer gedupliceert (meestal, maar dat kan natuurlijk per implementatie verschillen. Ik geloof dat VC++ 6.0 een ref-counted buffer implementatie voor std::string gebruikte?).

Het punt is namelijk dat, zoals ik al eerder zei, std::vector een contiguous block geheugen gebruikt. Als de interne buffer van de vector vol zit met, zeg, 1000 elementen, en je voegt er een aan toe, dan wordt er een nieuwe buffer gecreëert van bijvoorbeeld 1500 elementen. De oude buffer wordt dan gekopieerd naar de nieuwe door voor ieder van die 1000 elementen een copy-ctor aan te roepen, waardoor je dus tijdelijk 1000 kopies van je strings aanmaakt, terwijl de 1000 originelen even later weer weggegooid worden. En dat gebeurt weer met 1500 elementen als je vector even later weer vol zit.

Met een refcounted string is het simpelweg de pointer naar de buffer kopieren en de refcounter ophogen. Destruction is de refcounter verlagen, en als ie 0 is dan de buffer verwijderen. Op die manier voorkom je dus onnodige memory-allocaties en buffercopies

[ Voor 53% gewijzigd door .oisyn op 13-05-2004 13:15 ]

[CyBoB]

oke, omdat dit alles in een groter project plaatsvind heb ik eerst even een klein test programmatje geschreven om het een en ander te testen. dit werkt bijna hetzelfde als in het uiteindelijk programma.

hier komt me copy constructor... (MemEntry is trouwens een loos object met wat int attributen en dus die string (of iig de pointer))

C++:

MemEntry::MemEntry(const MemEntry &entry){
    a = entry.a;  //paar loze ints, das verder geen probleem
    b = entry.b;
    c = entry.c;
    d = entry.d;
    e = entry.e;
    f = entry.f;

    text = new TCHAR[_tcslen(entry.text)+1];
    _tcscpy(text, entry.text);

    //text = entry.text; //dit was voor het gebruik van een std::string
}

destructor:

C++:

MemEntry::~MemEntry(){
    delete text;
}

constructor:

C++:

MemEntry::MemEntry(){
    a = b = c = d = e = f = 0;
    text = "N/A";
}

hmm.. nu ik zo ff zat te kijken, kom ik erachter dat "text = "N/A";" niet werkt. als ik hier

code:

    text = new TCHAR[4];
    _tcscpy(text, _TEXT("N/A"));

van maak dan werkt het wel, maar is alleen ongelovelijk langzaam. ik neem aan dat dat komt doordat er op de heap gealloceerd wordt en die std::string op de stack!?

[curry684]

.oisyn schreef op 13 mei 2004 @ 12:59:
[...]
Als de interne buffer van de vector vol zit met, zeg, 1000 elementen, en je voegt er een aan toe, dan wordt er een nieuwe buffer gecreëert van bijvoorbeeld 1500 elementen.

VC.NET werkt iig met een doubling buffer heb ik een tijd terug gechecked. Dus begint met ruimte voor 1, en gaat vervolgens alle 2 machten aflopen. Vandaar dat ik ook zo zeker wist dat 600000 elementen onder VC.NET tot 20 allocaties leidt

En wat je zegt over std::string vind ik wel vreemd. Vanzelfsprekend staat het iedere implementer vrij om te kiezen voor een value-wise implementatie, maar afaik zijn alle gangbare versies toch voorzien van reference counting en copy-on-demand?

[.oisyn]

C++:

text = "N/A";

dit is geen allocatie. "N/A" is een statische string die in je executable staat, en die kun je dus ook niet vrijgeven. De reden dat het bij een std::string wel goed gaat is omdat hij een kopie maakt van die "N/A" en dat in een zelf gealloceerde buffer zet. Het vrijgeven van die buffer gaat dus ook prima
Maar afgezien van dat ziet je copy-ctor er goed uit

van maak dan werkt het wel, maar is alleen ongelovelijk langzaam

std::string doet precies hetzelfde, dus ik snap het verschil niet helemaal

Oh, en een array deleten doe je natuurlijk met delete[], niet met delete

Je zou trouwens ook nog _tcsdup () moeten maken, die alloceert en kopieert zelf. Alleen dan moet je 'm wel vrijgeven met de free () functie, omdat _tcsdup malloc gebruikt

[ Voor 20% gewijzigd door .oisyn op 13-05-2004 13:32 ]

[Soultaker]

Geheugen dat je alloceert met new[] moet je vrijgeven met delete[] (en niet met delete). Je destructor wordt dus:

C++:

MemEntry::~MemEntry(){
    delete[] text;
}

Maar schaam je niet; die fout staat wel ergens in de top 10 van veelgemaakte fouten in C++. (Nu nooit meer maken, natuurlijk ).

[CyBoB]

.oisyn schreef op 13 mei 2004 @ 13:31:

std::string doet precies hetzelfde, dus ik snap het verschil niet helemaal

Oh, en een array deleten doe je natuurlijk met delete[], niet met delete

Je zou trouwens ook nog _tcsdup () moeten maken, die alloceert en kopieert zelf. Alleen dan moet je 'm wel vrijgeven met de free () functie, omdat _tcsdup malloc gebruikt

delete[] ff vergeten

maar ik heb net ff een release build gemaakt en nu werkt het een stuk sneller dan de debug build.

zo te zien werkt het nu op beide manieren prima, maar wat is volgens jullie de best/mooiste manier?

[.oisyn]

curry684 schreef op 13 mei 2004 @ 13:29:
En wat je zegt over std::string vind ik wel vreemd. Vanzelfsprekend staat het iedere implementer vrij om te kiezen voor een value-wise implementatie, maar afaik zijn alle gangbare versies toch voorzien van reference counting en copy-on-demand?

Copy-on-demand strings zijn een hel in multithreading omdat je dan synchronisatie toe moet passen (de implementator zelf dus, niet de gebruiker ervan). Of je moet zorgen dat buffers alleen geshared worden binnen dezelfde thread, maar dat brengt weer allerlei checks met zich mee

VC++ 7.1 gebruikt iig een value-type string, ik heb het net getest met de debugger.

C++:

int main ()
{
    std::string s1 = "aap";
    std::string s2 = s1;
}

s1 en s2 hadden na deze 2 statements een verschillende interne buffer waar de string in stond.

[ Voor 4% gewijzigd door .oisyn op 13-05-2004 13:48 ]

[Soultaker]

De STL die bij MinGW zit doet wel aan reference counted string data (en dus aan copy-on-demand). In de source code zie ik echter niets van synchronisatie staan. Het lijkt er dus op dat die string-implementatie niet (uit zichzelf) thread-safe is; de user moet er dus voor zorgen dat 'ie 'm goed gebruikt.

Ik denk overigens niet dat synchronisatie in de string klasse heel veel kan uitrichten. De meeste problemen ontstaan namelijk 'buiten' de string klasse zelf; als applicaties references gebruiken die ongeldig zijn geworden doordat de string een andere interne buffer heeft gealloceerd. Dat probleem bestaat trouwens ook met de value strings van Microsoft.

[ Voor 4% gewijzigd door Soultaker op 13-05-2004 14:02 ]

[curry684]

Soultaker schreef op 13 mei 2004 @ 13:31:
Geheugen dat je alloceert met new[] moet je vrijgeven met delete[] (en niet met delete). Je destructor wordt dus:

C++:

MemEntry::~MemEntry(){
    delete[] text;
}

Maar schaam je niet; die fout staat wel ergens in de top 10 van veelgemaakte fouten in C++. (Nu nooit meer maken, natuurlijk ).

Volgens mij staat ie zelfs rocksolid op #1

[.oisyn]

Soultaker schreef op 13 mei 2004 @ 14:01:
De STL die bij MinGW zit doet wel aan reference counted string data (en dus aan copy-on-demand). In de source code zie ik echter niets van synchronisatie staan. Het lijkt er dus op dat die string-implementatie niet (uit zichzelf) thread-safe is; de user moet er dus voor zorgen dat 'ie 'm goed gebruikt.

Hoe ga je dat dan precies aanpakken? Je hebt geen toegang tot de shared buffer, en een sync op de string zelf heeft weinig nut Het is ook een black box iets, de eindgebruiker hoeft niet eens te weten dat er een shared buffer gebruikt wordt, en hoeft daar al helemaal geen rekening mee te houden.

Synchronisatie doe je natuurlijk als 2 threads op hetzelfde object zouden kunnen werken. Alleen stel dat thread T1 een string S1 heeft, en je maakt een thread T2 die zijn S2 initialiseert met S1. Elke thread heeft zijn eigen string object, en synchronisatie door jou dan ook niet nodig.

Wat je niet weet is dat S1 en S2 intern hetzelfde buffer gebruiken. Als je nu in T1 een S3 = S1 doet, terwijl je precies op hetzelfde moment de S2 vanuit T2 destruct, dan moet dus tegelijkertijd de refcount worden verhoogd en verlaagd. Als daarvoor geen automaire operatie wordt gebruikt, dan zou de volgende opsomming van gebeurtenissen kunnen optreden:

T2 is aan de beurt:
• ...
• T2 leest de refcount (momenteel 2) uit
• thread switch

T1 is aan de beurt
• T1 leest de refcount (momenteel 2)
• T1 verhoogd de refcount naar 3
• T1 schrijft de nieuwe refcount weg
• ...
• thread switch

T2 weer aan de beurt
• T2 had de al uitgelezen refcount van 2 in een register staan
• T2 verlaagd de refcount (naar 1 dus)
• T2 schrijft de refcount weg

Er zijn nu nog 2 strings (S1 en S3), terwijl de refcount 1 is. Destructie van een van die 2 strings zorgt er dus voor dat de buffer dus vrijgegeven wordt, terwijl hij in gebruik is.

Er is voor jou geen enkele mogelijkheid om dat te voorkomen, een lock op S1 lockt niet de gebruikte buffer zelf. Dit moet dus vanuit de implementatie geregeld worden, of door synchronisatie te doen per buffer, of door buffers niet te laten sharen door meerdere threads (de buffer heeft dan een owner thread, en als de huidige thread bij een operatie niet de owner is, dan moet de buffer sowieso gekopieerd worden)

[ Voor 9% gewijzigd door .oisyn op 13-05-2004 14:18 ]

[Soultaker]

Je hebt gelijk; omdat je niet kunt locken op de buffer kun je eigenlijk maar weinig doen om de strings thread-safe te gebruiken.

Overigens declareert de MingW basic_string template de reference count als _Atomic_word en doet daar __atomic_add en __exchange_and_add operaties op. Waar die dingen gedeclareerd worden weet ik niet precies, maar het gevolg is dus dat deze implementatie alleen werkt op systemen waarop die atomaire operaties beschikbaar zijn (of goedkoop geëmuleerd kunnen worden).

edit:
Gevonden:

C++:

typedef int _Atomic_word;

static inline _Atomic_word 
__attribute__ ((__unused__))
__exchange_and_add (volatile _Atomic_word *__mem, int __val)
{
  register _Atomic_word __result;
  __asm__ __volatile__ ("lock; xaddl %0,%2"
            : "=r" (__result) 
                        : "0" (__val), "m" (*__mem) 
                        : "memory");
  return __result;
}

static inline void
__attribute__ ((__unused__))
__atomic_add (volatile _Atomic_word* __mem, int __val)
{
  __asm__ __volatile__ ("lock; addl %0,%1"
            : : "ir" (__val), "m" (*__mem) : "memory");
}

[ Voor 38% gewijzigd door Soultaker op 13-05-2004 16:24 ]

[.oisyn]

Hmm interessant, kun je ook eens posten hoe die 2 functies gebruikt worden bij het aanpassen van de refcount?

[Soultaker]

Er zijn twee methoden die gebruikt worden bij het updaten van de reference count; _M_dispose om de huidige buffer vrij te geven en _M_refcopy() die wordt gebruikt om een extra reference naar een bestaande buffer te krijgen; een vrij standaard reference counting implementatie dus:

C++:

void
_M_dispose(const _Alloc& __a)
{
  if (__exchange_and_add(&_M_references, -1) <= 0)
    _M_destroy(__a);
}  // XXX MT

C++:

_CharT*
_M_refcopy() throw()
{
  __atomic_add(&_M_references, 1);
  return _M_refdata();
}  // XXX MT

Je kunt je zelf wel voorstellen hoe deze functies gebruikt worden (in destructors, copy constructions, assignment operators, assignment functies, etc.). Het is lastig om daar zinnige code van te plaatsen zonder gelijk schermen vol code mee te nemen.

De complete implementatie kun je hier trouwens gewoon inzien:• basic_string.h
• basic_string.tcc