68

I investigated performance degradation and tracked it down to slow HashSets.
I have structs with nullable values that are used as a primary key. For example:

public struct NullableLongWrapper
{
    private readonly long? _value;

    public NullableLongWrapper(long? value)
    {
        _value = value;
    }
}

I noticed that creating a HashSet<NullableLongWrapper> is exceptionally slow.

Here's an example using BenchmarkDotNet: (Install-Package BenchmarkDotNet)

using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;

public class Program
{
    static void Main()
    {
        BenchmarkRunner.Run<HashSets>();
    }
}

public class Config : ManualConfig
{
    public Config()
    {
        Add(Job.Dry.WithWarmupCount(1).WithLaunchCount(3).WithTargetCount(20));
    }
}

public struct NullableLongWrapper
{
    private readonly long? _value;

    public NullableLongWrapper(long? value)
    {
        _value = value;
    }

    public long? Value => _value;
}

public struct LongWrapper
{
    private readonly long _value;

    public LongWrapper(long value)
    {
        _value = value;
    }

    public long Value => _value;
}

[Config(typeof (Config))]
public class HashSets
{
    private const int ListSize = 1000;

    private readonly List<long?> _nullables;
    private readonly List<long> _longs;
    private readonly List<NullableLongWrapper> _nullableWrappers;
    private readonly List<LongWrapper> _wrappers;

    public HashSets()
    {
        _nullables = Enumerable.Range(1, ListSize).Select(i => (long?) i).ToList();
        _longs = Enumerable.Range(1, ListSize).Select(i => (long) i).ToList();
        _nullableWrappers = Enumerable.Range(1, ListSize).Select(i => new NullableLongWrapper(i)).ToList();
        _wrappers = Enumerable.Range(1, ListSize).Select(i => new LongWrapper(i)).ToList();
    }

    [Benchmark]
    public void Longs() => new HashSet<long>(_longs);

    [Benchmark]
    public void NullableLongs() => new HashSet<long?>(_nullables);

    [Benchmark(Baseline = true)]
    public void Wrappers() => new HashSet<LongWrapper>(_wrappers);

    [Benchmark]
    public void NullableWrappers() => new HashSet<NullableLongWrapper>(_nullableWrappers);
}

Result:

           Method |          Median |   Scaled
----------------- |---------------- |---------
            Longs |      22.8682 us |     0.42
    NullableLongs |      39.0337 us |     0.62
         Wrappers |      62.8877 us |     1.00
 NullableWrappers | 231,993.7278 us | 3,540.34

Using a struct with a Nullable<long> compared to a struct with a long is 3540 times slower!
In my case it made the difference between 800ms and <1ms.

Here is the environment information from BenchmarkDotNet:

OS=Microsoft Windows NT 6.1.7601 Service Pack 1
Processor=Intel(R) Core(TM) i7-5600U CPU 2.60GHz, ProcessorCount=4
Frequency=2536269 ticks, Resolution=394.2799 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1076.0

What is the reason performance is this poor?

5
  • I also tried making the field not readonly, it doesn't help.
    – Kobi
    Sep 8, 2016 at 12:39
  • 12
    Are you implementing GetHashCode and Equals in your struct? The default implementations use reflection. You should also implement IEquatable<NullableLongWrapper> to prevent boxing.
    – Lee
    Sep 8, 2016 at 12:39
  • @Lee - no - this is a compete example. No implemetation of GetHashCode and Equals. That's a good workaround though, I didn't try it.
    – Kobi
    Sep 8, 2016 at 12:41
  • 2
    Is this your actual code? Because long? is already a "nullable long wrapper" (its actual type is Nullable<long>), so there's no need to create a struct for it Sep 8, 2016 at 15:47
  • 4
    @BlueRaja - No, this is a minimal example that demonstrates the issue. My real struct has two long?s in it. It is similar to the result of an outer join, where the left or the right might be null.
    – Kobi
    Sep 8, 2016 at 16:07

2 Answers 2

86

This is happening because every one of the elements of _nullableWrappers has the same hash code returned by GetHashCode(), which is resulting in the hashing degenerating into O(N) access rather than O(1).

You can verify this by printing out all the hash codes.

If you modify your struct as so:

public struct NullableLongWrapper
{
    private readonly long? _value;

    public NullableLongWrapper(long? value)
    {
        _value = value;
    }

    public override int GetHashCode()
    {
        return _value.GetHashCode();
    }

    public long? Value => _value;
}

it works much more quickly.

Now, the obvious question is WHY is the hash code of every NullableLongWrapper the same.

