Why is [x|x<-[1..10]] method so slow in Haskell?

Question

Why is something like this runs extremely slow in Haskell?

test = [x|a<-[1..100],b<-[1..100],c<-[1..100],d<-[1..100],let x = a]

print $ length test

There are only about 10^8 numbers to run, it should be done in a blink of eye, but it seems like running forever and almost crashed.

Answer 1

Are you running this in ghci or in a compiled program? It makes a big difference.

If in ghci, then ghci will keep the computed value of test around in case you want to use it later. Normally this is a good idea, but not in this case where test is a huge value that would be cheap to recompute anyways. How huge? For starters it's a list of 10^8 elements, and (on a 64-bit system) a list costs 24 bytes per element, so that's 2.4G already. Then there is space usage of the values themselves. One might think the values are all taken from [1..100], so they should be shared and use a negligible amount of space in total. But the values in the list are really of the form x, which could depend on a, b, c and d, and length never examines the values in the list as it traverses it. So each element is going to be represented as a closure that refers to a, b, c and d, which takes at least 8*(4+1) = 40 more bytes, bringing us to a total of 6.4G.

That's rather a lot, and the garbage collector has to do quite a lot of copying when you allocate 6.4G of data, all of it permanently live. That's what takes so long, not actually computing the list or its length.

If you compile the program

test = [x|a<-[1..100],b<-[1..100],c<-[1..100],d<-[1..100],let x = a]

main = print $ length test

then test does not have to be kept live as its length is being computed, as clearly it is never going to be used again. So now the GC has almost no work to do, and the program runs in a couple seconds (reasonable for ~10^8 list node allocations and computations on Integer).