Optimizing Image Rotation with Loop Tiling | HTTP 203

[00:00:00]SURMA: (BEATBOXING) Let's do some some 203.

[00:00:04]Are we good?

[00:00:05]JAKE: We are good.

[00:00:06][THEME MUSIC PLAYING] SURMA: I don't know if you've noticed, but we've built a thing.

[00:00:16]JAKE: Are we going to talk about Squoosh again?

[00:00:18]SURMA: A little bit.

[00:00:19]JAKE: OK.

[00:00:19]SURMA: Maybe, but another aspect of Squoosh.

[00:00:21]JAKE: All right.

[00:00:21]SURMA: So that's kind of interesting.

[00:00:23]JAKE: OK.

[00:00:23]SURMA: So this might be a long one, so bear with me.

[00:00:25]I'm going to start at where we started, and then we kind of fell down into this rabbit hole.

[00:00:32]And I want the audience to fall into this rabbit hole with us.

[00:00:36]JAKE: Yes, and I'm really looking forward to this one.

[00:00:38]Because sometimes when we do these, one of us is maybe slightly pretending to know less about the subject than we do.

[00:00:46]Whereas in this one, there's a lot that I really don't understand.

[00:00:49]So-- SURMA: And I'm really worried that I might not actually be able to explain everything as much as you would like me to.

[00:00:55]JAKE: OK.

[00:00:56]Well, I'll-- SURMA: So let's see where we end up.

[00:00:57]JAKE: Yes, I'll let you know honestly.

[00:00:59]SURMA: Let's start with, what are images on the web if we manipulate them with JavaScript?

[00:01:04]So let's talk about image data, which is a data structure that we use in Squoosh.

[00:01:07]So once we get an image in and we decode it, and we turn it into an image data object, which is a data structure that exists on a platform.

[00:01:13]Basically, it has three properties-- the width, the height, and data.

[00:01:17]And data, there is a Uint8ClampedArray.

[00:01:20]And in there, you have just four bytes for each pixel.

[00:01:24]JAKE: Yes.

[00:01:24]SURMA: And it's the first row, and the second row, and so on.

[00:01:28]JAKE: And then each one is like red, green, blue, alpha, right?

[00:01:31]SURMA: Exactly.

[00:01:31]So what you see here is like it's a red pixel, then a green pixel, and a blue pixel, and a white pixel.

[00:01:36]And because the image is 2 by 2, that is what the image would look like, right?

[00:01:39]JAKE: Huh, nice.

[00:01:40]SURMA: So it's basically just a series of numbers with no concept of rows or columns.

[00:01:46]But because of that information, we can rearrange them and interpret them as a proper two-dimensional image.

[00:01:51]JAKE: Brilliant.

[00:01:51]SURMA: That's kind of how it works.

[00:01:53]All right.

[00:01:54]So now, in Squoosh, we had the goal to rotate an image by 90 degrees.

[00:01:58]JAKE: Sounds like a simple thing.

[00:02:00]Probably only take 10 minutes.

[00:02:02]SURMA: I mean, you wrote it-- the first version, right?

[00:02:05]And so let's talk about how you wrote it.

[00:02:07]You rotate an image by 90 degrees, gets an input image, which is this image data object.

[00:02:11]JAKE: Yes, it is.

[00:02:12]SURMA: And what we do, we figure out by 90 degrees, what is the width and the new height, which is pretty much just height and width swapped.

[00:02:19]JAKE: You're doing fancy Surma code already.

[00:02:21]SURMA: It's a little bit because otherwise it wouldn't fit.

[00:02:24]So I'm compressing things down.

[00:02:26]JAKE: Right, OK.

[00:02:27]SURMA: This is actually kind of two-- JAKE: So here, you're essentially assigning the height to the width, and the width to the height, because it's 90 degrees.

[00:02:33]Right, OK, I'm following.

[00:02:34]SURMA: And I'm trading in new output image, which has this new width and the new height.

[00:02:38]JAKE: Yes.

[00:02:38]SURMA: So now the goal is to go through the pixels and put them in the right spot in the output image.

[00:02:42]JAKE: Ba ba ba ba ba.

[00:02:43]SURMA: So what we do, we for loop over all the pixels in the input image, and we figure out where they would have to land in the output image.

[00:02:52]So basically the new x-coordinate is that kind of formula, the new y-coordinate's that.

[00:02:57]Then we figure out which input pixel it is, which output pixel, and just copy it over.

[00:03:01]JAKE: More fancy Surma code here-- wouldn't get through review.

[00:03:03]SURMA: I know.

[00:03:04]You don't like it.

[00:03:05]JAKE: OK, that's fine.

[00:03:06]SURMA: And then because we have four bytes per pixel, we just loop over four times, and just do another thing.

