[issue4207] Remove backwards compatibility in _heapq for performance

[Kristján Valur Jónsson]

New submission from Kristján Valur Jónsson <kristjan at ccpgames.com>:

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.

----------
components: Extension Modules
files: heapq1.patch
keywords: easy, patch, patch
messages: 75224
nosy: krisvale
severity: normal
status: open
title: Remove backwards compatibility in _heapq for performance
type: performance
versions: Python 2.6
Added file: http://bugs.python.org/file11889/heapq1.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue4207>
_______________________________________