On Tue, 24 Sep 2002, Leopold Toetsch wrote: > Sean O'Rourke (via RT) wrote: > > > What happens if you presize the PerlArray to its final size > > Then it is of course faster, but this is not a real world proposal IMHO,
The real-world version would increase the array's allocation by some fixed multiple, e.g. double its size, which would still improve things from O(n) to O(log n) reallocations. I suspect that this would be almost as fast. > you don't know in advance the usage pattern, so you can't do this. Of > course, the memory management of array/PerlArray could be smarter - but > what about shift/unshift? If we expect these (especially shift) to be as frequent as push/pop, and we want fast indexing as well, then maybe something like the SGI STL implementation of a dequeue (dequeueue?) would be best: keep an array of (pointers to) fixed-size chunks (rather than intlist's linked-list). This would also allow gaps in the middle to remain unallocated, and could speed up some splices. > So we should use a intlist based solution anyway. It's an improvement over the current implementation, but I don't think it's the best solution for perlarray's requirements: 1 - front insertion/removal 2 - back insertion/removal 3 - indexing 4 - less-frequent insertion/removal in the middle (splice) The current approach is necessarily bad for 1, good for 3, and unnecessarily bad for 2. IntList is good for 1 and 2, but bad for 3. Both are not-so-hot for 4, but I don't think a lot of people use splice. /s
