Haskell: How "cache" friendly is Lazy Eval / call by need

Question

I have been studying Haskell in my spare time for a couple of months now. I'm wondering how Haskell performs on the current stock hardware, in regards to the memory sub-system (L1, L2, L3 cache). Can someone please point me to any report/study on how cache friendly is Haskell because of its Lazy evaluation/call-by-need? Is there a way for us to get the info as to how many data cache misses and instruction cache misses happened and see if this is due to the lazy evaluation nature of the language?

Thanks.

Gilding

I've found cs.cmu.edu/~hdeyoung/15740/report.pdf ... will study this... please let me know if there are any other tools that come to your mind ... thanks – Gilding

Lazy evaluation may change when something is evaluated, but not how it is evaluated or how it is stored once evaluated. I think your questions about cache efficiency would be better directed at, e.g., how allocation and garbage collection interact with caches, heap vs. stack utilization, which structures have good locality, etc. – Imposture

@ReinHenrichs Laziness might be more relevant than that. Temporal locality is important as well. Even though a Haskell array or vector would have good space locality, I could see laziness causing cache misses due to poor temporal locality in some situations if expressions get evaluated in a cache-inefficient order. I can't think of a very concrete example off the top of my head unfortunately but I'm picturing a scenario where, due to laziness, a vector is accessed in small pieces spread between other operations, where it would be more efficient to do those vector operations all at once. – Printable

@DavidYoung Good points! – Imposture

I've found another interesting article on this topic: cs.cmu.edu/~rwh/papers/iolambda-cacm/cacm.pdf – Organize

Answer 1

This is primary a question of runtime value representation. Most types in Haskell are "lifted", i.e., they may contain bottom. In reality, this means that even Int is represented by a pointer, either to a machine Int or a computation (which could diverge, i.e.,bbottom).

Here is a quick primer on boxed vs. lifted (vs. primitive). I.e., Array# is not lifted, as it may not be bottom, but it is boxed, as it may contain lifted values.

So what does that have to do with non-strict evaluation? A non-evaluated computation is called a "thunk". Having a linked list of pointers to Ints is way worse for cache locality then having a compact array of machine integers and so is chasing pointers to thunks.

That is why there has been much research and engineering on demand analysis - if a the value of a computation will be needed anyway, it can be made strict.

AFAIK, "boxity" analysis is part of demand analysis. Anyway, GHC will try to get rid of pointers where possible.

But unfortunately I don't have any empirical data or studies on this.

EDIT: Some more reading on strictness/boxity analysis:

GHC -fstrictness

Demand analyzer in GHC

SO Answer by Richard Eisenberg, giving some more clarification on "levity" (lifted/unlifted), bottom and undefined.

Edit2:

Found a paper from 2002: Nethercote, Mycroft; The cache behaviour of large lazy functional programs on stock hardware

Cathrine

I don't believe it is the case that you ever have a pointer to bottom (i.e. "Int is represented by a pointer, either to a machine Int or bottom" isn't quite right). Bottom isn't an in-memory structure, it's a computation that doesn't terminate, throws an exception, or otherwise fails to give you an in-memory value at all. Lifted types are represented by pointers so that they can be thunks (in which case they need to be pointers to code to run to produce the value), which also means that the types must contain bottom (because the code might not terminate). – Aberration

@Aberration thanks, you are absolutely right, bottom is not an actual value. I have amended my answer and also added a link to a SO answer by Richard Eisenberg which I found very informative, about bottom, undefined and levity. – Cathrine