[00:03:12]We copy the r value, the g value, the b value, and the a value.

[00:03:15]JAKE: Yep.

[00:03:16]And off we go.

[00:03:16]SURMA: And this works.

[00:03:17]And this was actually decently fast.

[00:03:19]We shipped it this way.

[00:03:20]JAKE: We should say the reason we did this rather than canvas is because we wanted to run it in a worker.

[00:03:26]SURMA: That's an entire different story.

[00:03:28]But yes, we did a lot of tests with what seemed more fancy [INAUDIBLE] technology didn't seem to work.

[00:03:34]So we ended up writing our own piece of JavaScript just for this problem.

[00:03:37]JAKE: Yes, because offscreen canvas, only in a couple of browsers, whereas this is just basic-- SURMA: JavaScript.

[00:03:42]JAKE: --JavaScript, so that works everywhere.

[00:03:43]SURMA: And it can run in the worker because it has the image of it.

[00:03:45]So this-- we shipped this.

[00:03:46]This worked.

[00:03:47]JAKE: Yes.

[00:03:47]Yes, it did.

[00:03:48]SURMA: And then I looked at some point, and was like, hmm, there's actually kind of an obvious optimization that you missed.

[00:03:54]And so I basically added a little patch.

[00:03:58]This all stays the same, same as before.

[00:04:00]But now I'm creating a u32 array.

[00:04:04]JAKE: Yes, yes.

[00:04:05]SURMA: But basically we have the same underlying chunk of memory, but instead of seeing it as a series of bytes, we see it as a series of 32 bits-- numbers-- because every pixel consists of a 32-bit number, right, for r, g, b, and a.

[00:04:20]And so this way, we can simplify or actually remove the inner loop.

[00:04:25]JAKE: So it's this bit that was here that-- doing something four times every time, we're now just doing it once.

[00:04:30]SURMA: It's now one copy operation which actually maps to a machine instruction.

[00:04:33]Most of the times, the V8 will be, like, super smart and go, like, whoa fast.

[00:04:36]So this was actually quite a bit faster.

[00:04:38]So, cool.

[00:04:40]And then we ship this-- still fine.

[00:04:41]And then it turns out that for some reason, in one browser, this was super slow.

[00:04:47]JAKE: Right.

[00:04:47]And we've been advised by legal-- SURMA: By our legal department to not name the browser.

[00:04:52]JAKE: Apparently it's a Chrome policy not to-- SURMA: I've never heard that before, but-- JAKE: No, we're not allowed to talk about other browsers.

[00:04:59]So we can't mention which browser it is.

[00:05:01]SURMA: But it's one that didn't run in our machines.

[00:05:03]JAKE: It didn't run on your machine, did it?

[00:05:05]You had to use a VM to run this different browser.

[00:05:08]OK.

[00:05:08]SURMA: Either way-- like, most browsers were fine, good enough at least, and then for some reason, this one browser just ended up being extremely slow, like unreasonably slow.

[00:05:17]So we must have hit some weird corner case.

[00:05:19]JAKE: Yes.

[00:05:19]SURMA: Because this browser isn't slow usually.

[00:05:21]It's a very good browser.

[00:05:23]JAKE: Yes, and different JavaScript engines optimize with different things.

[00:05:26]So the fact that one browser was slower here isn't saying that that browser is terrible.

[00:05:30]It's just saying V8 is very good with this kind of tight loop code, over engines that have optimized for, like, more dumb bindings stuff.

[00:05:38]SURMA: Exactly.

[00:05:39]JAKE: So it wasn't that surprising that one browser was completely different in terms of problems with this piece of code.

[00:05:45]SURMA: So we thought, well, what do we do?

[00:05:47]Maybe we frame a web assembly at the problem, right?

[00:05:49]JAKE: Aye.

[00:05:50]SURMA: So we looked into that.

[00:05:52]And the first problem we had that, when you write WebAssembly and you load it, it turns into a module that has functions, the functions that you wrote in whatever language you were using.

[00:06:00]JAKE: Yes.

[00:06:01]SURMA: Right?

[00:06:01]JAKE: This is different to an ECMAScript module.

[00:06:04]It's a Wasm module.

[00:06:05]It's a different thing.

[00:06:06]SURMA: It's a different thing.

[00:06:07]And these functions can only take in and return numbers.

[00:06:11]So there is no easy way, straight up, to pass in an image.

[00:06:16]So what do you do, right?

[00:06:18]So what we ended up doing-- I'm going to reuse the video I made for my article-- JAKE: Oh, brilliant.

[00:06:23]SURMA: --basically, the JavaScript was going to load the image, put it into the WebAssembly memory, and then we're going to use WebAssembly to just do the reordering within that WebAssembly memory buffer and use JavaScript to read it back afterwards.

