This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: Clean-up and optimization for heapq siftup() and siftdown()
Type: performance Stage:
Components: Extension Modules Versions: Python 3.5
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: python-dev, rhettinger, scoder, serhiy.storchaka
Priority: low Keywords: patch

Created on 2015-05-18 01:05 by rhettinger, last changed 2022-04-11 14:58 by admin. This issue is now closed.

File name Uploaded Description Edit
heapitems5.diff rhettinger, 2015-05-18 01:05 Replace GET/SET macros with direct array access review rhettinger, 2015-05-18 01:06 Timing code
Messages (6)
msg243444 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-05-18 01:05
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.
msg243460 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-05-18 06:29
Perhaps the code will look simpler if introduce the macro _PyList_SWAP_ITEMS(list, i, j).
msg243816 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-05-22 07:42
New changeset 490720fc1525 by Raymond Hettinger in branch 'default':
Issue #24221:  Small optimizations for heapq.
msg243817 - (view) Author: Stefan Behnel (scoder) * (Python committer) Date: 2015-05-22 07:54
There are calls to PyObject_RichCompareBool() in the loops, which means that user code might get executed. What if that's evil code that modifies the heap list? Couldn't that lead to list resizing and thus invalidation of the list item pointer?
msg243822 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-05-22 08:44
The list item pointer is updated just after calling PyObject_RichCompareBool(). The code LGTM.
msg243826 - (view) Author: Stefan Behnel (scoder) * (Python committer) Date: 2015-05-22 14:28
Ah, sorry, yes. I somehow misread the arguments being passed *into* richcompare as subsequent array access. LGTM too. Sorry for the noise.
Date User Action Args
2022-04-11 14:58:17adminsetgithub: 68409
2015-05-22 14:28:14scodersetmessages: + msg243826
2015-05-22 08:44:14serhiy.storchakasetmessages: + msg243822
2015-05-22 07:54:12scodersetnosy: + scoder
messages: + msg243817
2015-05-22 07:43:00rhettingersetstatus: open -> closed
resolution: fixed
2015-05-22 07:42:12python-devsetnosy: + python-dev
messages: + msg243816
2015-05-18 06:29:14serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg243460
2015-05-18 01:20:00rhettingersetpriority: normal -> low
2015-05-18 01:06:27rhettingersetfiles: +
2015-05-18 01:05:53rhettingercreate