Algorithms + Data Structures = Programs - Episode 255: 🇩🇰 C++ Copenhagen Meetup & Replicate

Episode Date: October 10, 2025

In this episode, Conor and Bryce record live from Denmark! They recap the C++ Copenhagen Meetup hosted by Symbion, the replicate algorithm and much more!Link to Episode 255 on WebsiteDiscuss this episode, leave a comment, or ask a question (on GitHub)SocialsADSP: The Podcast: TwitterConor Hoekstra: Twitter | BlueSky | MastodonBryce Adelstein Lelbach: TwitterDate Recorded: 2025-09-20Date Released: 2025-10-10Roku Engineering SymposiumDenmark DGX SuperpodTweet of Beer PouringAPL replicateC++98 std::copy_ifArrayCast Episode 110: Implementing ReplicateAPL Wiki Replicatethrust::copy_if (stencil overload)cub::RunLengthDecodethrust::reduce_by_keythrust::permutation_iteratorBDE LibrariesASL LibrariesEASTLIntro Song InfoMiss You by Sarah Jansen https://soundcloud.com/sarahjansenmusicCreative Commons — Attribution 3.0 Unported — CC BY 3.0Free Download / Stream: http://bit.ly/l-miss-youMusic promoted by Audio Library https://youtu.be/iYYxnasvfx8

For the Danish listeners that are currently listening to this podcast, I do apologize once again on behalf of Bryce. I would never say such a blasphemous thing while in Denmark. The commonwealth press makes me think, is there a relation to replicate, in particular the second overload and run-length encoding? We're going on a boat that is not a boat, but it looks like a boat. You're likely to die from a...

I don't want to say a cyclist. I'm from a cohort of cyclist. I almost died multiple times. I think we could just take one of these boats? No. Should we take the ferry? No. Well, why not?

Welcome to ADSP, the podcast, episode 255 recorded on September 20th, 2025. My name is Connor, and today with my co-host, Bryce, we record live from the streets of Copenhagen. In this episode, we talk about multiple implementations of the replicate algorithm, Denmark, boats, and more. What's the name of this street? It's right there. You try to pronounce it. Congenstorv. I'm going to say that was probably like a five out of ten.

You would get a one. I would get a one. I'm not saying I wouldn't get a one. All right, we are here in the beautiful city of Copenhagen. It is 9.24 p.m. on a Saturday. We are in-between speaking engagements. We're just finished up two days. One in Arhus.

Orhus. Orhus. At the Roku Engineering Symposium. And then the next day we came to Copenhagen, and we spoke at the Copenhagen C-Bus-Bus meetup, which was pretty great. I think we had great audience interaction. Yeah, you're shaking your head. What am I doing wrong here? You've got the flattest introduction.

Don't you remember when we were on the road in Slovenia? Every single time this would happen, you'd be like, all right, we're back. Listen, folks. Hey, it's 924. I am tired. Weak sauce, folks. It's also 924 for me. And guess what?

I'm fired up. We're live. back, technically not on the road, from Copenhagen, Copenhagen, Copenhagen, and Danish. And let's start walking. Let's start moving. We're on a famous street. We're on the water.

People are out and about. People are drinking. I am also drinking. It seems to be a party city, because the last two nights I have noticed a lot of people everywhere. Out of the bars, hanging out, chilling. I don't know if it's a special time of year. Should we walk this side or this side? That side's quieter.

Now, we should walk on this side. We should walk on the phone side. You can't talk without the mic in front of your mouth, Bryce. I understand. You should have gotten two mics. I have two mics. I'm not traveling with two mics. Anyways, listen, folks, we're fired up.

I'm fired up. Bryce is a little sleepy. He's a little tired. But we are still in the land of the Danish. We talked about the rankings. We're not stopping at the hot dog cart. If you want a snack, we've got a snack after. Okay?

We're recording. If you were hungry, you could have picked up something when I got the beer of Denmark. Listen, folks, I've got a Carlsberg. I've learned many things since coming to Denmark. We love Denmark. It is the country of Jonas Vingegaard. I knew that Pagacha were talking about the tour to France, folks.

