Project

General

Profile

Actions

Bug #8312

closed

Fix weird performance of Hash#shift

Added by funny_falcon (Yura Sokolov) over 11 years ago. Updated over 11 years ago.

Status:
Closed
Assignee:
-
Target version:
-
ruby -v:
ruby 2.1.0dev (2013-04-23 trunk 40423) [x86_64-linux]
[ruby-core:54524]

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.


Files

fix_hash_shift.diff (967 Bytes) fix_hash_shift.diff funny_falcon (Yura Sokolov), 04/23/2013 11:45 PM
add_st_shift.diff (3.04 KB) add_st_shift.diff fix Hash#shift performance by adding st_shift funny_falcon (Yura Sokolov), 04/24/2013 12:21 AM
add_st_shift.diff (2.82 KB) add_st_shift.diff fix Hash#shift performance by adding st_shift (improved) funny_falcon (Yura Sokolov), 04/24/2013 07:44 PM

Updated by funny_falcon (Yura Sokolov) over 11 years ago

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

Actions #4

Updated by Anonymous over 11 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] [ruby-core:54524] Patch by funny-falcon

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0