Статьи

Простой тест производительности итератора карты

Февраль 3, 2019

Существует много измерений производительности Java Map, но критически важным является простое однопоточное сканирование. Вот простой тестовый код для Iterators и Java 8 Map.forEach() вместе с некоторыми графическими результатами.

1. Тестирование производительности сложно

Тестирование производительности является общеизвестно трудным делом, а для точного повторяемого тестирования требуется такая структура, как Java Microbenchmarking Harness, для фильтрации многих источников шума и предоставления статистики, такой как доверительный интервал. Тем не менее, результаты этого простого тестового кода здесь относительно повторяемы и хорошо коррелируют с тестами JMH, которые автор сделал на картах JDK и AirConcurrentMap (на кипятильник.com и на githubilerbay / airconcurrentmap ). Есть также более обширные тесты JMH для потоков и так далее.

JMH не сложен, но требует переключения передач из IDE на модель maven, изучения набора контрольных аннотаций и работы с еще одним деревом каталогов, полным лжи и, возможно, новым проектом IDE. Кроме того, мы хотим автоматически охватить спектр размеров карт и набор карт за один прогон: для этого требуются аннотации «параметризации» в JMH. Формат выходных данных этого теста можно легко настроить в соответствии с нужным графическим инструментом.

1.1 Проблемы, вызывающие шум

Многие вопросы должны быть решены, чтобы получить хороший тест:

  1. Внутренний цикл не должен иметь значительных накладных расходов. Это решается с помощью простого отслеживания изменений в общей статической переменной volatile int, увеличиваемой потоком «heartbeat»;
  2. Может возникнуть проблема с сборкой мусора. Этому помогает распределение циклического перебора GC по тестам для разных карт. Мы также избегаем создания недоступных объектов. Используйте -Xloggc: <file> в ORACLE JVM для просмотра GC;
  3. Код может быть оптимизирован в любое время JVM во время выполнения. Мы используем прогрев каждого теста, чтобы это произошло. Трудно понять, когда это произойдет, но это всего лишь секунды. Это можно минимизировать с помощью более длительных прогревов. Типичный флаг JVM ‘-XX: + PrintCompilation’ показывает ход оптимизации. Также см. Статью ORACLE ;
  4. JVM будет расти беспорядочно, пока растут Карты, поэтому тест сразу после роста должен прогреться;
  5. Разные Карты используют разные объемы памяти, поэтому даже разветвление JVM для каждого теста будет зависеть от характеристик роста JVM. Мы держим все Карты в одной JVM;
  6. Разные карты должны иметь одинаковое содержимое. Мы используем синхронизированные генераторы случайных чисел, засеянные размером карты;
  7. Большие карты требуют больше времени для итерации, чем меньшие, конечно. Сердцебиение позволяет выполнять больше прогонов меньших Карт, чтобы каждый тест занимал постоянное время;
  8. Карты не должны обмениваться содержимым, поэтому более ранние тесты не переносят данные в кэш ЦП, которые доступны для последующих тестов;
  9. Компилятор Just In Time не должен оптимизировать цикл. Мы печатаем сумму содержимого, чтобы цикл имел ощутимый результат. Если вместо этого использовать счетчик циклов, JIT может распознать шаблон и изменить цикл на число больше единицы, пропуская, таким образом, много итераций! Да, это происходит! (В AirConcurrentMap как минимум).

2. Результаты

Эти предосторожности помогают нам прийти к некоторым предварительным, но повторяемым выводам. Результаты показывают:

  • forEach () намного быстрее чем итераторы;
  • ConcurrentSkipListMap выполняет итерацию быстрее всего около 30 тыс. Записей, а AirConcurrentMap — быстрее;
  • ConcurrentSkipListMap forEach () быстрее всего около 100 записей, а AirConcurrentMap быстрее всего выше.

3. Детали кода

В тестовом коде используется оболочка класса Test для хранения определенной карты вместе с состоянием выполнения теста, таким как время, размер карты, циклы и промежуточные итоги. Надеемся, что эта организация делает main () более читабельным.

