FOLIOでやってるマネージメント勉強会の紹介

この記事は FOLIO Advent Calendar 2023 - Adventar 9日目の記事です。

マネージメント技術の学び方

突然ですが、マネージメント技術ってどう学んでいますか? 特に新任のリーダーにとっては暗中模索だったり、とりあえず業務を回すのに精一杯でなかなか深掘りできないといったケースも多いのではないでしょうか。

今日はそんなマネージメント技術の学び方についてFOLIOで実施している取り組みを紹介します。

課題

新規にマネージャーになる場合、業務で利用するスキルセットが大きく変わることになります。 マネージャーのスキルセットは相互に関連があり個別には学びにくくインプットから実践までのハードルもあります。 このとき、何をどの程度学べばいいのかといった指針がないと新任マネージャーが徒手空拳で戦うことになってしまうという課題があります。

また、FOLIOのようなスタートアップ企業の場合、バックグラウンドの異なる社員が多数在籍しておりマネージャーの役割・理想的な振る舞いに関する認識も様々です。 多様な価値観が同居するのは良いことですが、一人ひとりのマネージャーが違う流派で戦うことになると相談・アドバイスがしづらいという問題も出てきます。

結果として、何となく要領よくできる人や前職でマネージメント経験のある人がリーダーを担当することになり、長期的には社内からリーダーをやりたいと思う人が出づらくなる(学べるスキルが自明でなくキャリアにつながるのかわからない。要領よくできる自信がない。)、社内でリーダーが育ちにくくなる(社外から経験者を取り続けることになる。)といった問題がでてくることが想定されました。

マネージメント勉強会

上記の課題の解消に向けて、比較的距離感の近いバックエンドチームのマネージャー陣4名にてマネージメント勉強会を実施することになりました、

実施方法

  • エンジニアのためのマネジメント入門 を輪読する
  • 1名が区切りのいいところまで音読。他3名は内容をメモする
  • 内容のメモを順番に発表。このとき自分が持っている別の知識や、社内や前職での事例についても共有する

狙い

この会による狙いは以下です。

  • マネージャー自身が体系的にマネージメント技術を学ぶ
  • マネージャー間での価値観や経験知を共有する
  • マネージャー間で共通言語を作る
  • 今後マネージャーになる人にとって、マネージャーが学ぶべき内容を分かりやすく整理し、経験と勘がない状態でも技術とノウハウを身に着けマネージャーとして成長できる道筋を作る

やってみて

自分で読むより深く読める。記憶に残る

本に出てくる各種モデルやテクニックは読んだだけではなく実践して初めて意味が出てくるものです。 一方で本でサラッと読んだだけだと翌日には忘れてしまっているということもよくあるのではないでしょうか。 勉強会で時間をかけて話したり実際の経験と照らし合わせて自分自身が話すことで記憶に残り、普段のマネージメント業務で活かしやすくなる効果がありました。

毎週実施しているので学んだことを実際にミーティングのファシリテーションや1on1などでのコミュニケーションに取り入れてみてどうだったかといった感想のシェアをタイムリーに行えるのも良い点でした。これにより自分もやってみよう・真似してみようといった気持ちになりやすい環境になったと感じています。

マネージャー陣の中で共通言語ができた

実際の問題を議論するときに、5分かけて「行動変容ステージモデルってのがあって、それによると人の行動が変わるにはこういうステージがある。」と長々と解説されたあとに問題に対するアプローチに話題を移していくのはなかなか難しいものです。

この会を実施したことで「無関心期の人に実行期の施策をいきなり提案してるかもな」といった話がいきなり可能になり、問題認識・課題解決への方法模索がスムーズにりました。 もちろんモデルに当てはめればすぐ解決する問題ばかりではありませんが、アテもなく悩んでいる状態からモデルに当てはまるとしたら何をすればいいか考えている状態に移行できるというのは重要なことだと考えています。

答えが得られにくい問題に対しても相談がしやすくなった

他マネージャーへの相談については、答えを持っている経験豊富なマネージャーに相談という形から、仮に答えは持ってなかったとしても「このモデルに当てはめたらなにかアイデアが出るんじゃない?」といった発想の源に気づかせてくれるマネージャーに相談という形にシフトできるようになりました。

このシフトは答えを提示する形ではなく本人が答えを導き出すコーチング型の環境作りにも繋がりますし、マネージャーが「どうせ相談しても解決しないしな・・」と一人で抱えこんでしまうことを防止する効果もあります。

