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

Changes by Raymond Hettinger : -- resolution: -> rejected ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http:

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

Changes by Jesús Cea Avión : -- nosy: +jcea ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.o

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

showell 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

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

Changes by showell : Removed file: http://bugs.python.org/file16033/list_top_no_extra_mem.diff ___ Python tracker ___ ___ Python-bugs-list mail

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

showell added the comment: Ok, found the offending line, now all tests pass. The use case where this patch will pay off the most is slicing your way through a list of tasks. The toy program below gets about a 50x speedup. import time n = 80 lst = [] fo

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

showell 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_it

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

Daniel Stutzbach added the comment: For macro benchmarking, I suggest using the Unladen Swallow benchmark suite. -- ___ Python tracker ___ ___

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

showell 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, pa

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

Raymond Hettinger added the comment: Please take care in presenting timings. It is easy to get misleading results: * Factor-out the attribute lookup time (since that isn't the part being changed: -s 'c = range(100); c_ins=c.insert; c_pop=c.pop' 'c_insert(0, c_pop())' * The case of a

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

Adam Olsen added the comment: $ ./python -m timeit -s 'from collections import deque; c = deque(range(100))' 'c.append(c.popleft())' 100 loops, best of 3: 0.29 usec per loop $ ./python -m timeit -s 'c = range(100)' 'c.append(c.pop(0))' 100 loops, best of 3: 0.424 usec per loop

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

showell added the comment: The next stage for the patch is that I need to switch from using orphans count to using ob_allocated pointer. -- ___ Python tracker ___ __

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

Changes by Daniel Stutzbach : -- nosy: +stutzbach ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.py

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

showell added the comment: --- On Tue, 1/26/10, Florent Xicluna wrote: > From: Florent Xicluna > Subject: [issue7784] patch for making list/insert at the top of the list > avoid memmoves > To: showel...@yahoo.com > Date: Tuesday, January 26, 2010, 3:53 AM > > Florent

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

Florent Xicluna added the comment: Steve, thank you for your patch. IMHO, it's better to provide a patch against trunk (Py2) when the optimization is not specific to 3.x. I merged it manually on my working copy, and all tests pass without leaking. Patch for Py2 attached. However, I am not a

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

New submission from showell : I am attaching a patch to improve the performance of list operations that insert or delete elements at the front of the list. The patch has had some discussion on python-dev in the thread entitled "patch to make list.pop(0) work in O(1) time." So far the verdict