Home > Rant > Are built in C# classes really that great?

Are built in C# classes really that great?

Disclaimer: same as before…

UPDATE: There was an error in the test which I explain in the next post.

I have created my own sorted list which implements the same interfaces as SortedList, but it has exactly what I need for a sorted non-binary tree structure. Done a little testing and as it was obvious from the start, my class is faster.

My results:
random insertion and deletion: 1024
ZSortedList: 5ms (+1ms)
SortedList: 4ms

random insertion and deletion: 1024 * 4
ZSortedList: 22ms
SortedList: 23ms (+1ms)

random insertion and deletion: 1024 * 8
ZSortedList: 57ms
SortedList: 77ms  (+20ms)

random insertion and deletion: 1024 * 64
ZSortedList: 3260ms
SortedList: 6184ms  (+2924ms)

random insertion and deletion: 1024 * 100
ZSortedList: 7844ms
SortedList: 15131ms  (+7287ms)

Running conditions:
Both lists start out with a capacity of 1024 * 8 items
When I didn’t set a starting capacity for my own list, it was a bit slower than SortedList with low item count, but once I set the number of items to add to 1024 * 8 or higher, my list suddenly won every test, so I’m guessing this is near the default capacity of a SortedList.

Both lists have KeyValuePair<string,int> items.
This is needed because my list doesn’t have a type for keys, the items hold the keys and it would have been unfair if I had to create KeyValuePairs for my own list but not for the SortedList.

The key used for comparing items was a string in both cases. I passed my own IComparer to both lists to compare them. The key was a random number between 0 and 1000000000 converted to string.

I used a Stopwatch object to measure the time.

Conclusion:

My list checks the position, and if it is free, adds the item there. With the original code that I wanted to test, SortedList searched for the position twice, once to see if it can add the item and again to add it for real. In the modified code it only checks once and I have to catch its exceptions when trying to insert to an occupied position, but the results stayed nearly the same.

It is difficult to draw a conclusion. Either the try/catch handling takes as much time as searching for a string position, or there is some strange caching going on in C#. In the latter case I can’t say for sure whether my class is really that fast. I think what really slows down SortedList is not looking for the position at all, but adding the item, that’s why I couldn’t see much time difference in the two test cases. I have no idea what inner data structure it might use, probably some kind of list. My class on the other hand works on the most basic of data structures, an array, using the Array.BinarySearch static function to find the string position, and the Array.Copy when the array needs to be recreated. It’s good to know that C# array handling is working nicely, but I think there might be other strange results if I tried to recreate all the other collection types as well.

Here is the full code before someone says I cheated:

ZSortedList<KeyValuePair<string, int>> l1 =
    new ZSortedList<KeyValuePair<string, int>>(8*1024,new PlainComPair());
SortedList<KeyValuePair<string, int>, int> l2 =
    new SortedList<KeyValuePair<string, int>, int>(8*1024,new ComPair());
Stopwatch watch = new Stopwatch();
Random r = new Random();
string key;
int val;
watch.Start();
for (int ix = 0; ix < limit; ++ix)
{
    key = r.Next(1000000000).ToString();
    val = r.Next(1000000);
    var pos = l1.AddPos(key);
    if (pos != null)
        l1.AddToPos(pos, new KeyValuePair<string, int>(key, val));
    else
        ix--;
}
while (l1.Count > 0)
{
    l1.RemoveAt(r.Next(l1.Count));
}
watch.Stop();
long n1 = watch.ElapsedMilliseconds;
watch.Reset();
watch.Start();
for (int ix = 0; ix < limit; ++ix)
{
    key = r.Next(1000000000).ToString();
    val = r.Next(1000000);
    KeyValuePair<string, int> pair = new KeyValuePair<string, int>(key,val);
//if (!l2.ContainsKey(pair)) // <-- Commented out and added the try/catch block
    try
    {
        l2.Add(pair, val);
    }
    catch (Exception)
    {
        ix--;
    }
}
while (l2.Count > 0)
{
    l2.RemoveAt(r.Next(l1.Count));
}
watch.Stop();
long n2 = watch.ElapsedMilliseconds;
Advertisements
Categories: Rant Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: