#Help me figure out why a deterministic test in safe Rust is flaky

12 messages · Page 1 of 1 (latest)

forest tulip
#

Hey all, I'm currently learning about CRDTs and so, I tried to implement the most basic CRDT, the increment counter. While running the tests I noticed that the merge method sometimes fails. I started by running using rustc 1.58.1 but updating to rustc 1.61.0 yields the same results.

Here's the code:

use std::{collections::HashMap, hash::Hash, ops::Deref};

pub struct IncrementCounter<Id>
where
    Id: Eq + Hash + Default + Deref,
{
    id: Id,
    history: HashMap<Id, u32>,
}

impl<Id> IncrementCounter<Id>
where
    Id: Eq + Hash + Default + Deref,
{
    pub fn init<const N_REPLICAS: usize>(id: Id, ids: [Id; N_REPLICAS]) -> Self {
        let mut history = HashMap::with_capacity(N_REPLICAS);
        for id in ids {
            history.insert(id, 0);
        }
        Self { id, history }
    }

    pub fn increment(&mut self) {
        let n = self.history.get_mut(&self.id).unwrap();
        *n += 1;
    }

    pub fn merge(&mut self, history: &HashMap<Id, u32>) {
        self.history
            .values_mut()
            .zip(history.values())
            .for_each(|(l, r)| {
                *l = u32::max(*l, *r);
            });
    }
}

#[cfg(test)]
mod test {
    use crate::IncrementCounter;
    use std::collections::HashMap;

    #[test]
    fn test_merge() {
        let mut counter_n = IncrementCounter::init::<2>("n", ["n", "m"]);
        let mut counter_m = IncrementCounter::init::<2>("m", ["n", "m"]);
        // Increment N
        for _ in 1..=10 {
            counter_n.increment();
        }
        // Increment M
        for _ in 1..=5 {
            counter_m.increment()
        }
        // Merge M & N
        counter_n.merge(&counter_m.history);
        counter_m.merge(&counter_n.history);
        // Test
        let mut expected = HashMap::with_capacity(2);
        expected.insert("n", 10);
        expected.insert("m", 5);
        assert_eq!(counter_n.history, expected);
        assert_eq!(counter_m.history, expected);
    }
}
#

I just noticed the CRDT implementation isn't correct but that is besides the point right now.

true quartz
#

I see HashMaps. Without having taken a close look yet, that's a potential culprit

#

HashMap iteration order is unspecified and arbitrary

#

In fact, if you're using the default hasher, there is an element of randomness to it

#

(adding or removing elements has nondeterministic results)

forest tulip
#

Oops I forgot the error output

running 3 tests
test test::test_increment ... ok
test test::test_merge ... FAILED
test test::test_init ... ok

failures:

---- test::test_merge stdout ----
thread 'test::test_merge' panicked at 'assertion failed: `(left == right)`
  left: `{"m": 0, "n": 10}`,
 right: `{"n": 10, "m": 5}`', src/lib.rs:82:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    test::test_merge
#

I would hope that HashMaps would Eq without caring for order though, is that not the case?

median copper
#

the problem is ```rs
self.history
.values_mut()
.zip(history.values())

#

the order of values_mut and values is unspecified

forest tulip
#

Makes sense, thank you!