Struktury mogą być doskonałym rozwiązaniem w połączeniu ze słownikiem czy HashSet. Zwykle projektuje je się w sposób immutable, więc stanowią naturalny wybór na klucze w HashSet.

Niestety bardzo łatwo popełnić błąd, który poskutkuje gwałtownym spadkiem wydajności.  Załóżmy, że mamy dwie struktury, jedna zawierająca wyłącznie typy proste (value type), a druga również typ referencyjny czyli string:

    public struct WithValueType
    {
        public int ValueType1;
        public int ValueType2;
    }

    public struct WithReferenceType
    {
        public int ValueType;
        public string RefType;
   
    }

Napiszmy teraz prosty benchmark, sprawdzający ile trwa dodanie obiektów do HashSet:

        int times = 1000000;
        
        var withValueType = new HashSet<WithValueType>();
        var withReferenceType = new HashSet<WithReferenceType>();

        // withValueType
        Stopwatch timer = Stopwatch.StartNew();

        for (int i = 0; i < times; i++)
            withValueType.Add(new WithValueType {ValueType1 = i, ValueType2 = i});

        timer.Stop();
        Console.WriteLine($"WithValueType: {timer.ElapsedMilliseconds}");

        // withReferenceType
        timer = Stopwatch.StartNew();

        for (int i = 0; i < times; i++)
            withReferenceType.Add(new WithReferenceType { ValueType = i, RefType = i.ToString() });

        timer.Stop();
        Console.WriteLine($"withReferenceType: {timer.ElapsedMilliseconds}");
      

Na ekranie zobaczymy następujące wyniki:

Skąd ta różnica? To już nie jest mikro-optymalizacja, ale bardzo poważny problem wydajnościowy, który ostatnio zmarnował mi sporo czasu na profilowaniu aplikacji. Wiemy, że struktury możemy porównywać poprzez wartość. Jeśli w kodzie mamy warunek np. if(a != b), wtedy konkretne wartości zostaną porównane, a nie jak w przypadku klas, adres instancji. Problem w tym, że wykorzystywany jest mechanizm reflekcji, który zawsze jest wolniejszy. Z dokumentacji MSDN wiemy, że Equals dla struktur działa następująco:

1. Jeśli struktura zawiera przynajmniej jeden typ referencyjny, wtedy jest używany mechanizm reflekcji.
2. Jeśli struktura zawiera wyłącznie typy proste (value types), wtedy dane porównywane są bajt po bajcie.

Zobaczmy implementację ValueType.Equals:

public override bool Equals (Object obj) { 
            BCLDebug.Perf(false, "ValueType::Equals is not fast.  "+this.GetType().FullName+" should override Equals(Object)"); 
            if (null==obj) {
                return false; 
            }
            RuntimeType thisType = (RuntimeType)this.GetType();
            RuntimeType thatType = (RuntimeType)obj.GetType();
 
            if (thatType!=thisType) {
                return false; 
            } 

            Object thisObj = (Object)this; 
            Object thisResult, thatResult;

            // if there are no GC references in this object we can avoid reflection
            // and do a fast memcmp 
            if (CanCompareBits(this))
                return FastEqualsCheck(thisObj, obj); 
 
            FieldInfo[] thisFields = thisType.GetFields(BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic);
 
            for (int i=0; i<thisFields.Length; i++) {
                thisResult = ((RtFieldInfo)thisFields[i]).InternalGetValue(thisObj,false);
                thatResult = ((RtFieldInfo)thisFields[i]).InternalGetValue(obj, false);
 
                if (thisResult == null) {
                    if (thatResult != null) 
                        return false; 
                }
                else 
                if (!thisResult.Equals(thatResult)) {
                    return false;
                }
            } 

            return true; 
        }

Po metodzie CanCompareBits widzimy, że szybkie sprawdzanie jest wyłącznie możliwe, gdy nie ma typów referencyjnych. Wtedy po prostu są sprawdzane wartości bajtów (szybka operacja). Problemy zaczynają się, gdy dane są przechowywane na stercie, szczególnie w różnych miejscach.

W praktyce, gdy mamy typy referencyjne, wtedy obowiązkowo implementujemy Equals. Powyższe rozważania jednak nie usprawiedliwiają faktu, że to struktura z typami prostymi, a nie referencyjnymi, stanowi największy problem. HashSet zawsze wywołuje GetHashCode. W dokumentacji przeczytamy, że:

        /*=================================GetHashCode==================================
        **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. 
        **Returns: The hashcode for the type. 
        **Arguments: None.
        **Exceptions: None. 
        ==============================================================================*/
        [System.Security.SecuritySafeCritical]  // auto-generated
        [ResourceExposure(ResourceScope.None)]
        [MethodImplAttribute(MethodImplOptions.InternalCall)] 
        public extern override int GetHashCode();

Rozwiązaniem jest własna implementacja GetHashCode:

    public struct WithValueType
    {
        public int ValueType1;
        public int ValueType2;

        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        public bool Equals(WithValueType other)
        {
            return ValueType1 == other.ValueType1 && ValueType2 == other.ValueType2;
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return (ValueType1*397) ^ ValueType2;
            }
        }
    }

    public struct WithReferenceType
    {
        public int ValueType;
        public string RefType;

        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        public bool Equals(WithReferenceType other)
        {
            return ValueType == other.ValueType && string.Equals(RefType, other.RefType);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return (ValueType*397) ^ (RefType != null ? RefType.GetHashCode() : 0);
            }
        }
    }

Wyniki prezentują się teraz dużo lepiej:

Warto również zaimplementować interfejs IEquatable, jeśli chcemy uniknąć boxingu. Więcej informacji w moim poprzednim wpisie.