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年くらいしたら全部読み終わるかもしれない₍₍ (ง´･_･`)ว ⁾⁾

AIで自動文字起こしして発音採点までしてくれる英語学習用サービス Elsa Speech Analyzer がすごい

使ってて感動したので Elsa Speech Analyzer を紹介します。

speechanalyzer.elsaspeak.com

サービス概要

自分が喋った英語を分析して発音やイントネーション、語彙力や文法などを採点してくれるサービスです。 Recordingをスタートして英語を話すと以下のようにIELTSやTOEFLの参考スコアが表示されたり

発音その他もろもろのスコアを表示してくれます。

※ 画像のスコアは 残念ながら 筆者の本来の実力を表したものではありません

Elsa Speak とは違う

混同しがちなので先に記載しておくと発音矯正アプリのElsa SpeakとElsa Speech Analyzerは別のサービスになります。 Elsaといえば発音矯正アプリですが機能が異なるのでElsa Speakは合わなかった人もElsa Speech Analyzerなら合うかもしれません。

発音の指摘

発音であれば各単語ごとにどこが間違ってるか？を教えてくれます。（しかも自分の単語発音とお手本の単語発音を聴き比べることもできる）

イントネーションであれば誤って強調されている単語や強調したほうがよい単語などもわかりやすく表示してくれます。

発話速度

一分間にどのくらい喋っているか？の指標であるwpm(word per minutes) も表示してくれるので、ちょうどよい速度で話せているかも確認が可能です。

使い方

IELTS風やjob interview風のシチュエーションが提示されて、それ通りに喋るというのがelsa speech analyzerが用意している標準の使い方です。

これ自体もとてもよいのですが、シャドーイングに使うのも効果的だと感じました。TEDのスクリプトを読み上げて間違ってる発音をバシバシ指摘してもらうと自分では出来たつもりのところが出来てないということが客観的に分かるのでかなり効率がアップした気がします。（実は上の方でペタペタ貼ってる画像も全部スクリプトを読み上げたものなので本来の実力よりもかなり高いスコア表示になっています。IELTS 8.5欲しいね😭）

今は下記のTEDをシャドーイングに使っていて、かなり効果を感じています。

セシリア・M・オーファン: 「良い大学」とは？その重要性 | TED Talk

あとは下記動画で紹介されてるとおり、テーマを自分で設定して独り言英会話を採点してもらうのもかなり効果的だと思います。

www.youtube.com

自分が使ってる単語をベースに、こういう単語にするとそれっぽいよみたいな言い換えの提案もしてくれますし、

ChatGPTにスピーチ内容をrephraseしてもらえる機能もあるので、かなり改善しやすいのではないかと思います。

使ってみて

誤った発音を指摘してもらう前にそもそも正しく認識されない単語が結構ありました。これは英会話でも別の単語に聞こえてしまっている可能性が高いのでまずはそうならないようにしてから指摘された発音を治すようにしています。（別の単語として正しい発音だと認識されている状態から、発音は間違ってるけどギリギリ正しい単語と認識される状態に変わっていくので発音練習をすると発音スコアが下がるという現象が発生しがち。）

また自分が考えているより遅く喋っていることがわかりました。普通にTEDのスクリプトを読み上げると100wpmくらいだったので130wpmくらいになるように調整した状態で発音がうまくいくように練習しています。

いずれにせよ客観的な指標を元に継続的に改善できる。課金すれば回数無制限で何回でも使える（無料枠は３０分の音声解析ができる）というのでかなり英語学習を効率化してくれるサービスかなと思いました。

コンテナセキュリティ本輪読会 in FOLIO を開催した

コンテナセキュリティという本が出たので社内輪読会を開催しました。

コンテナセキュリティ　コンテナ化されたアプリケーションを保護する要素技術

コンテナのセキュリティ関連の知識は現代のアプリケーションエンジニアとしてはとても大事なものの、なかなか腰が重いという人も多いのではないでしょうか

自分も普段は機能要件に気を配ることが多く、重要性は認識しつつやれていない領域だったので、本の発売を機に手を出してみることにしてみました。

FOLIOではEKSを使っているのでせっかくなら他の人もと思い募集をかけたところ手をあげてくれた人がいて総勢7名での会になりました。4/17 から 6/12 までなので約二ヶ月弱で、それなりのハイペースでしたが途中でダレることもなく無事完走できました。

業務でインフラ周りを担当してる人も参加してくれたのでFOLIOではこうしてるよとか、最新情報はこうだよといった事も教えてもらえ、普段書いてるデプロイ用のyamlも解像度が上がった気がしました。

containerの隔離がどのように実現されているかの解説からcontainer escapeがどのようなリスクを孕んでいるのか？までの流れがとてもきれいだったと思います。linuxのcapabilities周りなども実際のコマンドレベルでは知らなかったのでOSからk8sまで幅広く学べたかなと思います。ページ数が少なめなこともあり一つ一つはもう少し深掘りしないとなとは思いつつ、どういう項目があって何を知らないか？の全体像がつかめる良書だったと思います。

Database Design and Implementation を読んだ

Database Design and Implementation: Second Edition (Data-Centric Systems and Applications) を読んだのでメモ程度の読書感想文です。

これは何

この本はSimpleDBという機能を省略したRDBMSを作っていきながらDBの仕組みについて学んでいく本です。 機能を省略したといいつつ根本的な機能は一通り揃っていて、例えばFileManagerやLog Managerなどのディスクに書き込むところやBufferPoolを管理するBufferManagerもちゃんとあるし、トランザクション管理をしてクラッシュ時にリカバリーする処理などもある。SQLのパースもやるしインデックスも使うしPlannerやOptimizerなども作るのでベースのコンポーネントとして抑えるべきところはしっかり抑えている印象がありました。

詳しい書評は先人達の記事を参照すると良いと思います。

読んだ感想

とりあえず一周じっくり読んだので2週目を実装しながら読み返しています。 https://github.com/matsu-chara/MySimpleDB

単純にRDBMSの内部を知ることが出来たというのもあるし、MySQLの実行計画読むときも今までとは別の直感が得られた気もするので満足度の高い一冊になりました。専門じゃない割にRDBMSの論文をよく読んでい る たのですが、興味範囲が偏りすぎて知らなかったことも結構あったので体系的な知識を身につけられたのも良かったかなと思いました。(特にOptimizer周りの具体的な実装とかほぼ何も知らなかった）

scala 2.13でコンパイルが遅いときにprofileを取る方法

Scalaでコンパイルが遅くなった場合にprofileを取る方法について検索すると Speeding Up Compilation Time with scalac-profiling | The Scala Programming Language という記事がでてきたり、 https://github.com/scalacenter/scalac-profiling を利用した方法がヒットしますが、ここにでてくるpluginはscala 2.13では（そのままでは）使えなかったり、もう少し楽な別の方法があったりするのでまとめました。

出力イメージ

こんな感じのグラフの生成を目指します。（といってもほぼ公式が提供してるツールだけで出来る）

出力方法

1. profile-trace というコンパイラオプションを利用することでprofile情報が出力されたjsonを取得する

以下を指定してビルドすれば出力されます

Compile / compile / scalacOptions ++= Seq("-Yprofile-trace",  name.value + "-main.json"),
Test / compile / scalacOptions ++= Seq("-Yprofile-trace", name.value + "-test.json"),

2. chromeのtrace機能に読み込ませる

Chromeを起動し、 chrome://tracing/ をURL欄に入力して遷移 > Loadボタンから先程のファイルを読み込む ことで上記のツイートのような解析結果が見られます

備考

jdk9以降を使っている場合は問題が出てしまう( 参考 のでjdk8でビルドするか以下のようにscala 2.13.11のsnapshotを利用するかなどの工夫が必要になります。

resolvers += "scala-snapshot" at "https://scala-ci.typesafe.com/artifactory/scala-pr-validation-snapshots/",
ThisBuild / scalaVersion := "2.13.11-bin-7e2671b-SNAPSHOT"

おまけ

謝辞

全面的に https://mobile.twitter.com/xuwei_k さんに助けて頂きました。ありがとうございます🙏🙏🙏🙏🙏🙏🙏🙏