[00:06:34]JAKE: Right.

[00:06:35]SURMA: So that means the WebAssembly really is completely isolated from all of the outer world, really, so to speak.

[00:06:41]It just has its chunk of memory to work and will read in the image, do the reordering that was shown before, and then JavaScript comes back, takes over, and reads back the resulting image.

[00:06:49]JAKE: So JavaScript and WebAssembly, the thing they share is memory.

[00:06:53]That they-- SURMA: Pretty much.

[00:06:55]JAKE: WebAssembly, it's its memory.

[00:06:56]SURMA: So this WebAssembly.memory is WebAssembly-specific memory.

[00:07:00]But it is also exposed as an array buffer that we can use as a u32 array or whatever we need in that very instance, right?

[00:07:06]JAKE: So the amount of memory we need for WebAssembly is essentially double the size of the image, because it's going to-- SURMA: Yeah.

[00:07:12]JAKE: --have the main image in memory and then the next bit.

[00:07:14]OK.

[00:07:16]SURMA: So how do we create Wasm?

[00:07:18]We've done it before with mScript in C.

[00:07:19]But that's also Rust.

[00:07:21]But we actually found a very interesting project we stumbled over called AssemblyScript.

[00:07:25]JAKE: Yes.

[00:07:25]SURMA: Which is a-- they call themselves a type script to WebAssembly compiler, which is true.

[00:07:33]But might be a little bit misleading.

[00:07:35]Because you can't just take any type script and compile it to WebAssembly.

[00:07:39]It is using the TypeScript syntax and the TypeScript standard library things, but with their own version of their library that is specifically tailored to WebAssembly.

[00:07:48]So what you can see here is the signature way.

[00:07:50]Now we have types, as you know, from TypeScript.

[00:07:53]But there's the I32 type, which is the type WebAssembly has, but JavaScript doesn't.

[00:07:57]JAKE: And that's the 32-bit integer, right?

[00:07:59]SURMA: Yes, the signed 32-bit integer.

[00:08:01]JAKE: Signed.

[00:08:02]SURMA: That's also be u32, which is the unsigned.

[00:08:05]JAKE: Why are we using signed?

[00:08:07]SURMA: Four reasons.

[00:08:08]JAKE: Four reasons?

[00:08:09]OK.

[00:08:09]Let's gloss over it.

[00:08:10]This is good.

[00:08:11]Because I can recognize this.

[00:08:12]It looks a lot like JavaScript.

[00:08:14]It looks a lot like TypeScript.

[00:08:15]SURMA: And so will the rest, except for two lines.

[00:08:17]So this looks the same.

[00:08:18]So we switch height and width.

[00:08:19]JAKE: Yep.

[00:08:20]SURMA: Now this is a bit interesting.

[00:08:22]Because we have this chunk of memory, we need to know where our input image starts and where our output image starts.

[00:08:30]That's what these two variables are.

[00:08:32]So our input image starts at 0, at address 0 in this memory.

[00:08:34]JAKE: Which is always does.

[00:08:35]SURMA: Index 0, you can say, and the output image is right after the input image ends.

[00:08:39]And the input image consists of width times height times four-- JAKE: Four bits per pixel.

[00:08:45]SURMA: Bytes.

[00:08:45]JAKE: Bytes per pixel.

[00:08:46][LAUGHTER] See the thing about this, and I'm sorry to interrupt the flow.

[00:08:52]I should say that I came to the web as a CSS person, CSS Front-End, and I learned JavaScript.

[00:09:00]Whereas you came to the web from being a programmer-- well, and then you went to the web, right?

[00:09:04]SURMA: [INAUDIBLE] I did embedded systems.

[00:09:06]Like I was literally writing kernel code and low level memory management.

[00:09:10]And I had no idea about CSS and how to do UI and anything like that.

[00:09:15]JAKE: Right.

[00:09:15]SURMA: It's just two completely different angles.

[00:09:18]JAKE: But I would say that if anyone is watching this, thinking what is going on?

[00:09:21]SURMA: Yeah.

[00:09:22]This is-- JAKE: I am feeling exactly the same.

[00:09:24]So don't worry too much about it.

[00:09:25]All right.

[00:09:25]Come on.

[00:09:26]Let's-- Let's go.

[00:09:27]SURMA: But for now, these are basic indices in the array.

[00:09:30]Where does the input image start?

[00:09:31]Where does the output image start?

[00:09:32]And then this looks familiar-- looping of all the pixels.

[00:09:35]JAKE: Yep.

[00:09:36]SURMA: And figuring out where the new coordinates are.

[00:09:39]We did all this before.

