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

[showell]

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

I will attempt to fix insert(0, pop) in the next patch I submit (using pointer vs. orphans count).

Just so we are clear on the performance that I'm promising, I expect benchmarks to prove out these facts:

  1) New-list will always perform comparably to old-list, particularly for access.
  2) New-list will outperform old-list for pre-pop.
  3) New-list will perform comparably to deque for pre-pop.
  4) Although not a super common use case, prepends that follow prepops should reclaim space and perform better than old list and comparably to deque.
  5) For prepends that exceed prepops, I expect deque to greatly outperform new lists, just as it did old lists.

As I explained on python-dev, the new patch should give lists the same performance profile as a pencil/paper todo list.  Prepop works in O(1) with occasional compacting.  Prepend generally works in O(N) unless you can reclaim space from prior prepops.

To measure memory wastage, the two worst case scenarios are a bunch of tiny lists or a list from you which you prepop just under 50% of the elements (although that 50% can be tuned later if that's the only showstopper).  You can certainly construct a benchmark that brings those negative aspects to light, but I think it would be more convincing to find an actual real-world program that performs worse or exhausts memory under the limitation.

In general, it would be nice to find a Python program that makes extensive use of lists to prove out that the new list implementation at least does not degrade performance.  To the extent that test suite all passes, we at least have some empirical evidence that "correctness" has not been jeopardized, but the more we can hammer on this, the better, of course.  Does anybody have a suggestion for a real-world list benchmark program?

----------

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