Optimizing memory layouts #22

New Issue

scott · 2024-12-15T04:43:16Z

scott commented

2024-12-15 04:43:16 +00:00

I've been thinking a bunch about how to optimize a number of terms on stacks to keep things small.

We need values that are used at runtime to be as small as possible.

The current memory plan for Value is of paramount importance.

Currently, it's 64 bytes, because List owns an imbl::Vector, which is 64 bytes. We can do better than this:

struct LBox {
    name: usize,
    cell: RefCell<Value>,
}

//...

enum Value {
    Nil,
    Placeholder,
    Boolean(bool),
    Keyword(usize), // use an idx, rather than a raw index
    Interned(usize),
    FnDecl(usize),
    String(Rc<String>),
    Number(f64),
    List(Box<Vector<Value>>),
    Dict(Box<HashMap<&'static str, Value>>),
    Box(Rc<LBox>),
    Fn(Rc<RefCell<Fn>>),
}

This gets us down to 8 bytes, or 64 bits.

Some notes here:

Keywords, interned strings, names (FnDecl, or LBox.name) are indices to Vecs holding &'static strs yanked from the source code. This saves us a byte over storing &'static strs directly. This also doesn't come at a very steep cost: equality is comparing the usizes that are stored there.
This gets lifetimes out of the way.
This does come with the added complexity, however, of needing a context to resolve those indices. And getting a string representation for output will require some reference to a context. Ok!
This should also be amenable to NaN boxing.

Regarding NaN boxing: At current the crate I'd like to use for that, https://github.com/CraftSpider/boxing, https://craftspider.github.io/2024/09/shorts-boxing/, only implements boxing for Box pointers, but not for Rc--which I need. I have no idea how much faster an interpreter could be if its value type were 8 bytes instead of 16 (or 24). Or how much slower it would be if we Boxed up our Rcs. Or how much work it would be to extend boxing to cover Rcs. Anyway, that's for future me to worry about.

Also, we'd have to use u32 instead of usize for indices, and it's probably best to use index_vec's Idx wrapper so that the index is typed. This would mean that we'd have Keyword(KwIdx) and Interned(StrIdx). Which, great!

I've been thinking a bunch about how to optimize a number of terms on stacks to keep things small. We need values that are used at runtime to be as small as possible. The current memory plan for `Value` is of paramount importance. Currently, it's 64 bytes, because `List` owns an `imbl::Vector`, which is 64 bytes. We can do better than this: ```rust struct LBox { name: usize, cell: RefCell<Value>, } //... enum Value { Nil, Placeholder, Boolean(bool), Keyword(usize), // use an idx, rather than a raw index Interned(usize), FnDecl(usize), String(Rc<String>), Number(f64), List(Box<Vector<Value>>), Dict(Box<HashMap<&'static str, Value>>), Box(Rc<LBox>), Fn(Rc<RefCell<Fn>>), } ``` This gets us down to 8 bytes, or 64 bits. Some notes here: * Keywords, interned strings, names (`FnDecl`, or `LBox.name`) are indices to `Vec`s holding `&'static str`s yanked from the source code. This saves us a byte over storing `&'static str`s directly. This also doesn't come at a very steep cost: equality is comparing the `usize`s that are stored there. * This gets lifetimes out of the way. * This does come with the added complexity, however, of needing a context to resolve those indices. And getting a string representation for output will require some reference to a context. Ok! * This should also be amenable to NaN boxing. Regarding NaN boxing: At current the crate I'd like to use for that, https://github.com/CraftSpider/boxing, https://craftspider.github.io/2024/09/shorts-boxing/, only implements boxing for `Box` pointers, but not for `Rc`--which I need. I have no idea how much faster an interpreter could be if its value type were 8 bytes instead of 16 (or 24). Or how much slower it would be if we `Box`ed up our `Rc`s. Or how much work it would be to extend `boxing` to cover `Rc`s. Anyway, that's for future me to worry about. Also, we'd have to use `u32` instead of `usize` for indices, and it's probably best to use `index_vec`'s `Idx` wrapper so that the index is typed. This would mean that we'd have `Keyword(KwIdx)` and `Interned(StrIdx)`. Which, great!

Sign in to join this conversation.