[00:09:40]And now there's these two AssemblyScript specific functions.

[00:09:44]The first one is load, which allows me to load a u32 from the memory at a given address.

[00:09:51]JAKE: Right.

[00:09:52]SURMA: And so in this case, what I'm doing is I'm using the input image space, where the image starts, plus the pixel I want to read.

[00:09:57]JAKE: So this is very similar to what we were doing before with the uint32array.

[00:10:02]But it's where-- but there's a special command to get it straight from memory rather than-- SURMA: Yeah.

[00:10:06]Because it's a WebAssembly memory.

[00:10:07]And that's, like-- JAKE: Right.

[00:10:08]SURMA: --implicit.

[00:10:09]It's not something you get handed as a reference.

[00:10:11]It's just there is a global, almost like.

[00:10:12]JAKE: But it's the same thing.

[00:10:14]We're passing the same indices into it.

[00:10:15]Yes.

[00:10:16]SURMA: Exactly.

[00:10:16]JAKE: OK.

[00:10:16]SURMA: So we're loading our pixel and then all we have to do is write it back to the output image.

[00:10:20]And it's the same thing, restoring the value v, which we just read, back as a user to into the output image space.

[00:10:26]JAKE: OK.

[00:10:27]SURMA: And now we have written AssemblyScript.

[00:10:30]JAKE: And then this converts to WebAssembly.

[00:10:32]And what really struck me with this is that if I wanted to write WebAssembly, this is the tool I would use.

[00:10:39]SURMA: Yeah.

[00:10:40]JAKE: Because this looks really familiar to me.

[00:10:42]SURMA: You don't have to learn a new language, right?

[00:10:43]Because-- JAKE: Yeah.

[00:10:44]SURMA: --I think you've learned a bit of C because of Squoosh.

[00:10:47]JAKE: Yes.

[00:10:47]SURMA: But that's pretty much it, as far as I know.

[00:10:50]You've not written Rust, I think.

[00:10:51]You kind of-- JAKE: I know PHP.

[00:10:53][LAUGHTER] SURMA: [INAUDIBLE] PHP to a WebAssembly compiler, then.

[00:10:56]JAKE: I would love it.

[00:10:57]It was the first language I learned.

[00:10:59]SURMA: So we have this function now.

[00:11:01]And now I want to compile it to WebAssembly.

[00:11:02]And luckily, AssemblyScript makes it very easy.

[00:11:04]So we just installed the AssemblyScript package.

[00:11:07]And then we have an ASC command, which we give our TypeScript file to.

[00:11:12]And it will give us back a WebAssembly file, with no additional glue or JavaScript, which I think is quite interesting.

[00:11:18]Because most other implementations for WebAssembly give you glue code, which is the initial-- JAKE: A huge JavaScript file, otherwise, is really difficult to deal with and work with.

[00:11:27]But this is just-- yeah, just Wasm, right?

[00:11:30]SURMA: So we did this.

[00:11:32]We got a rotate.wasm file.

[00:11:34]And now the interesting bit might be how to load it.

[00:11:37]Because usually, glue code loads it for you.

[00:11:39]But now you don't have glue code.

[00:11:40]How does this work?

[00:11:41]It's actually not that difficult.

[00:11:43]What you do is you take the instantiate streaming function from the WebAssembly object and put a fetch in there.

[00:11:49]Because the WebAssembly compiler, at least the non-optimizing one, can compile while the Wasm file is still downloading.

[00:11:55]JAKE: So this instantiate streaming takes a promise.

[00:11:57]SURMA: A promise, or response, or an array buffer-- JAKE: That's a weird API.

[00:12:02]It's, like, why does it take a promise?

[00:12:04]SURMA: Because they want to make this simple-- if you don't have to wait the fetch, right?

[00:12:09]JAKE: OK.

[00:12:10]I don't agree with it.

[00:12:11]But that's fine.

[00:12:11]SURMA: Sure, fine.

[00:12:11]JAKE: You should just put an array in there.

[00:12:12]SURMA: Either way-- I find it really interesting.

[00:12:14]It starts compiling while it's still downloading.

[00:12:16]So it's not like download, then compile.

[00:12:19]It's actually almost in parallel, which for WebAssembly modules, which can be quite big.

[00:12:25]You know?

[00:12:25]I think that the Unreal Engine one is, like, 40 megabytes.

[00:12:29]That will make quite a difference.

[00:12:31]JAKE: Yes, absolutely.

[00:12:32]Not so much here.

[00:12:33]SURMA: So no, absolutely not-- so yeah, the Wasm module is, by the way, it's, like, 500 bytes or something.

[00:12:38]So it's really small.

[00:12:39]It's smaller than the compressed ng's of JavaScript code that we had.

