Bug #8312

Fix weird performance of Hash#shift

Added by Yura Sokolov about 1 year ago. Updated 12 months ago.

[ruby-core:54524]
Status:Closed
Priority:Normal
Assignee:-
Category:-
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

Description

rbhashshift has an optimization for case when #shift is called outside hash iteration.
But in fact it is deoptimization, cause it uses rbhashforeach, 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 12 months ago

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

  • hash.c (rbhashshift): 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 (stshift): add stshift function

  • st.c (st_shift): ditto

[Bug #8312] Patch by funny-falcon

History

#1 Updated by Yura Sokolov about 1 year ago

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

#2 Updated by Sam Saffron about 1 year ago

+1

#3 Updated by Yura Sokolov about 1 year ago

#4 Updated by Charlie Somerville 12 months 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/bmhashshift.rb: add benchmark for Hash#shift

  • hash.c (rbhashshift): 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 (stshift): add stshift function

  • st.c (st_shift): ditto

[Bug #8312] Patch by funny-falcon

Also available in: Atom PDF