< :前の番号
^ :番号順リスト
> :次の番号
P :前の記事（スレッド移動）
N :次の記事（スレッド移動）
|<:前のスレッド
>|:次のスレッド
^ :返事先
_:自分への返事
>:同じ返事先を持つ記事（前）
<:同じ返事先を持つ記事（後）
---:分割してスレッド表示、再表示
| :分割して（縦）スレッド表示、再表示
~ :スレッドのフレーム消去
.:インデックス
..:インデックスのインデックス
Issue #17779 has been reported by tompng (tomoya ishida).
----------------------------------------
Bug #17779: 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる
https://bugs.ruby-lang.org/issues/17779
* Author: tompng (tomoya ishida)
* Status: Open
* Priority: Normal
* ruby -v: ruby 3.1.0dev (2021-04-06T03:02:46Z :detached: ff91b97c83) [x86_64-linux]
* Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN, 3.0: UNKNOWN
----------------------------------------
再現コード
~~~ruby
require'benchmark'
hash = 1000000.times.to_h { [rand, true]}
p Benchmark.realtime { 100000.times { hash.first } }
#=> 0.03949428700025237
hash.keys[1..100000].each { hash.delete _1 }
hash.delete hash.keys.first
p Benchmark.realtime { 100000.times { hash.first } }
#=> 12.849613588000011
~~~
原因と思われる部分
entriesのentries_start+1番目がdeletedな状態でentries_start番目を削除すると、それ以降entries_startが更新されなくなる
その結果、entriesの先頭からdeletedな要素が連続して続く状態が作られるようになり、その状態ではdeletedではない最初の要素を探すのにコストがかかるようになる
patchを添付しました
patch内容について気になる点
- st_tableのdeleteが少し遅くなるとruby全体の速度に影響するのかどうか
- とはいえ、元の `tab->entries_start = n + 1;` はfirstが高速に動作することを意図したものだと思うなので、このpatchにより意図通りの挙動をするようになるはず
---Files--------------------------------
st.patch (730 Bytes)
--
https://bugs.ruby-lang.org/