Skip to content
PodSubs
ShowsPeopleGuestsJobsNewsEvents
More
BlogPodCred
Menu
ShowsPeopleGuestsJobsNewsEventsBlogPodCredNetworksSign in
Join nowSign in
  • Shows
  • People
  • Jobs
  • News
  • More
    • Guests
    • Events
    • Blog
    • PodCred
    • Networks
    Join nowSign in

ADSP: Algorithms + Data Structures = Programs

ADSP: Algorithms + Data Structures = Programs artwork

Episode 219: Flood Fills & Adaptive Mesh Refinement

Jan 31, 202527 minAudio

In this episode, Conor and Bryce chat about the flood fill algorithm, adaptive mesh refinement, white dwarfs and more! Link to Episode 219 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast: Twitter Conor Hoekstra: Twitter | BlueSky | Mastodon Bryce Adelstein Lelbach Show Notes Date Generated: 2025-01-22 Date Released: 2025-01-31 Algorithms by Panos Louridas Flood Fill Adaptive Mesh Refinement White Dwarf city-strides-hacking GitHub Repo ArrayCast Epsiode 98 (coming soon) ADSP Episode 176: 🇺🇸 prior, deltas & Dinner with Phineas New Algorithms in C++23 - Conor Hoekstra - C++ on Sea 2023 Intro Song Info Miss You by Sarah Jansen https://soundcloud.com/sarahjansenmusic Creative Commons - Attribution 3.0 Unported - CC BY 3.0 Free Download / Stream: http://bit.ly/l-miss-you Music promoted by Audio Library https://youtu.be/iYYxnasvfx8

Audio and video play straight from the show's own hosting. PodSubs stores and serves no media.

Transcript

From the show. Tap a time to play from there.

BryceAt some point, something has to give, and then the theory is it goes boom.

ConorThere's the cold open right there. And then it goes boom. I also had the thought too that you know the reason I don't use pen and paper? It's because I have APL. That is basically like m not the inductive proof thing you just described, but like I can go and visually explore some algorithm or some solution in a REPL. And you you actually can do this with like Haskell as well. Like with a REPL, it's it's like the digital equivalent of like pen and paper. You can see step by step every single time you add some operation to some expression.

ConorLike literally yesterday I was presenting and I was showing solutions to that sushi for two problem uh that I presented in like 2023 at C on C and maybe one other conference. And I do it in the REPL, and it's like I'm showing you that when you chunk by it result, like you can see it visually.

BryceSo immediately my mind jumps to how would we implement this uh on a GPU? And the first my first thought is of course that okay, you can just partition the entire space up into chunks and then just have uh you know each chunk be done by a uh a thread block. So you just partition up the entire domain, and then uh you just you know locally do your flood fill within or or you can really just, I guess, paralyze it for every element.

BryceUm uh and then for every element determine if it's inside the region. Does that work? I suppose so, right?

ConorIt depends if what you're using your flood fill for. If you're using your flood fill just to literally do something like in the paint operation where you don't actually care about the resulting values, like if you're searching for the number of uh steps to get to some or number of moves to get to some final uh square, that's gonna be a lot trickier. Uh we can talk about that in a sec if you want. However, if you're just trying to flood it with a single value, a single color, then you're basically by partitioning it, you could do some coloring problem.

ConorAnd the tricky part is that when you join up your partitions, you don't actually know that the color that you filled in is um gonna be connected with your origin point. Uh so that's the tricky part, but that you just compare edges and stuff, and you're gonna end up doing a ton of extra work because you got like that was the next thing I was thinking of, which is uh so back when I worked in HPC, I primarily worked on um uh a type of grid code that used what's called adaptive mesh refinement.

BryceHave you ever heard of that? Nope. Okay, so um the particular application I worked on was uh simulations of uh uh the mergers of white dwarf stars. Um and so when you have two white dwarf stars that are um you know revolving around each other and they start merging, um, one of them uh the the the smaller one um which is becomes called the accreter, it'll start uh the bigger, more massive one will start pulling material off of the accreter.

BryceAnd there'll be this accretion stream that'll come from one of the stars into the other one. Um and as this stream of stellar material hits the uh um uh the bigger uh star that's sucking up the smaller one, uh you know, it's a pretty violent thing. And so you've got a bunch of stellar material that gets ejected out there. Um and so if you're gonna simulate this, you need to simulate not just the two stars, but this huge space around it, because you're gonna simulate all of this material that's getting ejected out there.

