避免装箱拆箱

Posted on

Java自带Collection、Guava等类库，提供了便捷的Set、Map、List等常用数据结构。在日常开发中，这些数据结构已经满足我们的需求。这些数据结构是基于泛型实现的，提供了一个“架子”，用户可以自行设定里面的具体类型。但涉及到原始类型Primitive types（long、int、double…）作为数据结构中的元素时，因为Java泛型的限制，对这些数据结构的操作会带来很多“不必要的”原始类型的装箱和拆箱。
例如：

1
2
3
Map<Long, Long> map = ...
map.put(1L);
long value = map.get(1L);

相当于：

1
2
3
Map<Long, Long> map = ...
map.put(new Long(1L));
long value = map.get(new Long(1L)).longValue();

为了这些问题，出现了很多支持原生类型的集合类库例如Trove、Eclipse Collections、koloboke、fastutil和argona。

具体的性能测试对比参见 https://github.com/austinv11/Long-Map-Benchmarks

从性能测试上来看Koloboke综合表现最好。但介于Koloboke在2016年后停滞在了1.0.0版本，用在生产环境还是有点虚的。论稳定性和功能的完整性，Eclipse Collections更胜一筹。

Koloboke

下面通过long-long map来初窥一下Koloboke。

使用

HashLongLongMap除了实现java.util.Map<Long, Long>的所有接口以外，还提供了long get(long key)和long put(long key, long value)等支持原生类型操作的接口。让我们可以以较低的改造成本将HashMap换成Koloboke的对应实现。

注意：

  • 不支持null key、null value。
  • 不支持多线程，但是是fail fast的。
  • 不支持Cloneable、Serializable。
  • 不能保证维持多于250,000,000个元素。当大小超过限制时，会抛出HashOverflowException。

选择

koloboke实现类库需要针对每种原始类型编写相应的实现，因此类库包会比较大（19MB）（但是方便呀）。koloboke除了提供实现类库以外，还提供了Compile，用户可以根据自己的需要生成所需的类。除了按需生成，Compile生成的实现在某些特殊场景上还比koloboke实现类库快5%。

实现

HashLongLongMap的实现类使用的实现方式和Java里面的HashMap不同，在解决Hash冲突时，使用的是开放地址法。如下图所示，它的key和value紧密相连。key存在偶数位，value存在相邻的奇数位。

优点：

  • 当Hash冲突时，不需要拉链，减少在添加和删除元素时的拉链的Node创建和销毁。
  • key和value在内存上紧密相连，（臆想）在同一缓存行，数据存取会比较快。
  • 存储使用long[]数组，并提供原生类型操作接口，避免不必要的装箱拆箱。
    缺点：
  • 当Hash冲突时，需要另外寻找位点，插入和查询性能会降低。（其实这对于拉链法也是一样的，Hash冲突，需要拉链，查询性能会降低）。

查找、插入和删除操作首先是找到key所在的位点index。index的计算方式是：

1
(mask(key)) & (capacityMask = (tab.length) - 2)

当index所在位置没有数据，即没有冲突时，就可以将tab[index] = key; tab[index + 1] = value;。如果冲突就设置index = (index - 2) & capacityMask。

那么问题来了怎么判断是否有冲突呢？存入的key是啥都有可能呐，又不能设置为null表示没有设置过值。为了解决这个问题，这里很鸡贼的引入了一个freeValue的概念。正如freeValue这个名字，freeValue就是不存在Map的keys里面的一个自由自在的long值。

那么问题又来了，万一我插入的key的值和freeValue相等呢？那我能怎么办，只能换一个不存在的freeValue值咯。（并且把数组里面原来的老的freeValue换成新的freeValue）。

增和查知道了，那删就是直接把key所在的index设为freeValue，标记为没有数据就行了吧（并不）。之前其他的数据因为冲突可能找了好几次才找到空位。这里直接设置为freeValue，那这个位点前面的数据可能就找不到了。所以需要根据情况进行相应的数据移动。如下图所示，KEY2因为KEY1已经占据，所以到前面找了个位置。当KEY1删掉后，KEY2也要进行相应的移动，移动到KEY1的位置。

删除移动的逻辑（简化版）

1
2
3
4
5
6
7
8
9
10
indexToRemove = indexToShift = index
while (true) {
    indexToShift -= 2
    if (indexShift对应的key == freeValue) {
        break
    } else if (indexShift对应的数据可以移动到indexToRemove所在位置){
        移动数据
        indexToRmove = indexToShift
    } 
}

Eclipse Collections

现有的原生类型类可能会出现OOM的BUG，详见 ISSUE 。预计在 10.0 milestone version修复

使用

LongLongHashMap只提供了操作原生类型的接口，没有实现java.util.Map<Long, Long>，在改造的时候可能工作量较大。

实现

