[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 closing this due to mostly unanimous rejection on python-dev.

If folks reopen this in the future, the last patch that I submitted has been reasonably well tested, but it has not been code reviewed.

The 1% speed penalty could probably be driven down without too much effort, but not totally eliminated.

The constraint not to add a member to PyListObject complicates the code considerably.

In diving deep into listobject.c, I noticed a couple things unrelated to my patch:

  1) There might be a refactoring available for calls to list_resize, where callers just pass in the delta, instead of the new list size.  Lots of the callers do addition that could be pushed into list_resize.  Not sure it would lead to speed ups, but it would probably reduce code size.

  2) The optimistic realloc scheme is probably needlessly wasteful for really large lists.  If you have a million elements, I am not sure you need to allocate 12% extra space, and I think that's what the current algorithm does (untested).

  3) There might be some merit in splitting out list_resize into list_resize_bigger and list_resize_smaller.  I think the callers generally know when they are shrinking/expanding the list, so callers that are shrinking the list could call a leaner method that just shrinks the list without having to execute other instructions.

----------
status: open -> closed

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