From: Daniel Berger <djberg96@...>
Date: 2008-06-21T10:18:31+09:00
Subject: [ruby-core:17356] A faster Array#delete

Hi all,

Windows XP
VC++ 8

I noticed that the Array#delete method in array.c is basically copying 
the existing array element by element into a new array object. I 
suspected it could be improved so I tried this.

Using an approach similar to Array#delete_at, I came up with this:

VALUE rb_ary_delete(VALUE self, VALUE v_object){
    long i, n, length;
    int modified = 0;
    VALUE v_return = Qnil;

    length = RARRAY(self)->len;

    for(i = 0; i < RARRAY(self)->len; i++){
       if(rb_equal(v_object, RARRAY(self)->ptr[i])){
          if(!modified){
             rb_ary_modify(self);
             modified = 1;
          }

          for(n = 0; n < length; n++)
             RARRAY(self)->ptr[n-1] = RARRAY(self)->ptr[n];

          length -= 1;
          RARRAY(self)->len = length;
          i -= 1;
       }
    }

    /* If there was no match found and block was provided,
     * return the value of the yielded block. Otherwise, return
     * the deleted value.
     */
    if((!modified) && (rb_block_given_p())){
       v_return = rb_yield(rb_block_proc());
    }
    else{
       if(modified)
          v_return = v_object;
    }

    return v_return;
}

Then I ran this benchmark:

require 'benchmark'

MAX = 30000
array =  ['daniel']  * 1000
array << ['charles'] * 1000
array << ['matz'] * 1000
array << ['larry'] * 1000
array << ['guido'] * 1000
array.flatten!

Benchmark.bm(10) do |x|
    x.report("delete"){
       MAX.times{ array.delete('larry') }
    }
end

Old Array#delete:

                 user     system      total        real
delete     13.125000   0.000000  13.125000 ( 13.468000)

New Array#delete:

                 user     system      total        real
delete      3.704000   0.000000   3.704000 (  3.781000)

So, about a 3x speed increase in my tests, where I compiled both 
versions with MS VC++ 8 on Windows XP.

I thought I would see a substantial memory usage decrease, but my 
(limited) testing didn't show more than an 8k decrease for the Ruby process.

The only test I could break was an unrelated Array#collect! test:

# With the change, it returns [3,3]
def test_collect_bang_removes_elements_before_they_are_reached
    a = [1,2,3]
    assert_equal([2, 3], a.collect!{ |e| a.delete(a[1]) })
end

However, I believe the semantics for modifying an array in-place in the 
middle of a collect block are undefined, so I'm not sure the test I came 
up with is actually valid.

Thoughts? Suggestions? Comments?

Thanks,

Dan