Haskell中where子句的性能差异疑问：为何exam2比exam1慢？

Let's break down why you're seeing this counterintuitive performance result—great catch by the way, this gets to the heart of Haskell's lazy evaluation and how GHC optimizes for memory vs. computation.

First, let's recap the two functions we're comparing:

exam1 :: Int -> [Int]
exam1 n = [1 .. n] ++ [1 .. n]

exam2 :: Int -> [Int]
exam2 n = list ++ list where list = [1 .. n]

What's happening with exam1 under -O2? #

Thompson's book notes exam1 computes [1..n] twice, but with lazy evaluation and GHC's optimizations, this doesn't mean storing two full lists in memory at once.

When exam1 runs:

• The ++ operator first traverses the first [1..n], generating elements on demand as they're needed (for output or further processing). Once an element is consumed, it can immediately be garbage collected (GC'd) because there's no remaining reference to it.
• Then it moves to the second [1..n], doing the same lazy generation and immediate GC of elements.

The result is that exam1 uses constant-ish space (O(1) or O(k) where k is the small buffer size for streaming) and avoids the overhead of allocating and holding a huge list in memory. Even though it's generating the sequence twice, this computation is cheap and cache-friendly—since elements are generated and used locally, they stay in CPU cache instead of hitting slow main memory.

Why is exam2 slower? #

The where clause in exam2 forces sharing of the list value. Here's what happens:

• To satisfy both uses of list in list ++ list, GHC has to fully evaluate [1..n] and store the entire list in memory. This means allocating O(n) space for 1 million integers—no lazy streaming here, because the list needs to be referenced twice.
• When ++ runs, it first traverses the full stored list, then traverses it again. But since the list is so large, most of it will live in main memory instead of CPU cache. This leads to frequent cache misses (when the CPU has to fetch data from slow main memory), which drastically slows down the traversal.
• On top of that, allocating and later GC'ing a 1 million-element list adds significant overhead that the streaming approach in exam1 avoids.

Why doesn't -O2 fix this? #

GHC's -O2 does a lot of optimizations, but it won't override explicit sharing unless it can prove that sharing is worse. In exam2, your code explicitly tells GHC to share list, so the optimizer respects that choice. For exam1, the lack of a shared binding lets GHC choose the more memory-efficient streaming approach, which ends up being faster for large n.

If you tested with a smaller n (like 10,000 instead of 1,000,000), you'd likely see exam2 outperform exam1—the list would fit in CPU cache, so the shared traversal would be cheaper than generating the sequence twice. But for large datasets, the memory and cache overhead of sharing dominates.

内容的提问来源于stack exchange，提问作者Dominik Schrempf