Bug #8312

Fix weird performance of Hash#shift

Added by Yura Sokolov almost 2 years ago. Updated almost 2 years ago.

[ruby-core:54524]
Status:Closed
Priority:Normal
Assignee:-
ruby -v:ruby 2.1.0dev (2013-04-23 trunk 40423) [x86_64-linux] Backport:1.9.3: UNKNOWN, 2.0.0: UNKNOWN

Description

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.

fix_hash_shift.diff Magnifier (967 Bytes) Yura Sokolov, 04/23/2013 11:45 PM

add_st_shift.diff Magnifier - fix Hash#shift performance by adding st_shift (3.04 KB) Yura Sokolov, 04/24/2013 12:21 AM

add_st_shift.diff Magnifier - fix Hash#shift performance by adding st_shift (improved) (2.82 KB) Yura Sokolov, 04/24/2013 07:44 PM

Associated revisions

Revision 40457
Added by Charlie Somerville almost 2 years ago

  • 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] Patch by funny-falcon

Revision 40457
Added by Charlie Somerville almost 2 years ago

  • 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] Patch by funny-falcon

History

#1 Updated by Yura Sokolov almost 2 years ago

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

#2 Updated by Sam Saffron almost 2 years ago

+1

#3 Updated by Yura Sokolov almost 2 years ago

#4 Updated by Charlie Somerville almost 2 years ago

  • 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] Patch by funny-falcon

Also available in: Atom PDF