Bug #8312: Fix weird performance of Hash#shift

• Status: Closed
• Assignee: -
• Target version: -
• ruby -v: ruby 2.1.0dev (2013-04-23 trunk 40423) [x86_64-linux]
• Backport: 1.9.3: UNKNOWN, 2.0.0: UNKNOWN

[funny_falcon (Yura Sokolov)]

rb_hash_shift has an optimization for case when #shift is called outside hash iteration.
But in fact it is deoptimization, cause it uses rb_hash_foreach, which initiate safe
iteration, so that deletion is delayed and whole hash traversing is done.

Fix simplifies code by doing same thing in both case: is there outer iteration or not.

Fix and benchmark is here: https://gist.github.com/funny-falcon/5444091

Benchmark results:

before fix:
    user     system      total        real
Hash#shift  2.810000   0.000000   2.810000 (  2.812111)
Hash#custom_shift  0.030000   0.000000   0.030000 (  0.034924)

after fix:
     user     system      total        real
Hash#shift  0.010000   0.000000   0.010000 (  0.019124)
Hash#custom_shift  0.030000   0.000000   0.030000 (  0.033300)

patch is attached to issue as well.

This fix should be backported to 1.9.3 and 2.0.0 as well, cause it highly affects
on Hash's usability as LRU cache.

[funny_falcon (Yura Sokolov)]

• File add_st_shift.diff add_st_shift.diff added

Other way to fix: add st_shift method, which shifts first element in one step.
Patch attached.

[sam.saffron (Sam Saffron)]

+1

[funny_falcon (Yura Sokolov)]

• File add_st_shift.diff add_st_shift.diff added

• Status changed from Open to Closed
• % Done changed from 0 to 100

This issue was solved with changeset r40457.
Yura, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

---

• benchmark/bm_hash_shift.rb: add benchmark for Hash#shift

• hash.c (rb_hash_shift): use st_shift if hash is not being iterated to
  delete element without iterating the whole hash.

• hash.c (shift_i): remove function

• include/ruby/st.h (st_shift): add st_shift function

• st.c (st_shift): ditto

[Bug #8312] [ruby-core:54524] Patch by funny-falcon