I knew that Pagacha was from Poland. For some reason, I guess it's because I've never visited Denmark. So whenever I learned something about a Danish person or a Danish thing, I just don't remember it. But I've been to Poland many times. I've been to Vrotslav. Actually, I've only been to the airport in Warsaw, but I'm in to Krakow.

I've been to Poland many times, but never been to have. It's true. I've been to Rotslav two or three times. I've been to Krakow once. I've been there three or four times. Anyways, the point being I know things about Poland. I knew absolutely nothing about Denmark other than Copenhagen was the capital. We talked about this before. We didn't know about Orhus.

And we're fired up. We're excited. We are also excited to be walking and talking. Do you think we could just take one of these boats? No. We're walking past. These aren't just boats. These are ships.

And I don't know why Bryce would have that thought. But it's definitely not possible for the two of us to man this. I know nothing about boats, and definitely not these boats or ships. What was I saying? Right, the beer of Denmark I didn't know was Carlsberg. I knew, you know, Heineken is Dutch, and Moretti is Italian, and Stella is Belgium. I know a lot of things about a lot of beers. Didn't realize that Carlsberg was Danish.

Jonas Vingegaard is Danish. And Denmark is now the soon-to-be owner, a land of the biggest, what is it, DGX? Superpod. Jensen was here, shaking hands. Yeah, I was talking with the wonderful folks of Symbian last night when we were at the meetup. You just mentioned that. The talks were awesome. The folks that were awesome. There's a tweet online showing me pouring. I don't know if it was Carlsberg. It was probably some other kind of Pilsner. It might have been Tuoborg. I've seen that around here a lot. Anyways, so we're fired up. This is going to go on the list of places we've recorded. When was the last time we walked and talked? Was it Venice with Rob Leahy? no it was not venice with rob lihi it was in new york city but maybe also with rob liegee we did walk no no maybe we just recorded in a bar there yeah i'm trying to think because we we were in new york i think we were on the street i think we were on the street the listener will tell us if yes if you count the transition from adobe i don't want to say hq because it's definitely not HQ, but, like, the Adobe New York offices with Sean, uh, we, all New York offices can be considered in HQ.

Fake news. Adobe HQ is in San Jose. We know that for a fact, folks. Anyways, uh, we recorded with Sean, but then I think at some point, either going to, I think it was going to Adobe offices, we were in a cab, and then we transitioned from the cab to the elevator to a room. We technically, there was a little bit of walking there. We never start to finish, did a podcast while walking in.

talking but we are now we got a lot of people they are people watching and they're staring at us they're probably thinking what are these guys doing it's a little bit awkward folks a little bit awkward i wanted to walk on the other side and brice said no and now people are staring at us the other side the other side is the quieter side do that again the other side is the quieter side oh i see uh i mean i know i said no to dessert but i'm reconsidering oh we're going to get by car we're not getting we're getting dessert we're getting it after We're not taking a dessert break right now. Scott, it's like, it's like, I'm basically with a child here, folks.

He sees ice cream and he's like, Mommy, can I get the ice cream? It's like, no, we're doing something right now. I declined dessert at the restaurant. I declined dessert at the restaurant. That's your own fault, something like a child would do. And then five minutes later, they want what they said they didn't want. I'm going to pass. We're going to be healthy today.

You already, I told you to give me a healthy snack today. And this guy brings me a chocolate chip cookie that has a bunch of pistachio cream on top of it, and then the whole thing is coated in chocolate. It was the least healthy thing I can imagine, but it was very good. By definition, if the whole thing was coated in chocolate, it didn't have patasio on top. It had patachio. But there was sascio was on top of the junk. I feel like for perhaps digressing from important things that the listener may want to.