Eclipse Collections的LongLongHashMap与前者的数据存储格式类似，都是KEY、VALUE紧密相邻存在一个数组中。不同的是它分别用key=0和key=1来表示空单元和被删除的单元。查找和插入的逻辑和Koloboke的HashLongLongMap类似，先找index，key冲突的话就去下一个位置找，匹配后key的index+1就是value存储的位置。

那么问题来了，那我要插入的数据的key为0或1怎么办（问题咋这么多）？LongLongHashMap使用了两个哨兵对象(sentinel object)来存储当key为0或1的值。查找、插入和删除都对这两个哨兵对象操作。

删除逻辑相对与Koloboke就简单很多，因为被删除的单元的key用1来表示，不需要在删除单元后移动其他的单元。只需要将被删除单元的key设置为1、value设置为0。

扩展阅读：

性能测试

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
@State(Scope.Benchmark)
//@Fork(value = 1, jvmArgsAppend = "-Xmx 64m -Xms 64m -XX:+PrintGCDetails")
@Fork(value = 1)
@Warmup(iterations = 1)
@Measurement(iterations = 1)
public class PutDeleteTest {
    private static final int                      SIZE          = 1000;

    private MutableLongObjectMap<TestValueObject> eclipseLOMap  = null;
    private MutableLongLongMap                    eclipseLLMap  = null;
    private LongObjMap                            kolobokeLOMap = null;
    private LongLongMap                           kolobokeLLMap = null;
    private Map<Long, TestValueObject>            jLOmap        = null;
    private Map<Long, Long>                       jLLmap        = null;
    private long                                  putIndex      = 0;

    ...

    @Benchmark
    public void kolobokeLongLongMapTest() {
        if (kolobokeLLMap == null) {
            kolobokeLLMap = HashLongLongMaps.newMutableMap(2048);
            for (; putIndex < SIZE; putIndex++) {
                kolobokeLLMap.put(putIndex, putIndex);
            }
        }
        kolobokeLLMap.put(putIndex, putIndex);
        kolobokeLLMap.remove(putIndex - SIZE);
        putIndex++;
    }

    @Benchmark
    public void eclipseHashLongLongMapTest() {
        if (eclipseLLMap == null) {
            eclipseLLMap = new LongLongHashMap();
            for (; putIndex < SIZE; putIndex++) {
                eclipseLLMap.put(putIndex, putIndex);
            }
        }
        eclipseLLMap.put(putIndex, putIndex);
        eclipseLLMap.remove(putIndex - SIZE);
        putIndex++;
    }

