ArrayList.Contains() slower in NET 2.0 ?

  • Thread starter Thread starter Robert Hooker
  • Start date Start date
R

Robert Hooker

We are moving to .NET2.0 - and have noticed that .Contains() seems to be
around 20% slower under NET2, compared to NET1.1.

This code shows the issue:
static void Main(string[] args)
{
System.Collections.ArrayList list = new System.Collections.ArrayList();

//Setup code
//
//Add 10000 objects to a collection.
//Don't care what type the object is for the purposes of this
demonstration
for (int i=0; i<100000; i++)
{
list.Add(new EventArgs());
}
//We are going to find this object (intentially right at the end of the
list)
object objectToFind = list[99998];
//
// End setup code

// Timing code
//
long startT = Environment.TickCount;
//Find the object 1111 times in the collection
for (int j=0;j<1111;j++)
{
bool objectInList = list.Contains(objectToFind);
}
System.Console.WriteLine("Contains took "+(Environment.TickCount-startT)+"
(ms)");
System.Console.ReadLine();
}

Under NET1.1 I consistently get times in the order of 20% quicker than the
same code under NET2.

Has anyone else noticed this? Is there a way I can avoid whatever new code
is being executed in the bowels of the framework?
Thanks
Rob
 
Robert Hooker said:
We are moving to .NET2.0 - and have noticed that .Contains() seems to be
around 20% slower under NET2, compared to NET1.1.
Click to expand...

Has anyone else noticed this? Is there a way I can avoid whatever new code
is being executed in the bowels of the framework?
Click to expand...

I would suggest avoiding using ArrayList.Contains on pretty large
lists. Using a hashtable with a constant value (or a value equal to the
respective key) is likely to be far faster for checking inclusion than
a list. (You can always keep a list *as well* if you need ordering
etc.)
 
Hello Robert,

As for the ArrayList Contains method performance issue, I've just performed
some tests according to the code you provided and did encounter the same
behavior.(test through console applcations) The .net 1.1 version is about
14% faster than .net 2.0 version.

Comparing the generated IL code of the two version, the .net 2.0 one has
some additional instructions within the "contains" method of ArrayList in
the for loop. Here are the disassemby code I got:

==========VS 2003/.NET 1.1===========
IL_002e: call int32 [mscorlib]System.Environment::get_TickCount()
IL_0033: conv.i8
IL_0034: stloc.3
IL_0035: ldc.i4.0
IL_0036: stloc.s j
IL_0038: br.s IL_0049
IL_003a: ldloc.0
IL_003b: ldloc.2
IL_003c: callvirt instance bool
[mscorlib]System.Collections.ArrayList::Contains(object)
IL_0041: stloc.s objectInList
IL_0043: ldloc.s j
IL_0045: ldc.i4.1
IL_0046: add
IL_0047: stloc.s j
IL_0049: ldloc.s j
IL_004b: ldc.i4 0x457
IL_0050: blt.s IL_003a
IL_0052: ldstr "Contains took "
IL_0057: call int32 [mscorlib]System.Environment::get_TickCount()


========VS 2005/.NET 2.0=============
int32 [mscorlib]System.Environment::get_TickCount()
IL_003c: conv.i8
IL_003d: stloc.3
IL_003e: ldc.i4.0
IL_003f: stloc.s j
IL_0041: br.s IL_0054
IL_0043: nop
IL_0044: ldloc.0
IL_0045: ldloc.2
IL_0046: callvirt instance bool
[mscorlib]System.Collections.ArrayList::Contains(object)
IL_004b: stloc.s objectInList
IL_004d: nop
IL_004e: ldloc.s j
IL_0050: ldc.i4.1
IL_0051: add
IL_0052: stloc.s j
IL_0054: ldloc.s j
IL_0056: ldc.i4 0x457
IL_005b: clt
IL_005d: stloc.s CS$4$0000
IL_005f: ldloc.s CS$4$0000
IL_0061: brtrue.s IL_0043
IL_0063: ldstr "Contains took "
IL_0068: call int32 [mscorlib]System.Environment::get_TickCount()

=================================================

Based on the IL reference, these IL instructions are setting and loading
data into local variables and also do some judgement on the value.

Therefore, the 2.0 code actually sacrifice some performance to improve the
strength of such weak-type collection's methods. Also, based on my
experience, there're many such adjustment in the base class library of .net
framework which improve the code strength and type-safety with some
sacrifice on the performance. However, these performance hit is really
worthy from a higher layer perspective(such as from a whole application's
designing viewpoint).

Please feel free to let me know if there is any other information you
wonder.

Sincerely,

Steven Cheng

Microsoft MSDN Online Support Lead



==================================================

Get notification to my posts through email? Please refer to
http://msdn.microsoft.com/subscriptions/managednewsgroups/default.aspx#notif
ications.



Note: The MSDN Managed Newsgroup support offering is for non-urgent issues
where an initial response from the community or a Microsoft Support
Engineer within 1 business day is acceptable. Please note that each follow
up response may take approximately 2 business days as the support
professional working with you may need further investigation to reach the
most efficient resolution. The offering is not appropriate for situations
that require urgent, real-time or phone-based interactions or complex
project analysis and dump analysis issues. Issues of this nature are best
handled working with a dedicated Microsoft Support Engineer by contacting
Microsoft Customer Support Services (CSS) at
http://msdn.microsoft.com/subscriptions/support/default.aspx.

