Conor

Right up there with those fundamental operations is this adjacent transform. Let's play a game, folks! What's the name in the Q language for adjacent transform in C and MapAdjacent in Haskell? It's five letters and starts with the letter P. Welcome to ADSP the podcast, episode 145, recorded on June 21st, 2023. My name is Connor, and today with my co-host Bryce, we record live from the roads of Italy during the Slovenia 2023 road trip on the way to Venice. In today's episode, we chat about how to parallelize the algorithm stud unique. Now we can switch to, because we didn't talk about this on the pod. What was it a couple days ago? We were chatting in the car and we were talking about some algorithm stuff, and I asked Bryce, and so now is it I'll put it to the listener if you're washing dishes, if you're on a run, if you're on a walk, or if you're just sitting on the couch or sitting sitting in a chair in the backyard enjoying enjoying the sunshine, think about this. So we've got we've got the stud unique algorithm, which is an algorithm for removing duplicate values that are uh next to each other. And this is similar to an algorithm called deduplicate or distinct that we chatted about a little bit. But the difference is that one removes all duplicates. So the easiest way to do this, if you don't care about performance or order, is you know, in Python you can just take your list of values and then convert it into a set. And uh that's a property of a set is that there's no duplicate values. So std unique, similar to deduplicate, do deduplicate, but uh you're only getting rid of adjacent values. So the question is, we were talking about the parallel implementation of this in Thrust, but you can sort of think of this, you can sort of think of this sequentially as well. And the the question is, what algorithms, two algorithms are used to implement unique? There are two other standard algorithms. And we'll we'll let you think for a sec while Bryce adds some commentary.

Bryce

Because he already knows the answer if you remember. Uh don't really remember. Um I do remember talking through this. Um one of uh I think I said. Ah no, it's not remove if, yeah.

Conor

It's not remove if.

Bryce

Um Ah, right. Okay, one of them's probably copy if.

Conor

Copy if is correct.

Bryce

Yes, that's the second thing. And then how do you figure out uh which things you're removing? Um adjacent transform or is it just adjacent difference?

Conor

In thrust, it is adjacent difference. And if you actually look at the implementation on GitHub, it actually doesn't explicitly mention adjacent difference. You see something called, I believe it's called head flags, and that is a specialization of adjacent difference where you are using the not uh equal to, or is it equal to?

Bryce

So it's so it's got just to clarify, uh in this implementation in Thrust, it has ON temporary storage to store the the flags that indicate whether or not you're removing a particular element.

Conor

Yes, that is correct. Um and sorry, and and just to clarify, it's uh head head flags and tail flags are two specializations that just sort of shift where the the Booleans, the trues and falses go. Either sort of does it go with the first adjacent element or with the second adjacent element. So that's why they're called head and tail flags, and the flags to indicate where they're the same basically. So you want to do it adjacent difference with equal to. No, not equal to. So I was right actually initially, because whenever you have a different value, that's when you want to perform a copy. But whenever they're equal to each other, you want to ignore them.

Bryce

Um so I I will again ask the typical question that I uh that I I almost always feel like I ask whenever you ask me uh whenever we we we talk about how an algorithm is implemented. Why can't we do this one pass? Um and I do admit it's a little bit trickier to do it one pass, um, because doing it like you could imagine doing it a single pass with some sort of like adjacent view. Um but the problem is that it's it's you don't just need to see like those two elements. Like if there's a run of elements, let's say that you got like, I don't know, 64 elements, all of which have um the same value, um when you paralyze that and split it up into multiple different chunks, it's possible that that you know one thread could have um uh you know the f the start of that sh run of um uh of equal elements, and another thread could have the end of that run of equal elements. Um and so it's not it's not simply sufficient to just look at the two elements next to each other. You sort of need some some information propagated from um earlier elements from or from neighboring chunks. But I still wonder whether there's a way to do this in a single pass. What are your thoughts?

Conor

So it should we should be we should be clear here, we're talking about in parallel. Um sequentially, it is very easy to do this in a a left-to-right single pass fashion, where you basically just look at two elements at a time, and whenever they're not equal to each other, you just perform a copy. Um and you can also do it uh in place, definitely, sequentially. In parallel, though, I don't really see how you can do it.

Bryce

I think it you it's necessary to materialize that that uh head flags because I'm not so convinced that it necessarily is. Um this may just be another example of where you need the um uh a reduction that uh guarantees ordering, a parallel reduction that guarantees ordering, which we've talked about extensively before on this podcast.

Conor

I mean you you could probably do it, but it you're gonna end up with like a different implementation in that. If you're chunking things up and doing a unique on each one of the chunks, you would then need to basically do an extra, so it'd kind of be like the scan behavior. Not in that you need to keep state, uh, you wouldn't need to, but like you would perform uh unique on each chunk and then merge that back together, but then still have to perform uh unique on that merged chunks result because if you split a chunk in the midst of a contiguous sequence of equal elements, you're gonna end up with two elements in a row, basically, and so you need to remove those.

