ryzhyk/arc-interner

A concurrent interner that deallocates unused values

arc-interner's Issues

lock contention on state::Container - could design it out at cost of api change?

With the move to DashMap, lock contention is reduced, but there is still a global lock acquired via the state::Container that in my use-case causes contention on the try_get. Try_get calls the internal lock method when the Container is not frozen which spins so it uses lots of cpu when contended.

Container has a freeze() method to reduce the lock contention once its fully populated, but with current model I can't see a way to call that as there could always be a new type T coming to ArcIntern::new().

Currently we're effectively using the state::Container as a kind of shared generic static between all interned types. Looking at alternatives to state::Container, they are effectively also a shared HashMap<TypeId, _> that already wrap in a mutex internally (e.g. generic_static crate), or we'd need to wrap in a mutex (e.g. anymap crate) . Macro approaches to generate per-type statics inside a library crate also appear to be unappealing

What would you think about an approach where the crate moves to a shared-nothing approach between types, so that interning type Foo and type Bar don't need to acquire the same locks at all? This could potentially eliminate the state::Container and its lock entirely. This could be done by introducing a factory type (which would be an api change).

Current non-factory pseudo-code

// setup - could just use ArcIntern directly, but have this wrapper so can try different interning approaches.
struct Wrapped<T>(ArcIntern<T>)
impl<T> Wrapped {
  pub fn new(t: T) Self {
     Self(ArcIntern::new(t))
  }
}
// Also implements Deref

// callsite
let a = Wrapped::new(Foo::new())
let b = Wrapped::new(Bar::new())

vs possible alternative factory code where per-type factories are separate statics containing their own DashMap<T,()> and therefore share no state.

// setup
static FOO_INTERNER= OnceCell<ArcInterner<Foo>> =  OnceCell::new();
static BAR_INTERNER= OnceCell<ArcInterner<Bar>> =  OnceCell::new();
struct Wrapped<T>(ArcIntern<T>)
impl Wrapped<Foo> {
  pub fn new(t: Foo) Self {
     Self(FOO_INTERNER::intern(t))
  }
}
impl Wrapped<Bar> {
  pub fn new(t: Bar) Self {
     Self(BAR_INTERNER::intern(t))
  }
}
...
// callsite
let a = Wrapped::new(Foo::new())
let b = Wrapped::new(Bar::new())

ArcInterner would likely need to pass a function as a type parameter to ArcIntern to handle the cleanup on drop, and ArcIntern::new would become internal only so that construction is always via ArcInterner::intern .

Include the rest of `internment`'s API

Even though only ArcIntern is flawed in internment, using its other APIs carries the risk that later on someone may start using ArcIntern without realizing its problems.

This crate should also export Intern and LocalIntern so that it can be used as a complete functional replacement.

Avoiding a copy when instantiating an ArcIntern

As the API currently stands, it looks like the only way to initialize an ArcIntern is via new which takes a val: T. Would it be possible to instead make new take &T, and require T: Clone? That way, no additional copy would be necessary when the value being instantiated is already interned.

I have a gist for how this might work under the hood (looking up in the map for the appropriate value and only copying the Vec if necessary): https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=b380b64e7ef57499d612a0114e94170a

What do you think?

Allow `T: ?Sized`

We're thinking of replacing all Arc instances with ArcIntern, however, the T we're working with here is ?Sized.

Next to ArcIntern opting out of that trait, we need From<Box<T>> and From<&T> for ArcIntern, to properly convert some instances of handling these types.

Upgrade to dashmap 4.0 when it's released.

Consider using Arc::as_ptr

1.45 was stabilized: https://blog.rust-lang.org/2020/07/16/Rust-1.45.0.html
Which included Arc::as_ptr: https://doc.rust-lang.org/stable/std/sync/struct.Arc.html#method.as_ptr

I believe the use of this would remove the need for the unsafe line added in #5

`ArcIntern<T>`'s `Hash` implementation is invalid

Since ArcIntern<T> provides Borrow<T>, the Hash implementations have to be the same. However, they're not.

This caused some problems when coercing ArcIntern to Borrow, and HashMaps stopped working correctly, as the given hashmap (before the coercion) used ArcIntern's hash functions, while after coercion, the hashmaps were looked up via T's Hash via Borrow<T>, which caused wrong results.