Производительность Guava ImmutableSet.contains
Guava ImmutableSet, похоже, плохо работает в моем тесте относительно contains. Для некоторых размеров он становится намного медленнее, чем List:
size benchmark ns linear runtime
100000 ListContains 110279.54 ==
100000 SetContains 7.15 =
100000 ImmutableSetContains 76716.47 =
200000 ListContains 275367.66 =====
200000 SetContains 7.34 =
200000 ImmutableSetContains 322185.50 ======
500000 ListContains 935210.10 ====================
500000 SetContains 7.79 =
500000 ImmutableSetContains 1382765.76 ==============================
В основном, я заполняю набор с целым числом целых тысяч отрицательных чисел, а тест содержит неотрицательные. Код тривиален, но слишком длинный для вставки в небольшой текстовой области, поэтому, пожалуйста, посмотрите здесь.
Интересно, что происходит здесь. Вероятно, я попал в какой-то дегенеративный случай, хотя я, очевидно, не пытался. Или, может быть, я только что взорвал бенчмарк. В противном случае, я задаюсь вопросом, может ли оно быть и должно быть исправлено.
Решение заключалось в том, чтобы изменить функцию смазывания на заменить
hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
по
return C2 * Integer.rotateLeft(hashCode * C1, 15);
Это занимает примерно одно и то же время и может иметь некоторый недостаток, но решает текущую проблему, красиво распространяя хэши.
Ответы
Ответ 1
Объяснение на самом деле очень простое. Представьте, что целые числа лежат в множестве M = {0, 1, ..., N-1} для некоторого N, который является степенью двух. И так делают хеши, из-за того, как Integer.hashCode определено. Хэши обрабатываются с помощью функции smear, идентичной этой > , чтобы минимизировать столкновения в младших битах в некоторых распространенных случаях.
Получается таблица размера 2*N, и члены M получаются в нее. Поскольку smear включает только сдвиги вправо, он отображает M на себя, что означает, что заполняется непрерывный диапазон таблицы. Так что скажем, что все слоты в левой половине таблицы используются, а другая половина не используется.
Когда вызывается contains(o), поиск начинается в слоте, позиция которого определяется o.hashCode(). Если найдено o, результатом будет true, если удаляется пустой слот, результат будет false. В противном случае поиск переходит к другому слоту. Чтобы минимизировать промахи в кэше, используется linear probing.
Когда нам не повезло, чтобы начать поиск в первом используемом слоте, все они должны быть пройдены, что означает шаги N. Начиная со случайной позиции, средние значения N/4 выполняются в среднем.
То, что произошло в моем тесте, не так, как указано выше, но причина его плохой производительности одинакова. Создание размеров до двух степеней делает проблему хуже.
