* [ruby-dev:51046] [Ruby master Bug#17779] 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる
@ 2021-04-06 17:53 tomoyapenguin
2021-04-15 0:55 ` [ruby-dev:51053] " nagachika00
0 siblings, 1 reply; 2+ messages in thread
From: tomoyapenguin @ 2021-04-06 17:53 UTC (permalink / raw)
To: ruby-dev
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/
^ permalink raw reply [flat|nested] 2+ messages in thread
* [ruby-dev:51053] [Ruby master Bug#17779] 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる
2021-04-06 17:53 [ruby-dev:51046] [Ruby master Bug#17779] 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる tomoyapenguin
@ 2021-04-15 0:55 ` nagachika00
0 siblings, 0 replies; 2+ messages in thread
From: nagachika00 @ 2021-04-15 0:55 UTC (permalink / raw)
To: ruby-dev
Issue #17779 has been updated by nagachika (Tomoyuki Chikanaga).
Backport changed from 2.6: REQUIRED, 2.7: REQUIRED, 3.0: REQUIRED to 2.6: REQUIRED, 2.7: REQUIRED, 3.0: DONTNEED
I think this is a performance thing.
If there are any real world application affected by this issue, please let me know.
----------------------------------------
Bug #17779: 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる
https://bugs.ruby-lang.org/issues/17779#change-91547
* Author: tompng (tomoya ishida)
* Status: Closed
* Priority: Normal
* ruby -v: ruby 3.1.0dev (2021-04-06T03:02:46Z :detached: ff91b97c83) [x86_64-linux]
* Backport: 2.6: REQUIRED, 2.7: REQUIRED, 3.0: DONTNEED
----------------------------------------
再現コード
~~~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は結果が安定しない(逆転することが多かったり)
~~~
---Files--------------------------------
st.patch (730 Bytes)
--
https://bugs.ruby-lang.org/
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2021-04-15 0:55 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-04-06 17:53 [ruby-dev:51046] [Ruby master Bug#17779] 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる tomoyapenguin
2021-04-15 0:55 ` [ruby-dev:51053] " nagachika00
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).