No, no, no. This is important, folks. Before he said, get me something healthy, he said, get me something savory. And so he gave me two different instructions. And, you know, which one are you supposed to listen to? The one that you think Bryce actually wants, or the last one? But you got, you got, I asked for them in savory and healthy, and you got me a cookie. Oh, yeah.

Savory crepes are the ones that don't have, like, chocolate sauce. They're the ones that have, like, meat inside of them, right? Correct. All right, I did mess that up, folks, a little bit. I did mess that up a little bit. Hey, listen, it's not on me. I was lightheaded. I was low on calories, and he's lucky he got anything, folks.

Anyways, we're talking about Denmark. We were talking about the folks at Symbian. Shout out to Jens, Nina. What? You said something about them getting the world's largest DGX SuperPod or something like that. Yes, I discovered that last night. And anyways, Denmark, I love Denmark. It's honestly, is it my favorite Scandinavian country?

I don't know. We have to spend some more time here. We'll be back. Number two per capita listeners of ADSP. We gave out some stickers. Some people have been tweeting about it. It's been fantastic. And yeah, any other things to say about Denmark before, I guess we should chat a little.

I'm trying to think about what my... favorite Scandinavian country is the thing is we've only really had one day

here in Copenhagen so I don't think that I can really include Denmark in the rankings

yet but I would have to say out of the ones that I've been to which would

be Finland Sweden and Norway and I think I've been to the capital I haven't been to Helsinki

really but I think I got to go with Stockholm I got to go with Sweden I think is my favorite

it's stock home not Stackholm? I mean, this... What are you Texan? No on to this thing? Uh, yeah, why not?

Okay. Well, if it ends with us in the water. We're going on a boat that is not a boat, but it looks like a boat. Yeah. Anyways, why Stockholm your favorite? And also, do you realize the blasphemy of you saying that Sweden is your favorite country of the Scandinavian countries while we're in Denmark? I'm just saying I have not had enough time to evaluate Copenhagen, but out of the ones that

have had enough time to evaluate Stockholm. Um, there was a lot of history in Stockholm. It was also one of my first international trade. Maybe it's not a lot of history in Denmark. We've all heard of that famously. I have not had enough time here to evaluate. I really enjoyed the... I got to see the Vasa in Stockholm with, you know, the connection to C++, yeah.

And, you know, very efficient train system. I really like to walk around the little, like, old market part of town. I just... It's... Yeah, a couple good meals. I just have fond memories of it It was one of my first trips I think that's probably why

I just have fond memories of it Because it was one of my first trips For the Danish listeners That are currently listening to this podcast I do apologize once again On behalf of Bryce I would never say Such a blasphemous thing while in Denmark

And I would It's hard for me I mean I already know that I love Denmark And I think I love all the Scandinavian countries I've been to all four I've been to all four capitals I got to be honest, Norway is the frontrunner primarily because that's where I proposed to my fiancé

and the Lofaten Islands in rain specifically for any Norwegian listeners. We do know that we have a lot of them. We do know we have a lot of them. We do. Norway, I think actually the rankings did get adjusted a little bit. I can't remember off the top of my head, but the Isle of Man,

due to its very low population and potentially one listener there or a traveler that is a listener from somewhere else, I think they're ranked number six And Finland drop below that I think Norway might be number five now Independent country though Is that a British

I believe it's a British protectorate Of some form I did see that there was Greenland Actually Registered as its own country On the platform that I'm The Isle of Man is a crown dependency So

No offense to the people Of the Isle of Man I'm just saying That it's separate front like you can't really judge it in comparison with say like Norway or Sweden which is a separate independent country but but the point uh that I'm about to make here is that we were questioning on the last recording two days ago on the way from orhus to Copenhagen that there was 205 countries and I did say that I thought there was 206 bones in the body and 194 plus or

minus depending on the count if it's UN plus or minus clearly they have one of these higher counts because Greenland is separate from Denmark aisle of man is separate from the UK um the rule the rule for this podcast has to be whether or not you have a whether or not you have a the rule for this podcast is whatever our platform so because our platform disambiguates

