Производительность 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 выполняются в среднем.

То, что произошло в моем тесте, не так, как указано выше, но причина его плохой производительности одинакова. Создание размеров до двух степеней делает проблему хуже.