異なるバックグラウンドでのマネージメントの価値観の違いについて理解を深める事ができた。

勉強会の場は会話でもなく議論でもなく、特定のトピックに対してお互いの経験・価値観を開示していく対話の場になっていました。

その結果、マネージャー同士での相互理解が深まり、通常は孤立しがちなマネージャーがマネージャーチームとしてまとまっていったように感じました。 当初は想定していなかった効果でしたが、いわゆる会話・対話・議論のうち、対話の要素をもった会にできたことが大きいと考えています。

参考

組織施策を機動的にチームに伝えるブリッジ役を果たしやすくなった

組織課題の認識も共通言語があれば伝わりやすく、用語ごとの齟齬も生まれにくくなります。 例えば「この組織にはアンラーニングが必要」といった場合に”アンラーニング”が意味している範囲・イメージのすり合わせできていないと、その先の施策の話はできません。

会社単位での施策を実施する際、いちいち「アンラーニングとはこういうことで」とバックグラウンドになる知識・理論を0から説明していくのはなかなか骨が折れる作業です。 一方でそこの土壌づくりをスキップすると、「良く分からない」「納得していない」施策となり、施策の形骸化に繋がっていきます。

普段から共通言語を作って組織を耕していくことで初めて具体的な施策という種蒔きが可能になるわけですが、そこの土壌づくりの一部を行えたかなと感じてます。 特に会社単位での施策を浸透させる際に一番のキーになるのは現場マネージャーであり、現場マネージャーに共通言語があることで「こう言えばマネージャーみんなに通じる」というモデルや理論をいくつも蓄える取り組みは組織を変えていくための力に繋がると考えています。

終わりに

エンジニアのためのマネジメント入門 はマネージメント技術について幅広いトピックを扱っており内容もコンパクトなので自分で読むのにもおすすめですが、今回のように話しながら理解を深めていくようなユースケースにもぴったりでした。

今回はピープルマネジメントについてを主に取り上げましたが、実際にはプロジェクト進行だったりプロダクトの企画だったりマネージする対象は多数ありますので、そういったところにも手を伸ばしつつ、FOLIOでマネージャーをやっているとノウハウが自然と身について自身もスキルアップしていける環境を作っていければと思います。

FOLIO Scramble! #4 這い上がりベンチャーの組織改善 に登壇しました

FOLIOの自社イベントで登壇しました。

folio.connpass.com

speakerdeck.com

内容的には以前発表した Inside Fintech Meetup ~ Finatext × Kyash × FOLIO ~で発表しました - だいたいよくわからないブログ の続きとなっています。

前回は初期開発フェーズにおいてドメイン知識ってどうやって獲得していくんだっけ?という話をしましたが、 今回は初期開発を追え運用フェーズに入ったシステムのドメイン知識ってどうやって移転したり、獲得してもらうんだっけ?という話をしました。

懇親会では「ドキュメントを書いても読んでもらうところがまた難しい」という感想もいただき、まさにそこまでやり切るのが難しく、大事なところだよなと改めて感じました。

当面は新しく入った人に対する長期オンボーディングという形で文化が維持できそうですが、オンボーディングを超えた部分で積極的に知識を得ていくインセンティブ構造を設計・実践していくのが今後の課題になりそうです。

登壇者紹介の写真、なんでもいいですよーと適当に答えていたら8年前の写真になってしまいました。

ScalaのHashMapに関する論文(Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections)輪読会 in FOLIO メモその3 CHAMP編

本記事について

FOLIOでやった輪読会のメモです。

Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections で提案されている Scalaの immutable.HashMap に使われているCHAMPについてまとめます。

目次

CHAMPとは

  • HAMTの進化系。
  • Scalaのimmutable.HashMapに採用されている
  • データレイアウトが変わって効率が良くなったりJVMに優しくなったりしている。削除時のパフォーマンスもアップした。

工夫1: データレイアウト変えた

bitmapをnodemap, datamapに分けた (int32のbitmapが2つ)ことで元のマッピングの無駄を解消した。

HAMT CHAMP
論文より
https://www.youtube.com/watch?v=pUXeNAeyY34 18:38より

