2021/01/10 19:21
mukaken
“実装時期が近い点についてはOS・CPUの64bit化が関係しているかも...2010年頃から64bit環境が一般的になって64bitポインタが性能面の足かせになるような状況が個別に表面化し、結果として同時期に改善”
2021/01/10 21:09
zu2
“古いプログラマ（私を含む）の常識として、連想配列は原則として格納順を保持しないというのがあると思います” 俺だ
2021/01/10 21:17
reihighjcj6a
Perlくんが気になる・・・？
2021/01/10 22:19
tohokuaiki
シンクロニシティ？
2021/01/10 22:23
mojimojikun
( ･∀･)つ〃∩ ﾍｪｰﾍｪｰﾍｪｰ
2021/01/10 23:02
yoiIT
“Python 3.7からは連想配列の要素の順序保持が仕様になっています。”
2021/01/10 23:06
programmablekinoko
興味深い
2021/01/10 23:13
topiyama
アルゴリズムは世に連れ（実装動作する環境が変われば、各リソースのコストパフォーマンス比率が変われば、変えたほうが良い）だなあ
2021/01/10 23:32
hiroomi
“突解決の方針が異なっているだけで、2段構えの前段の配列で添字を管理する点、後段の配列は格納順に要素を追加していく点などは完全に同”
2021/01/11 00:00
rti7743
面白い。64bitポインタのでかさが無駄になっているのかな。
2021/01/11 00:02
at_yasu
字が滑る。明日読む。
2021/01/11 00:23
masudatarou
PHPの連想配列とかでもJavaのHashMapでも実際は格納順維持されてるよね
2021/01/11 00:55
hamamuratakuo
キャッシュヒット率を高めた方が有利という話　メモリのシーケンシャルアクセスは有利という話　Rubyがチェイン法からオープンアドレス法に乗り換えているので、実はそちらの方が有望ということなのかもしれません。
2021/01/11 01:04
Dragoonriders
まあ、そらそうだろ。メモリアクセス自体遅いから、汎用的な実装でポインタ手繰っていくよりは、シーケンシャルに置いておいて、キャッシュに乗ったところを読んだ方が断然速い。メモリアクセス自体をすっ飛ばせる。
2021/01/11 01:42
sasasin_net
なんか気になっても調べる馬力ない話だ。スゲェー
2021/01/11 03:20
skypenguins
いかにキャッシュヒット率を上げるかと言う話
2021/01/11 05:55
Wafer
図が何を表しているかさっぱり読み取れない
2021/01/11 05:59
circled
どっかの島の猿も大体同じ時期に、お互いが離れた群れなのに、芋を洗って食うと美味いという性能改善してたぞ？
2021/01/11 07:09
m0t0m0t0
連想配列の順序が決まっているのありがたい
2021/01/11 08:07
tinsep19
よく気付くなぁ。
2021/01/11 09:09
frontline
今の会社、こういう話で驚きを共有したり議論したり出来る人を増やしたかった（過去形）。
2021/01/11 09:16
iga_k
知見やー。連想配列の順序保持がパフォーマンスにも効いてるかも仮説は面白い
2021/01/11 09:20
cavorite
ひとむかしまえに、メモリ-ストレージ間でよくやってたやつ
2021/01/11 09:42
yarumato
“3言語の連想配列の従来実装と新実装の概要、新実装が速くなるカラクリについて解説。現代のCPUから見るとメモリは非常に遅い。キャッシュヒット率を高めた方が有利 。メモリのシーケンシャルアクセスは有利”
2021/01/11 10:09
otori334
“メモリの読み書きに関連する改善が支配的だったのではないか？”
2021/01/11 10:48
sgo2
今時の環境はメモリはページの割り当て(仮想メモリ)→要求されたサイズに切り分け(ヒープ)の2段構えで管理されるのが普通だけど、ヒープは汎用的であるが故に均一かつ大量の確保を行うには無駄が多い事の方が重要では
2021/01/11 11:01
diveintounlimit
話としては面白いんだが図もうちょい何とかならんかったのか
2021/01/11 11:29
hdampty7
言う程CPUキャッシュ容量って多くないイメージあるけど。うまいことキャッシュにのるようにしてるってことかな。
2021/01/11 13:42
nekonyantaro
自然界でいう収斂進化みたいなものでしょうか。真似したというわけでもなく、必然的に最適な場所に落ち着いていくという。
2021/01/11 13:57
rryu
8バイトのメモリアクセスより64ビットの算術演算の方が速いのでインデックスを保持した方がいいと言う結論にみんななっているのがおもしろい。
2021/01/11 14:47
lizy
アルゴリズムとデータ構造も、参照の局所性という視点が必要になってくるのか
2021/01/11 14:52
nilab
「PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました」
2021/01/11 15:32
kazuhooku
pythonのが速度改善を目的にした実装（そして実際に速くなっている）という想定は正しいんだろうか。実際に書いた @methane さんが知ってそう
2021/01/11 18:04
sugawara1991
64bit化もあってリスト構造を教科書通りポインタで実装するとキャッシュヒットで不利という話かな。STL脳死で使うと遅いとなったりするのは嫌だが実装依存か規格準遵守で限界があるものか。最早C#使えってことか
2021/01/11 22:01
yosuke_furukawa
おもろ。開番地法にせよ、リンクリストにせよ、衝突した時の値のアドレスを管理するもの用意しておくだけでCPU cache hit率が上がって早くなる、と。
2021/01/11 23:44
asakura-t
perlは5.26（2017.05）で64bit環境向けに変更していたらしい＞perldoc.jp ／ハッシュの順番は5.18の時に積極的にランダム化されてた＞perldoc.jp