Message243444
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. |
|
Date |
User |
Action |
Args |
2015-05-18 01:05:53 | rhettinger | set | recipients:
+ rhettinger |
2015-05-18 01:05:53 | rhettinger | set | messageid: <1431911153.11.0.995728012143.issue24221@psf.upfronthosting.co.za> |
2015-05-18 01:05:52 | rhettinger | link | issue24221 messages |
2015-05-18 01:05:51 | rhettinger | create | |
|