between Greenland and Denmark which might mean that Denmark if it included the Greenland listeners might be number one. Here let's get the Carlsberg in the show what are we doing? Clearly we will cut the silence out folks of Bryce taking a photo of me anyways I think Norway's

the frontrunner also when we stayed at the hotel when I was at ND or we, my partner and I, when we were at NDC, Oslo, and when we were in Trondheim, almost all the places that had breakfast, they had multiple types of smoke salmon. I love seafood, and one of my favorite seafoods is smoke salmon. I grew up living off of it, and I've never had options, and the seafood in Norway is phenomenal. But I got to say, Finland has the saunas. Denmark is just absolutely gorgeous. I don't want to upset our Dutch listeners, and I am half Dutch.

So what I am going to say is definitely going to be more blasphemous. Actually, is it more blasphemous? I'm not sure. But if I have to compare the Netherlands and Denmark, Denmark might be in the lead. And the reason for this is because they're very similar, in my opinion, in that they're kind of built around and on the water. But the Netherlands, specifically Amsterdam, is chaotic. You're likely to die from a, I don't want to say a cyclist,

I'm from a cohort of cyclists. I almost died multiple times. And it's just crazy. They do have much better birds. Denmark has a bit of a weak bird game. But running around today, it was just absolutely, the recommendations that I got from the folks at Symbian last night for where to run were absolutely amazing.

Anyways, those are my hot takes. Bryce has been trying to say something, and he's been politely waiting. I'm going to hand the mic over to Bryce. Let's get Bryce's thoughts. I don't even know where to begin. There are so many ways in which you've been. so many countries in such a short period of time.

Who did I think? Potentially the Dutch. Oh, I was going to say, I was going to say Norway. I love my time in Norway. However, it was very cold and very rainy, but we did have a wonderful time in Oslo and Bergen last year. And we're very excited. Very excited to be going back.

Very excited to be going back. But I think we should talk about something technical. That's true. Well, I think we ought to talk about the thing we were talking about at dinner. Ah, we can't talk about that yet. Well, we can talk about it in the abstract, yeah? Uh, is there, is there even anything, is there even anything concrete, though, to hang on to there? Well, yeah, yeah, just describe, describe, and, and, you can't, we can't even say, you can't even say that?

I think you can describe the nature of the thing. Let's just wait, let's just wait three weeks, and then it'll be, this isn't going to be public, this isn't going to be poster through. No, that's not true. It'll be published in maybe two to three weeks. The problem is that I have an issue with, I guess we can talk about the example. I have, yeah, a library that is in the midst of being open-sourced. We'll be able to start talking about a lot more. Actually, we might be having a topic that we can switch to that I mentioned a couple episodes ago.

But the problem is that there's a problem that we don't actually know what the problem is. And so we spent half of dinner talking about solutions to the potential problem and realizing that what I thought was the source of the problem probably isn't the source of the problem. But we had an interesting conversation about lifetimes and ownership in these lazily evaluated frameworks that I think is... Too many details. I think it's fine. I think it's fine. I think it's pretty...

I don't think we're going to get in trouble for this. I don't think we're going to get in trouble for this. I don't know. I don't think. I don't know. We could just talk about replicate. So you just listened to her, you just heard a bunch of beeps, beeps. And so we'll be revisiting that.

Are we just going to sit here? We're going to chill here. We're going to chill here. All right. So there might be a little bit of background music from some party on the water, but hopefully you can't hear that too much. Replicate is a function from APL. And in the version that exists in APL, it's a binary function.

It takes two arguments, a sequence or an array. And the second argument is a what we will call index mask that corresponds, or it has the same length as the, original sequence or array and there's technically two overloads of this one of them the second argument is an index max the other one is just an integer so maybe we'll

start with the integer version because that one's a little bit easier for me to wrap my head around always yes so we'll we're going to use for our source array a character array because it's going to be easier to keep track of the input so if your character

