Использование стандартного Java HashMap (по сравнению с Trove THashMap) приводит к более медленной работе не-HashMap кода

Question

Я использую HashMap для кэширования около 2 миллионов значений, рассчитанных с помощью рекурсивного алгоритма. Я использую либо HashMap<Integer, Double> из рамок коллекций, или TIntDoubleHashMap из библиотеки Троув, контролируемой boolean useTrove переменная, как в коде ниже.

Я ожидаю, что библиотека Trove будет быстрее, поскольку она избегает автобокса и т. Д. И действительно, put() а также get() звонки занимают около 300 мс (всего) для THashMap по сравнению с около 500 мс для HashMap<>,

Теперь моя общая продолжительность выполнения программы составляет около 2,8 с при использовании THashMapи 6,7 с при использовании HashMap<>, Эта разница не может быть объяснена увеличением времени выполнения put() а также get() звонки в одиночку.

1. Я подозреваю, что это значительно увеличило время выполнения с HashMap<> это обусловлено тем фактом, что эта реализация довольно неэффективна для памяти, поскольку каждый тип int / double должен быть помещен в объект, и это увеличенное использование памяти вызывает пропуски кэша в других частях программы. Имеет ли это объяснение смысл, и как я могу подтвердить / отклонить эту гипотезу?

2. В общем, как мне изучить алгоритмическую оптимизацию для таких сценариев? Профилирование алгоритма не всегда указывает наHashMap<> быть виновником, по крайней мере, если рассматривать только процессорное время. Это просто вопрос заранее знать, что использование памяти должно быть приоритетом для программ, жаждущих памяти?

Код в полном объеме ниже.

import java.util.HashMap;
import gnu.trove.map.hash.TIntDoubleHashMap;

class RuntimeStopWatch {
    long elapsedTime;
    long startTime;
    RuntimeStopWatch() { reset(); }
    void reset() { elapsedTime = 0; }
    void start() { startTime = System.nanoTime(); }
    void stop() {
        long endTime = System.nanoTime();
        elapsedTime += (endTime - startTime);
        startTime = endTime;
    }
    void printElapsedTime(String prefix) {
        System.out.format(prefix + "%dms\n", elapsedTime / 1000000);
    }
}

public class HashMapBehaviour {

    static RuntimeStopWatch programTime = new RuntimeStopWatch();
    static RuntimeStopWatch hashMapTime = new RuntimeStopWatch();
    static HashMap<Integer, Double> javaHashMapCache;
    static TIntDoubleHashMap troveHashMapCache;
    static boolean useTrove;

    public static void main(String[] args) {
//        useTrove = true;
        useTrove = false;

        javaHashMapCache = new HashMap<>();
        troveHashMapCache = new TIntDoubleHashMap();

        programTime.start();
        recursiveFunction(29, 29, 178956970);
        programTime.stop();

        programTime.printElapsedTime("Program: ");
        hashMapTime.printElapsedTime("Hashmap: ");
    }


    static double recursiveFunction(int n, int k, int bitString) {
        if (k == 0) return 0.0;
        if (useTrove) {
            hashMapTime.start();
            if (troveHashMapCache.containsKey(bitString | (1 << n))) return troveHashMapCache.get(bitString | (1 << n));
            hashMapTime.stop();
        } else {
            hashMapTime.start();
            if (javaHashMapCache.containsKey(bitString | (1 << n))) return javaHashMapCache.get(bitString | (1 << n));
            hashMapTime.stop();
        }
        double result = 0.0;
        for (int i = 0; i < (n >> 1); i++) {
            double play1 = recursiveFunction(n - 1, k - 1, stripSingleBit(bitString, i));
            double play2 = recursiveFunction(n - 1, k - 1, stripSingleBit(bitString, n - i - 1));
            result += Math.max(play1, play2);
        }
        if (useTrove) {
            hashMapTime.start();
            troveHashMapCache.put(bitString | (1 << n), result);
            hashMapTime.stop();
        } else {
            hashMapTime.start();
            javaHashMapCache.put(bitString | (1 << n), result);
            hashMapTime.stop();
        }
        return result;
    }

    static int stripSingleBit(int bitString, int bitIndex) {
        return ((bitString >> (bitIndex + 1)) << bitIndex) | (bitString & ((1 << bitIndex) - 1));
    }
}

Answer 1

С Trove очень важно то, что вы захотите предварительно изменить размер коллекции. Поскольку хранилище в T*Maps основано на одном массиве, отсутствие предварительного размера коллекции приведет к созданию и копированию множества массивов. HashMap не имеет этой проблемы, потому что он использует связанные объекты.

Итак, подведем итоги: попробуйте определить размер вашей коллекции new TIntDoubleHashMap(<expected_size>)

В более широком смысле подумайте о том, для чего вы оптимизируете. Trove может быть наиболее эффективным с общим использованием памяти и иногда производительностью. Тем не менее, большой выигрыш в производительности достигается не за счет супер-хитрых алгоритмов хеширования, а скорее за счет того, что может быть меньше давления ГХ, потому что используется меньше временных объектов (для бокса). То, имеет ли это значение для вас полностью, зависит от вашего заявления. Также коэффициент загрузки позволяет компенсировать "плотность" данных в массиве за счет скорости поиска. Итак, тюнинг, который может быть полезен. Если вы получаете много коллизий во время поиска и хотите повысить производительность или хотите увеличить объем памяти за счет производительности, отрегулируйте коэффициент.

Если у вас есть память для записи и вам нужна производительность поиска, HashMap довольно сложно превзойти... особенно, если содержимое карты статично. JVM очень хорошо оптимизирует временные объекты, поэтому не стоит сбрасывать со счетов это слишком быстро. (Преждевременная оптимизация и т.д...)

Имейте в виду, что этот вид микропроцессора также не обязательно является отличным показателем реальной производительности. Он пропускает такие вещи, как GC-давление и JIT-компиляция. Такие инструменты, как JMH, могут помочь в написании более репрезентативных тестов.