應用JMH測試大型HashMap的性能

PolarDB初賽進展

寫這篇是因為PolarDB比賽很重要的一點是控制記憶體。C++隻有2G，Java也隻有3G，而6400W的鍵值對，即使隻是

Long

類型，也需要

16 * 64 * 10e6 ≈ 1G

的記憶體，這還不包括其他對象引用的相關開銷，是以記憶體控制在這裡是非常重要的，因為稍不小心就會被CGroup無情地kill掉。是以在比賽開始沒多久的時候我就研究了一下使用怎樣的HashMap可以達到記憶體最簡的狀況。在這個過程中，順便使用了JMH來分析了一下幾個侯選庫的性能。因為初賽相對來說比較簡單，而且HashMap實際上在複賽時候的Range操作上沒有發揮餘地，是以我決定将這篇寫下來分享給大家，希望能幫助更多對比賽有興趣的同學找到一個比較好的入手點。

之前的初賽簡單思路可以看這裡。

侯選的集合庫

我們能第一時間想到的最樸素最直接的候選者就是Java自帶的

HashMap

了，這是我們平時使用最多也是最熟悉的實作。隻不過在這裡因為性能和記憶體消耗的原因，它稍微有點不合适。其實市面上有很多其他優秀的集合庫實作的，我在這裡大緻列一下我這邊會測試的幾個：

FastUtil: 一個意大利的計算機博士開發的集合庫。
Eclipse Collections: 由高盛開發的集合庫，後來捐給了eclipse基金會，成為了eclipse的項目.
HPPC: 專門為原始類型設計的集合庫。
Koloboke: 又一位大神的作品，目标是低記憶體高性能。
Trove: 挂在bitbucket上面的一個開源項目。

因為是為了比賽而接觸的這些庫，是以我隻按照比賽場景給他們做了測試。我們會預生成6400W對8位元組的Key，和8位元組的長整型Value，之後會将這些key全部寫入各自的HashMap中去，然後再從中讀取出來，并與暫存的Value作比較，判斷正确性。整個的測試過程是交給JMH來做的。下面介紹一下JMH工具。

JMH簡介

JMH是由OpenJDK開發的，用來建構、運作和分析Java或其他Jvm語言所寫的程式的基準測試架構。它可以幫助我們自動建構和運作基準測試，并且彙總得到結果。現在一般Java世界裡面的主流Benchmark就是應用的JMH。

Scala這邊，我們所熟悉的Ktoso大佬包了一個

sbt-jmh

插件，使得我們可以友善地利用SBT來運作JMH測試。要使用

sbt-jmh

插件，首先，在

plugins.sbt

檔案裡面添加插件：

1// project/plugins.sbt
2addSbtPlugin("pl.project13.scala" % "sbt-jmh" % "0.3.4")

之後，在項目中的子產品定義中，使用它：

1// build.sbt
2enablePlugins(JmhPlugin)

然後，我們就可以在sbt的console下，執行如下指令，來運作jmh測試了：

1jmh:run -i 3 -wi 3 -f1 -t1 .*FalseSharing.*

上面的參數解釋下來，就是要求項目對符合正規表達式

.*FalseSharing.*

的基準測試，運作3次，運作之前要進行3次預熱，隻需要跑一遍，使用一個線程。

好，介紹結束，我們接下來看一下我們如何來編寫程式測試各種Map。

HashMap測試代碼

首先，我們先建立一個類，如下：

1@State(Scope.Benchmark)
2@OutputTimeUnit(TimeUnit.SECONDS)
3@BenchmarkMode(Array(Mode.Throughput))
4class jmh.HashMapBenchmark {
5
6}

JMH使用注解來标記的基準測試。上面三個注解的選項的意思分别是：

State 表明可以在類裡面建立成員變量，供所有測試複用，複用的範圍是在 Benchmark 當中；
OutputTimeUnit 表示輸出Benchmark結果的時候，計時機關是 TimeUnit.SECONDS ；
BenchmarkMode ，Benchmark的模式是測試吞吐率。

為了做基準測試，我們首先建立一個6400W大小的清單，清單的元素是一個二進制組，都是

Long

1 val random = new Random(42)
2
3 val testSet: List[(Long, Long)] = List.range(0, 64000000).map { _ =>
4 val key = random.nextLong()
5 val value = random.nextLong()
6 key -> value
7 }

