From: Eric Mahurin <eric_mahurin@...>
Date: 2005-06-30T04:52:50+09:00
Subject: shift vs. slice!(0) and others

I just did some benchmarking of various ways to insert/delete
elements off of either end of arrays and strings (100,000
operations starting or ending with a 100,000 element
array/string):

                     user     system      total        real
------
push             0.063000   0.000000   0.063000 (  0.062000)
append           0.078000   0.000000   0.078000 (  0.078000)
assign1          0.093000   0.000000   0.093000 (  0.094000)
assign           1.063000   0.000000   1.063000 (  1.060000)
insert           0.953000   0.000000   0.953000 (  1.013000)
string append    0.078000   0.000000   0.078000 (  0.078000)
string assign0   0.469000   0.000000   0.469000 (  0.468000)
string insert    0.437000   0.000000   0.437000 (  0.436000)
------
unshift          8.438000   0.000000   8.438000 (  8.587000)
assign           9.312000   0.000000   9.312000 (  9.475000)
insert           9.282000   0.000000   9.282000 (  9.507000)
string assign    2.562000   0.000000   2.562000 (  2.649000)
string insert    2.468000   0.016000   2.484000 (  2.571000)
------
pop              0.047000   0.000000   0.047000 (  0.047000)
delete_at        0.062000   0.000000   0.062000 (  0.063000)
slice!           0.094000   0.000000   0.094000 (  0.093000)
assign           0.297000   0.000000   0.297000 (  0.311000)
string slice!    0.234000   0.000000   0.234000 (  0.296000)
string assign    0.219000   0.000000   0.219000 (  0.218000)
------
shift            0.062000   0.000000   0.062000 (  0.062000)
delete_at       44.313000   0.000000  44.313000 ( 45.260000)
slice!          40.468000   0.000000  40.468000 ( 41.285000)
assign           8.688000   0.000000   8.688000 (  8.915000)
string slice!    2.469000   0.000000   2.469000 (  2.478000)
string assign    2.391000   0.000000   2.391000 (  2.479000)


The one that really sticks out is shift vs. delete_at(0) and
slice!(0).  I see a 650X difference in performance.  I'm
guessing shift is O(1) and the others are O(n).  I'm assuming
that shift simply increments the start of the array pointer and
frees memory at certain boundaries.  If that is the case, it
would be nice if the other forms did the same and unshift did
the opposite (simply decremented the start of the array/string
pointer).  This sure would be nice for easy and high
performance implementations of circular and gap buffers.


FYI, I did this on v1.8.2 on a windows machine.  Here is the
benchmark code:

require 'benchmark'
n = 100000
v = ?X
a0 = [v]*n
s0 = ("" << v)*n

Benchmark.bmbm { |b|
    b.report("push"          ) { a = []; n.times { |i|
a.push(v) } }
    b.report("append"        ) { a = []; n.times { |i| a << v }
}
    b.report("assign1"       ) { a = []; n.times { |i|
a[a.size]=v } }
    b.report("assign"        ) { a = []; n.times { |i|
a[a.size,0]=[v] } }
    b.report("insert"        ) { a = []; n.times { |i|
a.insert(-1,v) } }
    b.report("string append" ) { s = ""; n.times { |i| s << v }
}
    b.report("string assign0") { s = ""; n.times { |i|
s[s.size,0]=("" << v) } }
    b.report("string insert" ) { s = ""; n.times { |i|
s.insert(-1,"" << v) } }

    b.report("unshift"      ) { a = []; n.times { |i|
a.unshift(v) } }
    b.report("assign"       ) { a = []; n.times { |i|
a[0,0]=[v] } }
    b.report("insert"       ) { a = []; n.times { |i|
a.insert(0,v) } }
    b.report("string assign") { s = ""; n.times { |i|
s[0,0]=("" << v) } }
    b.report("string insert") { s = ""; n.times { |i|
s.insert(0,"" << v) } }

    b.report("pop"          ) { a = a0.dup; n.times { |i| a.pop
} }
    b.report("delete_at"    ) { a = a0.dup; n.times { |i|
a.delete_at(-1) } }
    b.report("slice!"       ) { a = a0.dup; n.times { |i|
a.slice!(-1) } }
    b.report("assign"       ) { a = a0.dup; n.times { |i| begin
a[-1] ensure a[-1,1]=[] end } }
    b.report("string slice!") { s = s0.dup; n.times { |i|
s.slice!(-1) } }
    b.report("string assign") { s = s0.dup; n.times { |i| begin
s[-1] ensure s[-1,1]="" end } }

    b.report("shift"        ) { a = a0.dup; n.times { |i|
a.shift } }
    b.report("delete_at"    ) { a = a0.dup; n.times { |i|
a.delete_at(0) } }
    b.report("slice!"       ) { a = a0.dup; n.times { |i|
a.slice!(0) } }
    b.report("assign"       ) { a = a0.dup; n.times { |i| begin
a[0] ensure a[0,1]=[] end } }
    b.report("string slice!") { s = s0.dup; n.times { |i|
s.slice!(0) } }
    b.report("string assign") { s = s0.dup; n.times { |i| begin
s[0] ensure s[0,1]="" end } }
}




		
__________________________________ 
Yahoo! Mail Mobile 
Take Yahoo! Mail with you! Check email on your mobile phone. 
http://mobile.yahoo.com/learn/mail