Know how ArrayList Works?

  • Thread starter Thread starter Phill
  • Start date Start date
P

Phill

Anyone know the internal working of this thing. I expected it to be
kinda slow at enumerating large lists of objects but it was actually
pretty good. I was able to write a quick linked list class that beat
it at enumerating but was not as fast as the arrayList at actually
adding the items into the list.

This makes me think it is using something like linked arrays. Where
instead of allocating a new node each time an object is added it
allocates an array of say 10 objects and when all 10 are filled it
allocates a new array of 10 and links it w/ the previous array.

This would account for the speed difference. I wonder how it is so
fast at this though:

for(int i = 0; i < myArrayList.count; i++)
{
myArrayList;
}

How can this be fast? I'm not telling it I'm going in order so how
does it get such good speed at seemingly random access to the linked
list?

Thanks I'd appreciate any insite anyone may have.
 
...
Anyone know the internal working of this thing.
Click to expand...

I'm not 100% sure this is the *actual* implementation, but I believe it is:

http://www.dotnet247.com/247reference/System/Collections/ArrayList/__rotor

....so why not look into it by yourself? :-)
This makes me think it is using something like linked arrays. Where
instead of allocating a new node each time an object is added it
allocates an array of say 10 objects and when all 10 are filled it
allocates a new array of 10 and links it w/ the previous array.
Click to expand...

The list starts with a "capacity" of 16, and then *doubles* the capacity as
required.

// Bjorn A
 
If you really want to know how it is implemented you should download
Lutz Roeder's Reflector tool from:

http://www.aisto.com/roeder/dotnet/

With it you can decompile the source into C#, VB.Net, or Delphi. This
is about as awesome as it gets for quickly finding out how something in
..Net is implemented. Hope this helps for this and in the future.

Have A Better One!

John M Deal, MCP
Necessity Software
 
Thanks, that is an exceptional tool.

What it shows is that ArrayList in fact uses only a simple object
array.
When it runs out of room it creates a new array 2x the size of the
original. Then it copies the contents of the old array to the new
array and replaces the old array w/ the new one.

I'm perplexed how this is faster than a linked list. Copying all the
values in an array to a new array should be slower than simply
creating a new node.

I guess I have tons to learn about how to write fast .Net programs.
 
Remember that you can set the initial capacity using one of the ArrayList
constructors. Often you either know how big it needs to be, or you can
estimate or know a typical size. If you allocate enough initial capacity,
often you can avoid some or all of the copying at runtime.

Even when you haven't a clue as to the initial size you may know that the
default size is going to be too small for a starting point.

This same often-overlooked optimization applies to other things too, such as
the initial size of a StringBuilder, which defaults to a miserly 16 bytes.

--Bob
 
Phill said:
Thanks, that is an exceptional tool.

What it shows is that ArrayList in fact uses only a simple object
array.
When it runs out of room it creates a new array 2x the size of the
original. Then it copies the contents of the old array to the new
array and replaces the old array w/ the new one.

I'm perplexed how this is faster than a linked list. Copying all the
values in an array to a new array should be slower than simply
creating a new node.
Click to expand...

Yes, but it only needs to happen relatively rarely.

Suppose you have an ArrayList with an initial capacity of 500, and you
add 10000 entries to it. It needs to copy 500+1000+2000+4000+8000
entries - a total of 15500 items copied. However, each of those copies
can be very fast - a direct copy in memory of the kind that processors
often have specific instructions for.

Using a linked list, you need to create an extra 10000 objects. This
will quite possibly involve a few gen0 garbage collections and object
promotion/compaction - all of which involves memory copying too.
 
Yes, setting a good size to begin w/ should improve performance quite
a bit if you know something about the eventual size.

The memory copy indeed must be quite fast.

Jon, Could you explain to me what a gen0 garbage collection is, and
what object
promotion/compactions are? I'm not familiar w/ those terms.
 
Phill said:
Yes, setting a good size to begin w/ should improve performance quite
a bit if you know something about the eventual size.
Yup.

The memory copy indeed must be quite fast.
Sure.

Jon, Could you explain to me what a gen0 garbage collection is, and
what object promotion/compactions are? I'm not familiar w/ those terms.
Click to expand...

That's a bit too big for a newsgroup post (while I'm watching The West
Wing, anyway :) Fortunately, Jeffrey Richter has spent time writing it
all nicely!

http://msdn.microsoft.com/msdnmag/issues/1100/GCI/default.aspx
 
Back
Top