HAMTでのcontentArrayも圧縮されていて効率的だが、valueが入っている場合と下位nodeへのpointerが入っている場合の具体的な値に着目すると無駄が見えてくる。

  • valueが入っている場合、contentArrayには実際には(key, value)が入っている。
    • ※ contentArrayを2要素利用している
    • ※ nodeを辿っていけばkeyは分かるのでは?と思うかもしれないが、trieでは要素が特定できるところまでしかnodeが作成されないのでnodeを辿っていってもkeyは特定できない。
  • pointerが入っている場合、contentArrayには実際には(null, pointer)が入っている。
    • ※ contentArrayを2要素利用している
    • ※ nullを入れる必要は無いのでは?と思うかもしれないが、bitmapを使った配列の圧縮を行うためには利用するslot数が揃っている必要があるのでnullを入れる必要がある。

上記のようにcontentが下位nodeへのpointerになっている時、key要素が必ずnullになってvalueにpointerが入っている構成だった。nullの分が無駄になりメモリフットプリントがよろしく無い。

CHAMPではcontentArrayの構成を [key, value, key, value, ….., pointer, pointer, pointer]のように後半にpointerを集めるようにし、bitmapをnodemap(下位nodeへのポインタが入っている要素一覧)とdatamap(key,valueが入っている要素一覧)に分けている。

上記の構成により以下のメリットを得ている。

  • 配列中のnullがなくなる
  • メモリフットプリント削減
  • valueかpointerかを見分けるためのinstanceOfも要らなくなる
  • pointerを読み飛ばす必要がないので処理量削減 & 局所参照性向上が見込める
    • valueのiterationや等号比較が早くなる
    • O(下位nodeへの参照 + item) => O(item) になった。

なおC/C++の実装では空slotをunion typesなどを使って有効活用しているらしい(詳細は不明)

工夫2: 正準形を定義し、delete時にも正準系が維持されるようにした。

HAMTでは要素がdeleteされると形が最適ではなくなってしまう問題があった。

そこで不変量を定義し、各部分木が不変量をkeepするように操作することでdelete時も最適な形に出来るようにした。

これによりdeleteを重ねた木に対してもlookupの速度などが向上し、メモリ消費量も削減された。

Canolical Formについて

不変量を考えていき、その不変量が維持されることをもってcanonical formとよぶ。

HAMTでもinsertについては不変量が維持されるが, deleteすると維持されなくなる。

例えば下図で ”C” を消してもHAMTとしてvalidだが、中間のnodeは無駄になってしまう。

論文 Figure1より

本来はこのようになっていてほしい。

論文 Figure1より

具体的なdeleteアルゴリズムについては論文を読んでもらうとして不変量について解説する。

不変量で使う値

  • Arity (local):
    • 外向きのエッジの数
    • CHAMPでは以下の2つがある
      • 下位nodeへのarity
      • payloadへのarity
    • 合計すればarityになる。それぞれはnodemap, datamapの1が立っているbit数を数えれば計算出来る
  • Branch Size (non-local)
    • ブランチサイズはノードから推移的に到達可能な要素の数
    • 実際にノードを辿らないと計算できない(non-localな値)ので近似値の計算が後で紹介されるらしい

CHAMP 不変量

branchSize ≥ 2 * nodeArity + payloadArity

  • 全ての部分木がこの条件を満たすようにする
  • この不変量はarityが2未満の部分木を許可しないということを述べている
  • 1要素しか持たないnodeはinline化される。
  • 下位nodeへのpointerしかもたないnodeは破棄される

不変量の例

論文Figure1より

(a)

  • 1層目
    • nodeArity = 0
    • payloadAirty = 2
    • branchSize = 2 # A, B
    • 2 >= 2 * 0 + 2 # OK

(b)

  • 3層目
    • (a)と同じ構成なのでOK
  • 2層目
    • nodeArity = 1
    • payloadAirty = 0
    • branchSize = 2 # B, C
    • 2 >= 2 * 1 + 0 # OK
  • 1層目
    • nodeArity = 1
    • payloadAirty = 1
    • branchSize = 3 # A,B,C
    • 3 >= 2 * 1 + 1 # OK

(b) からCを単純に消した違法CHAMP

  • 3層目
    • nodeArity = 0
    • payloadAirty = 1
    • branchSize = 1 # B
    • 1 >= 2 * 0 + 1 # OK (第3階層だけを考えるとvalidなnodeになっているのでこれでよい)
  • 2層目
    • nodeArity = 1
    • payloadAirty = 0
    • branchSize = 1 # B
    • 1 >= 2 * 1 + 0 # NG
  • 1層目
    • ※ 下位部分木が不変量を満たしてない = 前提条件がおかしいのでそもそも考えなくて良い
    • nodeArity = 1
    • payloadAirty = 1
    • branchSize = 2 # A, B
    • 2 >= 2 * 1 + 1 # NG

