New submission from Raymond Hettinger: The siftup() and siftdown() routines rearrange pointers in a list. The generated code repeats the list object to ob_item lookup for each access. This patch does that lookup only once per iteration. It cleans up the code by replacing the PyList_GET_ITEM and PyList_SET_ITEM macros with normal array access (the usual way of presenting the algorithm).
This gives about a 5% speed-up using CLANG (timing heapify(data[:]) for n=1000 goes from .3441 per iteration to .3299). However on GCC-4.9, the same patch gives a 2% slow-down (disassembly shows that this patch triggers a register spill and load in the inner loop which is a bummer). Since it speeds-up some builds and slows down others, I'm uncertain what to do with this one. I like the way the code reads with array accesses but was aiming for a consistent win. Am posting the patch here to collect thoughts on the subject and to not lose the work. ---------- components: Extension Modules files: heapitems5.diff keywords: patch messages: 243444 nosy: rhettinger priority: normal severity: normal status: open title: Clean-up and optimization for heapq siftup() and siftdown() type: performance versions: Python 3.5 Added file: http://bugs.python.org/file39413/heapitems5.diff _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue24221> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