array is A, B, C and you call the overload that takes an integer so you're arguments are the string or the character array ABC and the number three, your resulting output is AAA B, B, B, C, C, C, C. So you replicate or you repeat every element and number of times. The other version, the overload that takes an index map, where I guess index map, we'll just call it an integer sequence that corresponds to the length of your character array or your array.

We'll replicate or repeat each corresponding element, the number of times corresponding to that integer. So if you have ABC and one, two, three, your resulting sequence is A, B, B, C, C, C. So it's similar to a copy if, a stood copy if, or a thrust copy if, except that you can think of a copy if

as a specialization of replicate, where the maximum value of your integer is one. So it can just be zero and one. And actually, is that how you implement it? No, that's not how you implement it because you implemented it as an iterator. Yeah. So, I mean, what's interesting about this

is that, and there's a whole Arraycast episode that talks about the implementation of replicate and also the history of replicate is that the history of replicate was that it originally started as an algorithm or a primitive called compress, which was the same thing, but

instead of an integer sequence, it only took a mask of truths and falses, so ones and zeros. So it is, in that specialization, it is identical to copy-if. Basically, you are doing a filter or a compaction where you drop all the elements or characters corresponding to a zero

and you copy the ones corresponding to a one, which is essentially copy if except that copy if, I mean there's multiple overloads in the thrust library, but the standard copy if, it just takes a predicate. So it keeps the ones that return true for a predicate. But in thrust, you have the overload that we talk about a lot, the stencil overload where you can pass at a sequence that anything that evaluates to a true is kept. Bryce has a question or a comment or a thought. Yeah, the commonwealth press makes me think, is there a relation to replicate, in particular the second overload and run-length encoding?

Yes, absolutely. So run-length encode, or it's actually run-length decoding. But so run-length encoding and decoding, for those that are not familiar with the algorithm, it basically turns your sequence where we had A, B, B, C-C-C, if you run-length encode that, you turn that into, I mean, there's multiple ways you can do it. It turns it into the iterator construct, basically.

It turns it in. Run lengthen code would take the expanded sequence and turn it into the compressed form that you could express with this replicate function. And most libraries that have a run lengthen code, the output will be an array of pairs or key value pairs or a dictionary or something like that. Or not usually a dictionary because that can be unordered.

So the A, B, CCC, it ends up as 1A, 2B, 3C, and those are usually stored as either, you know, subarrays of length 2 or pairs, whereas replicate, you know, it passes these as separate sequences as arguments to the function. But the point being is that you asked, does run length encoding, but what you meant was decoding have a relationship, is that the decoding of a run length encoding is basically, you know, morally. equivalent to a replicate because replicate just takes the sequence and the integers that you're expanding whereas a run length decoding you know actually i don't actually know what a run length decode what that API is but usually it'll unpack the pairs and then like do the decoding that way do you uh okay so this this brings us nicely to the next topic i wanted to get to which is um uh there's a couple separate questions here um the first one is uh do you implement the so the There's two forms of the replicate.

There's the one that takes the array, and it's the one that takes the engineer. Do you implement the one that takes the array of replication lengths? Do you implement that with run-length decoding? And if not, that's the thing that you ought to think about, because we have an optimized version of that in Cub. And I don't, so I know that run-length encoding and run-length decoding is commonly used in image processing and in like compression and decompression. I don't know the exact specifics of how exactly it's used, but I do know that there are tricks to implement it very efficiently.

And my second question is, in your current implementation today, how do you implement it? And do you implement the case of the replicate within differently than the replicate with, you know, different length for each input? Because I imagine that there are, you know, if you know that you're always replicating, you know, the same, for every element, the same number of times, I imagine that you can do more efficient things. So maybe you can comment about how you implement your replica. And we should say we've been describing replicate as a function, but the replicate we were talking about earlier was really the implementation of that through a replicate iterator.

So first of all, when referring to the two overloads, let's say integer and the array overloads, because when you said N, I thought you said in. And so if I didn't hear what you said, the listener might be confused. So for the integer over, and wait, to answer your first, question, I do not use, first of all, I don't implement, well, actually, so now we're going back to talking about the library that we shouldn't be talking about. It's okay.