Класс Test реализует BiConsumer чтобы его можно было использовать при вызове forEach(this) . Он просто переопределяет accept(Integer, Integer) . Мы также тестируем forEach((k, v) -> total += v) (автор пробовал, и результаты примерно такие же). В любом случае локальная переменная не может быть использована в качестве общего накопителя, потому что локальные переменные должны быть «эффективно конечными» для внутреннего класса или лямбды, поэтому нам нужна переменная экземпляра в содержащей области, как в классе в любом случае. Редукция с использованием потока тоже подойдет, но здесь нас интересуют Итераторы. (См. Https://github.com/boilerbay/airconcurrentmap для соответствующих потоковых тестов в / jmh).

Сердцебиение — это static int увеличиваемое один раз в секунду отдельным потоком. Сердцебиение должно быть изменчивым, чтобы его изменения распространялись между потоками, иначе программа никогда не завершится.

USE_ITERATION и USE_LAMBDA являются static final , поэтому javac заблаговременно оценивает код, на который он влияет, удаляя мертвый код. Это определено как необходимое поведение, таким образом, нет никаких накладных расходов. Конечно, вы должны перекомпилировать тесты, но не меняйте их на нестатичные или не финальные!

Внутренний цикл не замедляется динамическим вызовом метода test.testIterator() потому что методы длиной 35 байтов или меньше всегда встроены. Кроме того, здесь нет полиморфизма — класс Test не имеет расширений, поэтому нет vtable для диспетчеризации и нет параметров для загрузки в стек.

Тесты относительно повторяемы и показывают общую картину на диаграммах.

4. Код

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
public class JavaCodeGeeksIteratorArticle {
    static volatile int heartBeat = 0;
    // otherwise use forEach()
    static final boolean USE_ITERATION = false;
    static final boolean USE_LAMBDA = true;
 
    public static void main(String... args) {
        System.out.println((USE_ITERATION ? "Iterator" :
            USE_LAMBDA ? " forEach(lambda)" : "ForEach()") + " performance test");
        Test tests[] = {
                new Test(new HashMap<Integer, Integer>()),
                new Test(new TreeMap<Integer, Integer>()),
                new Test(new ConcurrentHashMap<Integer, Integer>()),
                new Test(new ConcurrentSkipListMap<Integer, Integer>()),
                new Test(new AirConcurrentMap<Integer, Integer>())
        };
        int sizes[] = new int[] {
                1, 3, 10, 30, 100, 300, 1000, 3000, 10_000, 30_000, 100_000, 300_000,
                1000_000, 3_000_000, 10_000_000
        };
 
        // Just increment heartBeat every so often. It is volatile.
        // Reading it is very fast.
        new Thread(new Runnable() {
            public void run() {
                while (true) {
                    heartBeat++;
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                    }
                }
            }
        }).start();
 
        for (int i = 0; i < sizes.length; i++) {
            for (Test test : tests)
                test.fillTo(sizes[i]);
            // warmup
            for (Test test : tests) {
                int nextHeartBeat = heartBeat + 20;
                while (heartBeat < nextHeartBeat)
                    if (USE_ITERATION)
                        test.testIterator();
                    else if (USE_LAMBDA)
                        test.testForEachLambda();
                    else
                        test.testForEach();
            }
            for (Test test : tests) {
                test.time = 0;
                test.loops = 0;
                long t0 = System.nanoTime();
                int nextHeartBeat = heartBeat + 30;
                while (heartBeat < nextHeartBeat) {
                    if (USE_ITERATION)
                        test.testIterator();
                    else if (USE_LAMBDA)
                        test.testForEachLambda();
                    else
                        test.testForEach();
                }
                long t1 = System.nanoTime();
                test.time += (t1 - t0);
            }
            for (Test test : tests)
                test.printResult();
            // System.out.println("---------------");
        }
 
    }
}
 
