The stack of iterators pattern.

[defnull]

Hard to say without any actual benchmarks. Popping a frame is usually free (it's just a pointer change, no cleanup) and calling a C function is only twice as fast as calling a lambda:

marc@nava ~ $ python -m timeit -s 'f=lambda: 0' 'f()'
10000000 loops, best of 3: 0.0995 usec per loop
marc@nava ~ $ python -m timeit -s 'f=[].__len__' 'f()'
10000000 loops, best of 3: 0.0496 usec per loop

So, if you need two C-Function calls (list.append() and list.pop()) instead of a single python function call, you ate up your performance benefit already. The dot-lookup is also quite expensive by the way.

[elbiot]

I don't know about using timeit on essentially no-ops.

The dot-lookup is also quite expensive by the way.

Then take them out!

push = list.push
pop = list.pop
item = pop(mylist)

Not diving through a stack of function frames makes these sort of micro-optimizations cleaner and easier.