yegor256 / micromap Goto Github PK

Let's implemented similar to this: https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.entry

Currently when a Map gets dropped it does not clean up any of it's keys or values i.e. the following tests fail:

#[test]
fn drops_keys() {
    use std::rc::Rc;
    let mut m: Map<Rc<()>, (), 8> = Map::new();
    let k = Rc::new(());
    m.insert(Rc::clone(&k), ());
    drop(m);
    assert_eq!(Rc::strong_count(&k), 1);
}

#[test]
fn drops_values() {
    use std::rc::Rc;
    let mut m: Map<(), Rc<()>, 8> = Map::new();
    let v = Rc::new(());
    m.insert((), Rc::clone(&v));
    drop(m);
    assert_eq!(Rc::strong_count(&v), 1);
}

Serde dependency is not really necessary for the functionality of the crate, only adding serialization capabilities. A common practice is to make it an optional dependency (see, for example, gram-rs here and here)

This issue lists Renovate updates and detected dependencies. Read the Dependency Dashboard docs to learn more.

Repository problems

These problems occurred while renovating this repository. View logs.

• WARN: Detected empty commit - aborting git push

Errored

These updates encountered an error and will be retried. Click on a checkbox below to force a retry now.

• Update Rust crate indexmap to v2.5.0

Detected dependencies

• Check this box to trigger a request for Renovate to run again on this repository

I'd love to see a Set added as a wrapper around Map, much as rust's HashSet is a convenience wrapper around HashMap.

At the moment, we don't drop() the keys/values. Maybe we should when we clear the map?

Let's implement it similar to this: https://doc.rust-lang.org/std/collections/struct.HashMap.html#impl-Index%3C%26Q%3E-for-HashMap%3CK%2C%20V%2C%20S%3E

As self.next <= N always holds, the construction

for i in 0..N {
  if self.next <= i { break; }

can always be written as

for i in 0..self.next {

Let's add support for no_std context

Let's add https://github.com/jonhoo/flurry to the tests

Let's get it back to 90%+

According to our benchmark, we are slower than linear_map::LinearMap when map size is bigger than 5, but we shouldn't be, since we use the same algorithm as they do. They use Vec, while we manage our own array. Let's investigate and fix.

Somehow Vec and HashMap work with keys and values that don't implement Copy. We should do the same. I'm not sure exactly how this can be done, but it should be possible.

Let's implement them similar to this: https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.values

Let's create a new GitHub Action workflow, which will (on every new tag):

• checkout the repo
• create a number of similar Rust CLI scripts in src/bin
• each script will do exactly the same manipulations with a map
• each script will use different implementations of the map (HashMap, Micromap, etc.)
• collect the performance results into a .csv file
• using gnuplot render a graph in SVG
• add the results summary and a graph to README.md
• submit a pull request

Let's implement it similar to how it's done in HashMap

Let's implement it similar to this: https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.retain

Let's implement, similar to how it's done here: https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.keys

Also, into_keys(): https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.into_keys

A safe API should never cause UB, implement an unsafe function like insert_unchecked instead.

• https://crates.io/crates/heapless provides heapless::IndexMap and IndexSet

Let's implement it similar to this: https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.remove_entry

Cloning is not required for the core functionality of micromap as well as for HashMap, and this restriction can be removed from the many implementation blocks. The Clone constraint can be added separately for functions that really need it. E.g. that's how remove_entry's declaration may look like:

pub fn remove_entry<Q: PartialEq + ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
where
    K: Borrow<Q> + Clone,
    V: Clone,
{
    ...
}

It's only function in the main block that need Clone, but I believe it's possible to remove it from there too although this is not necessary.

Impl blocks like IntoIterator for &Map and Clone for Map must declare its own constraint if it needed. They actually do it anyway and there is no need to change anything there.

If K or V not deriving Clone then it will not be possible to call into_iter() and clone() but all other methods shoud work.

In fact, standard HashMap are not required Clone for into_iter() neither it to be called by reference nor by value and it is the difference between it and the micromap. IntoIterator for &HashMap returns references to its elements and IntoIterator for HashMap just comsumes a map so it's not accessible anymore.

As it's currently written the new in src/ctors.rs can lead to undefined behavior in safe Rust. You can invoke it with the following test:

#[test]
fn undefined() {
    let _m: Map<Vec<u8>, u8, 1> = Map::new();
}

I'm either getting a SIGILL or SIGSEGV depending on the actual conditions when running tests in release with

cargo test --release -- ctors::undefined

Let's implement it similar to this: https://doc.rust-lang.org/std/collections/struct.HashMap.html#impl-From%3C%5B(K%2C%20V)%3B%20N%5D%3E-for-HashMap%3CK%2C%20V%2C%20RandomState%3E

The current implementation requires to loop over empty slots. The code could be simpler - and depending on the use case faster - if the last pair would be moved to the empty slot on deletion and empty slots would never occur in the range 0..self.next.

For instance the implementation of len(&self) would reduce to self.next (therefore I would suggest renaming next to len if this adjustment would be made).

I didn't implement and benchmark this, but it potentially could be interesting:

Let's have two arrays instead of one:

    pairs0: [MaybeUninit<(K, V)>; N],    // for keys whose first bit is 0
    pairs1: [MaybeUninit<(K, V)>; N],    // for keys whose first bit is 1

The idea under them is pretty simple -- in the first array we will store pairs, where first (or any other fixed) bit is 0, the rest -- in the other.

My intuition why it would work:

• extracting first bit sounds as relatively cheap operations, something like just one BITAND and one CMP native instructions, while it can save as much as N / 2 iterations in some cases.
• even if it don't help, and all data unfortunately went to same bucket, it generates much smaller overhead, comparing to profit it makes in positive scenarios.
• probably taking first bit of structure is not so bad "hash function" and it will be relatively a lot of positive scenarios (for example if key is an integer, which is relatively often used as a key, it should pretty good).

Some thoughts about good implementation:

• Don't keep two arrays in reality, just assume that numbers with first bit 0 are in first half of the array
• Maybe it will worth to use this logic only for big micromaps (size 128, 64, probably 32)
• Maybe it will worth to use this logic only for Sized structs, and even for structs which have small size (not bigger than 8 bytes???)

Did someone tested such approach? Maybe any analogues you benchmarking against?

This test fails:

let mut m1: Map<u8, i32, 10> = Map::new();
m1.insert(1, 42);
let mut m2: Map<u8, i32, 10> = Map::new();
m2.insert(1, 42);
assert!(m1.eq(&m2));

I believe, it must pass. Let's fix.