Project

General

Profile

Actions
Copy link

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]
Backport:
1.9.3: UNKNOWN, 2.0.0: UNKNOWN
[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

Download all 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
Actions
Copy link
 #1 [ruby-core:54526]

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
Copy link
 #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
Copy link

Also available in: Atom PDF

Like0
Like0Like0Like0Like0