大型HashMap評估：JDK、FastUtil、Goldman Sachs、HPPC、Koloboke與Trove

介紹

這篇文章將會介紹以JDK中HashMap作為標準的五種知名庫的hash map實現，并逐一測試：

• 原始數據類型到原始數據類型的映射
• 原始數據類型到對象的映射
• 對象到原始數據類型的映射
• 對象到對象的映射（JDK僅在這部分出現）
</ul>

這篇文章將會綜述一個測試——使用一組隨機key進行map讀取訪問（給定大小的待測試Collection共用同一組key）。

我們也會關注這些集合內的數據存儲方式和一些頗為有趣的實現細節。

評估對象

JDK 8

在這個測試中，JDK中的HashMap是最古老的hash map實現。最近它有兩個主要的更新——一個在Java 7u40版本中對于空map的共享的底層存儲，以及在Java 8中將底層hash bucket鏈接成為哈希樹（改進更差情況下的性能）。

FastUtil 6.5.15

FastUtil為開發者提供了一套涵蓋上述四個方面的API（包括所有基本類型和對象的組合）。除了那些，這也有一些其它類型的映射適用于每一個參數的類型組合：數組映射、AVL樹映射和RB樹映射。然后，這篇文章中我們只對hash映射感興趣。

Goldman Sachs Collections 5.1.0

高盛集團在三年前公開了他的集合庫的源代碼。在我看來，（如果你有需要）這個庫提供最寬泛的開箱即用的集合。你應該注意你需要的不僅僅是一個hash map、tree map和你工作所需的其它東西。本文的目標，GS collections為每一個hash map提供了一個常規的、同步的和不可修改的版本。最后兩個僅僅提供了常規的映射，所以沒有什么性能優勢。

HPPC 0.6.1

HPPC為所有原始數據類型提供了數組列表、數組隊列、哈希集合和哈希映射。HPPC為原始數據類型key提供了普通的hash map，并且為object key提供了普通的和帶標識的hash map。

Koloboke 0.6

Koloboke是這篇文章中最年輕的庫。它是Roman Leventov開發的OpenHFT工程中的一部分。目前該庫為所有原始數據類型或對象的組合提供了hash map和hash set。這個庫最近被重命名成了HFTC，因此在一些我測試的實例中會使用一些舊的庫名。

Trove 3.0.3

Trove發布了很長的時間且十分穩定。不幸的是，現在這個項目已經沒有進一步的開發。Trove為所有的原始數據類型、對象的組合提供了鏈表、棧、隊列、hash set和hash map。我曾經寫過一篇關于Trove的文章。

數據存儲的實現和測試

本文將著眼于4種不同的map：

1. int-int
2. int-Integer
3. Integer-int
4. Integer-Integer
</ol>

讓我們來看看這些map各自是如何存儲數據的。我們將參考測試命名而不是實際實現的名字。因為許多這些實現調用方式十分相似，同時也不容易通過命名來區分。在了解實現細節之后，我們將驗證它們是如何影響實際的測試結果。

我們將會使用JMH 1.0來測試。這里是測試描述：遍歷所有大小在（10K、100K、1M、10M和100M）的映射（外循環）從而生成一組隨機key（它們將在給定大小的映射中進行測試），然后運行每一個測試來實現映射（內循環）。每一個測試將會運行1億次 / map_size（以便我們對每個測試實例調用map.get 1億次）。

1. 準備：設置好一組int key和所需的填充因子
2. 初始化一個map給定填充因子和容量=key的數量
3. 填充map的key，設置values = keys
4. 存儲一個key數組引用或者轉換為Integer[]型用以測試object key（否則會使用相同的key）
5. 所有的測試幾乎是相同的——得到key數組所存儲的值然后再使用這些值，這樣JVM將不會優化你的代碼：
</ol>

public int runRandomTest() {
    int res = 0;
    for ( int i = 0; i < m_keys.length; ++i )
        res = res ^ m_map.get( m_keys[ i ] );
    return res;
}

int-int

</tr>
</tr>
</tr>
</tr>
</tr> </tbody> </table>

如你所見，FastUtil、HPPC和Trove使用相同的存儲，所以可以預見它們有相同的性能。

處理GS Collections和Koloboke中空單元和被刪除的單元