class Test implements BiConsumer<Integer, Integer> {
    // The total provides a tangible result to prevent optimizing-out
    long total = 0;
    long time = 0;
    int size = 0;
    long loops = 1;
    Map<Integer, Integer> map;
 
    Test(Map<Integer, Integer> map) {
        this.map = map;
    }
 
    void fillTo(int newSize) {
        Random random = new Random(size);
        while (size < newSize) {
            Integer n = new Integer(random.nextInt());
            map.put(n, n);
            size++;
        }
    }
 
    void testIterator() {
        for (Integer v : map.values()) {
            total += v.intValue();
        } loops++;
    }
 
    // This has the same effect and is 'terser'
    void testForEachLambda() {
        map.forEach((k, v) -> total += v);
        loops++;
    }
     
    void testForEach() {
        map.forEach(this);
        loops++;
    }
 
    // Implement BiConsumer for forEach()
    @Override
    public void accept(Integer k, Integer v) {
        total += k.intValue();
    }
 
    void printResult() {
        double seconds = time / 1e9;
        System.out.printf("%22s size=% 9d entries/s(K)=% 11.3f total=%d\n",
                map.getClass().getSimpleName(), size, size * loops / seconds / 1e3, total);
 
    }
}

5. Данные результатов

Данные для графиков ниже. Это может быть импортировано, например, в Excel и отсортировано по классу и размеру Map для создания графиков вручную. Вам нужно вырезать и вставить данные, а затем использовать текст в столбцы. Можно использовать линейные диаграммы, вручную выбирая данные серии по одному для каждого класса карты. Можно также использовать ggplot на языке статистики ‘R’, изменив формат вывода данных. Игнорировать итоги: это дает только ощутимый результат, чтобы избежать оптимизации цикла.

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
JavaCodeGeeksIteratorArticle
 
Iterator performance test
               HashMap size=       1 entries/s=  31290.754K total=-289049400605539520
               TreeMap size=       1 entries/s=  50210.333K total=-331631386373881504
     ConcurrentHashMap size=       1 entries/s=  15881.356K total=-91464608232057952
 ConcurrentSkipListMap size=       1 entries/s=  42187.535K total=-254234286353018080
      AirConcurrentMap size=       1 entries/s=  25577.125K total=-149805405784208032
---------------
               HashMap size=       3 entries/s=  62664.626K total=-484691989675689270
               TreeMap size=       3 entries/s=  66908.091K total=-550745245141063704
     ConcurrentHashMap size=       3 entries/s=  38018.996K total=-211326922860746827
 ConcurrentSkipListMap size=       3 entries/s=  71265.063K total=-488278692474832005
      AirConcurrentMap size=       3 entries/s=  48540.146K total=-302163579336545082
---------------
               HashMap size=      10 entries/s=  86701.181K total=-832795481348512598
               TreeMap size=      10 entries/s=  87832.407K total=-916137658370092344
     ConcurrentHashMap size=      10 entries/s=  73069.458K total=-502840045890573499
 ConcurrentSkipListMap size=      10 entries/s=  96150.046K total=-880874881700377401
      AirConcurrentMap size=      10 entries/s=  72001.056K total=-591224549191451578
---------------
               HashMap size=      30 entries/s=  89419.363K total=-832238604657166224
               TreeMap size=      30 entries/s=  92397.645K total=-915559545928720920
     ConcurrentHashMap size=      30 entries/s=  71702.258K total=-502393457157098057
 ConcurrentSkipListMap size=      30 entries/s= 103387.524K total=-880213560719307683
      AirConcurrentMap size=      30 entries/s=  80807.271K total=-590716865563759348
---------------
               HashMap size=     100 entries/s=  90540.307K total=-845663104709828079
               TreeMap size=     100 entries/s=  96479.776K total=-930300717715488858
     ConcurrentHashMap size=     100 entries/s=  69055.433K total=-512752383626539310
 ConcurrentSkipListMap size=     100 entries/s= 111208.365K total=-897628029635465726
      AirConcurrentMap size=     100 entries/s=  89071.481K total=-604453907970584431