[00:12:43]JAKE: Nice.

[00:12:44]SURMA: That was actually quite cool.

[00:12:45]So now we get an instance back from this one.

[00:12:47]And on that instance, we can have exports.

[00:12:50]And exports is all the functions, but also the memory that we are going to work on.

[00:12:54]JAKE: Right.

[00:12:55]SURMA: So we can grow our memory.

[00:12:56]Because we didn't know what size it has.

[00:12:58]But we have to go to the size that fits our images two times, right?

[00:13:02]Which we would have to calculate.

[00:13:03]We'll skip this here.

[00:13:04]But I would-- JAKE: So that would just be that the size of the [INAUDIBLE] array data times 2.

[00:13:09]SURMA: Yeah.

[00:13:09]JAKE: OK.

[00:13:09]OK.

[00:13:10]SURMA: And then I will somehow load this image into the buffer, which is really just-- memory has a dot buffer property which is a normal array buffer.

[00:13:16]Plus we can use all the [INAUDIBLE] to put data in there.

[00:13:19]JAKE: Right.

[00:13:20]SURMA: Just put it in.

[00:13:20]JAKE: Yep.

[00:13:22]SURMA: And then you call rotate 90, and we'd image back, and you're done.

[00:13:25]JAKE: Ah.

[00:13:26]So exports has all of the methods.

[00:13:27]SURMA: So this is the method.

[00:13:29]This is the magic, where you call into WebAssembly.

[00:13:31]And you can also see it's synchronous.

[00:13:32]So WebAssembly is something that will actually take the control away from JavaScript and do its thing, and then return the control back to JavaScript.

[00:13:39]It's just like an actual function.

[00:13:40]JAKE: OK.

[00:13:41]OK.

[00:13:41]SURMA: Which I think is super nice.

[00:13:43]And so this was fast, and we were super happy about this.

[00:13:45]JAKE: Yes.

[00:13:46]This was much faster than-- SURMA: It wasn't faster in Chrome in the sense that it didn't outperform JavaScript.

[00:13:53]It was as fast, or almost as fast.

[00:13:55]But it was consistently fast across all browsers.

[00:13:58]JAKE: Yes.

[00:13:58]It had taken the browser that doesn't run a Mac from seven seconds down to, like, 500 or something, 500 milliseconds.

[00:14:06]SURMA: It was very, very acceptable.

[00:14:07]JAKE: Yes.

[00:14:08]It was really nice to see that similar value-- SURMA: --across all browsers.

[00:14:11]So we were super happy about this.

[00:14:13]So we opened PR in our Squoosh and you reviewed it.

[00:14:16]And we wrote an article.

[00:14:17]And then "Hacker News" happened.

[00:14:21]JAKE: "Hacker News" happened.

[00:14:22]SURMA: And that's something I would never say.

[00:14:23]Because usually the comments on our articles are quite annoying.

[00:14:28][LAUGHTER] JAKE: "Hacker News" can sometimes be quite pedantic, I find.

[00:14:34]But in this instance, there was some pedantry.

[00:14:38]But the pedantry was really interesting.

[00:14:40]SURMA: It was really interesting.

[00:14:41]JAKE: Some fascinating results-- and just a lot of it I didn't understand.

[00:14:46]And I hope you're going to explain it to me.

[00:14:48]SURMA: Yeah.

[00:14:48]So someone said, why aren't they using tiling?

[00:14:51]Tiling would make this so much faster.

[00:14:52]Let me quickly try it.

[00:14:53]And yeah, I totally did it for something, like, 20 milliseconds.

[00:14:55]I was, like, what?

[00:14:57]JAKE: Yeah.

[00:14:58]So they had taken it from-- what was it, sort of framed to fall into milliseconds down to-- what was it?

[00:15:04]SURMA: I think 40.

[00:15:05]JAKE: 40, which is such a huge improvement.

[00:15:07]And that was even faster than we were seeing from a canvas element.

[00:15:11]Yeah.

[00:15:11]SURMA: So and I had to obviously sit down and actually understand what's happening.

[00:15:15]So let's talk about what tiling actually is.

[00:15:17]JAKE: Yes.

[00:15:18]Please do.

[00:15:18]Because I have no idea.

[00:15:20]SURMA: So I'm going to explain tiling.

[00:15:22]But there was also another suggestion for performance optimization.

[00:15:24]I'm going to talk about both of these.

[00:15:25]But I'm going to get the other one first to get it out the way.

[00:15:28]Basically, some people were saying, oh, if you look at this y times width, it's completely independent of the inner loops.

[00:15:36]If I move it out between the outer and the inner loop, that would make it faster.

[00:15:40]Because that calculation can happen only once per outer loop.

[00:15:43]It doesn't need to happen every time in the inner loop.

[00:15:45]JAKE: Yes.

[00:15:45]And I thought this was going to be the kind of thing that the optimizer thingy doo dah would take care of for me.

[00:15:52]SURMA: And it is.

[00:15:52]JAKE: Ah.

[00:15:53]SURMA: So this is the kind of advice where you don't have to worry about these kind of things.

[00:15:56]Like moving constants out of a loop is something that not only most compilers can do-- so, like, the [INAUDIBLE] compiler could do this or the Rust compiler-- but even the V8 compiler that go from the JavaScript to machine code or from WebAssembly byte code to machine code, will do this.

[00:16:14]So this is an optimization that we don't have to do.

[00:16:16]And where we can say let's keep it readable and obvious and don't introduce another variable where people that read the code would have to have even more state in their head to understand what's going on.

[00:16:24]JAKE: Yes.

[00:16:25]OK.

[00:16:25]SURMA: But the other thing is tiling.

[00:16:28]And tiling is something that I hadn't heard of.

[00:16:30]I actually had heard of it.

[00:16:31]But I also was under the impression that compilers would do it for us.

[00:16:34]And in this case, it is not.

[00:16:36]JAKE: What is it?

[00:16:36]Tell me.

[00:16:36]SURMA: So what is tiling?

[00:16:37]So this is an image-- JAKE: Correct.

[00:16:39]SURMA: --it's actually the album cover of our podcast.

[00:16:40]I don't know.

[00:16:41]Did you know that we do a podcast, Jake?

[00:16:42]JAKE: We do a podcast, as well.

[00:16:43]SURMA: We should link to it in the description, Jake.

[00:16:45]JAKE: Yes.

[00:16:46]We should.

[00:16:47]SURMA: So we have been reading this image so far like this.

[00:16:52]We've been going row by row.

[00:16:53]JAKE: Yeah.

[00:16:53]SURMA: And just-- what is this pixel?

[00:16:55]Where does it belong?

[00:16:56]OK.

[00:16:56]Copy.

[00:16:57]And look at the next pixel in the same row.

[00:16:59]That's kind of what we did, and we thought fine.

[00:17:01]Tiling is a different approach where you tile the image into tiles.

[00:17:05]JAKE: That's good.

[00:17:06]Yeah, those are tiles.

[00:17:07]Excellent.

[00:17:08]SURMA: And then do whatever you're trying to do within a tile first.

[00:17:13]So instead of going row by row, you just go tile by tile.

[00:17:15]And within the tile, you go row by row.

[00:17:18]JAKE: This is legitimately-- SURMA: It's the same thing.

[00:17:22]JAKE: This is legitimately a different way of doing the same thing.

[00:17:25]SURMA: I know.

[00:17:25]Now the interesting thing is that this turned out to be so much faster.

[00:17:29]JAKE: Yeah.

[00:17:29]Like, a tenth of the time.

[00:17:31]I still don't understand yet.

[00:17:33]SURMA: So let's implement this real quick.

[00:17:34]Which it's not actually-- JAKE: Can I just say one of our previous recent episodes, we talk about the dangers of over optimization.

[00:17:42]SURMA: Yeah.

[00:17:42]JAKE: And why are we doing this?

[00:17:45]SURMA: Because it ends up being so much faster.

[00:17:48]JAKE: OK.

[00:17:48]OK.

[00:17:49]SURMA: We actually, with this optimization, we end up going well below 100 milliseconds, which within the RAIL guidelines makes it feel like an instantaneous response to the button.

[00:17:58]JAKE: It is an optimization that matters.

[00:17:59]Cool.

[00:17:59]SURMA: And before that, we were at, like, 300 to 500.

[00:18:01]Which was fine, but if you can go under 100, we should go under 100.

[00:18:06]JAKE: Especially for bigger images.

[00:18:07]OK.

[00:18:08]SURMA: So basically, I just do an additional two outer loops.

[00:18:11]Which usually sounds wrong, but in this case is very, very right, where we iterate over all the tiles that we have.

[00:18:18]And then, in there, we basically have the same old loop, where we loop over each individual tile.

[00:18:23]JAKE: I'm starting to hyperventilate.

[00:18:26]Why?

[00:18:28]OK.

[00:18:29]SURMA: So this is tiling implemented.

[00:18:31]JAKE: So I get it.

[00:18:32]SURMA: Let's talk about why this might make things faster.

[00:18:35]JAKE: OK.

[00:18:35]That is the bit I don't understand.

[00:18:37]SURMA: So originally, tiling-- when I Googled tiling and researched it, it was mostly the use case for matrix multiplication, which is a different use case.

[00:18:47]Because input values are used multiple times.

