0

I'm trying to build a data structure where multiple keys may point to the same value. However, I'm trying to avoid reference counting if possible as it has an overhead. Here are some ideas I've tried:

use std::collections::BTreeMap;
use std::rc::Rc;

use serde::Deserialize;
use serde::Serialize;

#[derive(Clone, Debug, PartialEq, Eq, Ord, PartialOrd, Serialize, Deserialize)]
struct Key;

#[derive(Clone, Debug, PartialEq, Eq, Ord, PartialOrd, Serialize, Deserialize)]
struct Value;

// Uses reference counting (perf cost).
#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
pub struct Option1 {
    db: BTreeMap<Key, Rc<Value>>,
}

// Cannot be serialized / deserialized.
// How to even have non-dropped references?
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Option2<'a> {
    values: Vec<Value>,
    db: BTreeMap<Key, &'a Value>,
}

// Inelegant, and no compile-time check for 
// possible bad indices go out of sync with the values.
#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
pub struct Option3 {
    values: Vec<Value>,
    indices: BTreeMap<Key, usize>,
}
cafce25
  • 15,907
  • 4
  • 25
  • 31
gust
  • 878
  • 9
  • 23
  • 2
    I would probably go with Option3, but with a [`SlotMap`](https://docs.rs/slotmap/latest/slotmap/) instead of a `Vec`. – PitaJ Aug 16 '23 at 01:23
  • 3
    Have you already measured the reference counting option and determined that the cost is a significant contributor to performance problems? It's the simplest and most logical option, and most other mutable designs are going to need some sort of garbage collection, which typically implies reference counting or a similar option. – bk2204 Aug 16 '23 at 01:27
  • 2
    `Option2` is [impossible](https://stackoverflow.com/questions/32300132/why-cant-i-store-a-value-and-a-reference-to-that-value-in-the-same-struct) and solved by something like `Option1` – cafce25 Aug 16 '23 at 04:19
  • 1
    Note that option 1, when serialized / deserialized, won't share the data anymore: each `Rc` will have its own copy of the `Value`. – jthulhu Aug 16 '23 at 05:27

0 Answers0