(c)

  • 3層目
    • (a)と同じ構成なのでOK
  • 2層目
    • nodeArity = 1
    • payloadAirty = 1
    • branchSize = 3 # D, B, C
    • 3 >= 2 * 1 + 1 # OK
  • 1層目
  • nodeArity = 1
  • payloadAirty = 1
  • branchSize = 4 # A, D, B,C
  • 4 >= 2 * 1 + 1 # OK

ScalaのHashMapに関する論文(Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections)輪読会 in FOLIO メモその2 JVM CompressedOOPs編

本記事について

FOLIOでやった輪読会のメモです。

本論には関係ないが Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections の以下の記載について深掘りする。

Due to the JVM’s 8-byte memory alignment, adding the hash code field to CHAMP does not increase its memory footprint.(5)

(脚注)5. This is valid for JVM instances with less than 32GB heaps with the CompressedOops option enabled (default)

目次

OOP とは

※ 本記事でJVMといった場合、HotSpot VMのことを指します。

JVMではObjectのインスタンスを作成しヒープに保存する際にメモリを割り当てる。この領域への参照やそれらに関する情報のことを OOP(Ordinary Object Pointer) と呼ぶ 。(参照先にはインスタンスのプロパティの値とかが入ってるイメージ。)

Java HotSpotの専門用語である「OOP」(Ordinary Object Pointer)は、オブジェクトへの管理ポインタです。

Java HotSpot™仮想マシンのパフォーマンスの向上