[00:18:52]If you multiply two matrices, you have to read the cell at 1, 1 multiple times for, I think, for each column that you're calculating the output matrix.

[00:19:01]JAKE: OK.

[00:19:02]SURMA: So it makes sense that, if you do tiling, you have a better chance of having that value still in the cache.

[00:19:07]We're talking now processor level 1 cache, by the way.

[00:19:10]JAKE: So hang on.

[00:19:14]OK.

[00:19:14]We will need to explain what that is at some point, as well.

[00:19:17]But my feeling is, by reading memory sequentially, you're more likely to hit caches.

[00:19:22]Because you're dealing with a little bit of memory that was very close to the last bit of memory.

[00:19:28]SURMA: So if I have these two really big matrices, and I go through the first row of the input matrix, by the time I come-- I end up at the end, the values from the start might have been kicked out of the cache.

[00:19:39]Because level 1 cache in the processor is really small.

[00:19:42]We're talking like 200 kilobytes of cache, maybe, or less.

[00:19:45]JAKE: Right.

[00:19:45]So the processor has an L1 cache-- SURMA: Which is, like, super fast.

[00:19:50]JAKE: --so that there's these set of caches that gets bigger and slower.

[00:19:53]SURMA: Yeah.

[00:19:54]JAKE: Until you get to memory-- SURMA: Actually, memory is actually really slow.

[00:19:56]JAKE: Memory is really slow-- in relative terms.

[00:19:59]SURMA: Yeah.

[00:19:59]JAKE: OK.

[00:19:59]SURMA: And so what the tiling does is, by shortening the amount of time you spend going away from the initial value, you have a better chance of having the initial value still in the-- JAKE: Buh, buh, buh, buh, buh, buh, but-- SURMA: For matrix multiplication.

[00:20:13]So with this one-- JAKE: Yeah.

[00:20:15]SURMA: This is going to make sense why this would make it faster.

[00:20:17]JAKE: Because the second row is a massive jump from the first-- SURMA: Yeah.

[00:20:21]The rotation-- we read every value once, and we write it once.

[00:20:24]So why would caching make things better?

[00:20:26]JAKE: That is roughly the question I have in my head.

[00:20:29]SURMA: So there's two theories.

[00:20:30]And I don't know which one of them is actually true.

[00:20:33]JAKE: Are you telling me you don't even know?

[00:20:35]SURMA: Well, I even talked to Benedict, our V8 VM engineer.

[00:20:38]And he's, like, I have two theories.

[00:20:40]But it's really hard to test.

[00:20:42]JAKE: OK.

[00:20:43]OK.

[00:20:43]SURMA: So one version is that [INAUDIBLE] are really smart at predicting what memory you are going to grab next.

[00:20:51]So by basically seeing the tiles, it can make better predictions what-- JAKE: Oh.

[00:20:56]SURMA: --cells to grab, already put into the cache for you, even though you haven't exited that code yet.

[00:21:01]And the other thing is that, because the cache is so small, that there's a certain pattern which cell can be cached in which cache cell.

[00:21:11]So this gets a little bit confusing.

[00:21:12]But basically, if you think about it, if you have like three cache cells, just three individual cells-- JAKE: What can go in a cell?

[00:21:19]SURMA: One value.

[00:21:19]JAKE: One value, OK.

[00:21:20]OK.

[00:21:21]SURMA: OK.

[00:21:21]So memory error zero can only go in cache cell zero.

[00:21:25]And cache one can go in cache cell one.

[00:21:26]Cache two can go in cache cell two.

[00:21:29]Memory error three can only go in zero again.

[00:21:31]You wrap around, right?

[00:21:32]So you assign those.

[00:21:34]JAKE: Yep.

[00:21:34]SURMA: And then again, by keeping it smaller, you have a better chance of not overwriting the old value that you have put into your level one cache.

[00:21:42]So basically, all this is about is, by making things, making your access memory smaller, so that you don't evict the cache from the things that you-- JAKE: No, this is basically, it's working because our inner loops are smaller.

[00:21:55]SURMA: Yeah.

[00:21:56]JAKE: Right.

[00:21:56]SURMA: So it makes the processor make better predictions and also make the processor not evict the cache.

[00:22:02]Because the area we work on is smaller.

[00:22:05]JAKE: So then does the tile size-- yeah, what's the tile size?

[00:22:10]SURMA: So that's what I thought, right.

[00:22:12]And so I did some benchmarks.

[00:22:14]On a MacBook, on an iMac, and a Pixel 3-- because the bigger the machine or the bigger the processor, the bigger the level one cache usually is.

[00:22:23]JAKE: Right.

[00:22:24]SURMA: So the iMac that I have is an 18 core massive processor thing.