---------------
               HashMap size=     300 entries/s=  94846.852K total=-860347586557330269
               TreeMap size=     300 entries/s=  94506.995K total=-944821983122037883
     ConcurrentHashMap size=     300 entries/s=  65857.587K total=-522786710141245214
 ConcurrentSkipListMap size=     300 entries/s= 112398.344K total=-915694233970137252
      AirConcurrentMap size=     300 entries/s=  92168.052K total=-618862268508225735
---------------
               HashMap size=    1000 entries/s=  74493.997K total=-852961390806337305
               TreeMap size=    1000 entries/s=  80026.348K total=-937067262358689631
     ConcurrentHashMap size=    1000 entries/s=  38450.309K total=-519070765727723030
 ConcurrentSkipListMap size=    1000 entries/s= 112085.413K total=-904572392174355552
      AirConcurrentMap size=    1000 entries/s=  89022.852K total=-609589031935380951
---------------
               HashMap size=    3000 entries/s=  57470.417K total=-847037038798366713
               TreeMap size=    3000 entries/s=  65963.172K total=-930168324830420495
     ConcurrentHashMap size=    3000 entries/s=  41073.089K total=-514814334734654678
 ConcurrentSkipListMap size=    3000 entries/s= 109217.866K total=-892841347702876464
      AirConcurrentMap size=    3000 entries/s=  89175.845K total=-600361285087522951
---------------
               HashMap size=   10000 entries/s=  46254.558K total=-846309210319384299
               TreeMap size=   10000 entries/s=  49044.408K total=-929403633977808893
     ConcurrentHashMap size=   10000 entries/s=  36385.473K total=-514246034592481772
 ConcurrentSkipListMap size=   10000 entries/s=  99442.425K total=-891342788950136070
      AirConcurrentMap size=   10000 entries/s=  85447.544K total=-599022098209904335
---------------
               HashMap size=   30000 entries/s=  43723.556K total=-848942181585517584
               TreeMap size=   30000 entries/s=  45253.915K total=-932143497084889069
     ConcurrentHashMap size=   30000 entries/s=  32665.051K total=-516220137420939070
 ConcurrentSkipListMap size=   30000 entries/s=  83393.494K total=-896231928805619954
      AirConcurrentMap size=   30000 entries/s=  80619.262K total=-603845100973163554
---------------
               HashMap size=  100000 entries/s=  40028.088K total=-849706795555554639
               TreeMap size=  100000 entries/s=  41755.506K total=-932944794183923404
     ConcurrentHashMap size=  100000 entries/s=  26064.027K total=-516724530444651670
 ConcurrentSkipListMap size=  100000 entries/s=  46619.667K total=-897138307784594414
      AirConcurrentMap size=  100000 entries/s=  75034.058K total=-605290263409285564
---------------
               HashMap size=  300000 entries/s=  28271.140K total=-850157323063101369
               TreeMap size=  300000 entries/s=  23442.635K total=-933312552546033574
     ConcurrentHashMap size=  300000 entries/s=  22886.588K total=-517086645455936620
 ConcurrentSkipListMap size=  300000 entries/s=  26852.530K total=-897567202447311134
      AirConcurrentMap size=  300000 entries/s=  43406.800K total=-605991920028554584
---------------
               HashMap size= 1000000 entries/s=  20762.874K total=-850266118577777400
               TreeMap size= 1000000 entries/s=  21465.730K total=-933426629396373490
     ConcurrentHashMap size= 1000000 entries/s=  17617.501K total=-517179596963620996
 ConcurrentSkipListMap size= 1000000 entries/s=  17753.452K total=-897660153954995510
      AirConcurrentMap size= 1000000 entries/s=  24726.115K total=-606121840885886155
---------------
               HashMap size= 3000000 entries/s=  20859.307K total=-850290350569160265
               TreeMap size= 3000000 entries/s=  17078.422K total=-933446707332090721
     ConcurrentHashMap size= 3000000 entries/s=  19987.888K total=-517202444269781983
 ConcurrentSkipListMap size= 3000000 entries/s=  23990.479K total=-897687847659433070
      AirConcurrentMap size= 3000000 entries/s=  30472.006K total=-606157150359044044
