Remove backwards compatibility in _heapq for performance

[kristjanvalur]

BPO	4207
Nosy	@rhettinger, @kristjanvalur
Files	heapq1.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2008-10-26.13:07:45.442>
created_at = <Date 2008-10-26.11:53:05.841>
labels = ['extension-modules', 'easy', 'performance']
title = 'Remove backwards compatibility in _heapq for performance'
updated_at = <Date 2008-10-26.13:49:27.459>
user = 'https://github.com/kristjanvalur'

bugs.python.org fields:

activity = <Date 2008-10-26.13:49:27.459>
actor = 'kristjan.jonsson'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2008-10-26.13:07:45.442>
closer = 'rhettinger'
components = ['Extension Modules']
creation = <Date 2008-10-26.11:53:05.841>
creator = 'kristjan.jonsson'
dependencies = []
files = ['11889']
hgrepos = []
issue_num = 4207
keywords = ['patch', 'easy']
message_count = 3.0
messages = ['75224', '75225', '75226']
nosy_count = 2.0
nosy_names = ['rhettinger', 'kristjan.jonsson']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue4207'
versions = ['Python 2.6']

[kristjanvalur]

Comparing _heapq with our own legacy C implementation, blue.heapq at
CCP, I noticed that ours was somewhat faster.
I discovered that a lot of effort is being spent to dynamically search
for a __lt__ operator, to provide backwards compatibility. I think we
should consider dropping that after this much time, especially for a
new python version. Running this code:

from timeit import *
s = """
import heapq
import random
l = [random.random() for i in xrange(10000)]
"""

print "heapify", Timer("heapq.heapify(list(l))", s).timeit(100)

s = s + """
heapq.heapify(l)
"""
print "pushpop", Timer("heapq.heappushpop(l,random.random())", s).timeit
(500000)

would give
heapify 0.289102944648
pushpop 0.343299078514
before. After the patch, we get:
heapify 0.0958507994731
pushpop 0.220800967721

This is "release" code on a snappy windows machine.

[rhettinger]

The compatability code was just added in Py2.6 and is needed for apps
like Twisted that currently rely on __le__ being tested. In 3.0, the
compatability code is removed and full speed is restored.

Also, the timing suite exaggerates the effect. A more typical use of
heaps involves a heap of tuples with the first tuple element being used
as a priority level. That increases the comparison time and decreases
the relative significance of the dispatch logic.

[kristjanvalur]

I am sorry for not doing my research about the age of the compatibility
fix.
However, modifying the test slightly to work with tuples of
(random.random(), random.random())
shows a performance increase from:

heapify 0.366187741738
pushpop 0.541365033824
replace 2.69348946584
push and pop 3.12545093022

to:

heapify 0.186918030085
pushpop 0.405662172148
replace 1.46039447751
push and pop 1.75253663524

This does look like a large price to pay for this compatibility layer.