Code Review: Struktury danych a wyszukiwanie

Struktury danych w niektórych scenariuszach są dużo szybsze niż klasy.  W następnym wpisie pokażę dokładnie kiedy należy ich używać i dlaczego. W dzisiejszym poście natomiast chciałbym pokazać bardzo często popełniany błąd:

internal struct Point
{
    public int X;
    public int Y;
}

Mamy tutaj prostą strukturę. Oczywiście pierwszy problem jaki rzuca się w oczy to nie spełnienie wymogu immutable object. Kiedyś o tym pisałem, że jeśli dane w strukturach można zmieniać to spowoduje to wiele problemów. Ale dzisiaj nie o tym. Taka struktura danych spowoduje problem wydajnościowy jeśli chcemy np. przeszukiwać kolekcję danych:

if(list.Contains(new Point{X=5,Y=0}))
{
}

Dlaczego taka prosta linia kodu jest zła?

Największym zagrożeniem przy pracy ze strukturami jest boxing. Wywołanie Contains spowoduje przynajmniej dwukrotne wykonanie boxingu. Po pierwsze standardowo metoda Equals jako parametr przyjmuje object a nie oczywiście Point. Z tego względu mamy już na wstępnie boxing.  Equal jest metodą wirtualną, czyli aby ją wywołać należy uzyskać dostęp do specjalnej tablicy zawierającej wskaźniki do metod (pointers table). Struktury nie mają takiej tablicy więc należy znów skonwertować taki typ value do referencyjnego. Musimy powyższe czynności wywołać dla każdego elementu znajdującego się w tablicy, którą przeszukujemy.

Napiszmy prosty test, pokazujący ile czasu zajmie wyszukiwanie powyższej struktury w tablicy:

var list=new List<Point>();
const int elementsCount = 10000000;

for (int i = 0; i < elementsCount; i++)
{
 Point p = new Point {X = i, Y = elementsCount - i};
 list.Add(p);
}

const int testsCount = 10;

for (int i = 0; i < testsCount; i++)
{
 GC.Collect();
 GC.WaitForPendingFinalizers();

 var stopwatch = Stopwatch.StartNew();
 list.Contains(new Point{X=5,Y=0});

 GC.Collect();
 GC.WaitForPendingFinalizers();

 Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

Otrzymany wynik to 500. Kolejnym krokiem jest optymalizacja poprzez stworzenie metod, które nie będą potrzebowały boxingu:

internal struct Point:IEquatable<Point>
{
   public int X, Y;

   public bool Equals(Point other)
   {
       return X == other.X && Y == other.Y;
   }
}

Stworzenie jednej prostej metody (implementacja IEquatable) likwiduje wszelkie problemy. Mamy dokładnie dopasowany parametr wejściowy oraz nie musimy wywoływać bazowej implementacji Equal (znajdującej się w ValueType), co wymagało dostępu do tabeli wskaźników.

Po optymalizacji wykonanie tego samego przeszukania zajmuje tylko <70. Różnica jest więc kolosalna i należy o tym pamiętać. Struktury używamy w sytuacjach gdzie tworzymy setki lub miliony małych obiektów – wtedy wyszukiwanie jest realnym problemem a nie mikro-optymalizacją.

4 thoughts on “Code Review: Struktury danych a wyszukiwanie”

  1. Piotrze, Twoje posty są bardzo pouczające i zazwyczaj mówią o rzeczach mało oczywistych. Jednak brakuje mi w nich jednego, bardzo ważnego elementu. Mianowicie linków do poprzednich postów, gdy o nich wspominasz. Wierzę, że wiesz jaka jest to zaleta zarówno dla czytelnika, jak i dla Ciebie 🙂 Pozdrawiam.

  2. Powtórzyłem sobie Twój przykład i wszystko się zgadza ale nurtuje mnie jedna rzecz:
    – dlaczego korzystając z microsoftowej struktury Point (z system.drawing) rezultaty są jeszcze lepsze (2x szybciej)?

    Zdekompilowałem sobie tą strukturę i bynajmniej nie implementuje ona IEquatable nie powinna być zatem boxowana i w efekcie równie wolna co nasz zwykly Point (nie implementujący IEquatable)?

  3. Nie sprawdzałem tego, ale bardzo mozliwe, ze jest ten Point traktowany jako typ natywny a wiec ze wszystkimi optymalizacjami w trakcie JIT.

Leave a Reply

Your email address will not be published.