---------------
               HashMap size= 10000000 entries/s=  18594.336K total=-850335966429011695
               TreeMap size= 10000000 entries/s=  14332.011K total=-933483200019971865
     ConcurrentHashMap size= 10000000 entries/s=  17038.665K total=-517248060129633413
 ConcurrentSkipListMap size= 10000000 entries/s=  18600.417K total=-897733463519284500
      AirConcurrentMap size= 10000000 entries/s=  39037.289K total=-606248382078746904
---------------
 
 
ForEach() performance test
               HashMap size=       1 entries/s=  60469.332K total=-429010055848020608
               TreeMap size=       1 entries/s= 162720.446K total=-1192873323002853184
     ConcurrentHashMap size=       1 entries/s=  39683.288K total=-238381128098095008
 ConcurrentSkipListMap size=       1 entries/s= 125216.579K total=-742139402594604448
      AirConcurrentMap size=       1 entries/s=  40199.780K total=-223453462147226592
---------------
               HashMap size=       3 entries/s= 154792.076K total=-907351702836558858
               TreeMap size=       3 entries/s= 209809.380K total=-1866688472587176884
     ConcurrentHashMap size=       3 entries/s= 100788.166K total=-558021636792810008
 ConcurrentSkipListMap size=       3 entries/s= 202179.445K total=-1380005440196857173
      AirConcurrentMap size=       3 entries/s=  99654.211K total=-536118642462089017
---------------
               HashMap size=      10 entries/s= 297297.392K total=-2080956150412338142
               TreeMap size=      10 entries/s= 228262.234K total=-2782965758065995472
     ConcurrentHashMap size=      10 entries/s= 189641.651K total=-1313404093180619596
 ConcurrentSkipListMap size=      10 entries/s= 304427.266K total=-2602702896415550485
      AirConcurrentMap size=      10 entries/s= 179131.091K total=-1257952993772621945
---------------
               HashMap size=      30 entries/s= 305634.315K total=-2079066757218703314
               TreeMap size=      30 entries/s= 224584.862K total=-2781566150975000263
     ConcurrentHashMap size=      30 entries/s= 174917.912K total=-1312321443993669200
 ConcurrentSkipListMap size=      30 entries/s= 354581.676K total=-2600502266614288915
      AirConcurrentMap size=      30 entries/s= 254150.967K total=-1256373143380530839
---------------
               HashMap size=     100 entries/s= 295763.376K total=-2123996537948400465
               TreeMap size=     100 entries/s= 225375.420K total=-2816005249627104526
     ConcurrentHashMap size=     100 entries/s= 168596.386K total=-1337959745143386554
 ConcurrentSkipListMap size=     100 entries/s= 366342.358K total=-2656351051389612808
      AirConcurrentMap size=     100 entries/s= 336305.468K total=-1307783105877232718
---------------
               HashMap size=     300 entries/s= 335940.642K total=-2176036047793281607
               TreeMap size=     300 entries/s= 213798.860K total=-2849343024468137449
     ConcurrentHashMap size=     300 entries/s= 196158.746K total=-1368245793652746886
 ConcurrentSkipListMap size=     300 entries/s= 348762.198K total=-2711376732587358984
      AirConcurrentMap size=     300 entries/s= 435378.640K total=-1375390632080685627
---------------
               HashMap size=    1000 entries/s= 312285.030K total=-2145888100702813327
               TreeMap size=    1000 entries/s= 157007.240K total=-2834013084542617045
     ConcurrentHashMap size=    1000 entries/s= 178919.552K total=-1350929801563960438
 ConcurrentSkipListMap size=    1000 entries/s= 253518.140K total=-2687136797657993712
      AirConcurrentMap size=    1000 entries/s= 449868.858K total=-1331959489090096491
