`Eq`, `is_empty` have false positives on races

[purplesyringa]

It is possible to have two concurrently modified sets A, B, such that neither version of A is equal to any version of B, but == returns true.

Set equality is implemented like this:

dashmap/src/set.rs

Lines 386 to 390 in 366ce7e

	impl<K: Eq + Hash, S: BuildHasher + Clone> PartialEq for DashSet<K, S> {
	fn eq(&self, other: &Self) -> bool {
	self.len() == other.len() && self.iter().all(|r| other.contains(r.key()))
	}
	}

Consider the following sequence of operations:

1. We start with A = {1}, B = {2}.
2. Thread 1 starts the comparison, verifying A.len() == B.len().
3. Thread 2 inserts 1 into B, resulting in B = {1, 2}.
4. Thread 1 finishes the comparison, verifying that the sole element 1 of A is present in B.

A similar counterexample exists for maps.

This means that PartialEq is not just inefficient, but strictly speaking incorrect. If the intention is testing code, perhaps eq should lock the whole map/set before performing comparison? I'm guessing consistently locking the shards in order should avoid deadlocks.

[purplesyringa]

I've realized that this also applies to len and is_empty: since the shards are locked independently, you can get the following behavior:

1. We start with A = {2}, where 2 is stored in shard 2.
2. Thread 1 calls A.len(), which locks the first shard and sees that it's empty. It then unlocks the first shard.
3. Thread 2 inserts 1 to shard 1 and then removes 2 from shard 2.
4. Thread 1 continues evaluating A.len(), locks the second shard and sees that it's empty.

So A is never empty in the sense that it's mutated from a single thread and there are elements in the set at each point in time, but A.is_empty() can return true.

I'm not sure how I feel about that. False positives on is_empty in particular seem dangerous if someone tries to rely on DashMap for synchronization. Since these are set-global operations as well and they lock all shards, maybe it's fine to do all the locking at the beginning to get a consistent view on the data structure? Or at least document them as approximations.

Though then again, you can simulate this even with iter. One could argue that iter().count() should produce the same result as len(), but if iter doesn't lock all shards simultaneously, this can produce a result that doesn't match any "true" value of the set at any point. You could even serialize a map with serde and get an invariant violation if you get unlucky, even if you only have one writer...

[xacrimon]

Yes, this is all correct and probably a WONTFIX to be honest. They're most there for completion and general these are not practically useful in a real application. My personal opinion is that you should really not be using operations like these on concurrent datastructures, len() etc are mostly there for testing and for heuristics/metrics etc so they're kind of a best effort thing.

In hindsight adding some of these were a mistake and I should have pushed back harder. Serialization in particular is really meant to be done when your application is in such a state that it isn't doing other write operations on the map, like a shutdown/startup situation.