E
Eric Mahurin
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 =3D 100000
v =3D ?X
a0 =3D [v]*n
s0 =3D ("" << v)*n
Benchmark.bmbm { |b|
b.report("push" ) { a =3D []; n.times { |i|
a.push(v) } }
b.report("append" ) { a =3D []; n.times { |i| a << v }
}
b.report("assign1" ) { a =3D []; n.times { |i|
a[a.size]=3Dv } }
b.report("assign" ) { a =3D []; n.times { |i|
a[a.size,0]=3D[v] } }
b.report("insert" ) { a =3D []; n.times { |i|
a.insert(-1,v) } }
b.report("string append" ) { s =3D ""; n.times { |i| s << v }
}
b.report("string assign0") { s =3D ""; n.times { |i|
s[s.size,0]=3D("" << v) } }
b.report("string insert" ) { s =3D ""; n.times { |i|
s.insert(-1,"" << v) } }
b.report("unshift" ) { a =3D []; n.times { |i|
a.unshift(v) } }
b.report("assign" ) { a =3D []; n.times { |i|
a[0,0]=3D[v] } }
b.report("insert" ) { a =3D []; n.times { |i|
a.insert(0,v) } }
b.report("string assign") { s =3D ""; n.times { |i|
s[0,0]=3D("" << v) } }
b.report("string insert") { s =3D ""; n.times { |i|
s.insert(0,"" << v) } }
b.report("pop" ) { a =3D a0.dup; n.times { |i| a.pop
} }
b.report("delete_at" ) { a =3D a0.dup; n.times { |i|
a.delete_at(-1) } }
b.report("slice!" ) { a =3D a0.dup; n.times { |i|
a.slice!(-1) } }
b.report("assign" ) { a =3D a0.dup; n.times { |i| begin
a[-1] ensure a[-1,1]=3D[] end } }
b.report("string slice!") { s =3D s0.dup; n.times { |i|
s.slice!(-1) } }
b.report("string assign") { s =3D s0.dup; n.times { |i| begin
s[-1] ensure s[-1,1]=3D"" end } }
b.report("shift" ) { a =3D a0.dup; n.times { |i|
a.shift } }
b.report("delete_at" ) { a =3D a0.dup; n.times { |i|
a.delete_at(0) } }
b.report("slice!" ) { a =3D a0.dup; n.times { |i|
a.slice!(0) } }
b.report("assign" ) { a =3D a0.dup; n.times { |i| begin
a[0] ensure a[0,1]=3D[] end } }
b.report("string slice!") { s =3D s0.dup; n.times { |i|
s.slice!(0) } }
b.report("string assign") { s =3D s0.dup; n.times { |i| begin
s[0] ensure s[0,1]=3D"" end } }
}
=09
__________________________________=20
Yahoo! Mail Mobile=20
Take Yahoo! Mail with you! Check email on your mobile phone.=20
http://mobile.yahoo.com/learn/mail=20
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 =3D 100000
v =3D ?X
a0 =3D [v]*n
s0 =3D ("" << v)*n
Benchmark.bmbm { |b|
b.report("push" ) { a =3D []; n.times { |i|
a.push(v) } }
b.report("append" ) { a =3D []; n.times { |i| a << v }
}
b.report("assign1" ) { a =3D []; n.times { |i|
a[a.size]=3Dv } }
b.report("assign" ) { a =3D []; n.times { |i|
a[a.size,0]=3D[v] } }
b.report("insert" ) { a =3D []; n.times { |i|
a.insert(-1,v) } }
b.report("string append" ) { s =3D ""; n.times { |i| s << v }
}
b.report("string assign0") { s =3D ""; n.times { |i|
s[s.size,0]=3D("" << v) } }
b.report("string insert" ) { s =3D ""; n.times { |i|
s.insert(-1,"" << v) } }
b.report("unshift" ) { a =3D []; n.times { |i|
a.unshift(v) } }
b.report("assign" ) { a =3D []; n.times { |i|
a[0,0]=3D[v] } }
b.report("insert" ) { a =3D []; n.times { |i|
a.insert(0,v) } }
b.report("string assign") { s =3D ""; n.times { |i|
s[0,0]=3D("" << v) } }
b.report("string insert") { s =3D ""; n.times { |i|
s.insert(0,"" << v) } }
b.report("pop" ) { a =3D a0.dup; n.times { |i| a.pop
} }
b.report("delete_at" ) { a =3D a0.dup; n.times { |i|
a.delete_at(-1) } }
b.report("slice!" ) { a =3D a0.dup; n.times { |i|
a.slice!(-1) } }
b.report("assign" ) { a =3D a0.dup; n.times { |i| begin
a[-1] ensure a[-1,1]=3D[] end } }
b.report("string slice!") { s =3D s0.dup; n.times { |i|
s.slice!(-1) } }
b.report("string assign") { s =3D s0.dup; n.times { |i| begin
s[-1] ensure s[-1,1]=3D"" end } }
b.report("shift" ) { a =3D a0.dup; n.times { |i|
a.shift } }
b.report("delete_at" ) { a =3D a0.dup; n.times { |i|
a.delete_at(0) } }
b.report("slice!" ) { a =3D a0.dup; n.times { |i|
a.slice!(0) } }
b.report("assign" ) { a =3D a0.dup; n.times { |i| begin
a[0] ensure a[0,1]=3D[] end } }
b.report("string slice!") { s =3D s0.dup; n.times { |i|
s.slice!(0) } }
b.report("string assign") { s =3D s0.dup; n.times { |i| begin
s[0] ensure s[0,1]=3D"" end } }
}
=09
__________________________________=20
Yahoo! Mail Mobile=20
Take Yahoo! Mail with you! Check email on your mobile phone.=20
http://mobile.yahoo.com/learn/mail=20