---------------
               HashMap size=    3000 entries/s= 269579.050K total=-2118053337323592431
               TreeMap size=    3000 entries/s= 129271.886K total=-2820412724828116661
     ConcurrentHashMap size=    3000 entries/s=  95870.060K total=-1340856888537750166
 ConcurrentSkipListMap size=    3000 entries/s= 203849.473K total=-2666107139705649888
      AirConcurrentMap size=    3000 entries/s= 443682.852K total=-1286068695711899563
---------------
               HashMap size=   10000 entries/s= 100969.734K total=-2116523986910706773
               TreeMap size=   10000 entries/s=  81240.085K total=-2819237854014952091
     ConcurrentHashMap size=   10000 entries/s=  74229.656K total=-1339726640597926192
 ConcurrentSkipListMap size=   10000 entries/s= 147733.052K total=-2664068913299591178
      AirConcurrentMap size=   10000 entries/s= 399269.901K total=-1279844336850624703
---------------
               HashMap size=   30000 entries/s=  77830.586K total=-2121068856388826590
               TreeMap size=   30000 entries/s=  73801.711K total=-2823183557187296024
     ConcurrentHashMap size=   30000 entries/s=  63503.394K total=-1343522194696030345
 ConcurrentSkipListMap size=   30000 entries/s= 148907.153K total=-2671403338078408622
      AirConcurrentMap size=   30000 entries/s= 450044.679K total=-1305454406448994036
---------------
               HashMap size=  100000 entries/s=  57919.591K total=-2122150626578319295
               TreeMap size=  100000 entries/s=  39468.243K total=-2823932886520250879
     ConcurrentHashMap size=  100000 entries/s=  30273.873K total=-1344103393021081000
 ConcurrentSkipListMap size=  100000 entries/s=  48766.187K total=-2672332261897079327
      AirConcurrentMap size=  100000 entries/s= 307460.503K total=-1311189966514089586
---------------
               HashMap size=  300000 entries/s=  42127.664K total=-2122825947560403955
               TreeMap size=  300000 entries/s=  26508.090K total=-2824353316156729769
     ConcurrentHashMap size=  300000 entries/s=  27206.845K total=-1344518179306734670
 ConcurrentSkipListMap size=  300000 entries/s=  19172.093K total=-2672628537815403377
      AirConcurrentMap size=  300000 entries/s= 152485.548K total=-1313414387297697136
---------------
               HashMap size= 1000000 entries/s=  40607.148K total=-2123037200986959355
               TreeMap size= 1000000 entries/s=  25159.911K total=-2824487462082592448
     ConcurrentHashMap size= 1000000 entries/s=  30257.523K total=-1344677675643783997
 ConcurrentSkipListMap size= 1000000 entries/s=  37742.151K total=-2672825003502099899
      AirConcurrentMap size= 1000000 entries/s= 148954.277K total=-1314169618297632691
---------------
               HashMap size= 3000000 entries/s=  43941.038K total=-2123087741997557902
               TreeMap size= 3000000 entries/s=  18891.646K total=-2824508924703531557
     ConcurrentHashMap size= 3000000 entries/s=  32007.894K total=-1344715062144774703
 ConcurrentSkipListMap size= 3000000 entries/s=  21722.543K total=-2672849927836093703
      AirConcurrentMap size= 3000000 entries/s= 126084.363K total=-1314312240875486125
---------------
               HashMap size= 10000000 entries/s=  35724.715K total=-2123169850545290476
               TreeMap size= 10000000 entries/s=  12693.940K total=-2824540855805427558
     ConcurrentHashMap size= 10000000 entries/s=  27254.306K total=-1344783485934551848
 ConcurrentSkipListMap size= 10000000 entries/s=  13572.712K total=-2672886420523974847
      AirConcurrentMap size= 10000000 entries/s=  92726.047K total=-1314522073830802703
---------------

6. Резюме

Можно получить повторяемые, значимые пользовательские тесты производительности Map, используя простой код с определенными мерами предосторожности. Этот код показывает некоторые из этих проблем. Код легко адаптируется к другим видам тестов Map и форматам вывода данных.

40
Share: