WEBVTT 1 00:00:00.120 --> 00:00:04.280 You know, we're so used to physical predictability when we 2 00:00:04.320 --> 00:00:08.039 write code. We expect our tools to behave like, well, 3 00:00:08.199 --> 00:00:09.320 like carpentry, right. 4 00:00:09.279 --> 00:00:11.800 Like you can measure everything out perfectly exactly. 5 00:00:12.119 --> 00:00:14.839 You allocate an array of one hundred injagers and you 6 00:00:14.880 --> 00:00:17.760 can calculate the exact byte size it'll consume in memory. 7 00:00:18.600 --> 00:00:22.600 But when you step into the world of pure functional programming, 8 00:00:23.280 --> 00:00:26.000 that predictability often just vanishes. 9 00:00:26.120 --> 00:00:29.039 Oh, it completely shatters the mental model we bring over 10 00:00:29.160 --> 00:00:32.039 from traditional imperative environments. 11 00:00:32.200 --> 00:00:36.759 Yeah, you write this beautiful, mathematically pure pipeline of data transformations, 12 00:00:37.200 --> 00:00:41.039 and for some inexplicable reason, a one liner mysteriously heats 13 00:00:41.119 --> 00:00:44.079 up eight hundred megabytes of memory and just hard crashes 14 00:00:44.119 --> 00:00:45.079 your machine. 15 00:00:44.719 --> 00:00:47.880 Which is incredibly frustrating. We assume a direct step by 16 00:00:47.920 --> 00:00:50.359 step translation from the code we read on the screen 17 00:00:50.399 --> 00:00:52.960 to the execution on the physical hardware. 18 00:00:52.719 --> 00:00:55.560 Right, But in a language built on pure math, the 19 00:00:55.640 --> 00:00:59.280 relationship between syntax and physical ram is heavily mediated by 20 00:00:59.320 --> 00:01:03.880 the compiler, and that creates some very very murky diagnostic waters. 21 00:01:04.040 --> 00:01:05.760 It really does. It can feel like a dark art 22 00:01:05.760 --> 00:01:07.519 if you don't know what you're looking at and. 23 00:01:07.519 --> 00:01:10.280 Clearing up those muddy waters is exactly what we are 24 00:01:10.280 --> 00:01:13.400 doing today. Yeah, welcome to a brand new deep dive 25 00:01:13.480 --> 00:01:16.719 into the source material. We are exploring the hidden mechanics 26 00:01:16.719 --> 00:01:21.599 of functional programming performance, guided by Samuel Thompson's incredibly thoroughbook 27 00:01:21.840 --> 00:01:23.599 Haskell High Performance Programming. 28 00:01:23.719 --> 00:01:26.959 It's such a critical source because it tackles a pervasive myth, 29 00:01:27.000 --> 00:01:29.840 this idea that writing fast Haskell code is some kind 30 00:01:29.879 --> 00:01:31.079 of academic sorcery. 31 00:01:31.239 --> 00:01:32.480 Yeah, which it isn't, right. 32 00:01:32.480 --> 00:01:35.280 Not at all. The reality is much more grounded. It's 33 00:01:35.319 --> 00:01:39.280 simply about understanding the physical realities of the memory graph. 34 00:01:39.400 --> 00:01:42.799 So for you listening, whether you are actively writing functional 35 00:01:42.840 --> 00:01:46.159 code and production or you're just intensely curious about compiler 36 00:01:46.200 --> 00:01:50.400 design and language architecture, our mission today is to demystify this. 37 00:01:50.519 --> 00:01:53.120 We're going to uncover how to build a concrete mental 38 00:01:53.120 --> 00:01:54.519 model of Haskell's performance. 39 00:01:54.599 --> 00:01:57.040 We'll find out why those elegant one liners sometimes cause 40 00:01:57.120 --> 00:02:00.239 massive space leaks, and how to engineer them for bed 41 00:02:00.359 --> 00:02:02.920 without sacrificing the beauty of the language. And it really 42 00:02:02.959 --> 00:02:05.400 all starts with the foundational design choice of the language, 43 00:02:05.400 --> 00:02:07.879 which is lazy evaluation. 44 00:02:08.400 --> 00:02:11.960 Laziness is the engine of Haskell right now, and it 45 00:02:12.039 --> 00:02:14.520 is a double edged sword. I mean, it's the source 46 00:02:14.560 --> 00:02:17.919 of the language's ability to handle infinite data structures, but 47 00:02:18.000 --> 00:02:20.599 it is also the root cause of its most infamous 48 00:02:20.599 --> 00:02:24.879 memory crashes because it just defers everything exactly. To understand 49 00:02:24.919 --> 00:02:27.599 the performance, we have to look at what laziness actually 50 00:02:27.680 --> 00:02:30.919 means under the hood. It means the run time defers 51 00:02:31.039 --> 00:02:35.039 actual computation until the absolute last possible moment. 52 00:02:35.240 --> 00:02:38.759 So when you declare a value, Haskell doesn't actually calculate it. 53 00:02:38.879 --> 00:02:40.000 No, it creates a thunk. 54 00:02:40.080 --> 00:02:42.520 A thunk, which is let's break down what a thunk 55 00:02:42.599 --> 00:02:45.120 looks like in physical memory, because it's not just a 56 00:02:45.159 --> 00:02:47.159 theoretical concept, is it not at all? 57 00:02:47.240 --> 00:02:50.360 In the GHC run time the Glasgow Haskell compiler, a 58 00:02:50.479 --> 00:02:54.080 thunk is a physical heap object. Okay, it consists of 59 00:02:54.120 --> 00:02:56.120 a header word, a pointer to the code that will 60 00:02:56.120 --> 00:02:59.840 eventually perform the evaluation, and crators to the free variable 61 00:03:00.240 --> 00:03:02.319 or the environment needed for that calculation. 62 00:03:02.520 --> 00:03:04.919 Wait, so instead of just storing a tiny sixty four 63 00:03:04.919 --> 00:03:08.199 bit integer, you might be allocating several machine words on 64 00:03:08.240 --> 00:03:11.039 the heap just to represent the promise of an integer. 65 00:03:11.080 --> 00:03:13.400 You are storing the instructions for how to get the 66 00:03:13.439 --> 00:03:14.080 integer later. 67 00:03:14.199 --> 00:03:17.840 Yes, Okay, let's unpack this because I like to think 68 00:03:17.840 --> 00:03:20.199 of this as a terribly procrastinating friend. 69 00:03:20.319 --> 00:03:21.400 I like that analogy. 70 00:03:21.599 --> 00:03:24.439 Yeah, Like, instead of handing you the five dollars they 71 00:03:24.479 --> 00:03:28.000 owe you, they write you and iou on a sticky note, 72 00:03:28.120 --> 00:03:30.599 and they just keep doing this for every transaction. 73 00:03:30.199 --> 00:03:31.319 Right, just handing out paper. 74 00:03:31.479 --> 00:03:36.039 Exactly Eventually their pockets are bursting with a million sticky notes. 75 00:03:36.680 --> 00:03:40.080 The sheer physical weight of the paper, you know, the 76 00:03:40.120 --> 00:03:44.080 overhead of all those pointers in environment variables, literally. 77 00:03:43.680 --> 00:03:47.080 Crushes them heap exhaustion. That is exactly what happens when 78 00:03:47.080 --> 00:03:50.479 those IOUs pile up. Thomasin illustrates us perfectly with the 79 00:03:50.520 --> 00:03:53.159 fold l function, the standard left fold oh. 80 00:03:53.039 --> 00:03:54.439 The classic crash example. 81 00:03:54.560 --> 00:03:56.639 Yes, if you try to sum a list of a 82 00:03:56.759 --> 00:03:59.800 million numbers from one to ten to the six using 83 00:03:59.840 --> 00:04:03.319 the default full dell, the program will almost certainly crash 84 00:04:03.400 --> 00:04:05.439 with a heap exhaustion error because. 85 00:04:05.240 --> 00:04:08.039 It's building the IOUs instead of doing the arithmetic right. 86 00:04:08.360 --> 00:04:11.240 It doesn't evaluate one plus two to get three. It 87 00:04:11.319 --> 00:04:14.520 allocates a massive thunk in memory for one plus two. 88 00:04:14.840 --> 00:04:18.000 Then it looks at the next element three and allocates 89 00:04:18.000 --> 00:04:20.920 a new massive thunk that points to the previous thunk 90 00:04:21.199 --> 00:04:23.480 representing one plus two plus three. 91 00:04:23.680 --> 00:04:27.040 So before a single CPU cycle is spent on actual addition, 92 00:04:27.519 --> 00:04:30.959 you've built a million no deep tree of pointers in 93 00:04:31.040 --> 00:04:31.519 your RAM. 94 00:04:31.959 --> 00:04:35.079 You run out of memory just storing the instructions for 95 00:04:35.120 --> 00:04:35.920 what to add later. 96 00:04:36.240 --> 00:04:38.639 So the fix is forcing the friend to hand over 97 00:04:38.639 --> 00:04:42.079 the cash immediately, like we need a strict operation. 98 00:04:42.360 --> 00:04:45.720 That strict alternative is fold l prime. You know with 99 00:04:45.759 --> 00:04:48.519 the tick mark. The tick convention indicates that it forces 100 00:04:48.560 --> 00:04:51.240 the evaluation of the accumulator at every single step. 101 00:04:51.360 --> 00:04:53.759 It gashes in the IOU immediately. 102 00:04:53.319 --> 00:04:56.480 Exactly, it does the addition and passes a raw evaluated 103 00:04:56.560 --> 00:04:59.000 number to the next step. The program now runs in 104 00:04:59.040 --> 00:05:03.079 constant space zero of one entirely bypassing the memory leak. 105 00:05:02.920 --> 00:05:06.720 Which introduces a really interesting tension. If strictness solves the 106 00:05:06.720 --> 00:05:08.639 space leak. We just need to know how to force 107 00:05:08.720 --> 00:05:13.040 strictness in our own custom data pipelines. But when we 108 00:05:13.079 --> 00:05:16.560 tell Haskell to evaluate something, it doesn't necessarily evaluate the 109 00:05:16.600 --> 00:05:17.399 whole thing, does it. 110 00:05:17.759 --> 00:05:20.079 No, it doesn't, and that is where the concept of 111 00:05:20.120 --> 00:05:24.480 weakhead normal form or WHNF comes into play. It is 112 00:05:24.560 --> 00:05:26.319 a critical technical. 113 00:05:25.879 --> 00:05:27.439 Boundary week head normal form. 114 00:05:27.560 --> 00:05:31.600 Okay, when you use the system function seek to force evaluation, 115 00:05:32.120 --> 00:05:36.279 or when pattern matching forces a value, Haskell usually only 116 00:05:36.360 --> 00:05:39.560 evaluates the expression up to the very first data constructor 117 00:05:39.600 --> 00:05:40.199 it encounters. 118 00:05:40.279 --> 00:05:42.800 Let's trace the mechanics of that. Say I have a 119 00:05:42.839 --> 00:05:46.879 computation that generates a complex nested tupple like a pair 120 00:05:46.959 --> 00:05:51.839 containing two massive unevaluated lists. If I force that tupple 121 00:05:51.879 --> 00:05:54.240 with ck, what actually happens in memory? 122 00:05:54.480 --> 00:05:58.240 The runtime evaluates just enough to verify the outermost structure. 123 00:05:58.439 --> 00:06:00.920 It looks at the expression and resolve until it sees 124 00:06:00.920 --> 00:06:03.160 the comma the data constructor for the tupple, and then 125 00:06:03.199 --> 00:06:06.160 what it confirms, Yes, this is a tuple, and it stops. 126 00:06:06.319 --> 00:06:08.759 It does not force the evaluation of the lists inside 127 00:06:08.759 --> 00:06:12.480 the tupple. The inner elements remain as unevaluated thunks, so. 128 00:06:12.480 --> 00:06:14.920 It verifies the shape of the outer box, but ignores 129 00:06:14.959 --> 00:06:17.879 the contents completely. Why would the language designers make it 130 00:06:17.879 --> 00:06:20.439 stop there? Like? Why not just evaluate the whole thing 131 00:06:20.480 --> 00:06:21.839 all the way down to a normal form? 132 00:06:22.079 --> 00:06:26.759 Because of infinite structures. If psych recursively forced evaluation all 133 00:06:26.800 --> 00:06:29.399 the way down and you passed it an infinite list, 134 00:06:29.759 --> 00:06:33.160 your program would just hang forever trying to evaluate infinity. 135 00:06:33.399 --> 00:06:35.839 Ah right, it would just spin forever. 136 00:06:35.639 --> 00:06:38.480 We had normal form is the safety valve. It guarantees 137 00:06:38.560 --> 00:06:42.120 termination while allowing you to incrementally unroll structions. But it 138 00:06:42.160 --> 00:06:44.720 also means that if you blindly trust psych to fix 139 00:06:44.759 --> 00:06:49.199 your space leaks in deeply nested data, you will be disappointed. 140 00:06:49.000 --> 00:06:51.920 Because those internal thunks will still pile up and crash 141 00:06:51.959 --> 00:06:55.079 your program precisely, which means as a developer, you have 142 00:06:55.120 --> 00:06:57.839 to be highly aware of what level of depth you 143 00:06:57.879 --> 00:07:02.519 are forcing. And you know, speaking of unintended memory retention, 144 00:07:03.040 --> 00:07:06.160 the text brings up a fascinating trap regarding point free 145 00:07:06.160 --> 00:07:09.839 style and something called CS constant applicative forms. 146 00:07:09.959 --> 00:07:14.439 Yes, memalization. Usually memmalization is a tool we want storing 147 00:07:14.480 --> 00:07:17.759 intermediate results so we don't recalculate them. Is dynamic programming 148 00:07:17.800 --> 00:07:18.279 one oh one. 149 00:07:18.399 --> 00:07:19.879 Sure you want to save time. 150 00:07:19.800 --> 00:07:22.600 But in Haskell, because functions and values are treated the 151 00:07:22.639 --> 00:07:27.160 exact same way, you can accidentally trigger permanent memorization across 152 00:07:27.160 --> 00:07:29.120 the entire lifetime of your program. 153 00:07:29.399 --> 00:07:32.319 Walk us through the fibmem example. How does a simple 154 00:07:32.360 --> 00:07:35.720 mathematical sequence turn into a permanent memory leak. 155 00:07:36.279 --> 00:07:38.879 So if you define a Fibonacci sequence at the top 156 00:07:39.000 --> 00:07:41.439 level of your module using point free style, meaning you 157 00:07:41.480 --> 00:07:44.720 just write fib mem equals followed by a pipeline of 158 00:07:44.759 --> 00:07:48.759 functions mapping over a list without specifying an input parameter 159 00:07:49.000 --> 00:07:52.079 like by C. The GHC compiler looks at that and 160 00:07:52.120 --> 00:07:53.399 sees no variables. 161 00:07:53.439 --> 00:07:56.120 And to the compiler, an expression with no variables is 162 00:07:56.199 --> 00:07:57.560 just a constant. 163 00:07:57.800 --> 00:08:02.480 A constant applicative forms, and because it is a constant, 164 00:08:02.560 --> 00:08:05.600 GHC evaluates at once and caches the result in the 165 00:08:05.639 --> 00:08:07.759 global heap for the duration of the program. Wait. 166 00:08:07.800 --> 00:08:09.480 Wait, so if I call that function to find the 167 00:08:09.519 --> 00:08:13.519 ten thousand Fibonacci number, the run time permanently stores all 168 00:08:13.560 --> 00:08:17.000 ten thousand intermediate list nodes in RAM. Yes, and the 169 00:08:17.040 --> 00:08:18.920 garbage collector will just never touch it. 170 00:08:19.240 --> 00:08:23.079 Exactly because the reference is tied to a top level constant, 171 00:08:23.279 --> 00:08:25.680 the garbage collector assumes it might be needed again. 172 00:08:26.040 --> 00:08:27.000 That is wild. 173 00:08:27.160 --> 00:08:30.120 The fix is incredibly subtle. If you change the definition 174 00:08:30.199 --> 00:08:33.399 to fib memarg and equals, you've introduced a parameter. It 175 00:08:33.440 --> 00:08:35.519 is no longer a cf it is a function. 176 00:08:35.559 --> 00:08:37.960 Even if the core logic is completely identical. 177 00:08:38.120 --> 00:08:41.600 Yes, By applying an argument, you create a new local 178 00:08:41.639 --> 00:08:44.960 expression every time the function is called. Once the specific 179 00:08:45.000 --> 00:08:48.159 call finishes, the reference is dropped, and the garbage collector 180 00:08:48.200 --> 00:08:52.200 can instantly sweep away those ten thousand intermediate nodes. Wow, 181 00:08:52.720 --> 00:08:57.840 it proves a fundamental rule of high performance. Haskell syntax 182 00:08:57.960 --> 00:09:00.480 implies memory semantics. 183 00:09:00.200 --> 00:09:02.919 That is a staggering amount of power tied to the 184 00:09:02.960 --> 00:09:06.399 presence of a single letter in So what does this. 185 00:09:06.360 --> 00:09:09.399 All mean for the programmer, especially someone who loves that 186 00:09:09.600 --> 00:09:11.960 super clean point free style. 187 00:09:12.240 --> 00:09:15.879 It means context is everything. Point free is beautiful. But 188 00:09:15.919 --> 00:09:18.360 if you lift a heavy computation to the top level 189 00:09:18.399 --> 00:09:21.879 without arguments, you are fundamentally changing its memory life cycle. 190 00:09:22.000 --> 00:09:24.639 You're accidentally building a permanent monument in your ram. 191 00:09:24.799 --> 00:09:25.399 Exactly. 192 00:09:25.720 --> 00:09:27.879 Well, let's shift from the behavior of functions to the 193 00:09:27.919 --> 00:09:30.360 shape of the data itself. We've talked about thunks in 194 00:09:30.399 --> 00:09:34.000 the context of loops, but those pointers also dictate how 195 00:09:34.039 --> 00:09:35.639 basic variables are constructed. 196 00:09:35.720 --> 00:09:35.919 Right. 197 00:09:36.200 --> 00:09:39.759 We're used to primitives being unboxed by default in imperative languages, 198 00:09:40.320 --> 00:09:43.200 but Haskell forces us to realize that a standard ind 199 00:09:43.279 --> 00:09:45.840 or double is actually a data constructor. 200 00:09:46.000 --> 00:09:48.240 So we're paying a pointer tax on every single number. 201 00:09:48.360 --> 00:09:51.440 Every basic type is boxed. An intin Haskell is a 202 00:09:51.480 --> 00:09:54.240 constructor that wraps a pointer which points to the actual 203 00:09:54.320 --> 00:09:57.039 primitive integer the int hash on the heap. 204 00:09:57.360 --> 00:10:01.480 That indirection is required because, as we discussed that D 205 00:10:01.600 --> 00:10:04.559 might not be a number yet. It might be a thunk, right, 206 00:10:04.679 --> 00:10:06.559 it might be promise. It's like having a map to 207 00:10:06.600 --> 00:10:09.759 a warehouse. I don't hold the number, I hold the 208 00:10:09.759 --> 00:10:12.240 coordinates to the warehouse, and I have to travel there 209 00:10:12.240 --> 00:10:13.320 to find out what the number is. 210 00:10:13.440 --> 00:10:15.039 That's a great way to visualize it. 211 00:10:15.080 --> 00:10:16.919 And if I have an array of a million integers, 212 00:10:16.919 --> 00:10:18.480 I don't have a dense block of numbers. I have 213 00:10:18.519 --> 00:10:20.759 an array of a million maps. 214 00:10:20.360 --> 00:10:23.200 And the overhead of those maps is catastrophic for high 215 00:10:23.200 --> 00:10:27.080 performance computing. Thomasin provides a benchmark with a custom pair 216 00:10:27.279 --> 00:10:31.440 data structure. A lazy standard pair holding two integers took 217 00:10:31.519 --> 00:10:34.200 up three hundred and seventy kilobytes of heat memory for 218 00:10:34.279 --> 00:10:35.720 one thousand iterations. 219 00:10:36.080 --> 00:10:38.879 Just to hold one thousand coordinate pairs three hundred and 220 00:10:38.919 --> 00:10:42.159 seventy kilobytes. How do we strip the maps away and 221 00:10:42.279 --> 00:10:43.360 just store the raw data? 222 00:10:43.600 --> 00:10:46.919 You use the unpack pragma in your data definition, combined 223 00:10:46.960 --> 00:10:51.960 with strictness annotations the bang pattern exclamation point. Right, You 224 00:10:52.000 --> 00:10:54.960 are essentially making a contract with the compiler. You're saying, 225 00:10:55.080 --> 00:10:58.759 I promise this field will always be evaluated strictly, so 226 00:10:58.799 --> 00:11:01.279 it will never be a thunk. Therefore, you can strip 227 00:11:01.279 --> 00:11:04.240 away the pointer and embed the raw in hash directly 228 00:11:04.279 --> 00:11:04.679 into the. 229 00:11:04.639 --> 00:11:07.559 Parent structure, and the memory difference in the benchmark it. 230 00:11:07.600 --> 00:11:10.480 Dropped from three hundred and seventy kilobytes down to just 231 00:11:10.519 --> 00:11:11.200 fifty kiloball. 232 00:11:11.320 --> 00:11:15.200 That is a sevenfold reduction just by eliminating the indirection. 233 00:11:15.440 --> 00:11:18.480 But there is a catch here. With polymorphism, we can't 234 00:11:18.480 --> 00:11:19.519 just untack everything. 235 00:11:19.639 --> 00:11:22.639 No, you cannot unpack polymorphic types or some types. If 236 00:11:22.639 --> 00:11:25.639 you have a generic data structure tree A, the compiler 237 00:11:25.679 --> 00:11:28.679 has no idea how many bytes A will require at. 238 00:11:28.559 --> 00:11:31.000 Compile time, because it could be anything, right. 239 00:11:30.879 --> 00:11:33.279 It could be an eight byte integer or a massive 240 00:11:33.320 --> 00:11:37.039 custom record. To handle that uncertainty, the compiler must use 241 00:11:37.080 --> 00:11:41.360 a uniform representation a pointer. Unboxing requires the compiler to 242 00:11:41.399 --> 00:11:45.080 know the exact fixed physical byte size of the data 243 00:11:45.159 --> 00:11:45.960 at compile time. 244 00:11:46.120 --> 00:11:48.919 That makes perfect sense. You can't embed an object if 245 00:11:48.919 --> 00:11:52.320 you don't know its dimensions. But if primitive numbers carry 246 00:11:52.320 --> 00:11:54.919 this kind of overhead, I shudder to think about how 247 00:11:54.960 --> 00:11:59.200 Haskell handles text Because drings are notorious in functional programming. 248 00:11:59.240 --> 00:12:02.159 Oh it is the most common performance trap for developers 249 00:12:02.240 --> 00:12:05.559 migrating to Haskell. The default string type is defined as 250 00:12:05.600 --> 00:12:07.639 a linked list of characters, which. 251 00:12:07.440 --> 00:12:10.159 Means every single letter in Hello world is a separate 252 00:12:10.200 --> 00:12:10.720 node on the. 253 00:12:10.679 --> 00:12:13.039 Heap, a node with a pointer to the character and 254 00:12:13.080 --> 00:12:16.320 a pointer to the next node. Furthermore, a char in 255 00:12:16.399 --> 00:12:19.519 Haskell is a full thirty one bit Unicode. 256 00:12:19.039 --> 00:12:20.759 Point that's incredibly bloated. 257 00:12:20.879 --> 00:12:24.120 The memory bloat plus the constant pointer chasing makes default 258 00:12:24.120 --> 00:12:28.679 strings completely unusable for heavy parsing or text manipulation. The 259 00:12:28.720 --> 00:12:31.639 modern standard is to immediately reach for the text library, 260 00:12:31.919 --> 00:12:35.759 which represents data internally as a packed UTF sixteen array 261 00:12:35.919 --> 00:12:37.440 or byte string for rowbites. 262 00:12:37.720 --> 00:12:41.279 But switching to text isn't just about shrinking the memory footprint. 263 00:12:41.600 --> 00:12:44.879 It unlocks one of the most powerful compiler optimizations in 264 00:12:44.960 --> 00:12:47.639 the GHC, which is stream fusion. 265 00:12:48.000 --> 00:12:50.799 Yes, stream fusion is incredible. 266 00:12:50.960 --> 00:12:53.200 Here's where it gets really interesting. Let's dig into the 267 00:12:53.240 --> 00:12:55.639 mechanics of this because I was reading this section and 268 00:12:55.679 --> 00:12:57.559 it sounds like actual magic. 269 00:12:57.919 --> 00:13:01.440 It feels like magic, but it's based on rigorous mathematical 270 00:13:01.480 --> 00:13:05.600 rewrite rules. Suppose you write a pipeline to process a 271 00:13:05.639 --> 00:13:09.159 text document, you want to convert it to uppercase, filter 272 00:13:09.200 --> 00:13:11.200 out the punctuation, and then take the length. 273 00:13:11.159 --> 00:13:14.159 So t dot length composed with t dot filter composed 274 00:13:14.200 --> 00:13:15.759 with t dot to upper exactly. 275 00:13:16.360 --> 00:13:19.559 In a naive run time, chaining three functions like that 276 00:13:19.639 --> 00:13:23.360 would allocate three separate arrays in memory. It would pass 277 00:13:23.399 --> 00:13:26.960 the entire document through uppercase, create a new massive array, 278 00:13:27.320 --> 00:13:30.039 pass that through the filter, create another array, and finally 279 00:13:30.080 --> 00:13:31.039 count the length. 280 00:13:30.879 --> 00:13:33.240 Which would absolutely kill your CPU cache. 281 00:13:33.399 --> 00:13:37.279 But stream fusion prevents that. The text library defines intermediate 282 00:13:37.279 --> 00:13:41.639 operations using a generic step data type yielding a value 283 00:13:41.759 --> 00:13:47.120 skipping or finishing. GHC uses specific rewrite rules like fold, 284 00:13:47.120 --> 00:13:51.679 slash build rules to transform the abstract syntax tree during compilation. 285 00:13:52.039 --> 00:13:54.600 Okay, so what does it actually do to the code. 286 00:13:54.440 --> 00:13:58.039 When it sees these chained operations. It mathematically fuses them 287 00:13:58.080 --> 00:14:01.639 into a single tight impair arative style loop over the 288 00:14:01.759 --> 00:14:04.120 underlying ut F sixteen array. 289 00:14:04.039 --> 00:14:06.919 Hold on, so it literally rewrites the ast. If I 290 00:14:07.120 --> 00:14:11.399 chain those three abstract functions, the compiler doesn't execute them sequentially, Nope, 291 00:14:11.480 --> 00:14:14.600 it e merges the uppercase logic, the filter logic, and 292 00:14:14.639 --> 00:14:17.639 the counter into a single loop, passing each character through 293 00:14:17.679 --> 00:14:20.360 all three steps before moving to the next character exactly. 294 00:14:20.360 --> 00:14:24.360 It completely eliminates the intermediate arrays. The intermediate data structures 295 00:14:24.440 --> 00:14:26.960 never actually exist in the compiled machine code. 296 00:14:27.039 --> 00:14:29.679 That is fascinating, you know, in imperative languages, to avoid 297 00:14:29.720 --> 00:14:31.919 those intermediate arrays, I would be forced to write a 298 00:14:31.919 --> 00:14:35.080 messy hand optimized wild loop, manually tracking the index and 299 00:14:35.120 --> 00:14:37.000 cramming all the logic into one block. 300 00:14:36.840 --> 00:14:38.840 Which is awful to read and maintain. 301 00:14:39.360 --> 00:14:43.799 Right, But here the abstraction is actually the enabler. Writing 302 00:14:43.840 --> 00:14:47.799 the high level, mathematically pure pipeline is what gives the 303 00:14:47.840 --> 00:14:51.240 compiler the map it needs to generate the optimized loop. 304 00:14:51.519 --> 00:14:54.360 The purity is what makes it possible, because the compiler 305 00:14:54.440 --> 00:14:57.759 mathematically guarantees there are no side effects. It knows it 306 00:14:57.799 --> 00:15:01.679 is safe to reorder and fuse the operation. The text 307 00:15:01.720 --> 00:15:06.200 also highlights a similar architectural trick for lists called difference lists. 308 00:15:06.240 --> 00:15:07.720 Oh yeah, tell me about difference lists. 309 00:15:07.759 --> 00:15:11.039 Standard list appending with a plus plus operator traverses the 310 00:15:11.240 --> 00:15:14.399 entire left hand list, which takes O of n time 311 00:15:14.720 --> 00:15:18.039 and builds up massive funk structures if nested. 312 00:15:17.759 --> 00:15:19.679 Which we know leads to heap exhaustion. 313 00:15:19.919 --> 00:15:22.879 Right, a difference list transforms the data structure into a function. 314 00:15:23.320 --> 00:15:25.480 Instead of storing the list one, two, three, you store 315 00:15:25.559 --> 00:15:27.960 function that propens one, two, three to another list. Oh. 316 00:15:28.039 --> 00:15:30.399 I see. By turning the data into a function, you 317 00:15:30.399 --> 00:15:32.399 can use function composition to append them. 318 00:15:32.600 --> 00:15:35.200 Right, You use the composition operator instead of a pend 319 00:15:35.320 --> 00:15:38.720 function composition is constant time oh of one. You defer 320 00:15:38.799 --> 00:15:41.279 the actual construction of the list until you finally apply 321 00:15:41.320 --> 00:15:44.039 the accumulated function to an empty list at the very end. 322 00:15:44.320 --> 00:15:44.919 It is a. 323 00:15:45.000 --> 00:15:48.879 Brilliant way to turn a performance bottleneck into a constant 324 00:15:48.879 --> 00:15:53.440 time operation purely through mathematical abstraction. I love the elegance 325 00:15:53.480 --> 00:15:55.399 of that. It's very elegant. But I have to play 326 00:15:55.399 --> 00:15:58.399 the skeptic here for a second. There is a ceiling 327 00:15:58.440 --> 00:16:02.320 to clever abstractions. What if I am doing heavy digital 328 00:16:02.360 --> 00:16:07.360 signal processing or massive matrix mathematics, I need raw contiguous 329 00:16:07.480 --> 00:16:10.279 Raisin memory and I need to mutate data in place. 330 00:16:10.840 --> 00:16:13.039 Doesn't functional purity just hit a brick wall? There? 331 00:16:13.159 --> 00:16:16.039 It does if you stay in this standard pure paradigm. 332 00:16:16.600 --> 00:16:19.559 Thomasin addresses this in the sections covering tabular data and 333 00:16:19.600 --> 00:16:23.600 the vector package. He gives a benchmark involving statistical windowing 334 00:16:23.679 --> 00:16:27.360 over a million random time stamps and observations. 335 00:16:26.720 --> 00:16:29.679 In the classic data science operation. How did the pure 336 00:16:29.799 --> 00:16:30.519 proach handle it? 337 00:16:30.879 --> 00:16:34.120 Even using unboxed vectors. A naive run with standard compiler 338 00:16:34.159 --> 00:16:37.440 settings was abysmal. The program consumed one hundred and thirty 339 00:16:37.480 --> 00:16:40.200 eight megabytes of memory, and more tellingly, it's meant twenty 340 00:16:40.240 --> 00:16:43.559 eight percent of its total execution time paused doing garbage collection. 341 00:16:43.799 --> 00:16:46.120 Spending nearly a third of your CPU time just taking 342 00:16:46.120 --> 00:16:48.840 out the trash is totally unacceptable for high performance. 343 00:16:49.080 --> 00:16:52.000 But the first line of defense is simply unleashing the compiler. 344 00:16:52.360 --> 00:16:56.159 By passing the DASHO two optimization flag to GHC, which 345 00:16:56.200 --> 00:17:00.320 turns on aggressive inlining infusion rules, the performance pro file 346 00:17:00.440 --> 00:17:04.200 drastically changes or the numbers. The memory footprint drops from 347 00:17:04.240 --> 00:17:07.440 one hundred and thirty eight megabytes to nineteen megabytes, and 348 00:17:07.519 --> 00:17:10.160 garbage collection drops to just one point three percent of 349 00:17:10.200 --> 00:17:11.119 the execution time. 350 00:17:11.799 --> 00:17:15.200 That is a staggering improvement for a single compiler flag. 351 00:17:16.720 --> 00:17:20.119 But let's push it further. Let's say I absolutely definitively 352 00:17:20.200 --> 00:17:23.559 need true in place mutation. I need to update a 353 00:17:23.559 --> 00:17:27.319 specific index in a massive array a million times without 354 00:17:27.319 --> 00:17:29.720 copying the array Okay, if I do that in Haskell 355 00:17:29.960 --> 00:17:33.680 using the mutable STMAD, aren't I just admitting defeat? Aren't 356 00:17:33.680 --> 00:17:36.559 I just writing C code but awkwardly forcing it into 357 00:17:36.599 --> 00:17:37.480 Haskell syntax. 358 00:17:37.640 --> 00:17:40.519 It's a very common critique, but it misses the architectural 359 00:17:40.559 --> 00:17:44.119 brilliance of the stmnad state threads. Yes, the stmonid gives 360 00:17:44.160 --> 00:17:47.039 you strough for mutable variables and mutable arrays that update 361 00:17:47.079 --> 00:17:50.039 in place, right, But it doesn't compromise the global architecture 362 00:17:50.079 --> 00:17:52.759 of your program because it uses the type system to 363 00:17:52.920 --> 00:17:54.359 enforce a strict quarantine. 364 00:17:54.559 --> 00:17:57.119 Explain the quarantine. How does the compiler know the mutation 365 00:17:57.200 --> 00:17:59.279 won't leak out and cause side effects elsewhere? 366 00:17:59.359 --> 00:18:02.920 It relies on a phantom type parameter. If you look 367 00:18:02.960 --> 00:18:05.160 at the type signature for the st monad, it has 368 00:18:05.200 --> 00:18:08.720 a type variable S like STSA okay, wait is es 369 00:18:09.240 --> 00:18:12.759 that's S represents the specific thread of state. When you 370 00:18:12.839 --> 00:18:15.440 use the run s two function to execute this mutable 371 00:18:15.480 --> 00:18:19.119 block and extract the pure result, run st uses rank 372 00:18:19.200 --> 00:18:23.759 to polymorphism. It requires the state type as to be universally. 373 00:18:23.279 --> 00:18:25.279 Quantified, meaning what for the compiler. 374 00:18:25.640 --> 00:18:29.079 It acts like a cryptographic lock. If your code tries 375 00:18:29.119 --> 00:18:31.759 to return a mutable reference or let a piece of 376 00:18:31.839 --> 00:18:34.720 mutable state escape the run a st block. The type 377 00:18:34.799 --> 00:18:37.920 checker physically cannot unify the types. It will throw a 378 00:18:37.920 --> 00:18:39.000 compile time error. 379 00:18:39.079 --> 00:18:39.640 Oh wow. 380 00:18:39.720 --> 00:18:42.480 It mathematically proves that the mutation is contained. 381 00:18:42.559 --> 00:18:45.440 So the inner block is a black box. Inside the box, 382 00:18:45.480 --> 00:18:48.559 you can write the dirtiest, fastest CE style mutating loops 383 00:18:48.599 --> 00:18:51.200 you want. But to the rest of the Hauskell program, 384 00:18:51.400 --> 00:18:54.319 that box is just a pure function taking an input 385 00:18:54.359 --> 00:18:56.160 and returning a deterministic output. 386 00:18:56.440 --> 00:19:00.720 Exactly. You isolate the imperative speed locally without polluting the 387 00:19:00.759 --> 00:19:03.839 purity of your global system. It proves you don't have 388 00:19:03.880 --> 00:19:07.000 to sacrifice safety for raw metal performance as long as 389 00:19:07.079 --> 00:19:09.839 your compiler is strict enough to enforce the boundaries. 390 00:19:10.359 --> 00:19:13.119 We've covered a massive amount of ground today. We've seen 391 00:19:13.119 --> 00:19:17.400 that high performance Taskell isn't about sorcery. It's about physical reality. 392 00:19:17.559 --> 00:19:18.440 It really is. 393 00:19:18.599 --> 00:19:22.359 It requires navigating the memory graph, knowing when laziness will 394 00:19:22.359 --> 00:19:25.000 build a mountain of thunks, and knowing how to crack 395 00:19:25.039 --> 00:19:29.039 the whip with the bang pattern, strict folds and unboxed primitives. 396 00:19:29.480 --> 00:19:34.279 It requires abandoning linkedless strings for dense UTF sixteen arrays 397 00:19:34.559 --> 00:19:39.240 and fundamentally trusting ghc's fusion rules and optimization passes to 398 00:19:39.279 --> 00:19:40.119 do the heavy lifting. 399 00:19:40.359 --> 00:19:43.000 It is that aligning your high level abstractions with the 400 00:19:43.000 --> 00:19:47.680 compiler's expectations, so map your math efficiently to the hardware. 401 00:19:47.519 --> 00:19:50.119