Simon Cozens wrote: > That's great, but what impact does it have on access to individual > elements? If you're not careful, you may find that accessing stuff in > the array gets quite seriously slower. Linked lists being O(n) access > and all that...
I certainly hope that access gets slower, otherwise we have a serious problem! intlist's approach of fixed size chunks with a separate index array fixes that; I was just demonstrating that the overhead of array expansion in the current implementation can be significant, therefore Leo's plan makes sense. Nothing in grey is intended for public consumption, it is purely a test bed. > Put another loop in, which sets I1 to every array element in turn, > (maybe make this an inner loop which runs each time you extend) and > re-benchmark. Single loop to access all elements once after creation: new P0, .PerlArray set I0, 1 set I1, 0 loop: set P0, I0 set P0[I1], I0 inc I0 inc I1 lt I0, 25000, loop print I0 print "\n" set I2, 0 loop_sc: set I3, P0[I2] inc I2 lt I2, I1, loop_sc end 25000: CVS = 47 seconds, grey = 1 second 100000: CVS = 13 minutes 13 seconds, grey = 15 seconds Nested loop: new P0, .PerlArray set I0, 1 set I1, 0 loop: set P0, I0 set P0[I1], I0 set I2, 0 loop_sc: set I3, P0[I2] inc I2 lt I2, I1, loop_sc inc I0 inc I1 lt I0, 5000, loop print I0 print "\n" end 5000: CVS = 26 seconds, grey = 30 seconds Doing any more iterations than that will take far too long, we already know that CVS will always win when access happens a lot more often than creation. -- Peter Gibbs EmKel Systems
