Potentially faster dedup_by implementation

[Plecra]

It seems like the dedup_by implementation makes two passes over the data, making many more copies than are strictly necessary. Doing this allows the same_bucket implementation to panic without causing a leak. I wouldn't call this bad, but it was a surprise to see that it was doing the extra work.

https://godbolt.org/z/4To1a1

Mimicking the way Drain handles this and temporarily shortening the vector allows us to cut down on the copies (and also conveniently removes a panicking branch).

I wonder if it makes sense to document the trade-off that std makes here? Imo, it'd make it easier to use the library correctly in the way that https://doc.rust-lang.org/std/vec/struct.Vec.html#current-implementation-7 does.

[pickfire]

I wonder if it would be even faster to split it into two loops since once read != write it will always be hitting that branch in the loop to do unsafe { ptr::copy_nonoverlapping(read, write, 1) };? Maybe it could help reduce branch misprediction? I feel like this could be applied to the same thing right now. https://godbolt.org/z/szon9b

I wonder why are we not using mem::swap but instead use ptr::copy_nonoverlapping? And do we really need to drop_in_place, from what I see it does not do that right now?

cc @lzutao @the8472 who may be interested in this.

[the8472]

The leaking behavior is unnecessary. A drop guard handle the tail.

[Plecra]

@pickfire drop_in_place is being called in truncate in the current implementation. If you''re asking why I'm using ptr::copy_nonoverlapping, it's because it's faster than mem::swap, and we don't need to use mem::swap in this implementation.

I'm pretty sure you're right @the8472! My mistake, I wound myself up trying to justify the truncate call. I think that means this would be a direct upgrade to the current implementation?

https://godbolt.org/z/d5ahhM (Note: My implementation seems to be broken in a couple ways, it's just for reference)

[Plecra]

https://github.com/Plecra/alt-dedup-rs

I tried to flesh out the implementation a little, and make sure it's working properly. The behaviour of the DropGuard still needs to be tested, and it'd be good to do a more thorough benchmark if this was being considered for addition.

I also implemented the nested loop version. I can't tell if it helped with performance yet, since my computer gives the benchmarks too much noise.

[pickfire]

@Plecra Do you think separating the branch into a different loop is a good idea in case they are not in the same bucket?

[Plecra]

@pickfire I've used a second (and third) loop in the implementation to avoid the read != write branch, did I misunderstand your recommendation?

[pickfire]

It still does seemed to be in the loop https://github.com/Plecra/alt-dedup-rs/blob/main/src/lib.rs#L69-L79, I think making that in the inner loop is the same as the one currently since that branch will always be there. I didn't benchmark and I am not sure if it will be faster, just a guess avoiding that branch may end up reducing branch mispredictions.

[Plecra]

🤔 I honestly don't know how I'd implement that - it seems like we need to branch somewhere to verify the the copies are legal. I'd welcome a PR showing what you mean.

[pickfire]

I mean we are branching it in another loop since once the dedup read and write is different, it will always copy stuff when it hit the other branch, so instead of having 2 branches when the bucket is different, we could keep it to the other loop to remove the branch. Not sure if it's faster though.

[AngelicosPhosphoros]

@Mark-Simulacrum proposed additional optimizations for this issue.
Details here:
#92104 (comment)