[Python-3000] BLists (PEP 3128)

[Daniel Stutzbach]

On 5/11/07, Raymond Hettinger <python at rcn.com> wrote:
> > Would it be useful if I created an experimental fork of 2.5
> > that replaces array-based lists with BLists,
> >  so that the performance penalty (if any) on existing code
> > can be measured?
>
> That would likely be an informative exercise and would assure that your
> code is truly interchangable with regular lists.  It would also highlight the
> under-the-hood difficulties you'll encounter with the C-API.
>
> That being said, it is a labor intensive exercise and the time might be better
> spent on tweaking the third-party module code and building a happy user-base.

Just to provide a quick update on my adventures with BLists:

I went forward with the exercise of replacing the array-based list
with BLists in the Python interpreter.  As a first pass, I went with a
simple, not-very-efficient redirect of the List API.  I had very few
problems getting this working well enough to compile.

The exercise also had the benefit that I have been able to test BLists
against the entire Python test suite.  Previously, I had adapted only
test_list.  test_builtin was particularly useful.  I was able to find
and fix a couple more bugs in my implementation this way.  Almost all
of the tests pass now.

There are also a handful of test failures where the tests are
asserting the CPython implementation details when the intent is really
just to assert(don't crash).  These tests are related to when
references are deleted to evil comparison/lookup functions or what
happens when a list changes size during iteration.  I'll probably
change the BList code to match CPython's behavior.

I have one genuine bug to fix that inexplicably causes test_shlex to
fail.  Once that is taken care of, I get back to looking at
performance.

However, I'm leaving tomorrow for 3 weeks (wedding + honeymoon), so
I'm not going to be able to make any further progress until I get
back.  :-)

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