BryceBut you end up where you've got this huge grid, and then in the center you have these two tiny stars. Um and if you simulate the entire grid with the resolution that you'd want, um, that becomes a uh mm computationally massive problem. Um and you're not actually interested in the entire grid. Um you you don't need the same resolution of the entire grid. There's a few places where you need really high resolution. For example, the accretion stream of material between the two stars.

BryceUm when the stars start merging, that stream can be very, very narrow. Um and so you might need a lot of resolution on that that um feature because it's a very small feature relative to the rest of the simulation, but it's very important. And also around the edges of the stars, uh the boundary of the stars, you want to have a lot of resolution so you can really study what's happening as the material uh it leaves in one star and hits the other star.

BryceUm and so this the technique that you use is you have a grid of a hierarchical grid of different resolutions. So you start off with a very, very coarse grid, um uh which is your root level grid, and then you can refine. So you pick a region of that grid, maybe multiple regions, and you say, we're gonna create a new grid that's gonna have twice the number of points that represents this region of the parent grid. And then you can refine further.

BryceSo to the applications I worked with, sometimes you could have up to eight levels of refinement. So uh basically like you you you take like some like sub-region of the of the grid and you say, like, okay, I'm gonna create a whole new grid that has uh uh uh you know a lot more points inside of it. And then you have to do what's you know interpolation and then coarsening uh between these grids. So if you're at the eighth level of refinement, uh you need to uh uh you know take an average of your eighth level very refined grid and you need to send it back up to the seventh level.

BryceAnd then the seventh level has to send it to the sixth and the fifth and the fourth and all the way up to the parent grid uh so that uh at every level of the grid you have a correct for that resolution view of the world. Um and I was thinking that with this with this fill problem, you could um, you know, if you if all you care about is just filling in the region, you could maybe take an approach similar to this, where you start off with a very coarse grid and then you partition it up, and then for each one of the partitions, you check, okay, are are all of the points in this partition within the boundary?

BryceUm uh and if so, you can do something simple, or if all of these points within the partition are not in the boundary, then you know it's pretty boring. You can just ignore it. And if it's an actual point where it's you know if if the boundary is within the the the sub the chunk that you're looking at, then you could go and uh you know look at it with greater refinement or something. Um so I don't know. At least my my mind it it it it sort of seemed like you could use a technique like that.

ConorIt was called adaptive metric something?

BryceAdaptive mesh refinement.

ConorYeah. It's funny when you were describing this, uh I actually almost implemented uh conceptually the exact same thing, but for a completely different application. I have uh I think I've mentioned it before on this podcast. I have a repo called City Stride Hacking that I use for creating heat maps and generating paths for my City Striding hobby where I try to collect streets all over the world. Uh but there is this limitation where when you're collecting the nodes that define the ends and uh curves of streets, you're only allowed to it'll the website will only return you a thousand at a time.

ConorAnd so I got around this by basically just like when you look at a uh rectangle defined by two latitude and longitude points, and you're trying to collect all the nodes in that space, it just I just defined like a a square small enough and then it just grids over it. But uh even that sometimes doesn't pick all of them up. And so I thought, you know, the smart thing to do would be just to uh have a recursive algorithm that looks at the top level, sends a request, and every time that you hit a thousand, you just partition your rectangle into like four sub-rectangles or like split it up by some like square thing.

ConorAnd then every time you send a request where you hit a thousand for that smaller rectangle, you just keep on sending requests where you partition your rectangle into smaller and smaller. And the nice thing about this is it probably actually ends up with fewer requests at the end of the day because as you run uh exhaustively a space like the Toronto, like I'm running, there's whole areas of the map where there's no more nodes because I run them all. And so at the top level, when you've partitioned it for the first time and then you've got like the bottom quarter of the map, that might result in like, you know, 250 requests with this really small rectangle that I had before.

ConorBut now at the top level, as soon as you get zero nodes, it'll just ignore that corner of the map. And now you saved yourself like 25 or 50% of the work. Anyways, while you were explaining this about this uh uh two-star, what did you call them? Red dwarfs or something? White dwarfs. White dwarfs. When you were describing that, I was like, huh, I never implemented this, but this is the exact same idea for something much less important that I never did implement, but would be a neat thing to do, but I was too lazy, and so I just, like I said, I just kept the small rectangle. And then actually, James, I hope James doesn't listen to the podcast.

ConorHe probably doesn't know who I am. Um, but I think he's been observing that people are uh like abusing or hitting his servers over and over again uh because he over time has been making it increasingly hard for me, for my algorithm, like my um Python code that hits the server like a thousand times. Uh he put these like rate limiting things in where every once in a while now it'll be like, sorry, you've exceeded your threshold, please wait like five to ten minutes. Because you need to be logged in with your credentials. Uh so I have some like, I don't know, Python cookie header thing uh that enables so he knows like which account it is and then just like blocks that user.

