Игрясь с JetBrain-оским пройайлером над оптимизацией работы парсера Эрли

Автор: mefrill
Дата: 17.01.06

наткнулся на одну простую, но как мне показалось очень полезную мысль...

А именно, о том что качество хэш-функции в реальных условиях можно оценивать с помщью банального профайлера.

Поясню мысл. Скорость работы словарей (они же Map-ы) разных Set-ов и других контейнеров основанных на технологии хэширования сильно зависит от двух факторов:
1. Количества слотов хэш-таблицы.
2. Качества хэш-функции.

При хорошей хэш-фукнции и достаточном объеме хэш-таблицы (обычно когда она в полтора раза больше чем рельно хранимое количество элементов) хэш-таблица дает практически константное время доступа. Причем та самая констатна очень не велика. Вот, например, функция поиска из класса Dictionary<K,V>:

private int FindEntry(TKey key)
{
      if (key == null)
      {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
      }
      if (this.buckets != null)
      {
            int num1 = this.comparer.GetHashCode(key) & 0x7fffffff;
                        // buckets - это просто массив!
            for (int num2 = this.buckets[num1 % this.buckets.Length]; num2 >= 0; num2 = this.entries[num2].next)
            {
                  if ((this.entries[num2].hashCode == num1) && this.comparer.Equals(this.entries[num2].key, key))
                  {
                        return num2;
                  }
            }
      }
      return -1;
}

Думаю, что даже тому кто ничего не понимет в технике хэширования поймет, что если количество проходов по циклу не привышает 1, то скорость работы этой функции чертовски высока.

Так вот качество хэш функции и достаточность размера хэш-таблицы можно выразить банальным условием. Кличество вызовов функции GetHashCode() должно быть больше или равно количеству вызовов Equals().

Подбирать значение хэш-функции и размер таблицы в тестах дело не благодароное, и конечно мало кто будет прибегать к столь изощьренным методом оптимизации. А вот запустить профайлер не проблема!

Если хэш-функция или размер таблицы стали узким местом, то функция моментально станет горячей точкой. Далее остается только проанализировать какая из функций вызвается очень часто. Если это Equals(), то мы имеем дело с плохой реализацией хэш-фукнции.

Далее остается только раскрыть список функций вызываемых функцией FindEntry() и выяснить какая из реализаций пар Equals/GetHashCode виновата в случившемся.

Так как выявлять подобные проблемы можно точно так же как и обычные проблемы с производительностью. И так как делать это можно хоть на работающей системе последние аргументы за использование мап-ов на основе деревьев исчезают. Ведь теперь мы легко можем добиваться идельной производительности.