Array#insert bogs down under heavy iteration

Hi,

It seems that Array#insert bogs down quite heavily
under heavy iterations.  I don't know if this is
avoidable or not, but I thought I would at least ask
about it:

MAX = 30000 # Also 60000 and 100000 - see below

Benchmark.bm(30) do |x|
   x.report("Array#insert(2)"){
      array = [1,2,3,4]
      MAX.times{ array.insert(2, "a", "b") }
   }

   # Test the -1 index specifically, since all it does
is append
   x.report("Array#insert(-1)"){
      array = [1,2,3,4]
      MAX.times{ array.insert(-1, "a", "b") }
   }

   x.report("Array#insert(-2)"){
      array = [1,2,3,4]
      MAX.times{ array.insert(-2, "a", "b") }
   }
end

Things seem reasonable until around 50,000 iterations,
then it starts to get worse fast (at least, on my
system).

30,000 iterations:
                  user     system      total       
real
Array#insert(2)   4.203000   0.000000   4.203000 ( 
4.438000)
Array#insert(-1)  1.594000   0.015000   1.609000 ( 
1.672000)
Array#insert(-2)  1.172000   0.000000   1.172000 ( 
1.297000)

60,000 iterations:
                   user     system      total       
real
Array#insert(2)    15.141000   0.000000  15.141000
(15.969000)
Array#insert(-1)   4.687000   0.000000   4.687000 ( 
4.906000)
Array#insert(-2)   4.532000   0.000000   4.532000 ( 
4.859000)

100,000 iterations:
                   user     system      total       
real
Array#insert(2)    61.203000   0.015000  61.218000 (
67.922000)
Array#insert(-1)   12.875000   0.094000  12.969000 (
14.328000)
Array#insert(-2)   8.454000   0.109000   8.563000 ( 
9.469000)

Roughly the same with 1.8.2, 1.8.3 and 1.8.4.

Nature of the beast or something that can be improved?

Regards,

Dan


	
		
__________________________________ 
Yahoo! Mail - PC Magazine Editors' Choice 2005 
http://mail.yahoo.com