Performance Quiz #4 -- Of Sets and Sundry
By popular demand, here is the next exciting Performance Quiz -- your chance for fame, glory and recognition or at least a few minutes of amusement anyway :)
Below are two methods for taking an array of strings in some random order, removing the duplicates from the array and then counting up how many distinct strings there were.
For the test setup the number of strings is the input "cStrings" -- we make the strings "0", "1", and so forth up to cStrings as our test strings and then set "cTests" to be 5 times the number of strings. "testOrder" is an array of cTests random numbers in the range [0, cStrings-1]
The questions are:
Q1: What is the time complexity of each algorithm?
Q2: The space usage?
Q3: Is the ListDictionary ever faster than the hashtable or smaller? If so, for what values of "cStrings" is this true?
static int TestViaListDictionary()
{
ListDictionary t = new ListDictionary();
int i;
for (i = 0; i < cTests; i++)
{
String key = testString[testOrder[i]];
if (!t.Contains(key))
t.Add(key, key);
}
int count = 0;
foreach (Object k in t) count++;
return count;
}
static int TestViaHashtable()
{
Hashtable t = new Hashtable();
int i;
for (i = 0; i < cTests; i++)
{
String key = testString[testOrder[i]];
if (!t.ContainsKey(key))
t.Add(key, key);
}
int count = 0;
foreach (Object k in t) count++;
return count;
}
The specific initialization code looks like this:
static String[] testString;
static int[] testOrder;
static int cStrings;
static int cTests;
static void InitializeTest()
{
int i;
testString = new String[cStrings];
for (i = 0; i < cStrings; i++)
testString[i] = i.ToString();
testOrder= new int[cTests];
Random r = new Random();
for (i= 0; i < cTests; i++)
testOrder[i] = r.Next() % cStrings;
}
Comments
- Anonymous
August 18, 2004
The comment has been removed - Anonymous
August 18, 2004
Question 1:
ListDictionary is O(N^2), because the call to "Contains" is a linear search, and Contains is called cTests times.
HashTable is O(N), because ContainsKey for a hashtable is a O(1) operation.
Question 2: Both are pretty close for small values. For larger values, ListDictionary would use less space because when the number of elements in the list reaches the total elements, in list doubles in size.
Compare this to Hashtable, which must increase in size to the next largest PRIME bucket size. Also, Hashtables by their nature never use up all of the buckets they have allocated, so they are almost always going to use more space for the same amount of data.
Question 3: According to the documentation, ListDictionary is faster for values of cTests < ~10. This is probably do to the fact it is faster to simply walk the list instead of during all the bucket lookups that a hashtable would require. - Anonymous
August 18, 2004
The comment has been removed - Anonymous
August 18, 2004
Here's some observed behavior...
I ran several tests. The first thing I noticed was that the ListDictionary must do some one-time initializations because the results I got were different if I ran some warmup tests first or if I simply starting running tests for measurements.
Using a simple TimeSpan to measure test runs (Perf counters would be much better for small numbers of strings...)
For 10 strings, both ran in less then 1 millisecond if ListDictionary was warmed up. If it was not then it took 46 mS and ths hashtable took 15 mSec.
100 strings both ran in less then 1 mSec
1000 strings, ListDictionary ran in 93 mSec and hashtable less then 1 mSec
10000 strings, ListDictionary ran in 25781.25 mSec (25 seconds), and hashtable in 46.875 mSec, which is 550 times faster then a ListDictionary.
I didn't have time to check memory allocations.
I'd guess that hashtable uses more memory due to extra allocations for buckets, but that might be swamped by ListDictionary reallocations. I'd want to run it under a memory profiler to be sure but I'm out of time. - Anonymous
August 18, 2004
Impressive comments so far, nice work guys! :) - Anonymous
August 18, 2004
BTW...why use:
foreach (Object k in t) count++;
when t.Count was available?
I ran the test both ways and while the actual measured time took longer to run the test the overall difference between the two collections still remained roughly the same so it did not seem to be worth making a distinction. - Anonymous
August 18, 2004
Oh I guess I wasn't very clear about the point there -- I wanted to benchmark the enumeration. The fact that it's a count is incidental to walking the elements which is the point. - Anonymous
August 18, 2004
The comment has been removed - Anonymous
August 18, 2004
Darn it you posted that response about enumeration while I was typing in my lengthy post. - Anonymous
August 18, 2004
Yes but yours is so good :)
I may not have to publish an answer at all if this keeps up :) - Anonymous
August 18, 2004
Some empirical observations:
Running cStrings at 10000, the ListDictionary is generally faster. I ran the loops for 50 times for both (from cold start), with 100ms pause between each run, and the ListDictionary is 66000 ticks (0,0184s) faster. At 100000 the Hashtable is 504367 ticks (0,141s) faster. I think the zero point is somewhere 15000-18000 cStrings. The initialization time for both is almost the same. This was something I was expecting (typo in my first feedback, should have written <20k, not 20)
From the allocation point, there are no big differences as far as I can see. Using performance monitor, the biggest difference is that Hashtable uses a lot of more Gen0 (760250 bytes vs. 538012 of ListDictionary, average).
IMHO, the allocation profiler (from Gotdotnet) indicated for both apparently good locality of memory allocation for the lists/tables (if I understand correctly the graphs).
I noticed a curious thing because of my error in the code, where I left the cTests at 5. The loop times for Hashtable and ListDictionary are almost identical. The curious thing is that the first 16 (always the first 16, tested 8 times to be sure) iterations took 300-500ticks, the subsequent iterations fell under 100, mostly at 80ticks. I tried 100 iterations and they remained under 100 after the first 16 iterations. GC gave up, or warmed up..? - Anonymous
August 18, 2004
The comment has been removed - Anonymous
August 19, 2004
I decided to get more accurate measurements so I wrote a wrapper around the QueryPerformanceCounter Win32 API to get counts at 100 nanoSecond intervals. I also refactored the test to measure the times separately for enumerating the collection and for invoking the methods Contains and Add for each collection type.
The results were interesting. The enumeration time is roughly the same for both collections. For the ListDictionary class the method Contains is definitely the time hog, but the method Add takes 2nd place. The same methods for the Hashtable are far more efficient for large sets of data. I still haven't checked memory allocations so I don't know if the difference is due to trading data space for speed or just differences in algorithms. I'd suspect the former.
Cache warmups (10 strings)
Dictionary warmup: Enumeration 969 uSecs; Total Test 64.93 mSecs.
Hashtable warmup: Enumeration 79 uSecs; Total Test 2.15 mSecs.
Testing 1 strings
Dictionary: Enumeration 10 uSecs; Contains: 23 uSecs; Add: 5 uSecs; Total: 98 uSecs.
Hashtable: Enumeration 9 uSecs; Contains: 24 uSecs; Add: 5 uSecs; Total: 100 uSecs.
Testing 1 strings
Dictionary: Enumeration 8 uSecs; Contains: 22 uSecs; Add: 5 uSecs; Total: 95 uSecs.
Hashtable: Enumeration 6 uSecs; Contains: 23 uSecs; Add: 5 uSecs; Total: 120 uSecs.
Testing 1 strings
Dictionary: Enumeration 7 uSecs; Contains: 21 uSecs; Add: 5 uSecs; Total: 92 uSecs.
Hashtable: Enumeration 6 uSecs; Contains: 22 uSecs; Add: 5 uSecs; Total: 91 uSecs.
Testing 5 strings
Dictionary: Enumeration 8 uSecs; Contains: 105 uSecs; Add: 22 uSecs; Total: 360 uSecs.
Hashtable: Enumeration 8 uSecs; Contains: 110 uSecs; Add: 22 uSecs; Total: 368 uSecs.
Testing 10 strings
Dictionary: Enumeration 13 uSecs; Contains: 505 uSecs; Add: 45 uSecs; Total: 993 uSecs.
Hashtable: Enumeration 9 uSecs; Contains: 214 uSecs; Add: 57 uSecs; Total: 710 uSecs.
Testing 100 strings
Dictionary: Enumeration 36 uSecs; Contains: 2.947 mSecs; Add: 609 uSecs; Total: 7.740 mSecs.
Hashtable: Enumeration 24 uSecs; Contains: 2.170 mSecs; Add: 504 uSecs; Total: 7.167 mSecs.
Testing 1000 strings
Dictionary: Enumeration 193 uSecs; Contains: 107.119 mSecs; Add: 22.6 mSecs; Total: 171.765 mSecs.
Hashtable: Enumeration 221 uSecs; Contains: 22.488 mSecs; Add: 4.805 mSecs; Total: 69.792 mSecs.
Testing 10000 strings
Dictionary: Enumeration 1.932 mSecs; Contains: 22.315.314 seconds; Add: 5.85.854 seconds; Total: 27.955.303 seconds.
Hashtable: Enumeration 2.747 mSecs; Contains: 245.769 mSecs; Add: 51.936 mSecs;Total: 756.750 mSecs.
test done - Anonymous
August 19, 2004
I feel like pointing out that the memory footprint of a ListDictionary will increase somewhat drastically running on a 64-bit machine when compared to a Hashtable. Of course, both will increase quite a bit due to all of the boxed references for every key and value. Then again, boxed references to ValueTypes are a bit of a waste to begin with.
Luckily, we don't have that problem in Whidbey. - Anonymous
August 19, 2004
There is no inherent boxing requirement in this problem -- the collection class usages all involve strings. - Anonymous
August 19, 2004
btw: I'll be posting "the solution" later today including source code for a benchmark program I wrote so you can try it yourself. Like David I used QueryPerformanceCounter to get the best measurements. It's pretty easy to set it up. - Anonymous
August 19, 2004
Oh, right....strings. It seems I was getting off topic. On the other hand, the size of all string references will double on a 64-bit machine as well. There's no way around that. <g>
But seeing as most dictionaries are in some form of string->object, the issue of boxing overhead isn't usually that big a deal. - Anonymous
November 27, 2007
This is not part of my series on performance tuning a specific app. Problem: I have a Registry class in which I want to place a generic collection of objects. In this way I can add new items to the...