Bryce

So, I mean I'm not sure if that I don't think I'm actually I'm looking at the the the in thrust, the cub special oh no no, okay. I'm looking at yeah. Hmm.

Conor

You gotta the listener has no idea what you're putting.

Bryce

I I I was looking at the um the cub the I was looking at the the how we implement this in thrust, and uh no Connor is correct. We do seem to do it in two passes right now, which is I think unfortunate.

Conor

Listen, folks, we're headed past a speed camera. I'm happy to report we're not speeding. You know why? That's because the speed limit's 130, baby! Woohoo! We love it, we're going 126.

Bryce

We should we should clarify this is in kilometers per hour, not miles per hour for our uh American audience.

Conor

Yep. That's the only time basically uh we're not we're under the speed limit, is when the speed limit is 130. Uh or when we're in a kid's uh school zone because we gotta protect the children.

Bryce

Yes, yes, of course. Um uh what what is that reduction that we've talked about before?

Conor

Is it a it's a associative only reduce. Yes.

Bryce

Um uh so a reduce that supports non-commutative operations. Correct. Um so this non-commutative reduce, could you do it with that?

Conor

No. Well, this this is not this has nothing to do with reductions, right? Like um you can do it in your quote-unquote single pass thing, and I think really more Yeah, you're right. It's not really a reduction I need per se. Well, it's it's uh it's not about really doing this in a single pass. What we're trying to do is not materialize this uh flags that looks at the temporary storage. So I think I think we should clear it, clean up our be a little bit more precise about what we're talking about here. And you can do that with that strategy of like chunking and basically doing uh you uniques on each of your chunks, but then like I said, when you merge those back together, you're gonna end up still having to do another unique to get rid of the potential duplicate values that are at the edges of the chunks, which, like I said, I I'm not sure if that's gonna end up being more performant because you're basically you're doing things. I mean, I don't know, a lot of our algorithms still do things, uh do a lot of extra work.

Bryce

So maybe I wonder if you can do it in a single pass with a scan.

Conor

I mean even if you did do it with a scan, that's that's and uh no, you couldn't because you're getting rid of stuff, right?

Bryce

Uh yeah, yeah.

Conor

The problem is you need to eliminate stuff. You need something that can And the thing is too, is if you're doing unique on each one of the chunks, you're doing basically like a bunch of copy ifs, which is gonna be super expensive. You're doing copy ifs on each of the chunks and then you're doing a copy if for the final stud unique. I I just think probably the implementation that is there right now is the best one.

Bryce

I'm not convinced.

Conor

Here's the here's a follow-up though, is that uh the reason I kind of brought this up was that I love, I love, listen folks, let me tell you what I love. I love the fact that there are all these different specializations of adjacent uh difference and now adjacent transform. I think it's really like the fact that adjacent difference has such a bad name is really, it's really, really unfortunate because it is such, I think, an important algorithm. It's only an adjacent difference really is an adjacent transform, but this zip tail type of transform, what's called map adjacent in Haskell and zip with next, I think, in Kotlin, there's a bunch of different languages that call this different stuff, it's such an important pattern and deserves, like I think it deserves to be up there with, you know, we've got reduces and folds, we've got scans, we've got maps, we've got filters. Right up there with those fundamental operations is this adjacent transform. So much so that in the language Q that we talked about several episodes ago when we were uh solving that uh skyline problem, it has Q has an adjacent difference function called. Do you know what it's called, Bryce? I do not. Five letters and starts with a P. Let's let's play a game, folks. What's the name in the Q language for adjacent transform in C and map adjacent in Haskell? It's five letters and starts with the letter P.

Bryce

I got no clue. I'm still I'm I'm trying to I'm trying to trying to come up with another solution to this problem uh from before.

Conor

Uh we'll play hangman. You've got we're gonna give you three lives, and uh if you guess, we'll give you five lives, guess a letter.

Bryce

Uh A.

Conor

Incorrect, down to four lives. Uh D. Bryce guessed D, incorrect, down to three lives.

Bryce

Uh E.

Conor

Bryce guessed E, incorrect, down to two lives.

Bryce

Uh why?

Conor

I'm gonna let you have another guess, because that's a terrible guess, Bryce.

Bryce

Uh I don't know. I don't know. I think you should just tell me.

Conor

The Wheel of Fortune fans are very upset. I'll give you a letter, it's R. And that is P R blank blank R.

Bryce

Uh.

Conor

