マップ系モジュールのベンチマーク

Erlang

最近、かなり以前に作成したErlangのハッシュマップ的なライブラリ(hashtrie)のrebar対応等を行う機会があったので、ついでにErlangでマップ的な処理を行うために使えるデータ構造(モジュール)群の性能測定をしてみた。

対象モジュール

※ orddictは明らかに他に比べて遅いと思われたので対象外とした(別に含めても良かったかもしれない)
※ etsは破壊的な操作が含まれることにより、他のモジュールとの測定コードの共通化が面倒だったので対象外

なおR17.0から導入されたmapsの性能特徴に関してはQiitaの記事を参照のこと。

計測環境

計測方法

  • ベンチマークコード: https://github.com/sile/hashtrie/blob/v0.1.3/src/hashtrie_bench.erl
    • 計測対象の操作は 挿入(store)、検索(find)、削除(erase) の三つ
      • 今回は簡単のために、検索および削除は、全て成功するキーで行っている (失敗探索等はない)
    • キーの型は 整数値 と 文字列(正確にはバイナリ) の二つ
      • 整数値の範囲は 0 から 最大要素数 までの連続する値
      • 文字列の場合は 最大百バイト までのランダムなバイト列
    • 要素数は 1、10、100、1000、10000、100000 の六通り
      • 要素数が 1 の場合は百万回ループ、100の場合は一万回ループ、といったように操作の適用回数の合計が百万回になるようにして計測を行った
      • 最終的な計測値は、操作一回辺りの平均所要時間
    • 入力要素の並び順は ランダム と 昇順 のニパターン
  • 全てのモジュールでHiPEコンパイルのON/OFFの両方で測定

計測結果

以下、縦軸は要素数で、横軸はモジュール名、セルの値は一操作辺りの平均所要時間(ナノ秒単位)。
※ 丸括弧内の数値はモジュールをHiPEでコンパイルした場合の各種操作の平均所要時間

ランダムに並んだ要素の挿入 (random-store)

キーが整数値

array (hipe) dict (hipe) gb_trees (hipe) hashtrie (hipe) splay_tree (hipe)
1 319 (204) 820 (349) 262 (168) 347 (219) 168 (150)
10 197 (135) 678 (316) 532 (144) 325 (189) 624 (150)
100 356 (208) 995 (378) 925 (205) 572 (337) 1526 (296)
1000 434 (279) 1347 (546) 1515 (542) 594 (310) 2517 (618)
10000 535 (370) 1570 (767) 1795 (641) 681 (365) 3633 (970)
100000 719 (508) 2577 (1760) 2568 (1031) 952 (634) 4751 (1377)

array が全体的に性能が良くて、次に安定しているのは　hashtrie といった感じ。
要素数が少ない内なら gb_trees や splay_tree も結構良い値が出ている(HiPE版なら)。

後は、HiPEを適用した場合の効果が思ったよりも大きかった。

キーが文字列

キーが文字列の場合は array は対象外 (以下同)

dict(hipe) gb_trees(hipe) hashtrie(hipe) splay_tree(hipe)
1 820 (367) 241 (155) 372 (246) 166 (146)
10 795 (357) 708 (388) 377 (234) 742 (266)
100 1202 (489) 1250 (822) 694 (462) 1890 (721)
1000 1659 (776) 2193 (1406) 717 (394) 3158 (1353)
10000 1975 (1123) 3206 (2232) 865 (531) 4656 (2101)
100000 6035 (5211) 4716 (3601) 1401 (1091) 6923 (3847)

キーが整数値の場合に比べて、全体的にオーバヘッドが増えているように見えるが、傾向自体はそんなに変わらなそうな印象。
array がない分 hashtrie が優秀に見える。

昇順に並んだ要素の挿入 (sequential-store)

キーが整数値

array (hipe) dict (hipe) gb_trees (hipe) hashtrie (hipe) splay_tree (hipe)
1 320 (204) 823 (352) 262 (169) 349 (219) 172 (154)
10 186 (138) 701 (316) 864 (257) 320 (188) 292 (120)
100 336 (191) 985 (368) 1942 (536) 572 (323) 295 (113)
1000 421 (252) 1336 (527) 3318 (1127) 594 (310) 328 (140)
10000 487 (296) 1508 (721) 4499 (1422) 681 (366) 335 (146)
100000 571 (352) 2603 (1802) 6058 (2106) 976 (669) 351 (160)

入力要素群がソートされている場合の挿入速度は splay_tree が圧倒的に早かった。 (スプレー木の特性上、この場合、単なるリストの先頭への要素追加とほぼ等しい処理となる。当然作成される木はバランスしていない)

array、hashtrie、dict は、入力のソートの有無は、あまり速度に影響がない模様。