OOPはネイティブマシンポインタと同じサイズ(LP64システムなら64bit)になる。なおLP64 = long, pointerが64bit (intは32bit), ILP32 = int, long, pointer が32bitである。(see データ型モデル ‐ 通信用語の基礎知識

OOPについての解説は本記事ではこれ以上解説しないので詳しく知りたい人は Ordinary Object Pointer in JVM - Speaker Deck を見ると良い。

CompressedOops とは

ILP32システムでは最大ヒープサイズが4Gバイト弱(2^32バイト弱)になるが、多くのアプリケーションでこれは少なすぎる。 LP64システムなら大きなヒープを扱えるがポインタ型が大きくなるので、ILP32システムで実行する場合よりも約1.5倍程度大きくなることがある。この問題を改善したい。

※ 改善のモチベーションはメモリよりは主にキャッシュとかメモリ帯域幅などの都合が大きい。

モリーのコストは低いですが、最近では帯域幅およびキャッシュが不足しているため、4Gバイト制限を解決するためだけにヒープ・サイズが大幅に増加するのは望ましくありません。

Java HotSpot™仮想マシンのパフォーマンスの向上

ということで、OOP(ordinary object pointer)を圧縮することで上記のメモリオーバーヘッドを解消するための仕組みがCompressedOopsである。

圧縮方法

図解が HotSpot under the Hood にあるのでそちらも参照。

圧縮OOPを使った表現ではOOPは 32bitオブジェクトオフセット + base として表現される。

  • OOP = (圧縮oop * 8) + base
    • つまりOOP = (圧縮oop << 3) + base
  • JVMでのデフォルトでのオブジェクトのバイトアドレス境界は8byteなので8倍されている。
    • 余談: バイトアドレス境界は-XX:ObjectAlignmentInBytesで増やすことも出来る。 (java)
  • バイトオフセットではなくオブジェクトオフセットなのがポイント。これにより最大約32GBのヒープ・サイズをアドレス指定するために使用できる。
    • IL32相当の4G分の空間の場合、4Gオブジェクトオフセットまで表現できるので4G*8 = 32GBまでヒープアドレスを表現できることになる。

32GB以上のヒープを表現するためにはbaseアドレスの加算が必要。逆に言うと32GB未満ならbaseは不要で実際にbase=0とされて計算が省略されるようになっている。

  • 前述の-XX:ObjectAlignmentInBytes オプションの説明に、以下のような記載があるのでオブジェクトアラインメントをいじればbaseを使わずとも32GBよりも大きなヒープサイズを圧縮OOPで実現できそう。
    • このオプションにより、大きいJavaヒープ・サイズで圧縮ポインタを使用できます。
    • (java)
    • ただし、様々な最適化されているライブラリがalignment=8byteを期待している気がするので気軽にいじって早くなるのかは不明

ScalaのHashMapに関する論文(Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections)輪読会 in FOLIO メモその1 HAMT編

本記事について

FOLIOでやった輪読会のメモです。

表題の論文は Scalaの immutable.HashMap に使われているCHAMPについての提案ですがベースとなるHAMTについて理解があったほうが読みやすいのでHAMTについて解説します。

※ Trie木については本記事では解説しないので必要に応じて別のサイトなどを参照してください。

以下の解説は Introduction to HAMT — Idea of the day に自分なりのメモを加えたものです。図を見てもらったほうがわかりやすいと思います。

目次

Hash値をTrieに格納する

8bitのbit列 00000000, 11111110, 11111111 をHash値だと思うことにする。

これを2bit区切りのTrie木に入れると以下のようになる。(※ ここでは例のために先頭2bitくぎりにしてるけど好きなbit数で区切ってよい)

  • 第1階層(1~2bit目担当): {00 => value: 00000000, 11 => 次階層へのpointer}
  • 第2階層(3~4bit目担当): {11 => 次階層へのpointer}
  • 第3階層(5~6bit目担当): {11 => 次階層へのpointer}
  • 第4階層(7~8bit目担当): {10 => value: 11111110, 11 => value: 11111111}

naiveなデータの持ち方

上記で概念的なTrieの構造について考えたので、具体的なデータの持ち方について考えてみる。まずは配列を使ったnaiveなアイデアを考える。

素数が2bitの場合とりうる値は4通り(00, 01, 10, 11) になるので、データを持つとしたらtrie木内のそれぞれの階層について以下のようなlength=4なarrayを持てば良い。

[00用slot, 01用slot, 10用slot, 11用slot]

最初のHash値の例でいうと以下のようになる。

  • 第1階層(左から1~2bit目担当): [value: 00000000, null, null, 次階層へのpointer]
  • 第2階層(左から3~4bit目担当): [null, null, null, 次階層へのpointer]
  • 第3階層(左から5~6bit目担当): [null, null, null, 次階層へのpointer]
  • 第4階層(左から7~8bit目担当): [null, null, value: 11111110, value: 11111111]

ただこの表現の場合は配列がnullだらけになる(sparseなarrayになる)のでメモリフットプリントが無駄に大きくなってしまう。

bitmap

HAMTではこれをbitmapで改善する。先程の第1階層を例に挙げる。

第1階層(1~2bit目担当): [value: 00000000, null, null, 次階層へのpointer]

このとき配列の非ヌル要素を1、ヌル要素を0で表現することにすると、第一階層は 1001 という4bitのbitmapで表現できる。それぞれ以下のようになる。

  • 左から1bit目 = hash値の1~2bit目が00のslotに対応
  • 左から2bit目 = hash値の1~2bit目が01のslotに対応
  • 左から3bit目 = hash値の1~2bit目が10のslotに対応
  • 左から4bit目 = hash値の1~2bit目が11のslotに対応

00, 01, 10, 11は10進法なら0,1,2,3なのだから普通にbitmap[0]とかbitmap[2]とかでアクセスすればslotに対応するbitmap中のbitにすぐアクセスすることができる。

このbitmapを使うとあるslotがnullか非nullかを判定することができる。第一階層1001を例にすると、

  • 判定したいslotが10用であった場合は bitmap[2]を見ると値が存在しているかが分かる
    • bitmap=1001 のとき bitmap[2] は 0 => 対応する要素はnull
  • 判定したいslotが00用であった場合は bitmap[0]を見ると値が存在しているかが分かる
    • bitmap=1001のとき bitmap[0] は 1 => 対応する要素は非null(valueかpointerが入っている)

bitmapは4つの枝の中からvalid branchをマークしているといえる。(see Bitwise trie with bitmap

bitmap to mark every valid branch

配列の圧縮

前述のbitmapだけでは配列の対応する要素がnullか非nullかという確認しかできないので先程まで使っていた値を持つ配列は以前として必要である。

ここで、メモリフットプリントを改善するために先程まで使っていたlength=4なarrayを圧縮することにする。

nullだらけのarrayを持つのではなく非ヌル要素のみを持った配列(圧縮された配列)を持つことでメモリフットプリントを改善することを考える。

圧縮前: [value: 00000000, null, null, 次階層へのpointer]
圧縮後: [value: 00000000, 次階層へのpointer]

さきほどのmask = bitmapがあれば、以下で述べる手順で値を取得することができる。

データの取得方法

キーに対応する値の取得を行うためには、圧縮された配列の各要素と圧縮前の配列の各要素を対応付ける必要がある。

これはhash値の先頭2bitに対応するbitmapのslotを確認し、それより左側に何個1が立ってるのかをカウントすることで知ることが出来る。 つまり 圧縮前の配列[i] = 圧縮後の配列[bitmap[i]より左にある1の数] となる。

例えばbitmapが 1001の場合を考えると以下のようになる。

  • hash値の1~2bit目が 00 => bitmap[0]が対応する。bitmap[0]より左にある1の数をカウントすると0個なので配列[0]に値が入っている => value = “00000000”を取得できる
  • hash値の1~2bit目が 11 => bitmap[3]が対応する。bitmap[3]より左にある1の数をカウントすると1個なので配列[1]に値が入っている => pointerを取得できる

余談1: popcnt について

上記で利用した1をカウントする操作のことをpopulation count(pop count)という。 この操作は専用のCPU命令が実装されていたりするので高速に動作する(らしい)。

  • Hash array mapped trie - Wikipedia
    • > This operation is available in many instruction set architectures (中略). Although population count can be implemented in software in O(1) time using a series of shift and add instructions, doing so may perform the operation an order of magnitude slower.`
  • Hamming weight - Wikipedia
    • > Intel Core processors introduced a POPCNT instruction with the SSE4.2 instruction set extension
    • > The ARM architecture introduced the VCNT instruction as part of the Advanced SIMD (NEON) extensions.
  • Integer (Java Platform SE 8)
    • Javaでは Integer.bitCount() で利用可能
  • Bitwise trie with bitmap - Wikipedia
    • > CTPOP (count population) operation that determines the number of set bits, which is available as Long.bitCount() in Java.

さらに余談だがNTT Comが開発したソフトウェアルーターの実装でPoptrieというデータ構造が使われている。論文タイトルを見るとこれもPopulation Countと入っているのでpopcntベースのTrieという意味では似ているところがあるかもしれない。(未読)

HAMTの構造

最終的にHAMTの各階層は以下で構成される。

  • N bitのbitmap
  • 各階層の非ヌル値のみを要素とする配列 (value か pointerのどちらかが入っている)
class Node {
  int bitmap; // 4byte = 32bit
  Object[] contents; // value or pointerが入る
}

以上により、trie木でHashMapを作成することができる。

HAMTの計算量

値を持つ配列を圧縮することでメモリフットプリントが向上しただけでなく値のtraversalもnullだらけの配列を走査するより早くなるといったことも特徴として挙げられる。

上記の解説ではhash値の2bitごとにtrie木の階層を作成していたが、論文や実際の実装では5bit区切りにすることがおおい。

bitmapのサイズは 2hash値の区切りbit数なので

  • 2桁区切りの場合は 22で4bitのbitmap (00, 01, 10, 11)
  • 5桁区切りの場合は 25で32bitのbitmap (00000, 00001, 00010, 00011, 00100, ….)

となる。5桁区切りにするのは単にint32で格納できるので都合がよいからのようだ。

2bit区切りの場合はtrieは2分木になっていたが、5bit区切りの場合はtrieは32分木になる。

計算量は(32bit bitmapの場合)最大で hash値の桁数/5回だけpointerをたどればよい。 全体としてはeffectively O(1) くらい。正確にはO(log_32(N))。

注意点

本記事の例ではbitmapや値を持つarrayは階層ごとに一つずつのように見えていたが実際には木のnodeの分だけ必要になる。

  • 第一階層が 00だったときの第二階層 10 に値がはいっているか? (つまりhash値 = 0010...に値があるか)
  • 第一階層が 10だったときの第二階層 10 に値がはいっているか? (つまりhash値 = 1010...に値があるか)

はもちろん結果が異なるので第二階層用のbitmapや値を持つ配列もnodeの数だけ必要になる。(例だと子要素のnodeが必ず一つだったので木の深さとたまたま一致していた。)

https://www.youtube.com/watch?v=pUXeNAeyY34 6:59より

node数の分となると子要素・孫要素と進むたびに分岐が発生してものすごい数のbitmapが必要になるように思えるが、そもそも存在しないpathについてはbitmapを保持する必要がないので実際に必要になる数は限られる。

その他

hash値の衝突の場合はLinkedListでもいいしRedBlackTreeぶらさげてもいいし別のhash関数使ってもう一つHAMTをぶらさげてもいいらしい。

参考文献