ConorSo it's kind of like a cat and mouse game. Currently, I have uh I just I put some whenever I you get the first warning, I just wait for like a minute or something. And that that seems to have worked for the moment, but uh anyways, a very interesting idea. And I'm sure uh actually speaking of the summed area tables from earlier on, we got, I think, messages from three or four different people. Off the top of my head, I know that Phineas, uh, soon to be guest of the upcoming Arraycast episode, and former guest that we had dinner with that time we went and played an escape room.

ConorUh we went to that vegan restaurant. Um so Phineas, uh, we recorded an impromptu uh episode at that restaurant. He reached out and said that I think it was for uh book orders, uh, because he works in finance. Um he said that they use uh some Daria table algorithm to get uh some information off of those. I might have that slightly wrong, but in finance they use it. And then I think also on GitHub uh in our discussion, someone had mentioned that they use it in image processing for something.

ConorThose are two of like the three or four. I had three or four people ping me and they were like, oh yeah, we use this algorithm for X, Y, and Z, where they were all completely different fields and completely different things. But it seems to be uh and I bring that up because this algorithm that you've just mentioned, this kind of adaptive drilling in, I'm sure is used also in uh a couple different places because it seems like a very intuitive way to get like highly detailed information in a certain space and then ignore the other spaces that you don't really care about.

BryceYes, it it it is quite widely used. I somewhere I have a great video, specifically the simulations that we did.

ConorUm but uh if they're online, do some digging afterwards and uh send me a YouTube link.

BryceI'll I'll show you I have a still picture. I'll I'll show you that at least.

ConorUm just uh tweet or or blue sky or mastodon or is there a generic term for social media so that we can uh No? Do we just say do we still say tweet?

BryceOh, wow, I shared my screen and the audio got weird. It's fine on my end, so um but here's the you could you can see here there's uh there's one star that's denser and uh and more massive and uh then there's the other one that uh has the stream of material going out from it. And then you see in the bottom one here, the that shows the what the in the size of the entire grid, and then those two stars are just in the center, so they're pretty small relative to the size of the grid. And then you can see these, you know, it more and more refined grids surrounding the stars here on the on the left.

ConorTake my word for it, listener. It looks cool.

BryceI will I will find that video, um, which I'm sure is on one of my other hard drives. I will find it later in uh uh uh because it's uh it's pretty cool. It's I I've actually been looking for it because I wanted to show Ramono.

ConorTo get back to the the your original question like 15 or 20 minutes ago, which is probably in the last episode at this point, so I'll repeat the question in full was you know, do you use pen and paper? Or that was this author, I think Panos was his name. Uh, you know, an algorithm is a thing that you can do by hand. I will say at my very first job, I used to use pen and paper, and it was a classic thing. I was literally just talking with my buddy Victor, um, who also worked there uh and has moved on to a different company since then. So we were both actuaries, and a part of uh actuarial calculations are these things called projections, and you are forecasting the financial and uh mortality future, if you will, of groups of people, and you typically will have like adverse scenarios that are like a projection off of a projection, and then you have to compare, like you have to hold money in the form of what they call reserves or capital uh in order for if some adverse situation uh happens that you've got the money on your books to pay out these insurance claims.

ConorAnd that you would do by hand all the time because you'd have you know different mortality rates. You'd have this sort of one line, which is your uh main projection, and then you'd have these kind of uh adverse scenarios at the five, the seven, the ten, and then those would have like different mortality. Anyway, so you'd do that stuff all the time to try and visualize this complex calculation. Uh so when it comes to stuff like that, that is a lot going on, um, it's not so much describing the algorithm, but it's more describing like uh a visualization of a calculation, if you will.

ConorUm that stuff uh I definitely think is super useful. But I'm I'm not sure the last time when I actually pen and paper worked through like a generic algorithm. Yeah. I don't know. Maybe we're breaking Sean Perrin's heart right now because it's like a although I'm sure he just sits there like a monk and does it in his head. Uh I don't know. Well, I'm sure we'll get a message from Sean um clarifying whether or not he actually uses pen and paper.

BryceUm I I w I think maybe part of the reason why I do it is I as much as I I hate to admit it, I do actually have a college degree, and that college degree is in uh applied math. And I I I've said I think a few times, maybe even on this podcast, that um I feel like the one thing that I really took away from my math education that I use with some regularity is uh uh proofs um going through and and constructing a proof.