    public static void main(String... args) throws RunnerException {
        Options opt = new OptionsBuilder().include(PutDeleteTest.class.getSimpleName()).addProfiler(GCProfiler.class)
            .jvmArgsAppend("-Xms4g", "-Xmx4g", "-XX:+PrintGCDetails").build();

        new Runner(opt).run();
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
PutDeleteTest.concurrentHashLongLongMapTest                                     thrpt    5  25222540.523 ±  2219795.461   ops/s
PutDeleteTest.concurrentHashLongLongMapTest:·gc.alloc.rate                      thrpt    5      2213.704 ±      194.760  MB/sec
PutDeleteTest.concurrentHashLongLongMapTest:·gc.alloc.rate.norm                 thrpt    5        96.659 ±        0.001    B/op
PutDeleteTest.concurrentHashLongLongMapTest:·gc.churn.PS_Eden_Space             thrpt    5      2202.213 ±      361.536  MB/sec
PutDeleteTest.concurrentHashLongLongMapTest:·gc.churn.PS_Eden_Space.norm        thrpt    5        96.132 ±        9.404    B/op
PutDeleteTest.concurrentHashLongLongMapTest:·gc.churn.PS_Survivor_Space         thrpt    5         0.014 ±        0.023  MB/sec
PutDeleteTest.concurrentHashLongLongMapTest:·gc.churn.PS_Survivor_Space.norm    thrpt    5         0.001 ±        0.001    B/op
PutDeleteTest.concurrentHashLongLongMapTest:·gc.count                           thrpt    5        85.000                 counts
PutDeleteTest.concurrentHashLongLongMapTest:·gc.time                            thrpt    5        55.000                     ms
PutDeleteTest.concurrentHashLongObjectMapTest                                   thrpt    5  24952212.914 ±  1230098.599   ops/s
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.alloc.rate                    thrpt    5      2189.621 ±      107.990  MB/sec
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.alloc.rate.norm               thrpt    5        96.659 ±        0.001    B/op
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.churn.PS_Eden_Space           thrpt    5      2201.926 ±      330.942  MB/sec
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.churn.PS_Eden_Space.norm      thrpt    5        97.186 ±       11.418    B/op
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.churn.PS_Survivor_Space       thrpt    5         0.017 ±        0.022  MB/sec
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.churn.PS_Survivor_Space.norm  thrpt    5         0.001 ±        0.001    B/op
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.count                         thrpt    5        85.000                 counts
PutDeleteTest.concurrentHashLongObjectMapTest:·gc.time                          thrpt    5        50.000                     ms
PutDeleteTest.hashLongLongMapTest                                               thrpt    5  42870761.215 ± 18706977.204   ops/s
PutDeleteTest.hashLongLongMapTest:·gc.alloc.rate                                thrpt    5      4048.116 ±     1765.868  MB/sec
PutDeleteTest.hashLongLongMapTest:·gc.alloc.rate.norm                           thrpt    5       104.000 ±        0.001    B/op
PutDeleteTest.hashLongLongMapTest:·gc.churn.PS_Eden_Space                       thrpt    5      4050.324 ±     1778.662  MB/sec
PutDeleteTest.hashLongLongMapTest:·gc.churn.PS_Eden_Space.norm                  thrpt    5       104.050 ±        5.407    B/op
PutDeleteTest.hashLongLongMapTest:·gc.churn.PS_Survivor_Space                   thrpt    5         0.027 ±        0.036  MB/sec
PutDeleteTest.hashLongLongMapTest:·gc.churn.PS_Survivor_Space.norm              thrpt    5         0.001 ±        0.001    B/op
PutDeleteTest.hashLongLongMapTest:·gc.count                                     thrpt    5       156.000                 counts
PutDeleteTest.hashLongLongMapTest:·gc.time                                      thrpt    5        87.000                     ms
PutDeleteTest.hashLongObjectMapTest                                             thrpt    5  44863139.823 ± 16865234.866   ops/s
PutDeleteTest.hashLongObjectMapTest:·gc.alloc.rate                              thrpt    5      4236.239 ±     1592.934  MB/sec
PutDeleteTest.hashLongObjectMapTest:·gc.alloc.rate.norm                         thrpt    5       104.000 ±        0.001    B/op
PutDeleteTest.hashLongObjectMapTest:·gc.churn.PS_Eden_Space                     thrpt    5      4232.196 ±     1681.207  MB/sec
PutDeleteTest.hashLongObjectMapTest:·gc.churn.PS_Eden_Space.norm                thrpt    5       103.853 ±        6.346    B/op
PutDeleteTest.hashLongObjectMapTest:·gc.churn.PS_Survivor_Space                 thrpt    5         0.027 ±        0.026  MB/sec
PutDeleteTest.hashLongObjectMapTest:·gc.churn.PS_Survivor_Space.norm            thrpt    5         0.001 ±        0.001    B/op
PutDeleteTest.hashLongObjectMapTest:·gc.count                                   thrpt    5       163.000                 counts
PutDeleteTest.hashLongObjectMapTest:·gc.time                                    thrpt    5        97.000                     ms
PutDeleteTest.kolobokeLongLongMapTest                                           thrpt    5  43996155.514 ±  7379424.883   ops/s
PutDeleteTest.kolobokeLongLongMapTest:·gc.alloc.rate                            thrpt    5        ≈ 10⁻⁴                 MB/sec
PutDeleteTest.kolobokeLongLongMapTest:·gc.alloc.rate.norm                       thrpt    5        ≈ 10⁻⁶                   B/op
PutDeleteTest.kolobokeLongLongMapTest:·gc.count                                 thrpt    5           ≈ 0                 counts
PutDeleteTest.kolobokeLongObjectMapTest                                         thrpt    5  42801168.145 ±  3999300.909   ops/s
PutDeleteTest.kolobokeLongObjectMapTest:·gc.alloc.rate                          thrpt    5       932.827 ±       87.300  MB/sec
PutDeleteTest.kolobokeLongObjectMapTest:·gc.alloc.rate.norm                     thrpt    5        24.000 ±        0.001    B/op
PutDeleteTest.kolobokeLongObjectMapTest:·gc.churn.PS_Eden_Space                 thrpt    5       932.455 ±      222.476  MB/sec
PutDeleteTest.kolobokeLongObjectMapTest:·gc.churn.PS_Eden_Space.norm            thrpt    5        24.001 ±        6.043    B/op
PutDeleteTest.kolobokeLongObjectMapTest:·gc.churn.PS_Survivor_Space             thrpt    5         0.007 ±        0.015  MB/sec
PutDeleteTest.kolobokeLongObjectMapTest:·gc.churn.PS_Survivor_Space.norm        thrpt    5        ≈ 10⁻⁴                   B/op
PutDeleteTest.kolobokeLongObjectMapTest:·gc.count                               thrpt    5        36.000                 counts
PutDeleteTest.kolobokeLongObjectMapTest:·gc.time                                thrpt    5        20.000                     ms

更为详细的测试，分析，待续。。。