[Python-3000] Two proposals for a new list-like type: one modest, one radical

[Daniel Stutzbach]

On 4/23/07, Mike Klaas <mike.klaas at gmail.com> wrote:
> On 4/23/07, Daniel Stutzbach <daniel at stutzbachenterprises.com> wrote:
> > So you can see the performance of the BList in more detail, I've made
> > several performance graphs available at the following link:
> >    http://stutzbachenterprises.com/blist/
>
> Very cool.  These detailed timings are very useful.
>
> Might it be possible to include variance bars?

I'm not really sure what variance bars would reveal.  Performing
exactly the same operations follows exactly the same code path, so
there's not a lot of variance to be found.  Let me explain my
methodology for generating these figures.

Right now I'm generating the timings using timeit.py, where the setup
step is run once, then the actual operation is run enough times to
exceed 10 milliseconds.  I repeat the process 3 times and take the
lowest value (to try to factor out noise introduced by other processes
and other OS issues).  The machine I run the tests on is generally
unloaded.

Once I had an initial working implementation, I've been using theses
experiments and graphs to figure out where I needed to do optimization
work.  I can testify that when I rerun the experiments with the same
code, the results would look *very* similar.

> A few of the graphs
> show your data structure faster than the list even for small N, and it
> would be great to see if it is meaningfully faster in these cases (if
> so, perhaps there are optimization possibilities for the current list
> data structure).

Yes, in some cases the optimizations I've made could be ported back to
the current list data structure.  I will try to hunt these down and
send patches via SourceForge.

> A quite glance at your results shows a few more cases where the blist
> faces problems, such no longer using Timsort, and so suffering in
> performance for sorted/reversed cases.  That would be painful to give
> up in the built-in list implementation.

I plan on implementing Timsort for BLists; I just haven't had time yet.

-- 
Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC