Speaker 1: You know, we're so used to physical predictability when we
Speaker 1: write code. We expect our tools to behave like, well,
Speaker 1: like carpentry, right.
Speaker 2: Like you can measure everything out perfectly exactly.
Speaker 1: You allocate an array of one hundred injagers and you
Speaker 1: can calculate the exact byte size it'll consume in memory.
Speaker 1: But when you step into the world of pure functional programming,
Speaker 1: that predictability often just vanishes.
Speaker 2: Oh, it completely shatters the mental model we bring over
Speaker 2: from traditional imperative environments.
Speaker 1: Yeah, you write this beautiful, mathematically pure pipeline of data transformations,
Speaker 1: and for some inexplicable reason, a one liner mysteriously heats
Speaker 1: up eight hundred megabytes of memory and just hard crashes
Speaker 1: your machine.
Speaker 2: Which is incredibly frustrating. We assume a direct step by
Speaker 2: step translation from the code we read on the screen
Speaker 2: to the execution on the physical hardware.
Speaker 1: Right, But in a language built on pure math, the
Speaker 1: relationship between syntax and physical ram is heavily mediated by
Speaker 1: the compiler, and that creates some very very murky diagnostic waters.
Speaker 2: It really does. It can feel like a dark art
Speaker 2: if you don't know what you're looking at and.
Speaker 1: Clearing up those muddy waters is exactly what we are
Speaker 1: doing today. Yeah, welcome to a brand new deep dive
Speaker 1: into the source material. We are exploring the hidden mechanics
Speaker 1: of functional programming performance, guided by Samuel Thompson's incredibly thoroughbook
Speaker 1: Haskell High Performance Programming.
Speaker 2: It's such a critical source because it tackles a pervasive myth,
Speaker 2: this idea that writing fast Haskell code is some kind
Speaker 2: of academic sorcery.
Speaker 1: Yeah, which it isn't, right.
Speaker 2: Not at all. The reality is much more grounded. It's
Speaker 2: simply about understanding the physical realities of the memory graph.
Speaker 1: So for you listening, whether you are actively writing functional
Speaker 1: code and production or you're just intensely curious about compiler
Speaker 1: design and language architecture, our mission today is to demystify this.
Speaker 2: We're going to uncover how to build a concrete mental
Speaker 2: model of Haskell's performance.
Speaker 1: We'll find out why those elegant one liners sometimes cause
Speaker 1: massive space leaks, and how to engineer them for bed
Speaker 1: without sacrificing the beauty of the language. And it really
Speaker 1: all starts with the foundational design choice of the language,
Speaker 1: which is lazy evaluation.
Speaker 2: Laziness is the engine of Haskell right now, and it
Speaker 2: is a double edged sword. I mean, it's the source
Speaker 2: of the language's ability to handle infinite data structures, but
Speaker 2: it is also the root cause of its most infamous
Speaker 2: memory crashes because it just defers everything exactly. To understand
Speaker 2: the performance, we have to look at what laziness actually
Speaker 2: means under the hood. It means the run time defers
Speaker 2: actual computation until the absolute last possible moment.
Speaker 1: So when you declare a value, Haskell doesn't actually calculate it.
Speaker 2: No, it creates a thunk.
Speaker 1: A thunk, which is let's break down what a thunk
Speaker 1: looks like in physical memory, because it's not just a
Speaker 1: theoretical concept, is it not at all?
Speaker 2: In the GHC run time the Glasgow Haskell compiler, a
Speaker 2: thunk is a physical heap object. Okay, it consists of
Speaker 2: a header word, a pointer to the code that will
Speaker 2: eventually perform the evaluation, and crators to the free variable
Speaker 2: or the environment needed for that calculation.
Speaker 1: Wait, so instead of just storing a tiny sixty four
Speaker 1: bit integer, you might be allocating several machine words on
Speaker 1: the heap just to represent the promise of an integer.
Speaker 2: You are storing the instructions for how to get the
Speaker 2: integer later.
Speaker 1: Yes, Okay, let's unpack this because I like to think
Speaker 1: of this as a terribly procrastinating friend.
Speaker 2: I like that analogy.
Speaker 1: Yeah, Like, instead of handing you the five dollars they
Speaker 1: owe you, they write you and iou on a sticky note,
Speaker 1: and they just keep doing this for every transaction.
Speaker 2: Right, just handing out paper.
Speaker 1: Exactly Eventually their pockets are bursting with a million sticky notes.
Speaker 1: The sheer physical weight of the paper, you know, the
Speaker 1: overhead of all those pointers in environment variables, literally.
Speaker 2: Crushes them heap exhaustion. That is exactly what happens when
Speaker 2: those IOUs pile up. Thomasin illustrates us perfectly with the
Speaker 2: fold l function, the standard left fold oh.
Speaker 1: The classic crash example.
Speaker 2: Yes, if you try to sum a list of a
Speaker 2: million numbers from one to ten to the six using
Speaker 2: the default full dell, the program will almost certainly crash
Speaker 2: with a heap exhaustion error because.
Speaker 1: It's building the IOUs instead of doing the arithmetic right.
Speaker 2: It doesn't evaluate one plus two to get three. It
Speaker 2: allocates a massive thunk in memory for one plus two.
Speaker 2: Then it looks at the next element three and allocates
Speaker 2: a new massive thunk that points to the previous thunk
Speaker 2: representing one plus two plus three.
Speaker 1: So before a single CPU cycle is spent on actual addition,
Speaker 1: you've built a million no deep tree of pointers in
Speaker 1: your RAM.
Speaker 2: You run out of memory just storing the instructions for
Speaker 2: what to add later.
Speaker 1: So the fix is forcing the friend to hand over
Speaker 1: the cash immediately, like we need a strict operation.
Speaker 2: That strict alternative is fold l prime. You know with
Speaker 2: the tick mark. The tick convention indicates that it forces
Speaker 2: the evaluation of the accumulator at every single step.
Speaker 1: It gashes in the IOU immediately.
Speaker 2: Exactly, it does the addition and passes a raw evaluated
Speaker 2: number to the next step. The program now runs in
Speaker 2: constant space zero of one entirely bypassing the memory leak.
Speaker 1: Which introduces a really interesting tension. If strictness solves the
Speaker 1: space leak. We just need to know how to force
Speaker 1: strictness in our own custom data pipelines. But when we
Speaker 1: tell Haskell to evaluate something, it doesn't necessarily evaluate the
Speaker 1: whole thing, does it.
Speaker 2: No, it doesn't, and that is where the concept of
Speaker 2: weakhead normal form or WHNF comes into play. It is
Speaker 2: a critical technical.
Speaker 1: Boundary week head normal form.
Speaker 2: Okay, when you use the system function seek to force evaluation,
Speaker 2: or when pattern matching forces a value, Haskell usually only
Speaker 2: evaluates the expression up to the very first data constructor
Speaker 2: it encounters.
Speaker 1: Let's trace the mechanics of that. Say I have a
Speaker 1: computation that generates a complex nested tupple like a pair
Speaker 1: containing two massive unevaluated lists. If I force that tupple
Speaker 1: with ck, what actually happens in memory?
Speaker 2: The runtime evaluates just enough to verify the outermost structure.
Speaker 2: It looks at the expression and resolve until it sees
Speaker 2: the comma the data constructor for the tupple, and then
Speaker 2: what it confirms, Yes, this is a tuple, and it stops.
Speaker 2: It does not force the evaluation of the lists inside
Speaker 2: the tupple. The inner elements remain as unevaluated thunks, so.
Speaker 1: It verifies the shape of the outer box, but ignores
Speaker 1: the contents completely. Why would the language designers make it
Speaker 1: stop there? Like? Why not just evaluate the whole thing
Speaker 1: all the way down to a normal form?
Speaker 2: Because of infinite structures. If psych recursively forced evaluation all
Speaker 2: the way down and you passed it an infinite list,
Speaker 2: your program would just hang forever trying to evaluate infinity.
Speaker 1: Ah right, it would just spin forever.
Speaker 2: We had normal form is the safety valve. It guarantees
Speaker 2: termination while allowing you to incrementally unroll structions. But it
Speaker 2: also means that if you blindly trust psych to fix
Speaker 2: your space leaks in deeply nested data, you will be disappointed.
Speaker 1: Because those internal thunks will still pile up and crash
Speaker 1: your program precisely, which means as a developer, you have
Speaker 1: to be highly aware of what level of depth you
Speaker 1: are forcing. And you know, speaking of unintended memory retention,
Speaker 1: the text brings up a fascinating trap regarding point free
Speaker 1: style and something called CS constant applicative forms.
Speaker 2: Yes, memalization. Usually memmalization is a tool we want storing
Speaker 2: intermediate results so we don't recalculate them. Is dynamic programming
Speaker 2: one oh one.
Speaker 1: Sure you want to save time.
Speaker 2: But in Haskell, because functions and values are treated the
Speaker 2: exact same way, you can accidentally trigger permanent memorization across
Speaker 2: the entire lifetime of your program.
Speaker 1: Walk us through the fibmem example. How does a simple
Speaker 1: mathematical sequence turn into a permanent memory leak.
Speaker 2: So if you define a Fibonacci sequence at the top
Speaker 2: level of your module using point free style, meaning you
Speaker 2: just write fib mem equals followed by a pipeline of
Speaker 2: functions mapping over a list without specifying an input parameter
Speaker 2: like by C. The GHC compiler looks at that and
Speaker 2: sees no variables.
Speaker 1: And to the compiler, an expression with no variables is
Speaker 1: just a constant.
Speaker 2: A constant applicative forms, and because it is a constant,
Speaker 2: GHC evaluates at once and caches the result in the
Speaker 2: global heap for the duration of the program. Wait.
Speaker 1: Wait, so if I call that function to find the
Speaker 1: ten thousand Fibonacci number, the run time permanently stores all
Speaker 1: ten thousand intermediate list nodes in RAM. Yes, and the
Speaker 1: garbage collector will just never touch it.
Speaker 2: Exactly because the reference is tied to a top level constant,
Speaker 2: the garbage collector assumes it might be needed again.
Speaker 1: That is wild.
Speaker 2: The fix is incredibly subtle. If you change the definition
Speaker 2: to fib memarg and equals, you've introduced a parameter. It
Speaker 2: is no longer a cf it is a function.
Speaker 1: Even if the core logic is completely identical.
Speaker 2: Yes, By applying an argument, you create a new local
Speaker 2: expression every time the function is called. Once the specific
Speaker 2: call finishes, the reference is dropped, and the garbage collector
Speaker 2: can instantly sweep away those ten thousand intermediate nodes. Wow,
Speaker 2: it proves a fundamental rule of high performance. Haskell syntax
Speaker 2: implies memory semantics.
Speaker 1: That is a staggering amount of power tied to the
Speaker 1: presence of a single letter in So what does this.
Speaker 2: All mean for the programmer, especially someone who loves that
Speaker 2: super clean point free style.
Speaker 1: It means context is everything. Point free is beautiful. But
Speaker 1: if you lift a heavy computation to the top level
Speaker 1: without arguments, you are fundamentally changing its memory life cycle.
Speaker 2: You're accidentally building a permanent monument in your ram.
Speaker 1: Exactly.
Speaker 2: Well, let's shift from the behavior of functions to the
Speaker 2: shape of the data itself. We've talked about thunks in
Speaker 2: the context of loops, but those pointers also dictate how
Speaker 2: basic variables are constructed.
Speaker 1: Right.
Speaker 2: We're used to primitives being unboxed by default in imperative languages,
Speaker 2: but Haskell forces us to realize that a standard ind
Speaker 2: or double is actually a data constructor.
Speaker 1: So we're paying a pointer tax on every single number.
Speaker 2: Every basic type is boxed. An intin Haskell is a
Speaker 2: constructor that wraps a pointer which points to the actual
Speaker 2: primitive integer the int hash on the heap.
Speaker 1: That indirection is required because, as we discussed that D
Speaker 1: might not be a number yet. It might be a thunk, right,
Speaker 1: it might be promise. It's like having a map to
Speaker 1: a warehouse. I don't hold the number, I hold the
Speaker 1: coordinates to the warehouse, and I have to travel there
Speaker 1: to find out what the number is.
Speaker 2: That's a great way to visualize it.
Speaker 1: And if I have an array of a million integers,
Speaker 1: I don't have a dense block of numbers. I have
Speaker 1: an array of a million maps.
Speaker 2: And the overhead of those maps is catastrophic for high
Speaker 2: performance computing. Thomasin provides a benchmark with a custom pair
Speaker 2: data structure. A lazy standard pair holding two integers took
Speaker 2: up three hundred and seventy kilobytes of heat memory for
Speaker 2: one thousand iterations.
Speaker 1: Just to hold one thousand coordinate pairs three hundred and
Speaker 1: seventy kilobytes. How do we strip the maps away and
Speaker 1: just store the raw data?
Speaker 2: You use the unpack pragma in your data definition, combined
Speaker 2: with strictness annotations the bang pattern exclamation point. Right, You
Speaker 2: are essentially making a contract with the compiler. You're saying,
Speaker 2: I promise this field will always be evaluated strictly, so
Speaker 2: it will never be a thunk. Therefore, you can strip
Speaker 2: away the pointer and embed the raw in hash directly
Speaker 2: into the.
Speaker 1: Parent structure, and the memory difference in the benchmark it.
Speaker 2: Dropped from three hundred and seventy kilobytes down to just
Speaker 2: fifty kiloball.
Speaker 1: That is a sevenfold reduction just by eliminating the indirection.
Speaker 1: But there is a catch here. With polymorphism, we can't
Speaker 1: just untack everything.
Speaker 2: No, you cannot unpack polymorphic types or some types. If
Speaker 2: you have a generic data structure tree A, the compiler
Speaker 2: has no idea how many bytes A will require at.
Speaker 1: Compile time, because it could be anything, right.
Speaker 2: It could be an eight byte integer or a massive
Speaker 2: custom record. To handle that uncertainty, the compiler must use
Speaker 2: a uniform representation a pointer. Unboxing requires the compiler to
Speaker 2: know the exact fixed physical byte size of the data
Speaker 2: at compile time.
Speaker 1: That makes perfect sense. You can't embed an object if
Speaker 1: you don't know its dimensions. But if primitive numbers carry
Speaker 1: this kind of overhead, I shudder to think about how
Speaker 1: Haskell handles text Because drings are notorious in functional programming.
Speaker 2: Oh it is the most common performance trap for developers
Speaker 2: migrating to Haskell. The default string type is defined as
Speaker 2: a linked list of characters, which.
Speaker 1: Means every single letter in Hello world is a separate
Speaker 1: node on the.
Speaker 2: Heap, a node with a pointer to the character and
Speaker 2: a pointer to the next node. Furthermore, a char in
Speaker 2: Haskell is a full thirty one bit Unicode.
Speaker 1: Point that's incredibly bloated.
Speaker 2: The memory bloat plus the constant pointer chasing makes default
Speaker 2: strings completely unusable for heavy parsing or text manipulation. The
Speaker 2: modern standard is to immediately reach for the text library,
Speaker 2: which represents data internally as a packed UTF sixteen array
Speaker 2: or byte string for rowbites.
Speaker 1: But switching to text isn't just about shrinking the memory footprint.
Speaker 1: It unlocks one of the most powerful compiler optimizations in
Speaker 1: the GHC, which is stream fusion.
Speaker 2: Yes, stream fusion is incredible.
Speaker 1: Here's where it gets really interesting. Let's dig into the
Speaker 1: mechanics of this because I was reading this section and
Speaker 1: it sounds like actual magic.
Speaker 2: It feels like magic, but it's based on rigorous mathematical
Speaker 2: rewrite rules. Suppose you write a pipeline to process a
Speaker 2: text document, you want to convert it to uppercase, filter
Speaker 2: out the punctuation, and then take the length.
Speaker 1: So t dot length composed with t dot filter composed
Speaker 1: with t dot to upper exactly.
Speaker 2: In a naive run time, chaining three functions like that
Speaker 2: would allocate three separate arrays in memory. It would pass
Speaker 2: the entire document through uppercase, create a new massive array,
Speaker 2: pass that through the filter, create another array, and finally
Speaker 2: count the length.
Speaker 1: Which would absolutely kill your CPU cache.
Speaker 2: But stream fusion prevents that. The text library defines intermediate
Speaker 2: operations using a generic step data type yielding a value
Speaker 2: skipping or finishing. GHC uses specific rewrite rules like fold,
Speaker 2: slash build rules to transform the abstract syntax tree during compilation.
Speaker 1: Okay, so what does it actually do to the code.
Speaker 2: When it sees these chained operations. It mathematically fuses them
Speaker 2: into a single tight impair arative style loop over the
Speaker 2: underlying ut F sixteen array.
Speaker 1: Hold on, so it literally rewrites the ast. If I
Speaker 1: chain those three abstract functions, the compiler doesn't execute them sequentially, Nope,
Speaker 1: it e merges the uppercase logic, the filter logic, and
Speaker 1: the counter into a single loop, passing each character through
Speaker 1: all three steps before moving to the next character exactly.
Speaker 2: It completely eliminates the intermediate arrays. The intermediate data structures
Speaker 2: never actually exist in the compiled machine code.
Speaker 1: That is fascinating, you know, in imperative languages, to avoid
Speaker 1: those intermediate arrays, I would be forced to write a
Speaker 1: messy hand optimized wild loop, manually tracking the index and
Speaker 1: cramming all the logic into one block.
Speaker 2: Which is awful to read and maintain.
Speaker 1: Right, But here the abstraction is actually the enabler. Writing
Speaker 1: the high level, mathematically pure pipeline is what gives the
Speaker 1: compiler the map it needs to generate the optimized loop.
Speaker 2: The purity is what makes it possible, because the compiler
Speaker 2: mathematically guarantees there are no side effects. It knows it
Speaker 2: is safe to reorder and fuse the operation. The text
Speaker 2: also highlights a similar architectural trick for lists called difference lists.
Speaker 1: Oh yeah, tell me about difference lists.
Speaker 2: Standard list appending with a plus plus operator traverses the
Speaker 2: entire left hand list, which takes O of n time
Speaker 2: and builds up massive funk structures if nested.
Speaker 1: Which we know leads to heap exhaustion.
Speaker 2: Right, a difference list transforms the data structure into a function.
Speaker 2: Instead of storing the list one, two, three, you store
Speaker 2: function that propens one, two, three to another list. Oh.
Speaker 1: I see. By turning the data into a function, you
Speaker 1: can use function composition to append them.
Speaker 2: Right, You use the composition operator instead of a pend
Speaker 2: function composition is constant time oh of one. You defer
Speaker 2: the actual construction of the list until you finally apply
Speaker 2: the accumulated function to an empty list at the very end.
Speaker 2: It is a.
Speaker 1: Brilliant way to turn a performance bottleneck into a constant
Speaker 1: time operation purely through mathematical abstraction. I love the elegance
Speaker 1: of that. It's very elegant. But I have to play
Speaker 1: the skeptic here for a second. There is a ceiling
Speaker 1: to clever abstractions. What if I am doing heavy digital
Speaker 1: signal processing or massive matrix mathematics, I need raw contiguous
Speaker 1: Raisin memory and I need to mutate data in place.
Speaker 1: Doesn't functional purity just hit a brick wall? There?
Speaker 2: It does if you stay in this standard pure paradigm.
Speaker 2: Thomasin addresses this in the sections covering tabular data and
Speaker 2: the vector package. He gives a benchmark involving statistical windowing
Speaker 2: over a million random time stamps and observations.
Speaker 1: In the classic data science operation. How did the pure
Speaker 1: proach handle it?
Speaker 2: Even using unboxed vectors. A naive run with standard compiler
Speaker 2: settings was abysmal. The program consumed one hundred and thirty
Speaker 2: eight megabytes of memory, and more tellingly, it's meant twenty
Speaker 2: eight percent of its total execution time paused doing garbage collection.
Speaker 1: Spending nearly a third of your CPU time just taking
Speaker 1: out the trash is totally unacceptable for high performance.
Speaker 2: But the first line of defense is simply unleashing the compiler.
Speaker 2: By passing the DASHO two optimization flag to GHC, which
Speaker 2: turns on aggressive inlining infusion rules, the performance pro file
Speaker 2: drastically changes or the numbers. The memory footprint drops from
Speaker 2: one hundred and thirty eight megabytes to nineteen megabytes, and
Speaker 2: garbage collection drops to just one point three percent of
Speaker 2: the execution time.
Speaker 1: That is a staggering improvement for a single compiler flag.
Speaker 1: But let's push it further. Let's say I absolutely definitively
Speaker 1: need true in place mutation. I need to update a
Speaker 1: specific index in a massive array a million times without
Speaker 1: copying the array Okay, if I do that in Haskell
Speaker 1: using the mutable STMAD, aren't I just admitting defeat? Aren't
Speaker 1: I just writing C code but awkwardly forcing it into
Speaker 1: Haskell syntax.
Speaker 2: It's a very common critique, but it misses the architectural
Speaker 2: brilliance of the stmnad state threads. Yes, the stmonid gives
Speaker 2: you strough for mutable variables and mutable arrays that update
Speaker 2: in place, right, But it doesn't compromise the global architecture
Speaker 2: of your program because it uses the type system to
Speaker 2: enforce a strict quarantine.
Speaker 1: Explain the quarantine. How does the compiler know the mutation
Speaker 1: won't leak out and cause side effects elsewhere?
Speaker 2: It relies on a phantom type parameter. If you look
Speaker 2: at the type signature for the st monad, it has
Speaker 2: a type variable S like STSA okay, wait is es
Speaker 2: that's S represents the specific thread of state. When you
Speaker 2: use the run s two function to execute this mutable
Speaker 2: block and extract the pure result, run st uses rank
Speaker 2: to polymorphism. It requires the state type as to be universally.
Speaker 1: Quantified, meaning what for the compiler.
Speaker 2: It acts like a cryptographic lock. If your code tries
Speaker 2: to return a mutable reference or let a piece of
Speaker 2: mutable state escape the run a st block. The type
Speaker 2: checker physically cannot unify the types. It will throw a
Speaker 2: compile time error.
Speaker 1: Oh wow.
Speaker 2: It mathematically proves that the mutation is contained.
Speaker 1: So the inner block is a black box. Inside the box,
Speaker 1: you can write the dirtiest, fastest CE style mutating loops
Speaker 1: you want. But to the rest of the Hauskell program,
Speaker 1: that box is just a pure function taking an input
Speaker 1: and returning a deterministic output.
Speaker 2: Exactly. You isolate the imperative speed locally without polluting the
Speaker 2: purity of your global system. It proves you don't have
Speaker 2: to sacrifice safety for raw metal performance as long as
Speaker 2: your compiler is strict enough to enforce the boundaries.
Speaker 1: We've covered a massive amount of ground today. We've seen
Speaker 1: that high performance Taskell isn't about sorcery. It's about physical reality.
Speaker 2: It really is.
Speaker 1: It requires navigating the memory graph, knowing when laziness will
Speaker 1: build a mountain of thunks, and knowing how to crack
Speaker 1: the whip with the bang pattern, strict folds and unboxed primitives.
Speaker 1: It requires abandoning linkedless strings for dense UTF sixteen arrays
Speaker 1: and fundamentally trusting ghc's fusion rules and optimization passes to
Speaker 1: do the heavy lifting.
Speaker 2: It is that aligning your high level abstractions with the
Speaker 2: compiler's expectations, so map your math efficiently to the hardware.
Speaker 1: Which leads us with a truly fascinating question to ponder.
Speaker 1: As GC and modern compilers continue to evolve, becoming increasingly
Speaker 1: capable of taking highly abstract, mathematically pure pipelines and automatically
Speaker 1: rewriting them into tight, in place machine code, where does
Speaker 1: that lead the developer?
Speaker 2: That's the big question.
Speaker 1: Will we eventually reach a tipping point where understanding thunks,
Speaker 1: memory semantics, and pointer overhead becomes entirely obsolete? Or will
Speaker 1: the physical reality of the machine, the CPU caches the RAM,
Speaker 1: the inevitable leaky abstraction of computing hardware always demand that
Speaker 1: software engineers eventually put down the map and peak under
Speaker 1: the hood. I think we'll always be peeking under the hood.
Speaker 1: To be honest, I think so too. Thank you for
Speaker 1: joining us on this deep dive into the source material.
Speaker 1: We hope it has equipped you with a sharper mental
Speaker 1: model of how your functional code breathes inside the machine.
Speaker 1: Keep testing your assumptions. Run your code base through the
Speaker 1: GPC profiler, and we'll catch you next time.