robclu / leapfrog

Lock-free concurrent and single-threaded hash map implementations using Leapfrog probing. Currently the highest performance concurrent HashMap in Rust for certain use cases.
Apache License 2.0
206 stars 9 forks source link

Suggestion for addition to library #8

Open mysteriouslyseeing opened 1 year ago

mysteriouslyseeing commented 1 year ago

With the requirement for values to implement Value, typically through the use of sentinel values, hard-to-diagnose bugs can crop up.

The suggestion is an addition of a type to the library; an enum using generics with three variants: a redirect variant, a null variant, and a variant which actually contains data. Developers using your library can use this enum, and those with very strict space or performance requirements can implement Value manually.

A sample implementation:

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum LeapValue<V> {
    Redirect,
    Null,
    Inner(V)
}

impl<V> LeapValue<V> {
    pub fn to_option(self) -> Option<V> {
        match self {
            Self::Inner(inner) => Some(inner),
            _ => None,
        }
    }
}

impl<V> Value for LeapValue<V>
where V: Sized + Debug + Clone + Copy {
    fn is_redirect(&self) -> bool {
        match self {
            Self::Redirect => true,
            _ => false,
        }
    }

    fn is_null(&self) -> bool {
        match self {
            Self::Null => true,
            _ => false,
        }
    }

    fn redirect() -> Self {
        Self::Redirect
    }

    fn null() -> Self {
        Self::Null
    }
}

What do you think?

robclu commented 1 year ago

Hey,

Thank you for the suggestion - I like the idea. I am not yet sure whether is it better to expose this to the user or to do something like this internally which would remove the requirement for users to have to implement Value, which would make the API easier to use.

Although it is opt-in, have to call to_option or match on the returned value is less than ideal.

If I can do it internally without impacting performance then the latter would be a better approach, so will try that first, and revert back to your suggestion if it turns out to be better.

Thanks!