[New-bugs-announce] [issue24221] Clean-up and optimization for heapq siftup() and siftdown()

[Raymond Hettinger]

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 <report at bugs.python.org>
<http://bugs.python.org/issue24221>
_______________________________________