BryceUm and actually sad story, my my I had this professor who was teaching our class on on proofs and logic, and he was a great professor, and he actually he he died very suddenly of a heart attack in the the middle of the semester. Um and I remember I I walked into class um uh and me, you know, I was I was me, so I was always late for class. Um uh and uh I walked into class and uh he wasn't there, there was some other professor there, and I just assumed, oh, I I've come into the wrong class.

BryceAnd so I very quickly exited and started walking down the hall, and then somebody ran out of the classroom and they were like, no, no, no, no, come in, like something's happened. And they told me that unfortunately our professor had been out for a run and I just had a heart attack. Um, and it was very sad, but he was an amazing professor. Um, and uh I feel like maybe one of the reasons why I go and write uh stuff uh out by hand um is that like I'm just going through like the process like of coming up with a proof to prove to myself that this algorithm is gonna work.

BryceAnd um, you know, when I'm when you're constructing uh uh a uh uh like an inductive proof, um you start off with like the zero case and then the one case and then the two case. And I and I think that's maybe why I start off with looking at like, you know, some you know one small problem and then I look at another small problem, um, etc. etc.

ConorYeah. I definitely don't have that background. I mean, I took a discrete mathematics course, but I wasn't paying attention too closely. And I also had the thought too that you know the reason I don't use pen and paper? It's because I have APL. That is basically like not the inductive proof thing you just described, but like I can go and visually explore some algorithm or some solution in a REPL. And you you actually can do this with like Haskell as well.

ConorLike with a REPL, it's it's like the digital equivalent of like pen and paper. You can see step by step every single time you add some operation to some expression. Like literally yesterday I was presenting and I was showing solutions to that sushi for two problem uh that I presented in like 2023 at C on C and maybe one other conference. And I do it in the REPL, and it's like I'm showing you that when you chunk by it result, like you can see it visually, like you are permuting and changing an input, and you can see it at every step.

ConorSo that is kind of convincing yourself, like, okay, I do this next thing, I expect this, okay, it happens. I do this next thing. Oh, right, there's a corner case there uh when you have whatever. So I'm not I'm not sure. Like, how often do you spend time in a REPL? I'm guessing Python's the only language that you really use actively that has a REPL. Like, do you spend any time in it?

BryceOr yeah, I do. Um I think I my my way of learning is by doing and experimenting. I'm I'm very unlikely to go and like read the documentation, learn how something works. I'm much more likely to go and pop into you know, for C God Vault, for Python, just into the REPL to just play around with something and and learn how it works uh the through example through doing. So I I do do that fairly frequently.

BryceI feel like I do it for C2, and the C equivalent of a REPL is to just go into God Vault.

ConorYes. That is as close as you will ever get to the REPL feedback uh when compared to languages like APL, Python, Haskell. Yeah, etc.

BryceI d I did I did just find the video. I will show you the video.

ConorAlright, here we go, folks. Maybe I'll cut in the audio if I if I have the energy.

BryceWhich I do sometimes I do because I don't think there is audio from the video.

ConorAlright, folks, I will not be cutting in the audio.

BryceLet me see if I can make it a little bigger.

ConorWe're in PowerPoint. We've got some blue with two dots. Oh, PowerPoint's gone. Uh I can just share my entire screen. It would be cool if I ever changed the thumbnails for uh ADSP the podcast. I would definitely put this as the thumbnail. But it's been 218, 19 episodes, and I've never changed the thumbnail once, and I'm not about to start now. Alright, here we go. We're hitting the play button.

BryceSo the the grid here is rotating. Um but uh it's a rotate.

ConorThat's a rotate, folks. Holy smokes.

BryceUm so the stars are actually rotating around each other incredibly fast. Like white dwarf stars are rotating each around each other at like, you know, uh a few times uh uh a second in some cases. So these things are these are giant stars that are spinning around each other very quickly, but we rotate the grid um at with the stars, so they appear to be rotating very slowly here because the frame of reference is rotating. And you can see here it's now zoomed in, you can actually see the grids.

BryceAnd you can see that one of the things that is uh that we do with the adaptive metrophone for these types of simulations is we add and remove refinement as needed. So you can see um as these stars moved, those little grids were, you know, finer grids were appearing and disappearing, tracking the stars as they move around this grid here. And now you can see that there's much coarser resolution towards the edges of the grid, uh, where the where you've just got some stellar matter and not the stars themselves.

BryceUh the reason that that uh that you study these things is that these are one of the um uh possible progenitors of uh type uh uh 1A supernovae. Um uh type 2a supernovae, or some type of supernovae, which are uh uh used super stellar distances uh because we believe that we up, there it goes just slurped up the star. And you could see as it zoomed in, you could see that towards the edges there was like lower resolution and in the center there was higher resolution.