This is the name of the adjacent transform algorithm, Bryce. Think about what uh prior? Woo! You got it correct, folks. The name of the adjacent transform algorithm is prior. Note that in C, our adjacent transform argument or uh algorithm takes a template argument for the number of adjacent elements you want to look at, whereas prior is fixed to two. There's no way to customize that, so it only looks at two elements at a time, similar to how adjacent difference works. And in Q, there are actually two specializations of prior because they're so frequently used, and those are deltas and differ. So deltas is basically prior with uh subtraction as the default binary operation, but it's commuted subtraction. So you're similar to how it works in adjacent difference, you're subtracting, if you're looking at sort of two elements at a time and you look at one on the left and one on the right, you're subtracting the one on the left from the one on the right. So if you have an increasing sequence of one, two, three, four, five, you'll get back the values one, one, one, one, one. Technically five ones because you copy the first value to be the first value of the output sequence, which I think is broken and we fixed in uh C23. So that's deltas, and which is basically the default behavior of adjacent difference if you don't specify a custom binary operation. And the second specialization of prior is different which is the uh prior or adjacent difference algorithm with the not equal to binary operation. So it's it's giving you a mask of basically where elements change. And this is a very useful algorithm because there's another function in Q called cut. And when you combine differ with cut, you can basically get that chunking mechanism where it'll it'll split your vector up into uh sublists and throw it in a table. We love that, folks. So I just uh my whole little monologue here that I wanted to get on the pod, seeing as we gotta find things technical to talk about, while we're on the road in the Slovenia 2023 podcast, is that adjacent transform is just such a useful algorithm, and it's such a shame that in C we called it adjacent difference because it completely obfuscates how useful and powerful it is. And uh, and yeah, now you know we've got prior and Q, two specializations, deltas and differ. We love it. Over to you, Bryce.

Bryce

Alright. I I've been I I have not been listening to you listening to you the last five minutes. I've been designing this algorithm in my head.

Conor

You're the worst co-host, Bryce!

Bryce

Okay, so one of the key properties that you get with a scan is that can you hook me up with a cookie? I can hook you up with a cookie. Um of the key properties you get with a scan. Do you want me to open it up or you're able to Okay. One of the key properties you get with a scan is that every element of the output gets to include information from all of the preceding elements. So when I think about the output of a unique operation, um the I I think that this is a property that you need, right? That that if if if a unique operation is removing some elements, or another way to think about it is that it's it's sort of like shifting everything over. Like if you have two elements that are the same, you shift over the right element, and then like you add a you know an empty element at the at the end. Um and so uh figuring out how much you have to shift over like the last element is gonna depend on how much prior elements were shifted over. So you need some information from all prior operations. So it seems to me like this is something that can be done with a scan, and well let let's l uh let's think about this as we would like a mathematical proof. So let's start off with just the first two elements. So we have the first two elements. Um we're going to look at those first two elements, and if they're equal, um then well actually for the first the first the first two may be um a little bit boring because the first element has no one that is uh so like the for the absolute first element in the sequence you're always gonna retain a unique because there's no element preceding it. But for the second element, you're gonna look at the first element and the second element. And if um if that second element is equal to the first one, then you need to omit it from the output. Um I guess a question. Yeah.

Conor

What what are you trying to do after the scan to get it in unique? Are you trying to store the index at which you need to copy this to afterwards? Are you trying to store a Boolean that says we don't need to keep this? Like, what are you trying to do with the scan?

Bryce

No, this this is I'm trying to do I'm trying to I'm trying to do the entire thing with the scan.

Conor

There's no way you can.

Bryce

There's no way.

Conor

Why not? Scan gives you n, like you you have n inputs, n outputs. That is like fundamentally in a separate category than you need.

Bryce

Um not if not if I propagate the information about like how many I've moved over to the left and then like at the end I just fill it in with like tombstone values.

Conor

It's still not just it's still you still can't do it. It's impossible. Like, because of the like the semantics of the left to right, which is the associativeness of the scan operation, there's no way you can go backwards. Like when you get to the end of the array, there's a potential that you need to copy the very last value to be in the second spot. And there's no way to do that with a scan. Um, well, yeah, and so I was Which is why I was asking, like, what are you doing after the scan? Because I'm not following what you're trying to build up to.

Bryce

Oh, so so okay, so one thought that I had was that like to some degree you may be right in that you may you may need to do a scan over the reversed sequence. Um because it may be the case that you don't need to know um like like for the to know what the value of that second element might be, I need to know what the values is of all the rest of the the sequence.

Conor

Um I think this is a this is a fool's errand.

Bryce

I don't I don't think it's and also too, you gotta you're making the mistake, although maybe this is just you're doing this as a mental exercise, but uh unique is I I I I I think that it is I I simply think that the that it is it is incorrect that the only way to implement this in parallel requires ON temporary storage. I just I you you're I don't see any reason that you would need to do that. I think that you can simply chunk this up and and propagate the information between the different chunks, and I don't think that you need to do two two passes either.

Conor