gb_treesの場合は、入力がソートされている方が却って悪い結果となっていた。

キーが文字列

dict(hipe) gb_trees(hipe) hashtrie(hipe) splay_tree(hipe)
1 813 (368) 241 (155) 380 (246) 166 (145)
10 801 (361) 1182 (677) 376 (229) 351 (180)
100 1146 (493) 2869 (1786) 691 (441) 384 (189)
1000 1630 (765) 4887 (3156) 720 (416) 390 (210)
10000 1985 (1134) 6885 (4493) 865 (532) 405 (219)
100000 5978 (5260) 9577 (6535) 1359 (1042) 533 (368)

要素をランダムに検索 (random-find)

キーが整数値

array (hipe) dict (hipe) gb_trees (hipe) hashtrie (hipe) splay_tree (hipe)
1 199 (149) 429 (227) 190 (153) 279 (163) 232 (144)
10 119 (89) 327 (163) 156 (96) 180 (108) 886 (166)
100 155 (124) 403 (197) 225 (111) 224 (111) 1866 (334)
1000 210 (159) 403 (200) 307 (168) 275 (146) 2916 (749)
10000 263 (200) 402 (219) 403 (238) 303 (172) 4061 (1156)
100000 320 (256) 459 (293) 540 (355) 356 (234) 5388 (1764)

ランダム検索は splay_tree だけが明らかに遅いのを除けば、それ以外のデータ構造間では、処理時間にそこまで大きな違いはなかった。
ただ、今回も array と hashtrie が他よりも性能が良い傾向があった。(gb_trees も入力サイズが小さいなら結構優秀)

splay_tree に関しては、データ構造の性質上、検索時等にも(部分的な)バランシングが行われるため、 完全に読み込みのみの他のデータ構造に比べて性能が落ちるのは仕方がないが、最初に一回大規模な入力をもとにマップを作成して、 後はひたすら検索のみ、といった用途には向かなさそう。
(とはいえ、検索されるキーが明らかに偏っている場合には、その限りではないが)

同じキーに対する検索と更新(or 削除)がセットになっているような処理の場合は、最初の検索時のバランシング(スプレー操作)により、 後続の更新操作のコストが軽減されるので、必ずしも検索操作単体が遅いことが、実際のユースケースでの性能劣化にはつながらないようにも思うが、 今回の計測では、そういった複雑な条件は全く考慮していないので、詳細は不明。

キーが文字列

dict(hipe) gb_trees(hipe) hashtrie(hipe) splay_tree(hipe)
1 435 (246) 176 (159) 308 (186) 231 (157)
10 403 (237) 215 (200) 240 (162) 1129 (362)
100 490 (280) 384 (356) 290 (170) 2289 (888)
1000 480 (285) 603 (554) 366 (213) 3631 (1540)
10000 509 (329) 895 (827) 407 (261) 5156 (2375)
100000 590 (421) 1257 (1201) 493 (368) 7961 (4355)

要素をシーケンシャルに検索 (sequential-find)

キーが整数値

array (hipe) dict (hipe) gb_trees (hipe) hashtrie (hipe) splay_tree (hipe)
1 199 (149) 436 (232) 190 (154) 279 (164) 235 (147)
10 119 (89) 328 (163) 157 (97) 179 (109) 523 (127)
100 153 (124) 400 (195) 217 (110) 224 (112) 707 (145)
1000 211 (159) 393 (187) 290 (147) 271 (143) 753 (175)
10000 264 (199) 386 (201) 362 (179) 299 (167) 782 (202)
100000 317 (239) 453 (293) 453 (221) 360 (242) 808 (224)

splay_tree だけが（アクセスの局所性があがったことにより)処理速度が大幅に向上しているが、それ以外はランダムの場合とで大きな違いは見られない。
(あえて云えば gb_trees の性能は若干向上している)

キーが文字列

dict(hipe) gb_trees(hipe) hashtrie(hipe) splay_tree(hipe)
1 435 (246) 177 (159) 305 (186) 229 (157)
10 406 (246) 216 (201) 240 (163) 575 (222)
100 491 (279) 380 (354) 289 (170) 826 (323)
1000 477 (284) 575 (531) 365 (212) 895 (369)
10000 504 (323) 773 (707) 400 (256) 919 (388)
100000 569 (416) 995 (916) 491 (364) 1142 (554)

ランダム順での要素の削除 (random-erase)

キーが整数値

arrayモジュールには要素の削除がないので対象外 (以下同)

