[issue7784] patch for making list/insert at the top of the list avoid memmoves

[showell]

showell <showell30 at yahoo.com> added the comment:

I am attaching a new patch that does not add a new element to PyListObject, roughly following a technique that Antoine Pitrou suggested on python-dev.  When I want to lazily avoid a memmove under the new patch, I set the MSB on allocated and store the original ob_item pointer in the new ob_item[-1].

On the advice of Daniel, I ran the new patch against the Unladen benchmark suite.  The results were pretty neutral--never more than a 1% penalty but no significant gains either.  I did not expect to see gains, for the obvious reason that I am improving performance on an operation that folks have been encouraged to work around.  The new patch continues to do well on microbenchmarks. 

The new patch fails one test in test_sys related to the 12 byte garbage collection header.  The failure is definitely introduced by my patch, but I am not sure what it's doing wrong.  All other tests pass.

Because the new code piggybacks on top of of allocated instead of creating a new variable in PyListObject, the new code is a bit more complex than the original patch, which is unfortunate.  There are probably some opportunities for making the new code simpler.

----------
Added file: http://bugs.python.org/file16033/DIFF_NO_EXTRA_MEM

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue7784>
_______________________________________