Около месяца назад на Хабре была статья про Trove — самую часто упоминаемую библиотеку, когда спрашивают про структуры данных с примитивами на Java. Примерно за пару дней до этого я сел эту библиотеку переписывать :) Время решительно кончилось, поэтому делюсь поиском с вами, хотя не очень-то надеюсь, что кто-то продолжит это дело :)
На данный момент сделаны хеш-таблицы 6 типов: множества примитивов, объектов и все 4 варианта мапов: примитив — примитив, примитив — объект, объект — примитив и объект — объект, над которыми нависает туча обобщающих интерфейсов.
Меня всегда удивляло, почему все подобные библиотеки создают еще одну иерархию типов, а не встраиваются в давно уже зарекомендовавший себя стандартный каркас коллекций Явы. Никаких принципиальных проблем с этим я не видел и не вижу. Поэтому над моей тучей интерфейсов, как на пантеоне, возвышаются java.util.Iterable, java.util.Collection и java.util.Map. Я не зря дал ссылки на документацию по Java 8. Реализованы почти все методы из будущих интерфейсов, кроме spliterator(). Можно начинать привыкать :)
Дополнительные элементы нового фреймворка Trove
mapIterator() — гибрид spliterator() из Java 8 и entrySet().iterator().
interface TMapIterator<K, V> {
boolean tryAdvance();
K key();
V value();
...
}
// идиома использования
for (IntKeyMapIterator<String> it = map.mapIterator(); it.tryAdvance(); ) {
doSomething(it.intKey(), it.value());
}
Едва ли это более громоздко, чем entrySet().iterator(), зато существенно эффективнее.
Во всех хешах объектов есть методы для управления разбиением объектов на множества эквивалентных:
class DHashSet<E> {
...
protected boolean elementsEquals(@NotNull E a, @Nullable E b) {
return a.equals(b);
}
protected int elementHashCode(@NotNull E element) {
return element.hashCode();
}
}
«Реверсивные» методы над целыми коллекциями: addAllTo(), allContainingIn(), removeAllFrom() — для ускорения поточных операций. В стандартном каркасе метод всегда вызывается на коллекции, которая будет изменяться, хотя итерироваться придется по второй. Хотя именно последняя «знает», как быстрее всего пройтись по всем элементам.
В некоторых случаях реверсивный проход может выполняться в 2 раза быстрее, чем внешний, с помощью обычного итератора. Например, при дампе множества в список.
Так как контракты соответствующих методов из стандартного каркаса имеют довольно тонкие нюансы, реверсивные методы не рекомендуется вызывать вручную, чтобы не сделать что-нибудь не то :) Они уже вызываются изнутри обычных методов в реализациях.
Реализация
Сердце Trove — хеш-таблицы с открытой адресацией и двойным хешированием для разрешения коллизий. При удалении элемента в них нельзя просто пометить ячейку, как свободную. Поэтому, если из таблицы регулярно удаляются и добавляются элементы, она полностью забивается занятыми и «удаленными» ячейками, скорость операций падает. В предыдущей версии Trove, чтобы не допустить этого, был счетчик удалений, эвристически завязанный на задаваемый коэффициент заполненности таблицы.
При коэффициенте k (от 0 до 1) получается, что при постоянных удалениях перед перестроением таблицы остается k — k^2 заполненных ячеек, и k^2 удаленных, при попеременных удалениях и вставках разных случайных элементов — k заполненных и (1 — k) ^2 — свободных (все величины — в долях от 1).
Подставим цифры. При коэффициенте по умолчанию — 0,5 — в обоих случаях получается максимум по четверти удаленных элементов в таблице. Очень красиво. Но вот при моем любимом коэффициенте 0,8 — при вполне нормальном шаблоне использования таблицы может остаться всего 4% свободных ячеек — это криминал.
Поэтому я ввел гораздо более простой принцип — количество удаленных ячеек в любой момент не должно превышать ни количество занятых (т. е. размер таблицы), ни количество свободных, иначе происходит перестроение:
class DoubleHashBase {
int size, free, removed, modCount;
...
final void postRemoveHook() {
modCount++;
if ( ( --size < ++removed || removed > free ) && autoRehashEnabled ) {
rehash();
}
}
Ключевой метод в реализации хеш-таблицы — поиск элемента. В случае таблицы с двойным хешированием, по массиву, длина которого — простое число, скачут в почти случайном порядке, и сравнивают элемент по текущему индексу с искомым. При этом ищут элемент в хеш-таблице, либо для того, чтобы его туда потом вставить, либо чтобы взять значение из параллельного массива (map.get() или set.contains()). В первом случае можно считать, что элемента в таблице, скорее всего, еще нет, а во втором — что он, скорее всего, уже там лежит. В предыдущей реализации Trove в обоих вариантах поиска в первую очередь проверяется, не пуста ли ячейка, и потом, не лежит ли там то, что мы ищем. Хотя при поиске «на взятие» надо в первую очередь проверять, не равен ли текущий элемент искомому (да так и есть :)
Это двухстрочное изменение ускорило IntHashSet.contains(int) на 5 нс.
Очередная попытка нормально написать бенчмарки на JMH
Итерация по CharHashSet, коэффициент заполнения 0.5, таблица занимает примерно 4 КБ в памяти. Детали опущены:
@GenerateMicroBenchmark
public char charSet_simple(CharSetState state) {
char sum = 0;
TCharIterator it = state.iterator;
while (it.hasNext()) {
sum += it.nextChar();
}
return sum;
}
@GenerateMicroBenchmark
public char charSet_forEachLoop(CharSetState state) {
char sum = 0;
for (char v : state) {
sum += v;
}
return sum;
}
public static class CharSum implements CharConsumer {
public char sum;
public void accept( char b ) {
sum += b;
}
}
@GenerateMicroBenchmark
public char charSet_forEachFunction(CharSetState state) {
CharSum procedure = new CharSum();
state.set.forEach( procedure );
return procedure.sum;
}
@GenerateMicroBenchmark
public char charSet_tryAdvance(CharSetState state) {
char sum = 0;
TCharIterator it = state.iterator;
while (it.tryAdvance()) {
sum += it.charValue();
}
return sum;
}
Результат:
Mean Mean error
charSet_forEachFunction 6,7 1,1 nsec/iter
charSet_forEachLoop 15,4 2,1 nsec/iter
charSet_simple 8,7 0,1 nsec/iter
charSet_tryAdvance 8,6 0,1 nsec/iter
Как видно, за удовольствие использовать самый короткий способ, foreach по j.u.Iterable, по-прежнему приходится платить.
Способ «simple» — примерно на 30% быстрее, чем аналогичный в предыдущей версии Trove, из-за того, что там следующий элемент искался по 2 раза на каждой итерации: и в методе hasNext(), а затем и в next(). Сейчас индекс следующего элемента сохраняется в поле класса итератора.
К чему все это
Как я уже сказал, у меня совершенно нет времени доделывать библиотеку:
Нет списков (CharArrayList)
Из всех классов временно убрана поддержка Serializable
Документации почти нет, только немного копипасты из Java 8.
Но, так как новый фреймворк согласован со стандартным, его очень просто протестировать на реальных задачах, особенно есть вы предусмотрительно писали
Map<Integer, Long> = new HashMap<>();
Хотя я не пробовал компилировать новую библиотеку ничем, кроме Java 7u25, по исходникам (и сборке) она должна быть совместима с Java 6.
Репозиторий включает очень развесистую обвязку для разработки под Intellij: bitbucket.org/leventov/trove/src/
Буду рад услышать ваши мысли про дизайн таких библиотек и реализацию хешей.
По ссылке на оригинал — (предпологаемое) обсуждение на английском.
Автор: leventov
