How to split a global vector so left is constant and right is mutable?

help
1

I have an application where a global vector is growing as the program proceeds and once an element is created it does not change.

Adding elements to the vector is fast, but using an element of the vector may take a long time.

If I use an RwLock on the vector, the reads will block writes.

Is there a way to do the following:

  1. Initialize the vector with a maximum size, set the elements to a default value that is not used, and set next_index to zero.

  2. Have the writes store useful information at next_index, return next_index for use by future reads, and increment next_index.

  3. Have the reads access elements below the current next_index, at the same time that a write stores information (as described in 2).

GrowLock: a fixed-capacity vector which allows concurrent reads and exclusive writes
2

vec is made with the assumpition that it should be allowed to reallocate and move it's members so you can avoid reallocatin but none of the api allows you to assume it's not being done

i think you will have to make a custom type and use unsafe for that.
probably something like

pub struct GrowOnly<const MaxCapacity:usize>{
 storage:[MaybeUninit<UnsafeCell<T>>;MaxCapacity],
 initialized: AtomicUsize,
}
imp<const MaxCapacity:usize> GrowOnly<MaxCapacity>{
  pub unsafe fn insert(&self,value:T)//no other thread can be inserting otherwise we need a way more complex approach to track how far along initialization is{
       //check initialized<MaxCapacity-1
       //write at storage[initialized+1]
       //increment initalized so that readers can access the new element
   }
   pub fn get_ready<'a>(&'a self)->&'a [T]{
        let amount=initialized.load(Ordering::Relaxed)//worst case we load just before the insert stores and lose the most recent updates 
        let init_slice=storage[0..];
        unsafe{ mem::transmute(init_slice)}//memory layout is the same and slice is initialized and not going to be mutated
   }
}
1 Like
3

Maybe pinning might help here:

4

Pinned_vec sounds like a good approach. The problem is that it would need a split_const_from_mut method that would not allow changing the immutable part while using the mutable part ?

5

Is this effectively similar to a bump allocator for the elements? Maybe bumpalo could work.

6

When the index in your usage is only used to access elements and has no further meaning, such as ordering or indicating when an element was created, you can instead use a reference to the stored element and remove the entire vector, lock, and related code.

fn store_my_data_forever(element: MyElement) -> &'static MyElement {
    Box::leak(Box::new(element))
}

That is all that is needed.

7

I think you meant

        let init_slice=&storage[0..amount];
8

The worst case is that you read the length before the corresponding storage is visible leading to UB. You need an Aquire read here.

2 Likes
9

but the variable only ever reaches a value once that value is ready so it's in writing it that you need strong ordering

10

When you read the length n you need a synchronization guarantee that all elements in the range 0..n are visible to you.

For this, you need a Release in the writing thread and an Aquire in the reading thread as these only work in pairs. A Release paired with Relaxed does nothing.

Ordering::Release: When coupled with a store, all previous operations become ordered before any load of this value with Acquire (or stronger) ordering. In particular, all previous writes become visible to all threads that perform an Acquire (or stronger) load of this value.

Ordering::Aquire: When coupled with a load, if the loaded value was written by a store operation with Release (or stronger) ordering, then all subsequent operations become ordered after that store. In particular, all subsequent loads will see data written before the store.

11

I tried to implement the collection you described, but I didn't test it so IDK if it fully works or if the implementation is safe / sound.
I would be really glad if someone could give a review to this code.

Github repo: GitHub - CieriA/atomicvec-rs: Rust library implementing fixed-capacity vector which allows concurrent reads and spin-lock writes.

Obviously I need to add some documentation and other methods but the main functionalities are there

12

That crate may be helpful im - Rust . I believe it would combine well with ArcSwap in arc_swap - Rust.

But yeah, easier solution would be to implement such data structure yourself with a mutex for push operation.

Even better would be to remove Mutex from the data structure and have a "Reader" with deref into slice and "Writer" with fn push<T>(&mut self, value: T) that will store T and do atomic increment of the length (Release) that "Reader" will load (Acquire, or Relaxed but if cache previous length and use fence(Acquire) when changed). Then reader will construct the slice via unsafe code. This should be the only unsafe block in this data structure, without locks (well, "Writer" will be under a lock or some other mechanism of synchronization, but it's up to the user).

1 Like
GrowLock: a fixed-capacity vector which allows concurrent reads and exclusive writes
13

But if push requires &mut self no reads can be done while writing, right? That'a a problem

14

Reader and writer are separate structs, &mut is only required on writer. See "split" pattern.

1 Like
15

ohh okok I get it now