BryceAnd uh here's uh here's another little little visual, and you can it shows you just how those finer grids can track features because they get dynamically added. And so like in in the there's two images here. There's one that shows before the accretion stream forms, and there's no fine grid between the two stars, and then there's an image that shows after it it forms where you've got these fine grids tracking that stream of material.

BryceAnd that gets added dynamically, and then you remove the resolution dynamically as needed to save computational resources. Anyways, yeah, but they're they're pretty cool, folks. They're pretty important for answering some of the fundamental questions about the universe because uh we we use this type of supernovae to uh measure stellar distances because we believe that they put out a fairly uniform amount of energy when these types of supernovae explode. And so if you can see, oh hey, this type of supernovae exploded over here, and we know how bright it appears to be um uh relative to us, then we can measure roughly how far away that thing was.

BryceUm and so it's measuring events like this that were we were able to determine that, oh hey, the universe is expanding. So, anyways.

ConorUm This is uh what do you call it? Cosmology 101 or 201? Maybe 401 with Bryce Lelbeck?

BryceAnd the reason that we would want to simulate these things is that you know, if we use these things to to measure stellar distances and to understand our universe, we want to make sure that we have a good understanding of uh uh their dynamics and whether they actually are standard candles and what actually causes these types of supernovae to uh to occur. The the theory is so white dwarfs are very, very dense. Um and uh once a white dwarf goes above a certain mass, which is called the trans chandel-secar limit, um, then there's literally no space for for any more stuff in the center of it.

BryceUm and then it just reaches a point where uh if any more stuff gets pulled into it by gravitational forces, um it'll just gonna explode because uh uh of the radiation forces and simply the lack of of any space left in the core of this very, very dense thing. It's like, you know, this thing is like essentially imagine there's no space between the atoms. It's all just completely compacted, but more stuff keeps coming in because of gravity. And so at some point something has to give.

BryceAnd then the theory is it goes boom.

ConorThere's the cold open right there. And then it goes boom.

BryceBut um one other thing I wanted to talk to you about from this book.

ConorUm so Yeah, I was gonna say we've we've got like, I think it's five minutes till we hit the hour mark, which would be uh a good two-part we'll call I don't know what we'll call it, algorithms, panos algorithms, one, two, or airport algorithm book. We'll we'll kind we'll kinda we'll come up with something catchy. So what's the rap wrap uh put a bow on this with uh the last thing or one of the other things that you wanted to chat about uh worth highlighting?

BryceSo so uh well I I had a whole new other topic.

ConorA whole new topic. Yes. All right. End of episode two nineteen, start of episode two twenty. Be sure to check these show notes either in your podcast app or at adspthepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions. Thanks for listening. We hope you enjoyed and have a great day.

BryceLow quality, high quality, that is the tagline of our podcast.

ConorIt's not the tagline. Our tagline is chaos with sprinkles of information.

Open the transcript file

Hosts and Guests

Nobody is credited on this episode yet.

Credit the people on this episode

Be the first to rate this episode

More episodes

All episodes
  1. Episode 313: C++26 Reflection vs CRTP, AI, Kids & More with Zach Laine

    Nov 20, 202647 minAudio

    In this episode, Conor and Bryce chat with Zach Laine about C++26 Reflection vs CRTP, AI, kids & more. Link to Episode 313 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP:...

    • Apple Podcasts

    Credit the people on this episode

  2. Episode 312: The C++26 Contracts Fiasco

    Nov 13, 202652 minAudio

    In this episode, Conor and Bryce chat with Zach Laine about the C++26 contracts fiasco. Link to Episode 312 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...

    • Apple Podcasts

    Credit the people on this episode

  3. Episode 311: Career Changes, GPUs & More with Zach Laine

    Nov 6, 202628 minAudio

    In this episode, Conor and Bryce talk with Zach Laine about his career and the career changes he has made. Link to Episode 311 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials...

    • Apple Podcasts

    Credit the people on this episode

  4. Episode 310: Leaving NVIDIA for... ?

    Oct 30, 202624 minAudio

    In this episode, Conor and Bryce talk about Bryce's next chapter and where he is leaving NVIDIA for. Link to Episode 310 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The...

    • Apple Podcasts

    Credit the people on this episode

  5. Episode 309: Default Construction & CppCon 2026 with Jason Turner

    Oct 23, 202629 minAudio

    In this episode, Conor and Ben chat with Jason Turner about default construction in C++. Link to Episode 309 on Website Discuss this episode, leave a comment, or ask a question (on GitHub) Socials ADSP: The Podcast:...

    • Apple Podcasts

    Credit the people on this episode