CODEWITHSUNDEEP
c#performancehashset
Sam Saffron
Sam Saffron

Reputation: 131092

HashSet performance Add vs Contains for existing elements

For some reason, it seems the Add operation on a HashSet is slower than the Contains operation when the element already exists in the HashSet.

Here is proof: 

    Stopwatch watch = new Stopwatch();
    int size = 10000;
    int iterations = 10000;


    var s = new HashSet<int>();
    for (int i = 0; i < size; i++) {
        s.Add(i);
    }

    Console.WriteLine(watch.Time(() =>
    {
        for (int i = 0; i < size; i++) {
            s.Add(i);
        }
    }, iterations));

    s = new HashSet<int>();
    for (int i = 0; i < size; i++) {
        s.Add(i);
    }

    // outputs: 47,074,764

    Console.WriteLine(watch.Time(() =>
    {
        for (int i = 0; i < size; i++) {
            if (!s.Contains(i))
                s.Add(i);
        }
    }, iterations));

    // outputs: 41,125,219

Why is Contains faster than Add for already-existing elements?

Note: I'm using this Stopwatch extension from another SO question.

    public static long Time(this Stopwatch sw, Action action, int iterations) {
        sw.Reset();
        sw.Start();
        for (int i = 0; i < iterations; i++) {
            action();
        }
        sw.Stop();

        return sw.ElapsedTicks;
    }

UPDATE: Internal testing has revealed that the big performance diff only happens on the x64 version of the .NET framework. With the 32 bit version of the framework Contains seems run at identical speed to add (in fact it appears that the version with the contains runs a percent slower in some test runs) On X64 versions of the framework, the version with the contains seems to run about 15% faster.

Upvotes: 15

Views: 12087

Answers (3)

Jim Mischel
Jim Mischel

Reputation: 133950

AddIfNotPresent does an additional divide that Contains doesn't perform. Take a look at the IL for Contains:

IL_000a:  call       instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
  IL_000f:  stloc.0
  IL_0010:  ldarg.0
  IL_0011:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_0016:  ldloc.0
  IL_0017:  ldarg.0
  IL_0018:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_001d:  ldlen
  IL_001e:  conv.i4
  IL_001f:  rem
  IL_0020:  ldelem.i4
  IL_0021:  ldc.i4.1
  IL_0022:  sub
  IL_0023:  stloc.1

This is computing the bucket location for the hash code. The result is saved at local memory location 1.

AddIfNotPresent does something similar, but it also saves the computed value at location 2, so that it can insert the item into the hash table at that position if the item doesn't exist. It does that save because one of the locations is modified later in the loop that goes looking for the item. Anyway, here's the relevant code for AddIfNotPresent:

IL_0011:  call       instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
  IL_0016:  stloc.0
  IL_0017:  ldloc.0
  IL_0018:  ldarg.0
  IL_0019:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_001e:  ldlen
  IL_001f:  conv.i4
  IL_0020:  rem
  IL_0021:  stloc.1
  IL_0022:  ldarg.0
  IL_0023:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_0028:  ldloc.0
  IL_0029:  ldarg.0
  IL_002a:  ldfld      int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
  IL_002f:  ldlen
  IL_0030:  conv.i4
  IL_0031:  rem
  IL_0032:  ldelem.i4
  IL_0033:  ldc.i4.1
  IL_0034:  sub
  IL_0035:  stloc.2

Anyway, I think the extra divide is what's causing Add to take more time than Contains. At first glance, it looks like that extra divide could be factored out, but I can't say for sure without spending a little more time deciphering the IL.

Upvotes: 11

Greg Beech
Greg Beech

Reputation: 136577

My guess is that you ran your test from Visual Studio which caused the inlining of AddIfNotPresent into Add to be suppressed, so you're seeing the result of an extra level of indirection in the method calls.

If I compile and run from the command line to remove any VS trickery...

> csc /o+ /t:exe Program.cs
> Program.exe

...then there is no performance difference.

Sample outputs (representative of a larger number of tests):

35036174
35153818

35225763
34862330

35047377
35033323

Upvotes: 1

John Rasch
John Rasch

Reputation: 63435

Interesting, on my machine (Dell Latitude D630, dual-core 2.2 Ghz) I am getting nearly identical results for both tests unless I run the stopwatch against a null action before the tests. For example:

I run the tests with the exact code you have given in the question:

Without Contains(): 8205794
With Contains():    8207596

If I modify the code in this manner:

After:

Stopwatch watch = new Stopwatch();
int size = 10000;
int iterations = 10000;

Add:

watch.Time(null, 0);

My results become:

Without Contains(): 8019129
With Contains():    8275771

This seems to me like something odd is going on inside of the Stopwatch that is causing these fluctuations.

Upvotes: 1

Related Questions