custom iterator performance

Question

I'm encountering what seems like quite surprising performance differences when iterating over a small container with a custom iterator. I was hoping someone might be able to help me understand where these differences are coming from.

First some context; I'm writing a number of python extension modules using boost::python, one of which contains a binding to a 3d float vector type that implements getitem. Since it has getitem its possible to iterate over it, however it seems quite slow, but its not obvious why so I decided to play around with some simple custom iterators in python to get a better idea of how things work. Which is where these iterators came from...

class MyIterator1(object):
    __slots__ = ['values', 'popfn']

    def __init__(self):
        self.values = ['x', 'y', 'z']
        self.popfn = self.values.pop

    def __length_hint__(self):
        return 3

    def __iter__(self):
        return self

    def next(self):
        try:
            return self.popfn()
        except IndexError:
            raise StopIteration

class MyIterator2(object):
    __slots__ = ['values', 'itfn']

    def __init__(self):
        self.values = ['x', 'y', 'z']
        it = iter(self.values)
        self.itfn = it.next

    def __length_hint__(self):
        return 3

    def __iter__(self):
        return self

    def next(self):
        return self.itfn()

class MyIterator3(object):
    __slots__ = ['values', 'i']

    def __init__(self):
        self.values = ['x', 'y', 'z']
        self.i = 0

    def __length_hint__(self):
        return 3

    def __iter__(self):
        return self

    def next(self):
        if self.i >= 3:
            raise StopIteration
        value = self.values[self.i]
        self.i += 1
        return value

def MyIterator4():
    val = ['x', 'y', 'z']
    yield val[0]
    yield val[1]
    yield val[2]

Next I ran these through a script with the timeit module (which assumes the above code is in a module called testiter)

import timeit

timer1 = timeit.Timer('r = list(testiter.MyIterator1())', 'import testiter')
timer2 = timeit.Timer('r = list(testiter.MyIterator2())', 'import testiter')
timer3 = timeit.Timer('r = list(testiter.MyIterator3())', 'import testiter')
timer4 = timeit.Timer('r = list(testiter.MyIterator4())', 'import testiter')
timer5 = timeit.Timer('r = list(iter(["x", "y", "z"]))', 'import testiter')

print 'list(testiter.MyIterator1())'
print timer1.timeit()

print "\n"

print 'list(testiter.MyIterator2())'
print timer2.timeit()

print "\n"

print 'list(testiter.MyIterator3())'
print timer3.timeit()

print "\n"

print 'list(testiter.MyIterator4())'
print timer4.timeit()

print "\n"

print 'list(iter(["x", "y", "z"]))'
print timer5.timeit()

This prints out the following

list(testiter.MyIterator1())
8.57359290123


list(testiter.MyIterator2())
5.28959393501


list(testiter.MyIterator3())
6.11230111122


list(testiter.MyIterator4())
2.31263613701


list(iter(["x", "y", "z"]))
1.26243281364

Unsurprisingly the python listiterator is the fastest, by quite a margin. I assume this is down to some magic optimisations within python. The generator is also considerably faster than the MyIterator classes, which again I'm not hugely surprised about, and assume is due to all the work being done in c, however thats just a guess. Now the others are more confusing/supprising. Are try/except statements as expensive as they seem in this context or is something else going on ?

Any help in explaining these differences would be greatly appreciated! Apologies for the long post.

Answer 1

A few ideas off the top of my head; sorry if they're not palpable enough:

• The first iterator is using the list's pop to implement next, meaning the list is mutated after each element is retrieved. Perhaps this mutation of a dynamically allocated composite data structure is reducing performance. All depends on the implementation details of lists, so this could be completely irrelevant.
• The last iterator is using a feature wired into the language (yield) in a simple context to produce the result. At a guess, I'll say this indicates there's more room for optimisation than a custom iterator class attempting to achieve the same result.
• The 5th timer isn't using a custom iterator, and is instead using the one provided for lists directly. Iterators for lists are probably well-optimized, and there isn't a layer of indirection that those custom classes use, some of which are using such a list iterator internally anyway.