GS collections只使用了鍵值數組。如果你曾經接觸過hash map的實現應該知道，一個map應該至少可以從占用的集合中區分空單元（一些映射也使用“被刪除的單元”來標記）。如果沒有額外存儲，你要怎樣實現這些功能呢？GS IntIntHashMap使用了一個包括key=0（空單元）和key=1（被刪除單元）的合作哨兵對象（sentinel object）。所有在keys=0或者1上的操作都在這個哨兵對象上完成。這樣，一個對象允許GSIntIntHashMap來使用復雜度為O(1)的存儲來標記而不是使用O（容量）來標記。這樣只需訪問2個存儲單元而不是3個，操作起來更快速。

Koloboke int-int map（map的實際名稱隱藏在工廠類中且可能變化）的實現更進一步。首先，一些例子中它使用更長的數據類型數組作為存儲，這能讓鍵值保持在一個元素中。int-int map是這種方法的一個例子：一個key被存儲在long類型的低32位，值則被存放在高32位上。在這樣的布局下，查找冷門數據時只會出現1次緩存未命中。GS collections可能會出現2次不中，其他情況可能會有3次。

Koloboke使用了一種完全不同的技術來標記沒有使用的條目。當一個map初始化后，它隨機選擇一個int，使用它作為一個自由的單元標記。如果你嘗試插入一個key = 自由單元標記，它就會獲取另一個map中不存在的隨機值。這意味著Koloboke僅僅4使用了個字節就極其高效地處理了空節點。

一般而言，這種方式不會強加任何性能上的損失，除非你的映射大小非常接近一個給定數據類型的上限。你可能會想，如果在更小的key數據類型情況下會發生什么？如果想要添加所有數據類型進入map，那么將會得到一個在koloboke-api庫中定義的HashOverflowException。可以使用以下這些測試來重現這種情況：

HashByteIntMap m = HashByteIntMaps.newMutableMap( 256 );
for ( int i = Byte.MIN_VALUE; i < Byte.MAX_VALUE; ++i )
{
    final byte key = (byte) i;
    m.put( key, i );
}
m.put( Byte.MAX_VALUE, 127 );   //exception will be thrown here
System.out.println( m.size() );

然而，在現實生活中這還不算問題。如果你想將每個或者大多數byte、char、short映射到一些值的話，最好使用key索引下的值類型數組。

int-int測試結果

每個測試部分將以結果數據表開始，之后配有一幅圖。表中的第一行是map大小，所有測試結果單位為毫秒。





如你所見，這些函數庫明顯的分成了四組（從快至慢）：

1. Koloboke結果最好：使用long[]類型來存儲和一個不錯的技巧，將一個隨機自由的單元值復制給結果。Koloboke collections所有的3個版本都得到完全相同的結果（這并不意味著在其它測試中它們會一樣得快）。
2. 用GS collections的實現速度排名是第二：使用2個數組而不是3個在這里獲得了不錯的代碼質量。
3. FastUtil 和 HPPC性能表現完全相同的（相差不到不到2%）。
4. 測試中Trove的實現最慢：在大多數映射的情況下，大概比Koloboke慢兩倍。在巨型映射（10M+）的情況下更慢。
</ol>

int-Object

tests.maptests.primitive.FastUtilMapTest	int[] keys, int[] values, boolean[] used
tests.maptests.primitive.GsMutableMapTest	int[] keys, int[] values
tests.maptests.primitive.HftcMutableMapTest	long[] (key-low bits, value-high bits)
tests.maptests.primitive.HppcMapTest	int[] keys, int[] values, boolean[] allocated
tests.maptests.primitive.TroveMapTest	int[] _set, int[] _values, byte[] _states

tests.maptests.prim_object.FastUtilIntObjectMapTest	int[] key, Object[] value, boolean[] used
tests.maptests.prim_object.GsIntObjectMapTest	int[] keys, Object[] values
tests.maptests.prim_object.HftcIntObjectMapTest	int[] keys, Object[] values
tests.maptests.prim_object.HppcIntObjectMapTest	int[] keys, Object[] values, boolean[] allocated
tests.maptests.prim_object.TroveIntObjectMapTest	int[] _set, Object[] _values, byte[] _states

不出意外，FastUtil、HPPC 和 Trove使用了3個數組（包括一個單元狀態的數組）。GS collections 和 Koloboke使用了2個數組，這個技巧類似于上面列出的特殊情況。

int-Object測試結果





本次測試結果分三組（從快至慢）：

1. Koloboke只使用了2個數組所以是最快的，對于空的單元而言代碼更簡單。
2. FastUtil 和 HPPC緊隨GS collections身后（它們沒有盡力去發揮2個存儲數組的優勢而是使用了3個數組）。在不同的測試結果下它們略有不同，但彼此非常接近。
3. Trove又是最慢的那個，比Koloboke要慢1.5至2倍。

