Re: Array.Clear vs List<>.Clear

Laura T. wrote:
Well, that's what you are going to get with List<T> anyway, copying and more (ridiculous) copying.

I wouldn't call the copying "ridiculous", and it is required in any case with _any_ array implementation. The only way to avoid it would be to use some linked data structure (eg LinkedList).

As Vadym said, the List<T> internally manages the list as an Array,[], so every time you add one element over the List<T>.Capacity, the it will create a new array, copy the elements, add the new item and then destroying the old array.

This would be required managing a dynamically-sized Array as well, except you'd have to do it yourself.

The unfortunate thing with List<T> is that the capacity does grow up one by one. I'd like to see something like "expand it by 10%", so that the next Add would not incur reallocations.

That's not correct. The List<T> does NOT "grow up one by one". The default size starts out at 4 elements, and each time you exceed the capacity of the list, the newly allocated storage has double the previous capacity.

So if you know how much you must expand, you sould set the List<T>.Capacity in advance to the max you need as you cannot shrink a List<T> capacity.

Yes, you definitely should provide whatever information you have, if you have it. If you know what the eventual required capacity will be, it is better to provide that.

The performance of simple System.Array could result better.

I don't see how, since the underlying behavior is basically the same.

For what it's worth, I wrote a short program to test the performance and behavior of the List<T> class. It confirms that with each new allocation, the capacity is doubled. It also shows that at least on a reasonably fast computer (Core 2 Duo 2.33Ghz), it takes less than 100 ms to add in sequence 1 million integers to a List<int>.

It's true that for smaller lists, there are more allocations, and so the copying is a larger part of the overall time cost. But then, for smaller lists, the total time cost is significantly lower anyway, so that proportional difference isn't really a big deal.

I really don't think "all that copying" is a significant performance factor.

Pete
.

Relevant Pages

  • Re: Array.Clear vs List<>.Clear
    ... and recreating the array then copying elements across seems ... Well, that's what you are going to get with Listanyway, copying and more ... a new array, copy the elements, add the new item and then destroying the old ... The unfortunate thing with Listis that the capacity does grow up one by ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Know how ArrayList Works?
    ... Remember that you can set the initial capacity using one of the ArrayList ... constructors. ... often you can avoid some or all of the copying at runtime. ... > When it runs out of room it creates a new array 2x the size of the ...
    (microsoft.public.dotnet.languages.csharp)
  • Increase capacity of a standard logical drive - cluster configurat
    ... We need to increase the capacity of one array in order to present the same ... array in order to have a bigger disk, ... letters that are associates with the logical drives. ...
    (microsoft.public.windows.server.clustering)
  • 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: Can you fix this program? : C++ Dynamic Array Problems
    ... Dynamic Array similar to System.Collections.ArrayList in .NET. ... Capacity = 0; ... void FoldersCollection::Add(Folder folder) ... int newCapacity = Capacity*2; ...
    (microsoft.public.dotnet.languages.vc)