Cheap equality check for Vector?

[maxbrunsfeld]

Is it possible to test if two Vector instances share the same allocated contents? I'd like to use im-rs in conjunction with the druid UI library, and implement Druid's Data trait for structs containing Vectors.

If it's not currently possible, would you be open to the addition of some method like .same for Vector (and possibly other collection types)?

[bodil]

This is already happening in the Eq implementations for all data types if you're on nightly, the reason being that it relies on trait specialisation (because you need Eq for pointer equality to be valid, PartialEq isn't enough, and we have to provide the slow version for PartialEq), which is a feature that hasn't made it to stable yet (I've been waiting for three years, not sure there's an end in sight yet). It might very well be a good idea to add a separate method for this in the interim...

[bodil]

Added a ptr_eq method. This behaves differently from the regular equality check in the case of inline Vectors, because they don't do structural sharing, so they'll always return false with this method. Let me know if that's what you had in mind or if you'd prefer a method which does regular equality checking with a pointer equality optimisation (which would need A to implement Eq).

[maxbrunsfeld]

Yeah, ptr_eq was exactly what I had in mind. Thanks for creating this sweet library ⚡️ .

[jakoschiko]

@maxbrunsfeld Is the current ptr_eq suitable for implementing Data::same? For a small Vector the ptr_eq method returns false for its clone:

let v = im_rc::Vector::unit(42);
let w = v.clone();
assert!(v.ptr_eq(&w)); // Panic!

Is a Data::same implementation allowed to do that?

[bodil]

As noted above, inlined vectors live on the stack and never share data, so they are never going to have pointer equality when cloned. If your Data::same means "is this the same bit of memory?" then in my mind the current behaviour is perfectly correct. If you expect a different result, you'd have to explain why.

[jakoschiko]

I don't know druid very well yet, but this is how I think it works:

There's an immutable Data tree and a mutable Widget tree. Each Widget node needs to be updated with a Data node. This is done by recursively decending both trees at the same time. Each Widget node tries to prevent the descent to its descendants by cloning its Data node and performing a fast equal check with Data::same on the next update. Data::same is not a shortcut for PartialEq/Eq, it has a different meaning ("for example two floating point NaN values should be considered equal when they have the same bit representation"). Ideally, if nobody touches the Data tree updating the Widget tree is very cheap.

But this does not work with the current implementation of ptr_eq. I don't know if the authors of druid assume that Data::same(&x, &x.clone()) == true, I could not find this assumption in the docs. It's just something I would assume when using an immutable collection (at least in any other language than rust).

[bodil]

The doc for Data::same reads:

If it returns true, the two values must be equal, but two equal values need not be considered the same here, as will often be the case when two copies are separately allocated.

It reads unambiguously identical to what Vector::ptr_eq does to me.

[cmyr]

heh was just pointed to this issue; did not know that druid had motivated the original ptr_eq implementations!

I think the behaviour of ptr_eq here is correct, but (as outlined in #129) the behaviour will definitely be unexpected for small collections; this isn't written down anywhere, but the approximate guideline I'd give for Data::same is 'pointer equality on the heap, bitwise equality on the stack'.

[xStrom]

The goal with Data::same is to know efficiently if the data is likely to be the same. False negatives are allowed (which the current Vector::ptr_eq can give) but false positives are not allowed (which the current Vector::ptr_eq can also give #131).

In regards to inline vectors giving a false negative with Vector::ptr_eq. This can be fine for Vector but for druid, just in terms of performance, it would make sense to just do a data check with those small inline vectors. There doesn't seem to be a way to know if a Vector is inline though. #129 proposes a potential Vector::is_inline method.

[bodil]

Vector::ptr_eq should definitely not be giving false positives, I hope #132 fixes that.