System.Collections.ArrayList performance analysis

re: System.Collections.ArrayList performance analysis

Sean Chase — Thu, 02 Dec 2004 07:48:00 GMT

Thank you for this information!

Are all the Collection classes implented the same in rotor and .Net framework?

STL_Guy — Thu, 02 Dec 2004 09:51:00 GMT

Are all the collection classes implemented the same way in Rotor and the .Net framework? Since this is the BCL team's blog, I'm assuming you would know for sure.

BTW I've always disliked the fact the .Net f/w documentation doesn't talk about the time complexities of the collection classes as clearly as the C++ standard's STL part does. Take a look at Bjarne's book and see how clearly he lists out the time complexities of various STL classes and the tradeoff's involved. So here's a difference between a documentation by a programmer versus just a documentation guy who has to pick on the brains of some busy developer for information.

Another question I have is why do the Synchronised wrapper classes do a blind lock for every function? Why doesn't it do something smart like a reader write lock etc? For example how does it matter how many threads are simultaneously trying to read the count of a collection? Why go to the cost of an expensive lock for something that is only read by various threads? I was shocked to see the source for some of the synchronised wrappers and see what a trivial implementation it is.

I'm hoping someone on the BCL team really reads these blogs and answers questions here.

re: System.Collections.ArrayList performance analysis

Paul Rudin — Thu, 02 Dec 2004 13:00:00 GMT

Incidentally - here's an apparent ArrayList bug I noticed.

Here's some c# code:

using System;
using System.Collections;
namespace AdapterProblem
{
class Class1
{
[STAThread]
static void Main(string[] args)
{
ArrayList source = ArrayList.Adapter(new object [] {"1" , "2"});
ArrayList range = source.GetRange(1,1);
ArrayList target = new ArrayList();
target.AddRange(range);
Console.WriteLine(target[0] == null? "It's null" : target[0]);
Console.ReadLine();
}
}
}

I would expect this to print out the second element of source -
i.e. the string "2". Actually it turns out that target[0] is null so
the program prints "It's null".

re: System.Collections.ArrayList performance analysis

Michael — Thu, 02 Dec 2004 23:45:00 GMT

It seems you can't iterate over an ArrayList that contains itself:

ArrayList list = new ArrayList();
list.Add(list);
foreach (Object obj in list);
// ArrayListEnumeratorSimple.get_Current throws InvalidOperationException

ArrayList Performance

Dominic Plouffe — Sun, 05 Dec 2004 04:21:00 GMT

ArrayList Performance

Blog link of the week 49

Daniel Moth — Mon, 06 Dec 2004 01:17:00 GMT

Blog link of the week 49

re: System.Collections.ArrayList performance analysis

Gang Peng — Wed, 08 Dec 2004 05:35:00 GMT

Paul, the bug is fixed in Whidbey.

Michael, the iteration problem is a bug we also fixed in Whidbey. The problem is ArrayListEnumeratorSimple class uses the list to check for boundary conditions. You can take a look at the rotor source for details.

Thanks for the feedback.

re: System.Collections.ArrayList performance analysis

Luong Luc — Fri, 10 Dec 2004 01:29:00 GMT

I'm looking for a technique for determing IndexOF of a class element in an ArrayList of CLASSES (such as Employee as shown below - not any regular objets).
Could you please help me out?

Example:
public class Employee
{
String _name;
int _id;
...........
...........
public Employee( int id, String name )
{
this._name = name;
this._id = id;
}
}
Thank you.

re: System.Collections.ArrayList performance analysis

Ryan Byington — Fri, 17 Dec 2004 05:09:00 GMT

I am not sure I fully understand your question but I will try. IndexOf(Object value) just call value.Equals (assuming value is not null) on every item in ArrayList starting at the begining until Equlas returns true and it returns that index for the item.

For your Employee object you will get a reference equals by default from Object to override this behavior simply override Equals method possibly like the following:

public override bool Equals(Object other)
{
Employee otherEmployee = other as Employee;

if(null == otherEmployee) {
return false;
}

return _name == otherEmployee._name && _id == otherEmplyee._id;
}

re: System.Collections.ArrayList performance analysis

Gang Peng — Fri, 17 Dec 2004 10:49:00 GMT

As Ryan mentioned, basically IndexOf just calls Object.Equals on the items.
So for the type objects, Type.Equals will be used. So it will work just find for ArrayList of type objects.

re: System.Collections.ArrayList performance analysis

David Taylor — Fri, 24 Dec 2004 14:32:00 GMT

Does everything you have said about ArrayList also apply to List<T>?