Well, so we've talked about that solution.

Bryce

Yeah, yes, but you're but yours required two passes still.

Conor

Uh but like a scan inherently requires two passes anyways. So like but also too, the thing I was gonna say.

Bryce

Well, no, no, no. There's we now have a s we have a single pass scan implementation. Yeah, yeah.

Conor

Yeah, yeah. Um, anyways, it's I don't think scan's gonna work. The thing that I was gonna mention though is that uh unique is in the category of algorithms that or or category of problems where you only need a fixed amount of information to the left. You don't need the entire state up until then. And this is we've talked about this, I don't know, three or four times, although people probably forget. Uh and this is another reason why a JSON transform is such an important algorithm, is that anytime you don't need the entire like state that depends on everything up until this point and it's a fixed window, you don't want to reach for scan, you want to reach for a JSON transform. Uh because but but why why it's not a fixed window here? It's a it's a because it's just to the left. All you need all you need to know is the value of the element to the left of the current element. And if it's the same, then that's when you talk about it.

Bryce

Yes, but but really if you if the question that you're trying to figure out is where where do I put this value in like the output sequence? Like that requires more information.

Conor

You said that's not what you were doing, though. You said you were trying to implement this all in a single pass with a scan.

Bryce

To do this in a single pass, you need to figure that out.

Conor

And then do something afterwards. Why? What you're saying you need to figure out where it's gonna go uh in the final sequence, but like figuring out where it goes is not enough. You have to do something. You have to do something like that. Right, but if I figure out where it goes, then I can just put it there in the output. That's just a sort of it's gonna require a full pass of the data in order to get that. Like you can't do it as you go. Like otherwise or if you do that, essentially you're you've just implemented the sequential scan, which is what the sequential scan does. It basically has two iterators, the one where you're copying to and the iterator pointing to the current element and it's just doing that comparison with the last element. Anytime uh they are not equal you found a new value um and then you copy it back, you increment that s the first iterator and then you go on.

Bryce

But like that's the sequential well but we we can't we can assume random access uh iterators here so we don't need to actually keep the the that stateful iterator. We can just keep an an index into the iterator.

Conor

An index is the exact same thing as uh iterator for the purposes of copying to a certain place. But uh anyway it sounds like you you want like a parallel version of that uh that that style of uh implementation I have no idea how you would do that I don't think it's possible. Wow it may not be it may not be um it just it seems it seems wrong to me that we would need temporary storage for this doesn't seem wrong to me folks let us know email us we don't have an email let us know in the GitHub discussion at the top of the show notes and uh you know maybe maybe I've I've definitely been wrong before so yeah it's an interesting question interesting on the back of that truck oh yeah yeah there's been a lot of a lot of that uh would you like to describe the ad nope I would not if you meet if you meet us at a conference and we're at some kind of social night and there are beverages involved feel free to ask us what was and that's what that's how we'll know you're a real deep deep uh hard fan of uh ADSP is that you're referencing you know episode 146 or whatever this is and uh you'll be like what was on the back of that uh Italian uh moving truck and uh and we'll let you know and by that point we'll have stickers too so uh we'll we'll we'll give you a sticker while we're at it yeah all right well I think we're gonna take a little bit of a pause mostly taking a break because my hand is getting tired from holding the microphone up goodness man next time you gotta do some work you gotta do some uh some curls or something yeah here you know what you know what folks Bryce is tired no this is I can what do you mean I'm holding the mic now and uh what are we talking about now we're at episode 147 uh I I think we should take a break anyways because I'm I'm gonna I'm gonna I'm not gonna be able to get this this unique question off my mind I need a few minutes to room it room it's alright folks there's a chance there's a chance this is the last time we record and if if it is the last time we record we're gonna because we're gonna record for tonight in Venice.

Bryce

Why? Because we've got to record at the end of the road trip.

Conor

Uh yeah we're like what are we gonna do it in our hotel room? Probably yeah that's so weird we're definitely gonna listen folks this is my goodbye we're gonna apparently record again but my but my goodbye from the road of the Slovenia 2023 road trip I honestly I'm a little bit surprised that it even happened because I'll be honest it was it was a it was a joke I mean we did title an episode Ljubljana Here we come but if you had actually asked me at the time what are the odds that that's gonna happen I would have put it below 50% because uh taking a podcast on the road is uh you know it's novel especially in the tech in the tech space we're breaking we're you know we're setting whole new standards but uh but but we made it happen the stars aligned all right well we're signing off for now we will talk to you later and spoiler we do have at least two or three more episodes which we recorded in Venice so stay tuned next week to hear those and be sure to check the show notes either in your podcast app or at adspthepodcast dot com for links to any of the things we mentioned in today's episode as well as a GitHub discussion where you can leave questions, comments, or thoughts thanks for listening we hope you enjoyed and have a great day quality