How to express "does not borrow anything but must not outlive" relationships?

In my program I use buffer, such buffer is big and lives up to the very end of program execution. It's essentially a Vec

struct Buffer(Vec<i32>);

struct Index(usize); 

impl Buffer {
    fn push(&mut self, val: i32) -> Index {
        self.0.push(val);
        Index(self.0.len() - 1)
    }
}

This buffer is "push only" - once something is pushed to the buffer it never gets popped, so I can be sure that if at some point in program I pushed something it will maintain the index assigned.

To get access to the buffer's elements I use this:

fn get(i: Index) -> &i32 {
    self.0[i.0]
}

As you remember, the slice::Index operator checks that i is a valid index and panics if it's not. In my case the index is always valid, the check is meaningless. Profiler tells me that this check takes about ~17% of the run time so I would be glad to move this check to compile time.

I thought I could do something like this:

fn get(i: Index) -> &i32 {
    unsafe { self.0.get_unchecked(i.0) }
}

while keeping Buffer::get fn safe. To make this sound I need to ensure that Index returned from Buffer::push never outlives self, but it must not borrow anything because I need buffers to be mutable accessible.

Any way to express this?

Usually to do this, you use a PhantomData like so:

struct Index<'a>(usize, Phantom data<&'a ()>);

And then only return that from your Buffer and make sure that the indexes passed into the buffer can only be the ones created by that buffer.

That would be borrowing, which is I'm trying to avoid. For example

fn main() {
    let mut b = Buffer::new();
    let id1 = b.push(0);  // first mut borrow
    let _id2 = b.push(1); // second borrow, BOOM
    println!("id1 = {}", id1.0); // keep id1 alive
}

Wow, that eliminates this idea. I have no way to check this, didn't think about it.

There's a thesis about it: https://curve.carleton.ca/05076cd2-c1c2-4207-9667-a3ee1af58db4 as well as an implementation: https://docs.rs/indexing/0.4.1/indexing/.

However, I am very suspicious of

Profiler tells me that this check takes about ~17% of the run time

In general, bounds checks are almost free, as they are trivially predictable not-taken branches. The case where they really hurt performance is that when the prevent auto-vectorization, but I doubt that profiler can display that info.

Do you actually get 17% increase in run-time performance if you just blindly use get_unchecked ?

6 Likes

This sounds a lot like an arena, take a look at typed-arena or if you want to support removal in the future generational-arena

1 Like

Err, no, I don't, it's about ~6% increase - but this is something. Thanks for the links

Yes, I knew that. Actually, this is approach I'm going to take