Игрясь с 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 виновата в случившемся.
Так как выявлять подобные проблемы можно точно так же как и обычные проблемы с производительностью. И так как делать это можно хоть на работающей системе последние аргументы за использование мап-ов на основе деревьев исчезают. Ведь теперь мы легко можем добиваться идельной производительности.
... << RSDN@Home 1.2.0 alpha rev. 631>>