The answer to that is discussed in this thread. However, it doesn't quite answer the question, since Hans' answer revolves around the struct having TWO fields from which to choose when computing the hash code - but in this code, there's only one field to choose from - and it's a value type (a struct).

However, the moral of this story is: Never rely on the default GetHashCode() for value types!


Addendum

I thought that perhaps what was happening was related to Hans' answer in the thread I linked - maybe it was taking the value of the first field (the bool) in the Nullable<T> struct), and my experiments indicate that it may be related - but it's complicated:

Consider this code and its output:

using System;

public class Program
{
    static void Main()
    {
        var a = new Test {A = 0, B = 0};
        var b = new Test {A = 1, B = 0};
        var c = new Test {A = 0, B = 1};
        var d = new Test {A = 0, B = 2};
        var e = new Test {A = 0, B = 3};

        Console.WriteLine(a.GetHashCode());
        Console.WriteLine(b.GetHashCode());
        Console.WriteLine(c.GetHashCode());
        Console.WriteLine(d.GetHashCode());
        Console.WriteLine(e.GetHashCode());
    }
}

public struct Test
{
    public int A;
    public int B;
}

Output:

346948956
346948957
346948957
346948958
346948959

Note how the second and third hash codes (for 1/0 and 0/1) are the same, but the others are all different. I find this strange because clearly changing A changes the hash code, as does changing B, but given two values X and Y, the same hash code is generated for A=X, B=Y and A=Y, B=X.

(That sounds like some XOR stuff is happening behind the scenes, but that's guess.)

Incidentally, this behaviour where BOTH fields can be shown to contribute to the hash code proves that the comment in the reference source for ValueType.GetHashType() is inaccurate or wrong:

Action: Our algorithm for returning the hashcode is a little bit complex. We look for the first non-static field and get it's hashcode. If the type has no non-static fields, we return the hashcode of the type. We can't take the hashcode of a static member because if that member is of the same type as the original type, we'll end up in an infinite loop.

If that comment was true, then four of the five hash codes in the example above would be the same, since A has the same value, 0, for all those. (That assumes A is the first field, but you get the same results if you swap the values around: Both fields clearly contribute to the hash code.)

Then I tried changing the first field to be a bool:

using System;

public class Program
{
    static void Main()
    {
        var a = new Test {A = false, B = 0};
        var b = new Test {A = true,  B = 0};
        var c = new Test {A = false, B = 1};
        var d = new Test {A = false, B = 2};
        var e = new Test {A = false, B = 3};

        Console.WriteLine(a.GetHashCode());
        Console.WriteLine(b.GetHashCode());
        Console.WriteLine(c.GetHashCode());
        Console.WriteLine(d.GetHashCode());
        Console.WriteLine(e.GetHashCode());
    }
}

public struct Test
{
    public bool A;
    public int  B;
}

Output

346948956
346948956
346948956
346948956
346948956

Wow! So making the first field a bool makes all the hash codes come out the same, regardless of the values of ANY of the fields!

This still looks like some kind of bug to me.

The bug has been fixed in .NET 4, but only for Nullable. Custom types still yield the bad behavior. source

14
  • 5
    I was so naive. I trusted them. Thanks!
    – Kobi
    Sep 8, 2016 at 12:46
  • 1
    Why do you think they will have the same hash code? They should be based on the value of the underlying long.
    – Lee
    Sep 8, 2016 at 12:48
  • 1
    Docs roughly say "don't use ValueType's default GetHashCode" In this particular case it might have something to do with the only field being boxed
    – J0HN
    Sep 8, 2016 at 12:53
  • 1
    Additionally, it seems that any struct which has the first field of Nullable<T> type will return the same hashcode. Probably has something to do with how the default implementation works, although Hans' answer doesn't mention nullables.
    – vgru
    Sep 8, 2016 at 12:54
  • 1
    @MatthewWatson: but Nullable<T> isn't a reference type, it should be a struct with an additional bool field inside, shouldn't it?
    – vgru
    Sep 8, 2016 at 13:06
12

This is due to struct GetHashCode() behavior. If it finds reference types - it tries to get hash from first non-reference type field. In your case it WAS found, and Nullable<> is also struct, so it just poped it's private boolean value (4 bytes)

4
  • What do you mean by "internal boolean value"? Sep 8, 2016 at 13:23
  • Sorry, I meant 'private''
    – eocron
    Sep 8, 2016 at 13:24
  • Hmm, but a bool is only one byte, but maybe it's using an address somewhere. Sep 8, 2016 at 13:25
  • 1
    If you do not specify alignment - it is 4 bytes. Machine word. This std implementation for performance purposes.
    – eocron
    Sep 8, 2016 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.