Project

General

Profile

Bug #17779

Updated by tompng (tomoya ishida) over 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により意図通りの挙動をするようになるはず 


 このpatchが不利になりそうなケースのベンチマーク 
 ~~~ruby 
 original_hash = 100000.times.to_h { [rand, true]} 
 keys = original_hash.keys.take(10000) 
 times = 4001.times.map { 
   hash = original_hash.dup 
   t = Time.now 
   # case1 
   keys.each { hash.delete _1 } 
   # case2 
   # keys[1..].each { hash.delete _1 }; hash.delete(keys.first) 
   Time.now - t 
 } 
 p min: times.min, avg: times.sum / times.size, mid: times.sort[times.size/2], max: times.max 

 # case1 先頭を削除するときのオーバーヘッドの測定 
 # master:    {:min=>0.001074, :avg=>0.0016952556860784804, :mid=>0.0016, :max=>0.01718} 
 # patched: {:min=>0.001088, :avg=>0.001468765058735316, :mid=>0.001236, :max=>0.02119} 

 # case2 先頭から2番目以降を削除(このpatchで変わらないはず)した後、最後に先頭を削除しentries_startが一気に更新されるパターン 
 # master: {:min=>0.00108, :avg=>0.0016331899525118718, :mid=>0.001615, :max=>0.007555} 
 # patched: {:min=>0.001087, :avg=>0.0016653474131467132, :mid=>0.001376, :max=>0.041265} 

 # minはこのpatchで1~3%くらい悪化していそう、avg mid maxは結果が安定しない(逆転することが多かったり) 
 ~~~ 

Back