這裡有個關于比賽的小技巧，由于Key都是8位元組的，是以其實每個Key都很容易轉化成

Long

類型的。是以我們在測試裡面也隻測試對于Long類型的寫入性能，以Java的

HashMap

為例：

1 @Benchmark
 2 @OperationsPerInvocation(OperationsPerInvocation)
 3 def testHashMap() = {
 4 val hashMap = new util.HashMap[Long, Long](64000000)
 5 testSet.foreach { case (k, v) =>
 6 hashMap.put(k, v)
 7 }
 8 testSet.foreach { case (k, v) =>
 9 val readValue = hashMap.get(k)
10 assert(readValue == v)
11 }
12 }

@Benchmark

表示這是一個要運作的基準測試。

@OperationsPerInvocation

注解會接收一個數值，表示這個測試的方法運作了多少次。在我們這邊是

OperationPerInvocation

次。注意，前面的變量在

jmh.HashMapBenchmark

的伴生對象中定義：

1object jmh.HashMapBenchmark {
2 val OperationsPerInvocation = 64000000 * 2
3}

然後，我們就能夠啟動sbt，輸入前面提到的

jmh:run

指令了。我們先跑一波看看：

1jmh:run -i 3 -wi 3 -f1 -t1 .*HashMap.*

跑起來以後我感覺我錯了，電腦風扇在狂轉，而且預熱半天都跑不完。

jstat

看一下gc情況試試先，發現100多秒都是FGC。。

1S0C S1C S0U S1U EC EU OC OU MC MU CCSC CCSU YGC YGCT FGC FGCT GCT
2931840.0 931840.0 0.0 0.0 932352.0 932352.0 5592576.0 5592545.4 9856.0 9391.3 1408.0 1316.6 12 36.611 9 145.669 182.280
3931840.0 931840.0 0.0 0.0 932352.0 932352.0 5592576.0 5592545.4 9856.0 9391.3 1408.0 1316.6 12 36.611 9 145.669 182.280

果斷殺掉，加上jvm參數以後再測試：

1jmh:run -i 3 -wi 3 -f1 -t1 --jvmArgs "-Xmx10g" .*HashMap.*

10G也是慢，跑太久了，不樂意跑了，果斷放棄。我們直接來看其他的實作。

這裡還要說一下，因為記憶體有要求，是以我們需要同時列印一下HashMap的記憶體大小。我所使用的是網上找到的一個應該是從Spark代碼中摳出來的一個實作，速度快，估值準。隻需要在

build.sbt

中如下引入即可。

1libraryDependencies += "com.madhukaraphatak" %% "java-sizeof" % "0.1"

主要代碼編寫

因為其實這裡的hashmap的庫使用其實大同小異，為了避免重複，是以我利用Scala的一些特性來進行代碼編寫。首先我定義了一個特質為

LongLongOp

1trait LongLongOp {
2 def put(key:Long, value:Long):Long
3 def get(key:Long):Long
4}

之後，我們寫一個周遊

testSet

的函數：

1 def testSetTraverse(hashMap:LongLongOp) = {
2 testSet.foreach { case (k, v) =>
3 hashMap.put(k, v)
4 }
5 testSet.foreach { case (k, v) =>
6 val readValue = hashMap.get(k)
7 assert(readValue == v)
8 }
9 }

然後，我們利用特質可以混入的特性，在生成HashMap的時候，混入

LongLongOp

，然後交由

testSetTraverse

執行。這樣我們每次隻需要建立HashMap即可了。例如，FastUtil的測試如下：

1 @Benchmark
2 @OperationsPerInvocation(OperationsPerInvocation)
3 def testFastUtil() = {
4 val map = new Long2LongArrayMap(MapSize) with LongLongOp
5 testSetTraverse(map)
6 printlnObjectSize("fastutil Long2LongArrayMap", map)
7 }

其中

printLnObjectSize

是用來列印

map

占用記憶體數量的：

1 def printlnObjectSize(message:String, obj: AnyRef) = {
2 val size = SizeEstimator.estimate(obj)
3 val sizeInGB = size.toDouble / 1024 / 1024 / 1024
4 println(s"$message size is ${sizeInGB}GB")
5 }

之後，依次使用Eclipse Collections, Hppc, Koloboke和Trove，就完成了我們的Benchmark編寫：

