PHPとPythonとRubyの連想配列のデータ構造が同時期に同じ方針で性能改善されてた話 - hnwの日記

PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました。具体的には以下のバージョンで実装の大変更がありました。 PHP 7.0.0 HashTable高速化 (2015/11) Python 3.6.0 dictobject高速化 (2016/12) Ruby 2.4.0 st_table高速化 (2016/12) これらのデータ構造はユーザーの利用する連想配列だけでなく言語のコアでも利用されているので、言語全体の性能改善に貢献しています1。 スクリプト言語3つが同時期に同じデータ構造の改善に取り組んだだけでも面白い現象ですが、さらに面白いことに各実装の方針は非常に似ています。独立に改善に取り組んだのに同じ結論に至ったとすれば興味深い偶然と言えるでしょう2。 本稿では3言語の連想配列の従来実

[zu2]

“古いプログラマ（私を含む）の常識として、連想配列は原則として格納順を保持しないというのがあると思います” 俺だ

[mukaken]

“実装時期が近い点についてはOS・CPUの64bit化が関係しているかも...2010年頃から64bit環境が一般的になって64bitポインタが性能面の足かせになるような状況が個別に表面化し、結果として同時期に改善”

[reihighjcj6a]

Perlくんが気になる・・・？

[frontline]

今の会社、こういう話で驚きを共有したり議論したり出来る人を増やしたかった（過去形）。

[asakura-t]

perlは5.26（2017.05）で64bit環境向けに変更していたらしい＞https://perldoc.jp/docs/perl/5.26.0/perl5260delta.pod ／ハッシュの順番は5.18の時に積極的にランダム化されてた＞https://perldoc.jp/docs/perl/5.18.0/perl5180delta.pod

[rryu]

8バイトのメモリアクセスより64ビットの算術演算の方が速いのでインデックスを保持した方がいいと言う結論にみんななっているのがおもしろい。

[Dragoonriders]

まあ、そらそうだろ。メモリアクセス自体遅いから、汎用的な実装でポインタ手繰っていくよりは、シーケンシャルに置いておいて、キャッシュに乗ったところを読んだ方が断然速い。メモリアクセス自体をすっ飛ばせる。

[iga_k]

知見やー。連想配列の順序保持がパフォーマンスにも効いてるかも仮説は面白い

[m0t0m0t0]

連想配列の順序が決まっているのありがたい

[minamishinji]

アルゴリズムも環境によって善し悪しが変わる。当たり前なんだけど、忘れがち。学び続けることが必要だね。

[NAT]

キャッシュヒット率を高めた方が有利という話。1バイトアクセスしたら周囲の64バイトのアクセスもタダみたいなもんです。「推測するな、計測せよ」

[YassLab]

“3言語とも各言語を使ったベンチマークテストを実施した上で新実装を採用したわけで、これが別の言語・別のアプリケーションでも最適なデータ構造とは限りません。大事なのは「推測するな、計測せよ」ですよね”

[yosuke_furukawa]

おもろ。開番地法にせよ、リンクリストにせよ、衝突した時の値のアドレスを管理するもの用意しておくだけでCPU cache hit率が上がって早くなる、と。

[sugawara1991]

64bit化もあってリスト構造を教科書通りポインタで実装するとキャッシュヒットで不利という話かな。STL脳死で使うと遅いとなったりするのは嫌だが実装依存か規格準遵守で限界があるものか。最早C#使えってことか

[kazuhooku]

pythonのが速度改善を目的にした実装（そして実際に速くなっている）という想定は正しいんだろうか。実際に書いた @methane さんが知ってそう

[nilab]

「PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました」

[lizy]

アルゴリズムとデータ構造も、参照の局所性という視点が必要になってくるのか

[nekonyantaro]

自然界でいう収斂進化みたいなものでしょうか。真似したというわけでもなく、必然的に最適な場所に落ち着いていくという。

[hdampty7]

言う程CPUキャッシュ容量って多くないイメージあるけど。うまいことキャッシュにのるようにしてるってことかな。

[diveintounlimit]

話としては面白いんだが図もうちょい何とかならんかったのか

[sgo2]

今時の環境はメモリはページの割り当て(仮想メモリ)→要求されたサイズに切り分け(ヒープ)の2段構えで管理されるのが普通だけど、ヒープは汎用的であるが故に均一かつ大量の確保を行うには無駄が多い事の方が重要では

[otori334]

“メモリの読み書きに関連する改善が支配的だったのではないか？”

[yarumato]

“3言語の連想配列の従来実装と新実装の概要、新実装が速くなるカラクリについて解説。現代のCPUから見るとメモリは非常に遅い。キャッシュヒット率を高めた方が有利 。メモリのシーケンシャルアクセスは有利”

[cavorite]

ひとむかしまえに、メモリ-ストレージ間でよくやってたやつ

[tinsep19]

よく気付くなぁ。

[circled]

どっかの島の猿も大体同じ時期に、お互いが離れた群れなのに、芋を洗って食うと美味いという性能改善してたぞ？

[Wafer]

図が何を表しているかさっぱり読み取れない

[skypenguins]

いかにキャッシュヒット率を上げるかと言う話

[sasasin_net]

なんか気になっても調べる馬力ない話だ。スゲェー

[hamamuratakuo]

キャッシュヒット率を高めた方が有利という話　メモリのシーケンシャルアクセスは有利という話　Rubyがチェイン法からオープンアドレス法に乗り換えているので、実はそちらの方が有望ということなのかもしれません。

[at_yasu]

字が滑る。明日読む。

[rti7743]

面白い。64bitポインタのでかさが無駄になっているのかな。

[hiroomi]

“突解決の方針が異なっているだけで、2段構えの前段の配列で添字を管理する点、後段の配列は格納順に要素を追加していく点などは完全に同”