Why in comparing python tuples of objects is __eq__ and then __cmp__ called?

Question

When comparing tuples of objects apparently the __eq__ method of the object is called and then the compare method:

import timeit

setup = """
import random
import string
import operator

random.seed('slartibartfast')
d={}

class A(object):
    eq_calls = 0
    cmp_calls = 0
    def __init__(self):
        self.s = ''.join(random.choice(string.ascii_uppercase) for _ in
              range(16))
    def __hash__(self): return hash(self.s)
    def __eq__(self, other):
        self.__class__.eq_calls += 1
        return self.s == other.s
    def __ne__(self, other): return self.s != other.s
    def __cmp__(self, other):
        self.__class__.cmp_calls += 1
        return cmp(self.s ,other.s)

for i in range(1000): d[A()] = 0"""
print min(timeit.Timer("""
for k,v in sorted(d.iteritems()): pass
print A.eq_calls
print A.cmp_calls""", setup=setup).repeat(1, 1))

print min(timeit.Timer("""
for k,v in sorted(d.iteritems(),key=operator.itemgetter(0)): pass
print A.eq_calls
print A.cmp_calls""", setup=setup).repeat(1, 1))

Prints:

8605
8605
0.0172435735131
0
8605
0.0103719966418

So in the second case where we compare the keys (that is the A instances) directly __eq__ is not called, while in the first case apparently the first ellement of the tuple are compared via equal and then via cmp. But why are they not compared directly via cmp ? What I really don't quite get is the default sorted behavior on the absence of a cmp or key parameter.

Answer 1

It is just how tuple comparison is implemented: tuplerichcompare

it searches the first index where items are different and then compare on that. That's why you see an __eq__ and then a __cmp__ call. Moreover if you do not implement the __eq__ operator for A, you will see that __cmp__ is called twice once for equality and once for comparison.

For instance,

print min(timeit.Timer("""
l =list()
for i in range(5): 
    l.append((A(),A(),A()))
    l[-1][0].s='foo'
    l[-1][1].s='foo2'
for _ in sorted(l): pass 
print A.eq_calls
print A.cmp_calls""", setup=setup).repeat(1, 1))

prints out 24 and 8 calls respectively (the exact number clearly depends on random seed but in this case they will always have a ratio of 3)