Re: Framework 2.0 array redim unsatisfactory performance

Tech-Archive recommends: Fix windows errors by optimizing your registry

> Remember List(Of T):
> <quote>
> Implements the System.Collections.Generic.IList<> interface using an array
> whose size is dynamically increased as required
> </quote>
> http://msdn2.microsoft.com/library/6sh2ey19(en-us,vs.80).aspx
>
> Notice "an array whose size is dynamically increased as required" which
> IMHO
> is clearly refers to a single array, its singular.

I see what they say, but if this had been true there would not have been
that much memory deallocated, I think.

Test with List(Of Integer) containing 1 million elements shows that when the
initial capacity is specified 92.6% memory is used by objects. While when
the initial capacity is not specified, as much as 50% of memory gets
deallocated as the List(Of T) grows.

Furthermore, the fact that it is almost exactly 50% makes me thinking that
List(Of T) really copies array to twice bigger when needed - the model using
geometric sum would produce precisely this result.



Tomasz

//C# example
long totalMem0 = Process.GetCurrentProcess().WorkingSet64;
long usedMem0 = GC.GetTotalMemory(true);
int n = 1000000;
List<int> li = new List<int>(n);
for (int i = 0; i < n; i++) {
li.Add(i);
}
long totalMem1 = Process.GetCurrentProcess().WorkingSet64;
long usedMem1 = GC.GetTotalMemory(true);
Debug.WriteLine("% mem used: " + ((double)(usedMem1 - usedMem0)) /
(totalMem1 - totalMem0) * 100);


.

Relevant Pages

  • Re: sizeof([ALLOCATED MEMORY])
    ... applications exist which could make use of that extra memory if only ... Perhaps I should elucidate "dynamic array". ... Repeated growth in size can lead to quadratic expense due to continually ... the array keep track of both a logical size and a physical capacity ...
    (comp.lang.c)
  • Re: Fast string operations
    ... Looping: I thought looping over arrays in managed code was "slow" ... array handling and such. ... The problem with TrimHelper is that it always returns a new string instance. ... The customer perceives this as a memory leak. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: High Memory Consumption of Classes and Arrays
    ... Only the array itself has overhead. ... memory as a reference type. ... > least consume 40 bytes of memory. ...
    (microsoft.public.dotnet.framework.performance)
  • Re: Fast linked list
    ... > amounts of memory rather than huge chunks of it. ... random insertions into a vector/dynamic array are not as slow ... to cause a cache miss. ... some hard numbers on speed differences between lists and arrays. ...
    (microsoft.public.vc.mfc)
  • Re: Fast linked list
    ... > amounts of memory rather than huge chunks of it. ... random insertions into a vector/dynamic array are not as slow ... to cause a cache miss. ... some hard numbers on speed differences between lists and arrays. ...
    (microsoft.public.vc.language)