Manually allocate memory in stable for collection

help
1

Hello again, I'm hoping someone can help point me to the right apis or indicate if they exists or unstable related to the title. What I'm looking to do is to produces a faster version of the crate linear_map https://crates.io/crates/linear-map

Effectively this is just a replacement for Hashmap backed by a Vec specifically Vec::<(K, V)>. From what I can tell there isn't inherently anything wrong with this, but the layout seems fairly un-cache friendly since we have to stride over V while searching for keys. So this effectively get slower the larger V since we're going to miss cache more often.

Just to test I made what I would consider the sort of naive replacement. Literally just.

pub struct LinearMap2<K, V> {
  keys: Vec<K>,
  value: Vec<V>,
}

I'm using this as part of a dynamic programming language I'm working on. Specially for property and method lookups. This is part of a larger struct that using a linear_map when there a few properties on an instance but a full hashmap when we hit some threshold. I went ahead an made a minimal impl for what I had above and some initial benchmarks are really promising. In one bench there was a 30% speedup for a script in my language.

The downside with above is it's pretty space wasteful. essentially we waste 16 bytes on two duplicate len and capacity fields. So this gets to the title question. If I wanted to create something like

pub struct LinearMap2<K, V> {
    ptr_keys: NonNull<K>,
    ptr_vals: NonNull<V>,
    cap: usize,
    len: usize
}

Is there a way for me to allocate for the key and vals slices in stable rust?

2

You mean something like std::alloc::alloc?

3

I had looked at std::alloc::alloc but I wasn't sure how to handle resizing since I believe can't do Layout::new::<[Sometype; variableLength]>();

4

I'm not very proficient in manual memory allocations in Rust, but maybe you can use something like
Layout::array?

5

I believe this is exactly what I need :confetti_ball: Thank you

6

Personally, I wouldn't worry too much about the 16 bytes, unless there are a lot of maps with a very small amount of keys and values. Using allocators will definitely complicate the code a lot and open up possibility for errors, so I would choose them only after careful measuring.

7

I definitely agree, but I've got several criterion benches that shows a prototype of what I have described already showing some promise relative to linear_map crate. I'll have to see if I can get it to be faster than the two Vec solution I had above.

If this was for work I'd probably either stick with the crate or just the two vector solution, but this is mostly for a for fun project so I'm willing to try some stuff out that's pretty likely to be waste of time.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.