[00:22:30]It has massive [INAUDIBLE],, while the Pixel 3, obviously, has a very, very tiny level 1 cache.

[00:22:35]JAKE: All this code is single call, anyway, right?

[00:22:37]SURMA: Yeah.

[00:22:38]JAKE: Yeah.

[00:22:38]SURMA: So basically, at zero is the relative time it took for no tiling.

[00:22:42]JAKE: So that's the original-- SURMA: That's baseline tiling.

[00:22:45]JAKE: --wasn't, yes.

[00:22:46]SURMA: So what you can see here is how the time shifted relatively to that base time, depending on what the tile size is.

[00:22:52]JAKE: Interesting.

[00:22:53]SURMA: So if I have a tile size of two, a two-by-two pixel grid, it makes the code slower.

[00:22:59]Which is not very surprising, because you have so much more looping going on and more jumps.

[00:23:04]JAKE: OK.

[00:23:04]SURMA: It gets faster really, really quick.

[00:23:06]At some point, over here, you kind of hit level one cache boundaries where it then gets slower again.

[00:23:13]JAKE: Right.

[00:23:14]I see.

[00:23:15]OK.

[00:23:15]SURMA: To be honest, there's one weird thing where the Pixel 3 is slow, even with the massive grid, which I'm not quite sure why that is.

[00:23:22]I think-- JAKE: You mean it's fast even-- SURMA: Yeah.

[00:23:24]JAKE: It's faster.

[00:23:24]SURMA: I expected the pace was going to, like, go up somewhere around here.

[00:23:27]JAKE: You would assume the level one cache is less than any Mac book.

[00:23:30]SURMA: It probably is.

[00:23:31]And there's probably another effect here that I don't quite understand.

[00:23:34]JAKE: OK.

[00:23:34]SURMA: But what I felt-- JAKE: There's different architecture, as well, in that processor.

[00:23:36]OK.

[00:23:37]SURMA: But it seems to be a sweet spot between, like, 16 and, I don't know, 64, depending on what you want.

[00:23:44]I think 16 looks really promising in this graph.

[00:23:47]Which means you have, like, a 256 pixel grid that you work with.

[00:23:51]JAKE: I thought I was going to come into this episode and I was going to go away understanding why the tiling works.

[00:23:56]No.

[00:23:57]It just does.

[00:24:00]SURMA: I spent the last week on this.

[00:24:01]Right?

[00:24:02]JAKE: Right.

[00:24:02]SURMA: You've been kind of sitting across from me and hearing me talking to people and trying to figure this out.

[00:24:07]This is as close I've gotten to understand it.

[00:24:09]In that there is this interaction between the processor predicting what values went in the cache.

[00:24:15]And then, not forcing the processor to evict that cache, because you read too far ahead.

[00:24:19]JAKE: But this is a massive case for tools, not rules, right?

[00:24:22]Don't go away and rewrite all your code-- SURMA: With tiling.

[00:24:25]JAKE: --with tiling.

[00:24:26]SURMA: No.

[00:24:26]Right.

[00:24:26]JAKE: This is something you would have to very carefully profile on a wide range of machines with different processor architectures to see is this actually working across-- SURMA: And also I find it interesting because we started at let's rotate an image, a very high level use case.

[00:24:39]And we fell down.

[00:24:41]And ended up with, like, let's talk about processor architecture and level one caches.

[00:24:45]JAKE: Yes.

[00:24:46]SURMA: So thanks to "Hacker News", I guess, for ruining my week.

[00:24:49]But it's been actually been very educational, even though I still don't fully understand it.

[00:24:53]JAKE: But I feel like-- SURMA: I'm OK with that.

[00:24:55]JAKE: Yeah, and I feel that my understanding of lower level stuff is-- like I say, there's that confusion element.

[00:24:59]But I feel like I've got an appreciation for-- SURMA: The smarts, right-- JAKE: Yeah.

[00:25:04]SURMA: --that go into that.

[00:25:05]JAKE: It's incredible.

[00:25:07]SURMA: So let's take a breather.

[00:25:09]And we'll see our poor audience.

[00:25:12]next time.

[00:25:13][LAUGHTER] JAKE: But this is going into Squoosh in-- SURMA: Yeah.

[00:25:16]It's going to be-- [INTERPOSING VOICES] [MUSIC PLAYING] JAKE: Yes.

[00:25:20]SURMA: Oh.

[00:25:21]That's the one thing-- ah.

[00:25:23][GRUNTS] I have to write this down.

[00:25:26]How do I fix this?

[00:25:28]JAKE: [LAUGHS] (SINGING) Something for the edit.

[00:25:33]SURMA: OK.

[00:25:34]Let's go from here.