It's okay to talk about the library. I don't implement. I do have a run-length encoding. It does not use Cub. It uses a thrust implementation that relies on reduced by key. And I don't have run-length decoding as a method. And also, I do not use the cub run-length encoding or decoding in any of this replicate stuff.

It's all thrust-based. I know for certain Cub has a run-length in code, which you should definitely be using. Maybe you can comment about why you're not. I'm not certain if it has a run-length decode, though. So, yeah, that's interesting. I'm not using it because there are only one or two functions that rely on Cub directly,

because it's something that I only started adding at the very tail end of the work that I've been doing. Now that you mention it, it'd be very easy to just direct. rely on that, especially if it's specialized. So then how do you implement these two overloads today? I mean, so that is the topic of this episode. It's for me to ask you, how would you implement? Because when I was implementing this, I think actually the first way that I approached

it didn't end up working. And I ended up having to switch. And I'm actually going to have to pull up the code while you talk through how you think. So, I mean, I can actually, the integer one, is less interesting because the integer one I just do lazily and I definitely know

that the initial implementation was just an invocation of the thrust fancy iterator the permutation iterator because a permutation iterator basically just takes some mapping oh I see we are at a

ferry stop we might stop talking for a while We probably should go walk somewhere else No, I think it's fine We're just going to pause here for a few minutes While this ferry docks and undocks Should we take the ferry? No

Well, why not? I don't know where this fairy goes Well, that's the fun part For all we know, this ferry goes on like a two-hour loop And we're not going to be back here for two hours I mean, it could also go to, like, go to, like, Norway or something. Maybe we'll get there early. This is, this ferry is not a large boat, I would say.

It's, uh, and maybe holds, like, 20 or 30 people. So it's pretty clear that it is a local ferry. I'm going to take a picture for, for the listener. We'll put it on the social media. Oh, wow. That was, that was quick. We didn't even have a chance to get on that fair. The ferry's gone.

That sucker, look at how fast that thing's going. And for any of the very, um, For the avid listener that has referenced the photo online that Bryce will tweet and his saying that this only seats 20 to 30 people, his estimation abilities are wildly off. I would say this easily sits 100, maybe more. Okay, maybe it is more like that. I see ferries in Vancouver that are a fraction. I'm talking like a tenth the size of this that can pack in 20 easily. That's, you know, with standing room, that ferry can fit 200.

I said seat, though, to be fair. I did not say including standing room. Well, yeah, well, wow, well. Anyways, we're going to hand the mic back. We were talking about, so the integer overload, lazily done. I think the initial implementation was with a permutation iterator, and then I... Can you elaborate on that? So a permutation iterator, for instance, in the simplest case, if we go back to our original sequence of ABC,

we can give it a sequence, I believe it is, of indices in whatever order you want. And it's basically the equivalent of a scatter iterator. Why do they call it a permutation iterator? Nobody knows. We'd have to ask Nathan or Jared, the two authors of Thrust. but the same way that sequence the algorithm does not correspond to the iterator version which is the counting iterator

in my mental model is that scatter is the algorithm and scatter is an algorithm I see there another one is here all right moving no it's fine it's fine nobody has indicated that they're upset with us being here I mean fine we can move you finish there's another spot over there though

okay fine I don't know you kind of's being very Canadian about the fact that we're at a ferry terminal. It's a very stop, not a terminal. There was a giant spider above your head. Really? Yeah. So I don't mind moving.

That's the only reason I agreed. So, okay, so sorry, you're going to have to restart your explanation. Be sure to check these show notes, either in your podcast app or at ADSP thepodcast.com for links to anything we mentioned in today's episode, as well as a link to a get-up discussion where you can leave thoughts, comments, and questions. Thanks for listening. and have a great day. Low quality, high quantity.

That is the tagline of our podcast. It's not the tagline. Our tagline is chaos with sprinkles of information.