[C# / WP7] List<string> heeft 4 begin entries

[Jan_V]

Kom ik net tegen, heel apart.
Ben m'n code aan het debuggen en zie dat een List<string> na het declareren al 4 null-entries heeft.

Wat ik doe is een List<string> declareren (private set) en deze vullen met de waarden die uit een array komen, zoals hieronder is te zien.

code:

this.Values = new List<string>();
for (int i = 0; i < mChunk.sValues.Length; i++)
{
    if (!string.IsNullOrEmpty(mChunk.sValues[i]))
    {
        Values.Add(mChunk.sValues[i]);
    }
}

Geen spannende code.
Echter, wanneer ik in de watch kijk naar de zojuist aangemaakte this.Values, dan zie ik dat deze al 4 items heeft, allemaal met de waarden null.
Ook wanneer ik een 5e item in de collectie stop, dan worden er 4 nieuwe items in de collectie gestopt, waarbij de laatste 3 null zijn.

Volgens mij werkt dit niet zo bij 'normale' .NET applicaties. Het zou kunnen zijn dat de .NET versie van WP7 blokken toewijst, zodat deze achter elkaar in het geheugen komen te staan of zo, echter kon ik hier zo snel niet iets op MSDN over vinden (heb ook niet super uitgebreid gezocht).

Iemand hier met meer informatie hierover, of dat ik gewoon iets sufs aan het doen ben en dus een bug/feature heb gemaakt?

[Verwijderd]

Ik heb laatst met ASP.NET ook gemerkt dat er bij een List<SpecificObject> (was een zelfgemaakte class die ik niet zo 1.2.3. weet op te noemen) 4 null entries waren.
Ook als ik een List<string> aanmaak kan ik wel in de static/non public members een _DefaultSize van 4 vinden. Echter is de itemArray leeg.

Verder kan ik je ook niet helpen maar ik kan wel bevestigen dat ik dit gedrag heb gezien in 'normale' .NET applicaties.

[ Voor 8% gewijzigd door Verwijderd op 23-12-2010 09:48 ]

[RobIII]

Je zit naar interne variabelen van de list te kijken als je 't mij vraagt. Hoe de list intern z'n zaakjes regelt is helemaal niet boeiend
Wat een list doet is zorgen dat er niet bij elke add een nieuwe allocatie gedaan moet worden. Lees de remarks hier maar eens. Een stringbuilder (om een ander voorbeeld te nemen) werkt intern ook zo. Ik weet niet hoe een list 't intern implementeert (en dat boeit ook niet) maar volgens mij is 't elke keer dat jij een add() doet en de (interne) grootte overschrijdt dat 'ie z'n (interne) capaciteit verdubbelt. Dus 4, 8, 16, 32, 64.

C#:

List<int> foo = new List<int>();
for (int i = 0; i < 1000; foo.Add(i++))
    Console.WriteLine("{0} {1}", foo.Count, foo.Capacity);

1 4
2 4
3 4
4 4
5 8
6 8
7 8
8 8
9 16
10 16
11 16
12 16
13 16
14 16
15 16
16 16
17 32
18 32
19 32
20 32
21 32
22 32
23 32
24 32
25 32
26 32
27 32
28 32
29 32
30 32
31 32
32 32
33 64
34 64
35 64
...
...

Maar nogmaals: je zit in de "blackbox" te prutten; weg daar jij! Shoo!

Als je vantevoren al (ongeveer) weet hoeveel elementen de list/queue/stack/... gaat bevatten of hoe lang een string ongeveer gaat worden (stringbuilder) dan kun je de initiele capaciteit bij al die objecten al aan de constructor meegeven (en dus zijn er minder (her)allocaties nodig).

En voordat je helemaal los gaat met TrimExcess(): lees daar de remarks ook even.

Als vuistregel/richtlijn: doorgaans is alles wat onder "raw" te vinden is in je debugger, of alles dat begint met een _underscore, niet interessant: interne implementatie en niet jouw probleem

[ Voor 81% gewijzigd door RobIII op 23-12-2010 10:10 ]

[Dars123]

Volgens mij hebben containers (Lists, Stacks, Queues etc. in C#, maar ook bijv. vectors in C++) al tijdens constructie geheugen gealloceerd voor 4 elementen, dus wat je ziet is volstrekt normaal.

Kijk anders even wat het verschil is tussen List.Count en List.Capacity in de documentatie op MSDN.

[The Flying Dutchman]

Dars123 schreef op donderdag 23 december 2010 @ 09:56:
Volgens mij hebben containers (Lists, Stacks, Queues etc. in C#, maar ook bijv. vectors in C++) al tijdens constructie geheugen gealloceerd voor 4 elementen, dus wat je ziet is volstrekt normaal.

Kijk anders even wat het verschil is tussen List.Count en List.Capacity in de documentatie op MSDN.

Inderdaad, beginnen met 4 elementen. Is er een 5e element nodig, dan zul je zien dat de interne size 8 wordt. Is er een 9e element nodig, dan wordt de interne size geloof ik 16.

Vraag de Count op van de list en je weet hoeveel elementen er daadwerkelijk in zitten.

[Gimmeabrake]

The Flying Dutchman schreef op donderdag 23 december 2010 @ 10:21:
[...]


Inderdaad, beginnen met 4 elementen. Is er een 5e element nodig, dan zul je zien dat de interne size 8 wordt. Is er een 9e element nodig, dan wordt de interne size geloof ik 16.

Vraag de Count op van de list en je weet hoeveel elementen er daadwerkelijk in zitten.

De interne size wordt inderdaad altijd verdubbeld, heb het laatst nog moeten leren voor school. Het gaat hier intern om een circulaire arraylist, bij een linkedlist zou je dit soort gedrag natuurlijk niet tegenkomen. Als ik me niet vergis wordt er verdubbeld omdat dat in de meeste situaties simpelweg de beste performance oplevert.

Bottomline: niks van aantrekken

[Jan_V]

Dank voor de uitleg. Wist niet dat dit standaard gedrag was, waarschijnlijk omdat ik normaal nooit een List<T> aan het watchen ben.

[.oisyn]

De Capacity van de List is dus blijkbaar default 4. Gefeliciteerd

Dars123 schreef op donderdag 23 december 2010 @ 09:56:
Volgens mij hebben containers (Lists, Stacks, Queues etc. in C#, maar ook bijv. vectors in C++) al tijdens constructie geheugen gealloceerd voor 4 elementen, dus wat je ziet is volstrekt normaal.

Beetje kort door de bocht. Ik zou zeker niet rekenen op 4 elementen, en in C++ is het typisch 0 (zodat een lege container geen geheugen hoeft te alloceren)

[ Voor 68% gewijzigd door .oisyn op 23-12-2010 16:34 ]

[RobIII]

.oisyn schreef op donderdag 23 december 2010 @ 16:32:
Beetje kort door de bocht. Ik zou zeker niet rekenen op 4 elementen

Ik zou helemaal nergens op rekenen als 't om interne implementatie gaat

[.oisyn]

Het gaat niet om de interne implementatie, het gaat om de specs. En die zeggen dat er een default capacity is (maar niet hoeveel).

[ Voor 76% gewijzigd door .oisyn op 23-12-2010 17:07 ]

[RobIII]

.oisyn schreef op donderdag 23 december 2010 @ 17:04:
De docs hebben het duidelijk over een "default capacity". Daar kun je dus op rekenen. Niet hoeveel het is, maar wel dat er een default is.

Wacht; ik begreep even dat je bedoelde dat je van die 4 kon uitgaan omdat 't zo in de docs staat. Maar docs wijzigen nogal eens (as you surely know). Maar je doelt natuurlijk op het gebruiken van 't Capacity property om daar de "default" uit te halen. Dus:

C#:

var foo = new List<bar>();
int c = foo.Capacity;

Ik begreep:

C#:

var foo = new List<bar>();
//Assume 4 for capacity because the docs say so...

Maar ik vind 't nog altijd netter om, als 't effe kan, aan de constructor meteen de juiste capacity mee te geven (of een 'educated guess' voor mijn part). Maar da's een ander verhaal.

Verder zie ik weinig nut eigenlijk in heel dat capacity verhaal; die list moet toch X elementen gaan bevatten; boeie wat z'n capacity is en 't ding alloceert vanzelf wel weer als 't nodig is. Alleen als je in bulk een bestaande list gaat vullen kan 't nog eens interessant zijn om de capacity expliciet te setten (groter te maken) om zo een paar allocaties te besparen en voor elke allocatie O(n) copies. Meestal zul je kunnen volstaan met de constructor al meteen de juiste waarde meteen mee te geven.

[ Voor 29% gewijzigd door RobIII op 23-12-2010 17:22 ]

[.oisyn]

Nou blijkbaar begrijp je helemaal niets van mijn posts . Ik reageer op Dars123 die zegt dat de capacity standaard 4 is. Ik zeg dat je daar niet op moet rekenen omdat dat nergens gedocumenteerd staat. Verder beweert hij dat het bij C++'s std::vector ook 4 is, terwijl ik juist zeg dat het daar 0 is, gezien de achterliggende designprincipes van C++ (je betaalt niet voor wat je niet gebruikt - een vector alloceert pas geheugen als er ook elementen in zitten)

[ Voor 7% gewijzigd door .oisyn op 23-12-2010 17:13 ]

[RobIII]

.oisyn schreef op donderdag 23 december 2010 @ 17:11:
Nou blijkbaar begrijp je helemaal niets van mijn posts

Dat blijkt dan wel weer Zeggen we dus toch 'tzelfde

[ Voor 7% gewijzigd door RobIII op 23-12-2010 17:14 ]

[MLM]

.oisyn schreef op donderdag 23 december 2010 @ 17:11:
Nou blijkbaar begrijp je helemaal niets van mijn posts . Ik reageer op Dars123 die zegt dat de capacity standaard 4 is. Ik zeg dat je daar niet op moet rekenen omdat dat nergens gedocumenteerd staat. Verder beweert hij dat het bij C++'s std::vector ook 4 is, terwijl ik juist zeg dat het daar 0 is, gezien de achterliggende designprincipes van C++ (je betaalt niet voor wat je niet gebruikt - een vector alloceert pas geheugen als er ook elementen in zitten)

Als sidenote, in het EASTL document, staat vermeld:

Many current versions of std STL allocate memory in empty versions of at least some of their containers.

en als ik me het niet verkeerd herinner doet onder andere VC++'s STL dat ook (std::string implementatie o.a.), maar dat kan ik fout hebben, dus pas op met dat soort veronderstellingen (zeker in mijn toekomstige/jouw huidige business).

[.oisyn]

Vziw is er geen enkele VC++ container die standaard alloceert. std::string al helemaal niet, want die heeft intern een buffer van ik geloof 16 chars in z'n class zelf staan zodat voor relatief korte strings (<= 15) helemaal geen geheugen gealloceerd hoeft te worden

.edit: ah, map en set doen dat wel, voor de root node.

[ Voor 9% gewijzigd door .oisyn op 23-12-2010 17:26 ]

[Dars123]

Bij nader inzien en met hulp van de debug functionaliteit in Visual Studio:

C# List Class:
- private static int _standardCapacity = 4
- allocatie van dit aantal elementen geschiedt pas op het moment dat het eerste element wordt toegevoegd, dus de property Capacity bedraagt 0 op het moment dat de standaard constructor wordt aangeroepen, en bedraagt 4 nadat het eerste element is toegevoegd.
- de Capacity wordt verdubbeld zodra de Count groter wordt dan de Capacity

Dus ik ben toch benieuwd waar de vier nulls van Jan_V vandaan komen, tenzij het eerste element dat is toegevoegd aan de List null was.....

(Microsoft implementatie van) c++:
- std::string heeft bij constructie een capacity van 15 chars.
- de groei van de capacity van een vector is beduidend zuiniger dan bij C#, wellicht kent iemand de 'groei strategie' van de interne array?