Wednesday, August 6, 2008

Python: know when to be lazy

Lazy is good. One Python trend I've noticed quite a bit is the severe under-usage of generators. I often see list comprehension being used in situations where building a temporary list is not only wasteful, but more work.

Example:

print sum([x * 2 for x in something])

In this case, LC is being used to build a temporary list whose only purpose is to be iterated by "sum". Instead of constructing this list, why not pass an iterable object to "sum" and have it accumulate the sum from that? Well, not only can you, but it's even less to type (a whopping two characters less):

print sum(x * 2 for x in something)

Simply excluding the square brackets takes it from a list-comp to a generator expression, which is lazily evaluated. To demonstrate, proof that generators don't actually compute anything until they are pulled:

def f(x):
print x

a = [f("LC") for x in xrange(10)]
b = (f("GE") for x in xrange(10))

print "outside"
b.next()

print "outside"
b.next()

So naturally, these can be a really useful and compact way to transform a sequence. But the generator-expression syntax doesn't really allow for very complex stuff... Lucky Python also supports generator functions using the "yield" keyword that allows you to lazily preserve state between calls to "next"

def powersof2():
x = 1
while True:
yield x
x *= 2

g = powersof2()
print g.next()
print g.next()
print g.next()

And then, another thing I see is similar use of the map, filter, zip functions, which here in Python2.5 land return an entire list (this won't be an issue in Python3, however). For the time being, if you need a lazy map/filter, either use generator expressions or use the itertools module

from itertools import imap, ifilter

def even(x):
return not(x % 2)

print sum(ifilter(even, imap(int, "1 2 3 4 5 6 7 8 9".split())))

In this case, the imap/ifilter works better than generator expressions (IMO) because of the need for the strings as integers in the "even" function. With GE I'm forced to either call the int function twice, or to break it up across lines:

print sum(int(x) for x in "1 2 3 4 5 6 7 8 9".split() if even(int(x)))
# OR
ints = (int(x) for x in "1 2 3 4 5 6 7 8 9".split())
print sum(x for x in ints if even(x))

But, since this is lazy, the filtering is done as the mapping takes place (neither are bundled into any temporary lists or anything)

Likewise, using "range" instead of "xrange" for integer iteration is also a wasteful practice (this will be fixed in Python3 as well).

To wrap it up, just for fun (no practical value to a Python coder at all), how would you make a lazy sequence in Python if it didn't support generators or iterators? The way the lisp gods did before us... (lazy cons streams)

def fibonacci(a=0, b=1):
return (a, lambda: fibonacci(b, a + b))

def take(n, seq):
if n:
return (seq[0], lambda: take(n - 1, apply(seq[1])))

def lmap(f, seq):
while seq:
yield f(seq[0])
seq = apply(seq[1])

print sum(lmap(int, take(1000, fibonacci())))

(I know, I cheated with the lmap function, but Pythons recursive limit makes it a bit impractical)

11 comments:

Adam Byrtek said...

When it comes to laziness in Python you might be also interested in this presentation.

David Goodger said...

"With GE I'm forced to either call the int function twice, or to break it up across lines:"

You can do it in one (logical) line easily:

print sum(x for x in (int(x) for x in "1 2 3 4 5 6 7 8 9".split()) if even(x))

Generator expressions are perfectly valid in for loops, even nested ones.

Wybiral said...

"You can do it in one (logical) line easily"

Yes, definitely. My problem with that is that it starts to get hard to read when you have multiple LCs or GEs (lots of "for in" ... "if"s to visually parse).

IMO, imap and ifilter are still the best way to represent that, visually.

Calvin Spealman said...

These are all good tips to be aware of, but some times the obvious may be deceptive.

The list comprehension might get used and thrown away, and that sure feels pretty wasteful. However, we always forget about the hidden costs of generators (and their expression cousins). Sure, they're lazy computed and we save the storage of the whole list at once, but they also cost an extra function call (the generator's next() method). If the cost of computing each element is very small and the length is great enough, the cost of all those extra function call overheads and actually be greater than what you spend in cpu time to computer the values you're actually interested in. I've profiled it in a few cases and seen real examples where list comprehensions are faster than generator expressions.

Unless the list would be very large, don't kick those square brackets right away.

Wybiral said...

"but they also cost an extra function call (the generator's next() method)"

Even with containers like lists, the next method is being called... All iterations in Python work like that (unless some builtins are optimized behind the scenes). "for" calls "__iter__" and returns an object with a "next"