Object-int

對于Object key，FastUtil和HPPC使用了第三個數組。這看上去并不是什么好主意。因為你可以允許使用一個私有的哨兵對象作為object key的一個標志。實際上它的性能略差。

GS collections、Koloboke 和 Trove使用的是2個數組，所以有理由期待它們會快一點。

Object-int測試結果

這里分三組再次進行測試，但是不像之前那樣特意區分（由快到慢）：

1. Koloboke略快于GS collections，但是GS collections在10K和10M大小上的測試略勝一籌。
2. Trove和HPPC緊隨其后。
3. FastUtil是本次測試最慢的那個——它比Koloboke慢2-2.5倍。有趣的是，雖然使用的都是底層數組=3的情況，但是HPPC的實現明顯比FastUtil要快。

Object-Object

在Object-Object的映射的結果情況有些復雜：

• FastUtil和HPPC在每個映射中使用了3個數組，這沒啥新奇。
• .JDK中HashMap是存儲在Node對象中的唯一項，這將鍵值進行了結合。那意味著每一項你至少有24個字節的開銷。而事實上則是32個字節的開銷，因為每一個bucket中的HashMap是一個雙向鏈表，所以每一項有兩個額外的指針。
• Trove使用2個映射（和一個針對空單元的特殊哨兵對象）。
• 最后，GS collections 和 Koloboke正在使用一個交叉存儲的鍵值數組，這使它們成為了這6個Collection中CPU緩存利用得最好的一個。

現在，對這些map的實現了解之后。讓我們開始測試這些map的性能。

Object-Object測試結果

Object-Object測試結果更為復雜。

1. 通常情況下，Koloboke比JDKHashMap更快。但除了超大型map，其他情況即使Koloboke勝出，速度優勢也不是那么明顯。
2. 對于大型和超大map，GS Collections已經非常接近Koloboke 和 JDKmaps的性能，但對于小型map測試結果相去甚遠了。
3. 最后，FastUtil、HPPC和Trove對于各種大小的map下性能幾乎相同。

10億項測試

我將創建一個大小為10億項（entry 鍵值對），然后看看這些集合會發生什么。測試中設置因子為0.5，這意味著所有這些映射必須分配一個非常大的數組，允許的最大長度接近2³¹。

FastUtil、HPPC和GS collections因為各種異常失敗了(并不是因為OOM——我為這次測試分配了110G的內存)。

Koloboke、Trove和JDK設法通過了這些測試。不幸的是，這些測試在JMH上卻沒有成功運行。他們運行了另外一套代碼。

以上就是測試的結果（如果需要和之前的結果進行比較，需要把之前的結果乘以10。因為所有之前的結果總共調用了100M次map.get）：

tests.maptests.primitive.HftcMutableMapTest : time = 95.05 sec
tests.maptests.primitive.TroveMapTest : time = 235.062 sec

tests.maptests.prim_object.HftcIntObjectMapTest : time = 216.361 sec
tests.maptests.prim_object.TroveIntObjectMapTest : time = 304.019 sec

tests.maptests.object_prim.HftcObjectIntMapTest : time = 335.139 sec
tests.maptests.object_prim.TroveObjectIntMapTest : time = 217.412 sec

tests.maptests.object.HftcMutableObjTest : time = 272.792 sec
tests.maptests.object.JdkMapTest : time = 163.335 sec
tests.maptests.object.TroveObjMapTest : time = 239.133 sec

如你所見，Koloboke在primitive-primitive的轉化上贏得了很大的優勢。在primitive-to-object的轉換測試方面也明顯快了不少。

在object-primitive轉換測試中，Koloboke就明顯比Trove用時要久。

最后，對于object-object的轉換測試，我必須改變Koloboke map的初始化代碼，因為一旦我添加5億個元素性能就開始迅速下降：

HashObjObjMaps.getDefaultFactory().withHashConfig(HashConfig.fromLoads(0.5, 0.6, 0.8)).newMutableMap(keys.length)

Koloboke 2.0？

Roma Leventov剛剛宣布他正在考慮建一個更新更快的Koloboke庫，但是這需要你的反饋。你能幫他給出一點建議嗎？

總結

• Koloboke已經被證明是hash map實現最快也是存儲最高效的庫，但是它還剛剛誕生并沒有被廣泛使用，難道你不想試試？
• 如果你正在尋找更加穩定和成熟的庫（或者愿意犧牲部分性能），你或許應該看看GS collections library。與Koloboke不同，GS Collection給了你一個更加寬泛的開箱即用的集合。

源代碼

文章源代碼