Предыстория
В бытность мою студентом 3-го курса довелось мне в рамках лабораторного практикума программировать численный метод. Он был реализован (на Java), более того — он даже выдавал правильный результат, но была одна проблема: работал чересчур медленно. Стоило немного увеличить размерность, и всё — можно было идти
Метод был итерационный, и на каждой итерации старые значения обновлялись. Профайлинг подсказал, что львиную долю времени занимает работа с ассоциативными массивами наподобие Map<Integer, Double>.
Первая возникшая мысль: «а давай-ка я на чистые массивы переведу всё» — была отброшена почти сразу. Вариант «переписать все на C» даже не рассматривал. Поэтому принялся искать готовые решения, позволяющие работать с коллекциями примитивов. Нашел два: Trove4j и Apache Common Primitives.
Я выбрал первый вариант. Автор декларирует увеличение производительности и уменьшение потребления памяти.
Устанавливаем
Итак, зайдя по ссылке, указанной выше, и скачав сборку и javadocs, я приступил к изучению.
Исходный код генерируется из шаблонов при помощи прилагаемого генератора и ant-скрипта. Это выглядит разумным, т.к. позволяет вносить изменения в код лишь раз, а изменения отразятся на всех соответствующих классах.
Знакомимся с правилами именования
В Trove4j используются специфические правила наименования классов.
Первой буквой идет T — по словам автора, для указания того, что это часть библиотеки Trove.
Далее идет наименование типа: Int, Double, Object и т.д.
Затем название коллекции: ArrayList, HashSet, HashMap.
Примеры: TByteArrayList, TIntHashSet, TFloatObjectHashMap, TDoubleDoubleHashMap.
Особняком стоят THashSet и THashMap.
Ищем отличия от JDK Collections
Автор предоставил достаточно гибкий механизм управлением стратегией хеширования для хеш-таблиц. Есть стратегия по умолчанию, но при необходимости ее можно заменить своей реализацией. Хотя, по правде сказать, я не встречал ситуаций, когда это было необходимо.
Важнейшим отличием от JDK Collections Framework является то, что в Trove4j все хеш-таблицы построены на массивах, а не на связанных списках. Это позволяет экономить значительное количество памяти за счет исключения ссылок между элементами.
“The Trove maps/sets use open addressing instead of the chaining approach taken by the JDK hashtables. This eliminates the need to create Map.Entry wrappper objects for every item in a table and so reduces the O (big-oh) in the performance of the hashtable algorithm. The size of the tables used in Trove's maps/sets is always a prime number, improving the probability of an optimal distribution of entries across the table, and so reducing the the likelihood of performance-degrading collisions. Trove sets are not backed by maps, and so using a THashSet does not result in the allocation of an unused «values» array.”
Переходим от JDK Collections к Trove4j
THashSet реализует Set, поэтому его внедрение наименее болезненно. Остальные хеш-таблицы и все ассоциативные массивы соответствующие им интерфейсы из JDK не реализуют, однако в пакете gnu.trove.decorator можно найти исчерпывающий набор оберток для них, согласующих эти классы с интерфейсами.
Получаем результат
После переписывания лабы с использованием Trove4j, скорость расчета заметно возросла. Ну а лаба была благополучно сдана через пару дней.
Последующее применение
Trove4j был внедрен в рабочем проекте: он быстро прижился в выполняющем огромное количество расчетных операций модуле симуляции, став ее незаменимым инструментом.
Переход от HashSet и HashMap к их аналогам позволил уменьшить потребляемое количество памяти на треть. Скорость работы также возросла.
P.S.
Хотел опубликовать в JAVA, но недостаточно кармы.
