Episode 145: 🇸🇮 SRT23 - Parallel std::unique

[codereport]

Episode Link: https://adspthepodcast.com/2023/09/01/Episode-145.html

Feel free to write comments or ask questions 🙂

[7h3kk1d]

I'm not sure how adjacent_difference is implemented in parallel in the first place but I imagine a similar approach could be used to deduplicate. In response to Connor's note that if you run a parallel deduplicate that you'd have to run it again on the joined set, in reality you'd only need to do this on the very edge elements. So if there's some way to overlap the chunks that you're parallelizing over it seems like this could be done in a single pass

[codereport]

You are definitely right! The next two episodes we revisit this problem so updates are coming : )

[vmiheer]

Yup I think of adjacent difference, stencil is of size 2.

[vmiheer]

This pattern is so familiar with Stencil programming. If you chunk the array, each chunk needs to get last element from previous chunk. Scientifically called "ghost" region. And it should be possible in 1 pass. Here's the alternate problem, select an element if it's not seen in window of last k elements.

[JVApen]

I don't get how you can do std::unique in a single pass if using multiple threads.
If you cut the array in chunks, there is no way of knowing where to write in the original sequence without fully executing the first chunk.
If you somehow figure it out, you cannot write in the original sequence as you introduce a race condition with the processing of the first chunk.

Assuming you are writing to a new structure, you have the same problem.
While processing the second chunk, you cannot know where to start writing without the results of the first chunk.
The race condition does get resolved this way.

As such, you always have a second loop over the result (assuming no duplicates, this would be all data) or does this not count as a second pass?

A quick implementation of how I would approach this problem can be found here: https://compiler-explorer.com/z/boPcr1451

PS: I still have to listen to 147