ScalaのHashMapに関する論文(Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections)輪読会 in FOLIOを開催した

Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collectionsの輪読会を開催したのでレポブログです。

OOPSLA2015で発表されたCHAMPというScalaのimmutable.HashMapとして採用されているデータ構造についての論文です。 実際にScalaのソースを見ても論文へのリンクがついていました。

scala/src/library/scala/collection/immutable/HashMap.scala at 93d6281876ae53d7eb0d1f1e8369437f0a260015 · scala/scala · GitHub

CHAMP自体はHAMT(Hash Array Mapped Trie)というHashMapの改善バージョンといった位置づけで内部のデータ構造を効率化したり、JVM向けの最適化(JVMだとarrayもobjectだからlength propertyとか無駄になっちゃうよねとか）しているものでした。

いきなりこの論文を読み始めたんですがHAMTについてはっきり分かる形では書かれておらず、前提になっているアレコレを急いで調べたりしましたがそれはそれで学びになったのでよかったのではないでしょうか。

目次

HAMT

HAMTについては以下の資料が理解に役立つと思います。特に最初のものが図解で基本的なアイデア（Hash値をn bitずつに区切ったtrie木を構築してbitmaskとともに圧縮して持つ）がわかりやすいと思いました。

動画も参考になると思います。

www.youtube.com

ベースとなる価値観としてimmutable collectionというかpersistent data structure周りの直感があると役に立つので 純粋関数型データ構造(PDFS) を読んだことがあるとピンとくるところがあるかもしれません。（読んだことがなくてもHAMTは理解できる）

このデータ構造のキモはbitmaskでデータを圧縮して持つことにありますが、その際にpopulation countというビット演算が利用されているところが興味深いところでした。popcntは様々なCPUで専用命令があるのである程度の処理性能の向上が期待できそうですね。

CHAMP

CHAMPについてはHAMTに比べると情報が少ないのですが下記が参考になると思います。

動画も参考になると思います。（同じタイトルですが別の人の別の講演）

www.youtube.com

内容的には新しいアイデアでHAMTを一歩すすめた形で、HAMTでお〜っとなった後に読むと面白いのではないかと思いました。（JVMの方が効く最適化ではあるものの、JVM以外でも有効なような気もする・・？みたいな疑問もあり解像度がすごい高い訳では無いですがアイデアは理解できたと思います。）

輪読会について

はじめは予習なしでアドリブでだらだら毎週ちょっとずつ読んでいこうという目論見だったのですが、前提知識などがある程度必要でその場で読み進めるのは難しそうだったので毎週二人ずつ予習して３０分ずつ解説という形を取らせてもらいました。最初は予習なしで募集しておいてアレですがみんな快く予習＆発表に協力してくれました。7人くらいでわいわいやれたので発表頻度的にもあまり頻繁ではなくできたかなと思っています。（木をcanonical formにする形式化のところを担当する人と、ベンチマーク取ってるところを担当する人で難易度の差が激しかったりはする）

普段使ってるScalaのデータ構造も意外と実装を知らなかったりするのでこういうところで一つずつ中身を知っていけるといいですね。

余談

4年越しで計画の1/6が進んだのであと20年くらいしたら全部読み終わるかもしれない₍₍ (ง´･_･`)ว ⁾⁾