1import java.util.concurrent.TimeUnit
 2
 3import com.koloboke.collect.impl.hash.MutableLHashParallelKVLongLongMapGO
 4import com.madhukaraphatak.sizeof.SizeEstimator
 5import gnu.trove.map.hash.TLongLongHashMap
 6import org.openjdk.jmh.annotations._
 7
 8import scala.util.Random
 9
10object HashMapBenchmark {
11 final val OperationsPerInvocation = 64000000 * 2
12}
13
14trait LongLongOp {
15 def put(key: Long, value: Long): Long
16
17 def get(key: Long): Long
18}
19
20@State(Scope.Benchmark)
21@OutputTimeUnit(TimeUnit.SECONDS)
22@BenchmarkMode(Array(Mode.Throughput))
23class HashMapBenchmark {
24
25 import HashMapBenchmark._
26
27 val random = new Random(42)
28 val MapSize = 64000000
29
30 val testSet: List[(Long, Long)] = List.range(0, MapSize).map { _ =>
31 val key = random.nextLong()
32 val value = random.nextLong()
33 key -> value
34 }
35
36 def testSetTraverse(hashMap: LongLongOp) = {
37 testSet.foreach { case (k, v) =>
38 hashMap.put(k, v)
39 }
40 testSet.foreach { case (k, v) =>
41 val readValue = hashMap.get(k)
42 assert(readValue == v)
43 }
44 }
45
46 def printlnObjectSize(message: String, obj: AnyRef) = {
47 val size = SizeEstimator.estimate(obj)
48 val sizeInGB = size.toDouble / 1024 / 1024 / 1024
49 println(s"$message size is ${sizeInGB}GB")
50 }
51
52 @Benchmark
53 @OperationsPerInvocation(OperationsPerInvocation)
54 def testEclipseCollection() = {
55
56 import org.eclipse.collections.impl.map.mutable.primitive.LongLongHashMap
57
58 val map = new LongLongHashMap(MapSize)
59 testSet.foreach { case (k, v) =>
60 map.put(k, v)
61 }
62 testSet.foreach { case (k, v) =>
63 val readValue = map.get(k)
64 assert(readValue == v)
65 }
66 printlnObjectSize("Eclipse LongLongHashMap", map)
67 }
68
69 @Benchmark
70 @OperationsPerInvocation(OperationsPerInvocation)
71 def testHppc() = {
72
73 import com.carrotsearch.hppc.LongLongHashMap
74
75 val map = new LongLongHashMap(MapSize, 0.99) with LongLongOp
76 testSetTraverse(map)
77 printlnObjectSize("hppc LongLongHashMap", map)
78 }
79
80 @Benchmark
81 @OperationsPerInvocation(OperationsPerInvocation)
82 def testKoloboke() = {
83 val map = new MutableLHashParallelKVLongLongMapGO() with LongLongOp
84 testSetTraverse(map)
85 printlnObjectSize("Koloboke", map)
86 }
87
88 @Benchmark
89 @OperationsPerInvocation(OperationsPerInvocation)
90 def testTrove() = {
91 val map = new TLongLongHashMap(MapSize, 1.0f) with LongLongOp
92 testSetTraverse(map)
93 printlnObjectSize("Trove LongLongMap", map)
94 }
95}

其中Eclipse collection的

put

方法的傳回值是

void

，與其他集合不一樣，是以隻能單獨為它寫一個測試方法。

結果

運作的過程中，Koloboke報一個詭異的空指針錯誤，是以沒有通過測試；FastUtils在這個量級好像有點慢，不樂意等是以最終沒有把它加入測試。最終我們得到如下的結果清單：

綜合記憶體使用以及性能，我個人覺得在此次比賽初賽中，也許HPPC是個比較好的選擇。

是以，初賽使用Java的

HashMap

實作的小夥伴，是不是應該趕緊思考一下換一下記憶體索引的結構，來避免OOM呢？

原文釋出時間為： 2018-11-07

本文作者：Kirito的技術分享

本文來自雲栖社群合作夥伴“

Kirito的技術分享

”，了解相關資訊可以關注“

”。

應用JMH測試大型HashMap的性能

PolarDB初賽進展

侯選的集合庫

JMH簡介

HashMap測試代碼

主要代碼編寫

結果

繼續閱讀

Java String.format方法的簡單使用

neo4j之cypher使用文檔

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

線性表之順序表的實作

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method