Hash Lookup vs Binary Search

So I was browsing through our code base, and saw that in several places, we have some binary searches. Binary search is known to be pretty effective when we are finding things in a sorted array. It has O(lg(n)) running time. Hashtables, on the other hand, have O(1) running time. For small tables, though, binary search can be faster than hashtables since a comparison is cheaper than computing a hash function. At some point, though, we can expect the hashtable to out perform binary search. Let's try and find out what the break-even point is:

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace HashVsBinary
	{
	class Program
	{
	static void Main(string[] args)
	{
	var r = new Random();
	var targets = Enumerable.Range(0, 1000 * 1000).Select(_ => r.Next(int.MaxValue)).ToList();
	for (int totalCount = 1; totalCount < 1000*1000*10; totalCount*=2)
	{
	var a = Enumerable.Range(0, totalCount).Select(_ => r.Next(int.MaxValue)).Distinct().Select(v => new thing(v)).OrderBy(t => t.value).ToArray();
	var d = a.ToDictionary(t => t.value);
	var watch = new System.Diagnostics.Stopwatch();
	{
	watch.Start();
	var found = targets.Select(t => BinarySearch(t, a)).Where(t => t != null).Count();
	watch.Stop();
	Console.WriteLine(string.Format("found {0} things out of {2} in {1} ms with binary search", found, watch.ElapsedMilliseconds, a.Length));
	}
	{
	watch.Restart();
	var found = targets.Select(t => HashSearch(t, d)).Where(t => t != null).Count();
	watch.Stop();
	Console.WriteLine(string.Format("found {0} things out of {2} in {1} ms with hash search", found, watch.ElapsedMilliseconds, d.Keys.Count));
	}
	}
	Console.ReadLine();
	}
	static thing HashSearch(int needle, Dictionary<int, thing> hash)
	{
	if (!hash.ContainsKey(needle))
	return null;
	return hash[needle];
	}
	static thing BinarySearch(int needle, thing[] sortedHaystack)
	{
	return BinarySearch(needle, sortedHaystack, 0, sortedHaystack.Length - 1);
	}
	static thing BinarySearch(int needle, thing[] sortedHaystack, int minimum, int maximum)
	{
	if (minimum > maximum)
	return null;
	var middle = (minimum + maximum) / 2;
	if (needle == sortedHaystack[middle].value)
	return sortedHaystack[middle];
	if (needle < sortedHaystack[middle].value)
	return BinarySearch(needle, sortedHaystack, minimum, middle - 1);
	return BinarySearch(needle, sortedHaystack, middle + 1, maximum);
	}
	class thing
	{
	public int value;
	public thing(int v)
	{
	value = v;
	}
	}
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

And here's the results:

Well, it doesn't look like binary search is ever better than the hashtable. Binary search is logarithmic at first, but then it starts growing faster. The hashtable performs pretty consistently at the beginning, and then slowly grows at the end.

The abnormalities are probably due to caching. There's two places where the slope changes. Those probably correspond to different layers of memory. Maybe first an L2 cache miss, and then an L3 cache miss.

I also implemented an iterative binary search:

	static thing BinarySearch(int needle, thing[] sortedHaystack)
	{
	var min = 0;
	var max = sortedHaystack.Length - 1;
	while (min <= max)
	{
	var middle = (min + max) / 2;
	if (needle == sortedHaystack[middle].value)
	return sortedHaystack[middle];
	if (needle < sortedHaystack[middle].value)
	{
	max = middle - 1;
	}
	else
	{
	min = middle + 1;
	}
	}
	return null;
	}

view raw gistfile1.cs hosted with ❤ by GitHub

It did not perform significantly better. Hashtable was still always faster.

An Emperical Look at .NET's Gen 0 Garbage Collection

A while back, we had an issue with .NET's garbage collector. In particular, Gen 0, which should be super efficient and fast, was slowing down our multi-threaded application.

We had a 24-core machine, and an application that needs to do 5000 totally independent tasks. No matter who many threads we threw at it, task manager always showed about 200% CPU usage. Digging into the concurrent profiler, we saw that many threads were paused all over the place. The more threads we started, the more time they paused. Looking at what they were blocking on, they were all blocking on memory allocation. Every few milliseconds, one thread would enter Gen 0, and start garbage collecting. The other threads would quickly block when they tried to allocate some memory. Then Gen 0 would complete, and all other threads would continue again. The more threads we had, the more frequent these garbage collection cycles became, causing our application to never exceed 200% CPU on a 24-core system.

Let's try to reproduce it in a simpler program.

First, let's show that threading does work with a simple program:

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	namespace Gen0
	{
	class Program
	{
	static void Main(string[] args)
	{
	var ts = new System.Diagnostics.Stopwatch();
	foreach (var threadCount in Enumerable.Range(1, 8))
	{
	ts.Restart();
	Enumerable.Range(0, 100).AsParallel().WithDegreeOfParallelism(threadCount).ForAll(
	_ => DoStuff());
	ts.Stop();
	Console.WriteLine(string.Format("{1} threads: {0} ms", ts.ElapsedMilliseconds, threadCount));
	}
	Console.ReadLine();
	}
	static void DoStuff()
	{
	var r = new Random();
	var sum = 0;
	for (int i = 0; i < 1000*1000; i++)
	{
	sum += r.Next(2);
	}
	}
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

And the output on my 4-core machine:

Looks like it's working. So let's add some memory allocations:

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	namespace Gen0
	{
	class Program
	{
	static void Main(string[] args)
	{
	var ts = new System.Diagnostics.Stopwatch();
	foreach (var arraySize in new int[] {1, 10, 100, 1000, 10000})
	{
	foreach (var threadCount in Enumerable.Range(1, 6))
	{
	ts.Restart();
	Enumerable.Range(0, 100).AsParallel().WithDegreeOfParallelism(threadCount).ForAll(
	_ => DoStuff(arraySize));
	ts.Stop();
	Console.WriteLine(string.Format("{2} ints per object, {1} threads: {0} ms", ts.ElapsedMilliseconds, threadCount, arraySize));
	}
	}
	Console.ReadLine();
	}
	static void DoStuff(int size)
	{
	var r = new Random();
	var sum = 0;
	for (int i = 0; i < 1000*100; i++)
	{
	var s = new Stuff(r, size);
	sum += s.Next();
	}
	}
	class Stuff
	{
	private Random rand;
	int[] lotsOfSpace;
	public Stuff(Random r, int size)
	{
	rand = r;
	lotsOfSpace = new int[size];
	}
	public int Next()
	{
	return rand.Next(2);
	}
	}
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Here are the results:

 
 


  

  
threadCount
 

  
arraySize
  
1
  
2
  
3
  
4
  
5
  
6
 

  
1
  
658
  
376
  
278
  
223
  
208
  
211
 

  
10
  
677
  
392
  
282
  
241
  
227
  
237
 

  
100
  
1049
  
700
  
581
  
535
  
526
  
544
 

  
1000
  
4607
  
3826
  
3895
  
3918
  
4289
  
4399
 

  
10000
  
34185
  
35658
  
41861
  
46026
  
49758
  
52625
 

This time around, I am allocating some memory on the heap. There's probably some magic that .NET is doing for me to burn all those extra CPU cycles for larger sizes, but the trend I am looking for is clearly there. When the objects are large, scaling the number of threads does not give me as much of a performance gain as I had hoped.

Let's see if I can tune it for that CPU graph that I am looking for:

This is my CPU graph while scaling through the 6 threads. We see that the CPU usage goes up, but never hits 100% even when using 6 threads.

Now let's try some of the other garbage collector configurations. Let's enable gcServer:

 
 


  

  
threadCount
 

  
arraySize
  
1
  
2
  
3
  
4
  
5
  
6
 

  
1
  
677
  
383
  
282
  
189
  
202
  
255
 

  
10
  
724
  
373
  
279
  
509
  
309
  
273
 

  
100
  
1312
  
696
  
627
  
849
  
1565
  
2317
 

  
1000
  
6329
  
4596
  
4457
  
9292
  
13110
  
12540
 

  
10000
  
49819
  
48821
  
44955
  
50832
  

  

 

How about gcServer disabled, and gcConcurrent disabled?

 
 


  

  
threadCount
 

  
arraySize
  
1
  
2
  
3
  
4
  
5
  
6
 

  
1
  
644
  
400
  
277
  
221
  
213
  
207
 

  
10
  
678
  
380
  
295
  
243
  
223
  
224
 

  
100
  
1055
  
665
  
546
  
516
  
514
  
520
 

  
1000
  
4712
  
3736
  
3692
  
3984
  
3900
  
4052
 

  
10000
  
34827
  
35426
  
43847
  

  

  

 

How about gcServer enabled, and gcConcurrent disabled?

 
 


  

  
threadCount
 

  
arraySize
  
1
  
2
  
3
  
4
  
5
  
6
 

  
1
  
675
  
346
  
273
  
192
  
175
  
178
 

  
10
  
710
  
371
  
281
  
211
  
193
  
197
 

  
100
  
1309
  
753
  
588
  
529
  
500
  
562
 

  
1000
  
7537
  
4905
  
4591
  
5654
  
4509
  
4457
 

  
10000
  
49413
  
46509
  
46088
  
46285
  
46737
  

 

So it seems that the configurations make some impact, but they are not going to solve our problems completely. Let's see if we can do something better.

What if we try to manage our own memory by maintaining our own list of Stuff objects that can be reused?

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	namespace Gen0
	{
	class Program
	{
	static void Main(string[] args)
	{
	var ts = new System.Diagnostics.Stopwatch();
	foreach (var arraySize in new int[] { 1, 10, 100, 1000, 10000 })
	{
	foreach (var threadCount in Enumerable.Range(1, 6))
	{
	ts.Restart();
	Enumerable.Range(0, 100).AsParallel().WithDegreeOfParallelism(threadCount).ForAll(
	_ => DoStuff(arraySize));
	ts.Stop();
	Console.WriteLine(string.Format("{2} ints per object, {1} threads: {0} ms", ts.ElapsedMilliseconds, threadCount, arraySize));
	}
	}
	Console.ReadLine();
	}
	static void DoStuff(int size)
	{
	var r = new Random();
	var sum = 0;
	for (int i = 0; i < 1000 * 100; i++)
	{
	using (var s = Stuff.Create(r, size))
	{
	sum += s.Next();
	}
	}
	}
	class Stuff : IDisposable
	{
	private Random rand;
	int[] lotsOfSpace;
	private Stuff() { }
	public int Next()
	{
	return rand.Next(2);
	}
	public void Dispose()
	{
	stuffStore.Add(this);
	}
	private static System.Collections.Concurrent.ConcurrentBag<Stuff> stuffStore =
	new System.Collections.Concurrent.ConcurrentBag<Stuff>();
	private static System.Collections.Concurrent.ConcurrentDictionary<int, int[]> emptyArrays =
	new System.Collections.Concurrent.ConcurrentDictionary<int, int[]>();
	public static Stuff Create(Random r, int size)
	{
	Stuff next;
	if (stuffStore.TryTake(out next))
	{
	next.rand = r;
	if (next.lotsOfSpace.Length != size)
	{
	next.lotsOfSpace = new int[size];
	emptyArrays.AddOrUpdate(size, new int[size], (key, prev) => prev);
	}
	else
	{
	int[] emptyArray;
	emptyArrays.TryGetValue(size, out emptyArray);
	System.Diagnostics.Debug.Assert(emptyArray != null);
	emptyArray.CopyTo(next.lotsOfSpace, 0);
	}
	return next;
	}
	emptyArrays.AddOrUpdate(size, new int[size], (key, prev) => prev);
	return new Stuff
	{
	rand = r,
	lotsOfSpace = new int[size]
	};
	}
	}
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

The code has gotten more complicated, and the results show it as well:

 
 


  

  
threadCount
  

  

  

  

  

 

  
arraySize
  
1
  
2
  
3
  
4
  
5
  
6
 

  
1
  
3684
  
2124
  
1510
  
1186
  
1200
  
1196
 

  
10
  
3841
  
2178
  
1497
  
1273
  
1200
  
1162
 

  
100
  
4423
  
2737
  
1782
  
1344
  
1399
  
1256
 

  
1000
  
7941
  
4294
  
2955
  
2364
  
2480
  
2170
 

  
10000
  
60650
  
32238
  
22427
  
18197
  
17902
  
16450
 

But we do notice that this scales fairly well with the number of threads. In fact, 6 threads is almost always better than 4 threads. Very weird.

I am not going to delve into the weirdness today because I've come across a solution that scales well, but is much slower on small objects, and twice as slow on a single thread for large objects. And just for kicks, here are the times if we don't empty out the array when we reuse it:

 
 


  

  
threadCount
  

  

  

  

  

 

  
arraySize
  
1
  
2
  
3
  
4
  
5
  
6
 

  
1
  
2674
  
1414
  
1328
  
857
  
801
  
854
 

  
10
  
2678
  
1418
  
997
  
847
  
876
  
886
 

  
100
  
2699
  
1396
  
1105
  
791
  
801
  
764
 

  
1000
  
2714
  
1410
  
1087
  
784
  
853
  
811
 

  
10000
  
2727
  
1412
  
1005
  
870
  
955
  
961
 

From these experiments, we can see that the garbage collector works very well for small objects. However, it has trouble with large objects. For large objects, we would do well maintaining our own pool of resources. This method seems to be twice as slow, but it scales fairly well on my 4 core system.


I didn't take very good measurements, but the number of gen 0 collections went from 10's of thousands when .NET was managing the memory, to just hundreds when I was doing it myself. When large objects were an issue, the number of gen 1 and 2 collections went from the single digits to thousands.