dict(hipe) gb_trees(hipe) hashtrie(hipe) splay_tree(hipe)
1 880 (338) 315 (151) 496 (198) 201 (133)
10 918 (311) 376 (105) 391 (157) 610 (165)
100 922 (357) 633 (148) 488 (208) 1464 (315)
1000 1086 (406) 917 (310) 509 (229) 2386 (617)
10000 1183 (524) 1206 (487) 607 (299) 3445 (910)
100000 2416 (1730) 1646 (838) 843 (533) 4659 (1418)

ランダム削除もだいたい他の操作と似たような傾向で hashtrie が全体的に速く、 gb_treesは要素数が比較的少ない場合に優秀、splay_treeは(局所がない)ランダムアクセスに弱い、という結果になっている。

キーが文字列

dict(hipe) gb_trees(hipe) hashtrie(hipe) splay_tree(hipe)
1 857 (327) 297 (174) 521 (226) 199 (145)
10 843 (333) 433 (238) 444 (207) 640 (218)
100 1103 (462) 928 (589) 586 (287) 1740 (648)
1000 1213 (509) 1449 (996) 606 (323) 2907 (1190)
10000 1470 (781) 2107 (1577) 736 (425) 4359 (1914)
100000 6095 (5450) 3229 (2714) 1217 (955) 6697 (3575)

シーケンシャルに要素を削除 (sequential-erase)

キーが整数値

dict(hipe) gb_trees(hipe) hashtrie(hipe) splay_tree(hipe)
1 880 (339) 315 (152) 498 (197) 203 (134)
10 917 (312) 324 (106) 379 (154) 305 (96)
100 838 (313) 400 (121) 487 (212) 414 (102)
1000 960 (348) 497 (157) 511 (230) 440 (120)
10000 1036 (449) 582 (173) 614 (303) 429 (110)
100000 2262 (1622) 676 (216) 912 (605) 446 (129)

これも他の操作と同様に、入力データがシーケンシャルに並んでいる場合は、splay_treeの処理速度が大幅に向上している。
(gb_trees もランダム削除の場合に比べて良い結果となっている)

キーが文字列

dict(hipe) gb_trees(hipe) hashtrie(hipe) splay_tree(hipe)
1 852 (322) 297 (173) 513 (233) 199 (147)
10 827 (323) 388 (212) 444 (208) 292 (120)
100 941 (433) 552 (334) 582 (303) 451 (162)
1000 1082 (472) 729 (474) 617 (329) 484 (178)
10000 1344 (752) 947 (641) 779 (464) 489 (196)
100000 5477 (4781) 1237 (915) 1171 (867) 562 (307)

感想

とりあえず今回測ってみた範囲内での感想:

  • arrayは、キーが整数値の場合は結構使えそう
    • 思っていたよりも良い結果が出ていたので、目的があえば積極的に使っていっても良さそう
    • ただし、入力の範囲が極端に疎だったり、値の上限が極端に大きい場合などは、性能が劣化する可能性もありそうなので注意が必要かもしれない
  • dictは、可もなく不可もない感じ
    • 他のデータ構造に比べて極端に性能が劣るケースはなかった(若干削除が苦手？)が、その反対もなかった
    • あえて使いどころを探すなら、大規模(数万件以上)なデータから一番初めに一回だけオブジェクトを作成して、後はひたすら検索のみ、というケースで有効かもしれない
  • gb_treesは、標準で提供されているマップ系のモジュールの中で一番使いやすそう
    • 入力データサイズが小さい場合は、全般的に高速 (空オブジェクトの生成コストも低い)
    • 入力データの並び順に依存して、結構処理性能に差がでたりはするが、それでも全般的にdictよりは速いことが多かった
    • gb_trees:take_smallest/1 等を使えば、優先順位付キュー的な用途にも利用可能
      • ただし、最後の使用途の場合は splay_tree の方が良い選択である可能性がある
  • hashtrieは、安定して良い性能が出ていた
    • 若干、数値が良すぎるような気がしないでもないので気になる (バグがないか)
    • 削除時のテーブルのリサイズ(縮小)に未対応なので、一時的でもサイズが大きくなってしまうと、それを回収する方法がない
    • とはいえ dict や gb_trees の大体として実験的に使っていっても良いかもしれない
  • splay_treeは、明らかに性能傾向が偏っている
    • 汎用的なマップとして使用するには、ランダムアクセスに弱いのが厳しい
    • 入力データが明らかに偏っていると分かっている場合にはかなり有効
      • 入力データサイズが小さい場合も効率的
    • タイムスタンプのように常に上昇していく値をキーとした優先順位付きキューへの転用などには結構向いているかもしれない
      • 挿入時は木の末尾に、取り出し時は木の先頭に、アクセスが偏るため
    • 用途が嵌れば便利に使えるので、個人的には結構お気に入り
  • データ構造の実装モジュールにHiPEは有効
    • HiPEにするだけでコンスタントに数割程度(大きい時には数倍)は性能が向上していた