From: "funny_falcon (Yura Sokolov)" <funny.falcon@...>
Date: 2013-04-24T00:21:59+09:00
Subject: [ruby-core:54526] [ruby-trunk - Bug #8312] Fix weird performance of Hash#shift


Issue #8312 has been updated by funny_falcon (Yura Sokolov).

File add_st_shift.diff added

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

----------------------------------------
Bug #8312: Fix weird performance of Hash#shift
https://bugs.ruby-lang.org/issues/8312#change-38842

Author: funny_falcon (Yura Sokolov)
Status: Open
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


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.


-- 
http://bugs.ruby-lang.org/