==================================================



This posting is provided "AS IS" with no warranties, and confers no rights.
 
Hello Robert,

Have you got any further ideas on this issue or does the information in my
last reply helps you a little? If there is anything else we can help or any
other information you wonder, please feel free to let me know.

Sincerely,

Steven Cheng

Microsoft MSDN Online Support Lead


This posting is provided "AS IS" with no warranties, and confers no rights.
 
Looks like about the only change is an additional null test in the loop.
Hard to believe a single test would account for 20%, but maybe.
I think this fixes a bug so it is needed code.

--
William Stacey [MVP]

| We are moving to .NET2.0 - and have noticed that .Contains() seems to be
| around 20% slower under NET2, compared to NET1.1.
|
| This code shows the issue:
| static void Main(string[] args)
| {
| System.Collections.ArrayList list = new System.Collections.ArrayList();
|
| //Setup code
| //
| //Add 10000 objects to a collection.
| //Don't care what type the object is for the purposes of this
| demonstration
| for (int i=0; i<100000; i++)
| {
| list.Add(new EventArgs());
| }
| //We are going to find this object (intentially right at the end of the
| list)
| object objectToFind = list[99998];
| //
| // End setup code
|
| // Timing code
| //
| long startT = Environment.TickCount;
| //Find the object 1111 times in the collection
| for (int j=0;j<1111;j++)
| {
| bool objectInList = list.Contains(objectToFind);
| }
| System.Console.WriteLine("Contains took
"+(Environment.TickCount-startT)+"
| (ms)");
| System.Console.ReadLine();
| }
|
| Under NET1.1 I consistently get times in the order of 20% quicker than the
| same code under NET2.
|
| Has anyone else noticed this? Is there a way I can avoid whatever new code
| is being executed in the bowels of the framework?
| Thanks
| Rob
|
|
|
 
Thanks all - for you replies. I'm happy enough that the 15%-20% slow-down is
at least experienced by others and its not me on crack.

Collectively, your replies have given me a few hints as to ways to improve
things. (Avoid .Contains were we can, and where we can't, I'll investigate
other Comparers)

Thanks again
Rob
 
Hi Greg. "default comparison"? In the code, the only difference I see is 1
line with and added test for null.

--
William Stacey [MVP]

|I believe the default comparison is also a bit slower.
|
| Cheers,
 
Rob, have you tried substituting List<T> for ArrayList? Perhaps the
implementation of that collection is a bit faster.
 
Hello Chris,

Based on my check, the Generic List<T> will also suffer such an performance
overhead since it will also perform additional typesafe and null value
checking. Anyway, I think it is worthy of such overhead which may prevent
many potential problems from an application's perspective.

Sincerely,

Steven Cheng

Microsoft MSDN Online Support Lead


This posting is provided "AS IS" with no warranties, and confers no rights.
 
Strangely enough - List<T> "Contains" is measureably SLOWER (about 10%
slower) than ArrayList's "Contains".
Sigh...
 
Sorry about that, I should have checked the implementations first...

The algorithms look identical in Reflector but List<T>.Contains uses
an EqualityComparer<T> to check for identical elements while
ArrayList.Contains calls the usual Equals method. I suppose that
might account for the difference.
 
William Stacey said:
Looks like about the only change is an additional null test in the loop.
Hard to believe a single test would account for 20%, but maybe.
I think this fixes a bug so it is needed code.
Click to expand...

There is definitely an unneeded test for null in the second loop in
ArrayList.Contains(item)
Equals is required to be commutative
(http://msdn2.microsoft.com/en-us/library/ms173147.aspx), so one can easily
call item.Equals since item has already been found to be non-null, instead
of on each array element, especially since Equals is required to test its
argument for null anyway.

Furthermore, it seems that List<T>.FindIndex(delegate (T x) { return
--
William Stacey [MVP]

| We are moving to .NET2.0 - and have noticed that .Contains() seems to be
| around 20% slower under NET2, compared to NET1.1.
|
| This code shows the issue:
| static void Main(string[] args)
| {
| System.Collections.ArrayList list = new
System.Collections.ArrayList();
|
| //Setup code
| //
| //Add 10000 objects to a collection.
| //Don't care what type the object is for the purposes of this
| demonstration
| for (int i=0; i<100000; i++)
| {
| list.Add(new EventArgs());
| }
| //We are going to find this object (intentially right at the end of the
| list)
| object objectToFind = list[99998];
| //
| // End setup code
|
| // Timing code
| //
| long startT = Environment.TickCount;
| //Find the object 1111 times in the collection
| for (int j=0;j<1111;j++)
| {
| bool objectInList = list.Contains(objectToFind);
| }
| System.Console.WriteLine("Contains took
"+(Environment.TickCount-startT)+"
| (ms)");
| System.Console.ReadLine();
| }
|
| Under NET1.1 I consistently get times in the order of 20% quicker than
the
| same code under NET2.
|
| Has anyone else noticed this? Is there a way I can avoid whatever new
code
| is being executed in the bowels of the framework?
| Thanks
| Rob
|
|
|
Click to expand...
 
Back
Top