Generators could have a minor coefficient performance overhead from however it preserves state between calls. But conceptually, building an entire list just for one iteration is wrong unless it's very tiny.

For the sake of scalability, I'd like to know that my LC isn't going to eat up all of my ram for some large sequence... Especially if it's just being used for one iteration :)

Calvin Spealman said...

Wybiral, I understand your concerns about large lists and that every iteration (supposedly) calls __iter__ and then makes lots of next() calls. However, the logic is subtly deceptive and it took me a long to realize how many cases are unintuitive more efficient with the list comprehension than the generator expression.

In particular, there is more overhead with the generator object than many people realize, so under a certain size list you're saving memory anyway by avoiding that. Secondly, as a list grows, it over-allocates space as an optimization on append and extend operations, so between the size steps it makes, there is no extra memory cost in larger lists. As you get larger and larger lists, the cost for more elements is more and more often zero, because the memory would be allocated for its pointer array anyway. As for the next() calls, the deceptive bit here is the difference between calling listiterator.next(), a builtin function versus the method-wrapper for generator.next() which in turn calls back into your python function (which you are creating, via a generator function or generator expression) and the overhead of a python function call is often the expensive bit here, relative to that of creating and iterating over the list.

Some people start out thinking in these cases a generator expression is always better. Most come to see that for small lists, the list comprehension can still be better, but know that when it gets large you use a generator expression. Where the deception happens is where the line is drawn between small and large lists that make it worth one over the other.

My argument is just that the list comprehension is appropriate in more situations than most people realize.

Wybiral said...

Yes, it's certainly appropriate for some, but what we're seeing here is minor coefficient penalty with GE at the cost of constant memory versus linear memory increase with LC and only a minimal performance improvement (if any on some platforms and future implementations)

Then you also have to consider where you want to break the computational load up at... Generation time, or use time. With LC, you're bulk-applying the function in one swoop, whereas GEs distribute the computation to each use.

And in many cases, generators (not just GE, functions included) can do things that LC can't... Such as representing an infinite stream (at least until computers get infinite memory).

I'm looking at it from the perspective that a small coefficient penalty is worth the linear-vs-constant memory increase, and that breaking up the calls lazily is more appropriate in a number of situations.

Python3 is moving all of the old list-building stuff (map/filter/zip/range) into generators, so I'm sure they will also be concerned with improving the performance of generators... I assume they're doing this for a reason :)

Calvin Spealman said...

I suppose I'm looking at this from the context of examples like you were giving in the post. In particular, if you are consuming the entire generator immediately, which you are when you pass it (inline even) to a function like sum(), then the benefit shifts to LC more often than other times.

In other words, generators may be lazy, but you're still consuming it all at once, reducing the effectiveness and relevancy of lazy computations. Not that there aren't plenty of cases where its still good, of course.

The ideal would be an implementation that could pick the best on a case by case basis, but in the current design of Python, I am unsure how it would be possible. If we could determine purity of functions, we could know when a generator could safely be pre-executed, for example (possibly even in parallel). All just enjoying mental fun, for now.

Wybiral said...

"I suppose I'm looking at this from the context of examples like you were giving in the post. In particular, if you are consuming the entire generator immediately, which you are when you pass it (inline even) to a function like sum(), then the benefit shifts to LC more often than other times."

My examples were trivial just to show what I was talking about. Now assume that "sum" were a function that stopped iterating after it grabbed a certain value (such as "all" or "any")... With a list, you've wasted more time and space than needed.

This is the part I don't understand... You want the objects being produced, not a collection of them. Forget about the coefficient difference, that could all change between implementations. Think about what you're doing, it makes more sense not to build a list.

Even more power in generators comes from being able to conditionally construct a pipeline for data to flow through (read on streams from SICP).

Calvin Spealman said...

I was never denying the usefulness of generators: I love them. I was just claiming that a subset of the times where you could use a LC or a generator and people assume a generator to be better, an LC may actually be better. I'm not even claiming that a LC is more appropriate most of the time, just more times than many might realize.

This has gone on for a bit. I don't think we really disagree about anything here.

Wybiral said...

TonyD: I deleted your comment because it was unnecessarily vulgar. Not because it was critical. To your point of generators not having a __getitem__ method, this isn't mean to build sequences with random access. Its meant to build sequences to be iterated over later.

PS: I wont delete your comments if you tone down the language and hostility.