manishearth / elsa Goto Github PK

That is, frozen versions of the the indexmap crate (previously known as ordermap).
Having a guaranteed order and being able to use indices would come in handy, especially for interners (a FrozenIndexSet is pretty much exactly an interner).

It looks like it was added in 5a1e6f4 but it's not available on docs.rs or crates.io; need to release?

FrozenMap hands out references to its values, but since the map also owns the keys it is possible to provide references to the keys as well.

Assuming K: StableDeref, implement:

fn insert_key_value(self, k: K, v: V) -> (&K::Target, &V::Target);
fn get_key_value(…) -> (&K::Target, &V::Target);

From what I can find .push for at least the FrozenVec risks invalidating references, as implemented at https://github.com/Manishearth/elsa/blob/master/src/vec.rs#L32 .

https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees describes this behaviour and when push/insert will (re)allocate.

Have I missed what you do to avoid this?

Consider the following program

use elsa::FrozenMap;
use std::cell::UnsafeCell;

fn main() {
    with_elsa();
    manual();
}

fn with_elsa() {
    // Within the second `insert` call, we are at the same time holding
    // - `&usize`
    // - `&mut HashMap<u8, Box<usize>>` (when calling entry() in insert impl)
    // Seems like UB?
    let v: FrozenMap<u8, Box<usize>> = Default::default();
    let a = v.insert(1, Box::new(1));
    let b = v.insert(2, Box::new(2));
    println!("{a} {b}");
}

fn manual() {
    // This is basically what is happening inside FrozenMap.
    let target: UnsafeCell<Box<u32>> = UnsafeCell::new(Box::new(1));
    let x = get_x(&target);
    let mut y = get_y(&target);
    // `x` and `y` are now (indirectly in the case of `y`) aliasing!
    // And `y` is mutable. Seems like UB?
    println!("{x} {y}");
    // Although `y` is short lived and the Box is never dereferenced.
    // Maybe this saves us from UB?
    let _ = y;
    let _ = x;
}

fn get_x<'a>(target: &'a UnsafeCell<Box<u32>>) -> &'a u32 {
    unsafe { &**target.get() }
}

fn get_y<'a>(target: &'a UnsafeCell<Box<u32>>) -> &'a mut Box<u32> {
    unsafe { &mut *target.get() }
}

This is totally fine according to miri but to my understanding of the aliasing rules it seems like basically every program using elsa has UB.

This could be avoided by using an inner hashmap that has a *mut self parameter rather than &mut self for its member methods (for example map.entry(key)). But I guess this is purely theoretical UB anyway, not causing miscompilations (or failing miri) in practice.

EDIT: I guess UnsafeCell<HashMap<K, UnsafeCell<V>>> could work, but maybe that has performance implications 🤷

So that I can access all the functionality of the underlying HashMap when I'm finished using it as a cache.

The non-sync versions implement Default; the sync versions should as well.

I guess FrozenIndexMap's value type needs to be StableDeref,
Is not stable to deref for usize?

Would be nice if the methods had docs and doctests. A lot of this can be copied from std

Is there some thread safety reason they can't implement Clone?

This crate is now used in rustc as of rust-lang/rust#108300

However, it seems to be making some misleading claims about the LockFreeFrozenVec:

The spinlocks are really rare as they only happen on reallocation due to a push going over the capacity.

However, when looking at the source code it appears to take the lock on every push:

And it also takes the lock on reads as well!

I've read the current implementation of FrozenMap and I think the use of StableDeref could be replaced by Pin.

Is there any reason why Pin isn't used instead?

(This is a discussion, rather than an issue. Can it be converted into one?)

Two questions, about FrozenVec:

0. Am I right in understanding that FrozenVec will never be re-allocated on resize?

1. is FrozenVec more prone to fragmentation issues as it grows, since it will never be re-allocated on resize?

2. why does FrozenVec not expose a with_capacity-like for creating new FrozenVecs?

(Thank you! 🙏)

It’s a bit tricky to reproduce, but here’s a way that seems to reliably do it, as of now:

use std::{
    collections::HashMap,
    panic::{catch_unwind, AssertUnwindSafe},
    sync::Mutex,
};

#[derive(PartialEq, Eq, Debug)]
struct H(u32);

impl std::hash::Hash for H {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        if PANIC_ON.lock().unwrap().as_ref() == Some(&self.0) {
            panic!();
        }
        0_u32.hash(state);
    }
}

static PANIC_ON: Mutex<Option<u32>> = Mutex::new(None);

fn main() {
    let mut map = HashMap::new();
    for i in 1..=28 {
        map.insert(H(i), String::new());
    }
    for i in 1..=27 {
        map.remove(&H(i));
    }
    *map.get_mut(&H(28)).unwrap() = String::from("Hello World!");

    let map = elsa::FrozenMap::from(map);

    let hello_world = map.get(&H(28)).unwrap();

    println!("exists: {hello_world}");

    let _ = catch_unwind(AssertUnwindSafe(|| {
        *PANIC_ON.lock().unwrap() = Some(28);
        map.insert(H(1), String::new());
    }));

    println!("gone: {hello_world}");
}

(run this code online on rustexplorer.com)

See here and here in the hashbrown source-code for more information.

It would be great if FrozenMap let you pass a custom hasher as a type argument, for example FNV or Fx! This is helpful for performance in compiler implementations, for example.

Hi! I just found out about this crate because I wanted to keep track of which directories were created and which files were written by a parallel static site generator I'm working on and an append-only set seemed like a good solution that's potentially more efficient than a regular set behind a mutex.

While I couldn't find an append-only set anywhere, elsa at least offers append-only map types, and it seems like it would be trivial to build set types on top. However, I noticed that both map types don't implement Sync, which makes them no better than std types for my use case.

Am I wrong to think that an append-only set would be the right tool for my use case? Are Sync set and map types possible (such that they perform better than a mutex-protected map or set) and in-scope for this crate?