PERFORMANCE: list versus a "dlist"

[Courageous]

Python lists, which are in actuality tail-preallocated dynamic
arrays, are compared to the performance of a similar dynamic
array using a head and tail preallocation strategy. This
construct is referred to as a "dlist" -- a double-ended list.

The tail preallocation strategy for the dlist involved
keeping actual length and allocated length, and doubling the
allocated space whenever an addition would involve appending
past the allocated region.

The head preallocation strategy involved keeping a "virtual
index" into the array which is initially set to a position
into the allocated region of memory at a position corresponding
to 1/3 of the way through. Certain critical conditions are
monitored which will trigger a reset to 1/3 of the way through
via either a reallocate/copy or a simple move, depending on
circumstance.

The performance of this construct is compared to python's
list as a FIFO (insert at head, pop at tail). Results are
reported as follows:

#insert/delete       DLIST            LIST

100                  .006             .006
1000                 .006             .018
10000                .065             .365

As before, on containers containing < 100 items or so, the
use of this additional datatype made no measurable difference
in performance of the tests. However, at list sizes at or near
1000 elements, the DLIST implementation broke forth as a clear
winner, where scaleability of the dlist imeplementation seemed
to indicate at or near O(1)+k cost for insertion at the head.

This is an early implemenation of this datstructure, and none
of the typical sequence manipulation code is available for it
as of yet.





C/