Bug #17779
Updated by tompng (tomoya ishida) about 3 years ago
再現コード
~~~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当てる前と後のベンチマーク
~~~ruby
hash = 1000000.times.to_h { [rand, true]}
t=Time.now
100000.times { hash.first }
p Time.now-t
# => before: 0.047851
# => after: 0.047678
hash.keys[1..100000].each { hash.delete _1 }
hash.delete hash.keys.first
t=Time.now
100000.times { hash.first }
p Time.now-t
# => before: 24.724466
# => after: 0.051886
~~~
patch内容について気になる点
- st_tableのdeleteが少し遅くなるとruby全体の速度に影響するのかどうか
- とはいえ、元の `tab->entries_start = n + 1;` はfirstが高速に動作することを意図したものだと思うなので、このpatchにより意図通りの挙動をするようになるはず