Struct PinnedConcurrentCol 

pub struct PinnedConcurrentCol<T, P, S>
where
    P: ConcurrentPinnedVec<T>,
    S: ConcurrentState<T>,
{ /* private fields */ }

A core data structure with a focus to enable high performance, possibly lock-free, concurrent collections using a PinnedVec as the underlying storage.

Pinned vectors grow while keeping the already pushed elements pinned to their memory locations. This allows the following concurrency model.

• Writing to the collection does not block. Multiple writes can happen concurrently.
  • However, PinnedConcurrentCol itself does not provide guarantees for race-free writing; and hence, the write methods are marked unsafe.
  • It is the responsibility of the wrapper to make sure that multiple writes or reading during write to the same position do not happen concurrently.
• Only one growth (capacity expansion) can happen at a given time.
  • If the underlying collection reaches its capacity and needs to grow, one and only one thread takes the responsibility to expand the vector.
• Growth does not block.
  • Writes to positions which are already within capacity are not blocked by the growth.
  • Writes to to-be-allocated positions wait only for the allocation to be completed; not any other task of the thread responsible for expansion.

As clear from the properties, pinned concurrent collection aims to achieve high performance. It exposes the useful methods that can be used differently for different requirements and marks the methods which can lead to race conditions as unsafe by stating the underlying reasons. This enables building safe wrappers such as ConcurrentBag, ConcurrentOrderedBag or ConcurrentVec.

Implementations

impl<T, P, S> PinnedConcurrentCol<T, P, S>

where P: ConcurrentPinnedVec<T>, S: ConcurrentState<T>,

pub fn new_from_pinned<Q>(pinned_vec: Q) -> Self

where Q: IntoConcurrentPinnedVec<T, ConPinnedVec = P>,

Wraps the pinned_vec and converts it into a pinned concurrent collection.

pub unsafe fn into_inner(self, pinned_vec_len: usize) -> P::P

where P::P: IntoConcurrentPinnedVec<T, ConPinnedVec = P>,

Sets the length of the underlying pinned vector to the given pinned_vec_len and returns the vector.

Safety

This method is unsafe as pinned concurrent collection does not keep track of the writes and length. This is the responsibility of the wrapper through the specific ConcurrentState implementation. Therefore, the following situation is possible:

• concurrent collection is created with an empty pinned vector.
• the caller calls reserve_maximum_capacity with sufficient capacity, say 2.
• then, write(1, value) is called by writing to the second position, skipping the first position.
• and finally, calls into_inner(2).

This would return a pinned vector with a valid entry at position 1 but uninitialized value at position 0, which would lead to an undefined behavior.

Therefore, the wrapper must ensure that the pinned vector is in a valid state before taking it out.

Safe Usage Examples

The unsafe into_inner method can be wrapped with a safe method if the following guarantee is satisfied:

• All values in range 0..pinned_vec_len of the concurrent collection are written.

Two such example wrappers are ConcurrentBag and ConcurrentVec.

• Concurrent bag and vector do not allow leaving gaps, and only push to the back of the collection.
• Furthermore, they keep track of the number of pushes.
• Therefore, they can safely extract the pinned vector out with the length that it correctly knows.

pub unsafe fn clone_with_len(&self, pinned_vec_len: usize) -> Self

where T: Clone,

Clones the underlying pinned vector, sets its length to the given pinned_vec_len and returns the vector.

Safety

This method is unsafe as pinned concurrent collection does not keep track of the writes and length. This is the responsibility of the wrapper through the specific ConcurrentState implementation. Therefore, the following situation is possible:

• concurrent collection is created with an empty pinned vector.
• the caller calls reserve_maximum_capacity with sufficient capacity, say 2.
• then, write(1, value) is called by writing to the second position, skipping the first position.
• and finally, calls clone_inner(2).

This would return a pinned vector with a valid entry at position 1 but uninitialized value at position 0, which would lead to an undefined behavior.

Therefore, the wrapper must ensure that the pinned vector is in a valid state before taking it out.

Safe Usage Examples

The unsafe clone_inner method can be wrapped with a safe method if the following guarantee is satisfied:

• All values in range 0..pinned_vec_len of the concurrent collection are written.

Two such example wrappers are ConcurrentBag and ConcurrentVec.

• Concurrent bag and vector do not allow leaving gaps, and only push to the back of the collection.
• Furthermore, they keep track of the number of pushes.
• Therefore, they can safely extract the pinned vector out with the length that it correctly knows.

pub fn state(&self) -> &S

Returns a reference to the current concurrent state of the collection.

pub fn capacity(&self) -> usize

Returns the current allocated capacity of the collection.

pub fn maximum_capacity(&self) -> usize

Returns maximum possible capacity that the collection can reach without calling PinnedConcurrentCol::reserve_maximum_capacity.

Importantly note that maximum capacity does not correspond to the allocated memory.

pub unsafe fn iter(&self, len: usize) -> impl Iterator<Item = &T>

Returns an iterator to the elements of the underlying pinned vector starting from the first element and taking len elements.

Safety

This method is unsafe due to two reasons.

• Firstly, PinnedConcurrentCol does not guarantee that all positions are initialized. It is possible to create the collection, skip the first position and directly write to the second position. In this case, the iter call would read an uninitialized value at the first position.

• Secondly, PinnedConcurrentCol focuses on lock-free writing. Therefore, while the iterator is reading an element, another thread might be writing to this position.

Example Safe Usage

This method can be wrapped by a safe method provided that the following safety requirement can be guaranteed:

• All values in range 0..pinned_vec_len of the concurrent collection are written.

An example can be seen in ConcurrentVec.

• Concurrent vec zeroes memory on allocation.
• Furthermore, it uses a pinned vector of Option<T> to represent a collection of Ts. It has a valid zero value, Option::None.
• The iter wrapper simply skips Nones which correspond to uninitialized values.

pub unsafe fn iter_over_range<R: RangeBounds<usize>>( &self, range: R, ) -> impl Iterator<Item = &T>

Returns an iterator to the elements of the underlying pinned vector over the given range.

Safety

This method is unsafe due to two reasons.

• Firstly, PinnedConcurrentCol does not guarantee that all positions are initialized. It is possible to create the collection, skip the first position and directly write to the second position. In this case, the iter call would read an uninitialized value at the first position.

• Secondly, PinnedConcurrentCol focuses on lock-free writing. Therefore, while the iterator is reading an element, another thread might be writing to this position.

Example Safe Usage

This method can be wrapped by a safe method provided that the following safety requirement can be guaranteed:

• All values in range of the concurrent collection are written.

An example can be seen in ConcurrentVec.

• Concurrent vec zeroes memory on allocation.
• Furthermore, it uses a pinned vector of Option<T> to represent a collection of Ts. It has a valid zero value, Option::None.
• The iter wrapper simply skips Nones which correspond to uninitialized values.

pub unsafe fn iter_mut(&mut self, len: usize) -> impl Iterator<Item = &mut T>

Returns a mutable iterator to the elements of the underlying pinned vector starting from the first element and taking len elements.

Safety

This method is unsafe due to the following reasons:

• PinnedConcurrentCol does not guarantee that all positions are initialized. It is possible to create the collection, skip the first position and directly write to the second position. In this case, the iter call would read an uninitialized value at the first position.

Example Safe Usage

This method can be wrapped by a safe method provided that the following safety requirement can be guaranteed:

• All values in range 0..pinned_vec_len of the concurrent collection are written.

An example can be seen in ConcurrentVec.

• Concurrent vec zeroes memory on allocation.
• Furthermore, it uses a pinned vector of Option<T> to represent a collection of Ts. It has a valid zero value, Option::None.
• The iter wrapper simply skips Nones which correspond to uninitialized values.

pub unsafe fn get(&self, index: usize) -> Option<&T>

Returns a reference to the element written at the index-th position.

Safety

This method is unsafe due to two reasons.

• Firstly, PinnedConcurrentCol does not guarantee that all positions are initialized. It is possible to create the collection, skip the first position and directly write to the second position. In this case, the get call would read an uninitialized value at the first position.

• Secondly, PinnedConcurrentCol focuses on lock-free writing. Therefore, while the get method is reading an element, another thread might be writing to this position.

Example Safe Usage

This method can be wrapped by a safe method provided that the following safety requirement can be guaranteed:

• The value at position index is written.

An example can be seen in ConcurrentVec.

• Concurrent vec zeroes memory on allocation.
• Furthermore, it uses a pinned vector of Option<T> to represent a collection of Ts. It has a valid zero value, Option::None.
• The get method wrapper simply the value, which will be None for uninitialized values.

pub unsafe fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to the element written at the index-th position.

Safety

This method is unsafe due to the following reason.

• PinnedConcurrentCol does not guarantee that all positions are initialized. It is possible to create the collection, skip the first position and directly write to the second position. In this case, the get call would read an uninitialized value at the first position.

Example Safe Usage

This method can be wrapped by a safe method provided that the following safety requirement can be guaranteed:

• The value at position index is written.

An example can be seen in ConcurrentVec.

• Concurrent vec zeroes memory on allocation.
• Furthermore, it uses a pinned vector of Option<T> to represent a collection of Ts. It has a valid zero value, Option::None.
• The get_mut method wrapper will return None for uninitialized values.

pub unsafe fn reserve_maximum_capacity( &mut self, current_len: usize, maximum_capacity: usize, ) -> usize

Note that PinnedConcurrentCol::maximum_capacity returns the maximum possible number of elements that the underlying pinned vector can grow to without reserving maximum capacity.

In other words, the pinned vector can automatically grow up to the PinnedConcurrentCol::maximum_capacity with write and write_n_items methods, using only a shared reference.

When required, this maximum capacity can be attempted to increase by this method with a mutable reference.

Importantly note that maximum capacity does not correspond to the allocated memory.

Among the common pinned vector implementations:

• SplitVec<_, Doubling>: supports this method; however, it does not require for any practical size.
• SplitVec<_, Linear>: is guaranteed to succeed and increase its maximum capacity to the required value.
• FixedVec<_>: is the most strict pinned vector which cannot grow even in a single-threaded setting. Currently, it will always return an error to this call.

Safety

This method is unsafe since the concurrent pinned vector might contain gaps. The vector must be gap-free while increasing the maximum capacity.

This method can safely be called if entries in all positions 0..len are written.

pub unsafe fn write(&self, idx: usize, value: T)

Writes the value to the idx-th position.

Safety

This method makes sure that the value is written to a position owned by the underlying pinned vector. Furthermore, it makes sure that the growth of the vector happens thread-safely whenever necessary.

On the other hand, it is unsafe due to the possibility of a race condition. Multiple threads can try to write to the same idx at the same time. The wrapper is responsible for preventing this.

This method can safely be used provided that the caller provides the following guarantee:

• multiple write or write_n_items calls which writes to the same idx must not happen concurrently.

pub unsafe fn single_item_as_ref(&self, idx: usize) -> &T

Reserves and returns a reference for one position at the idx-th position.

The caller is responsible for writing to the position.

Safety

This method makes sure that the values are written to positions owned by the underlying pinned vector. Furthermore, it makes sure that the growth of the vector happens thread-safely whenever necessary.

On the other hand, it is unsafe due to the possibility of a race condition. Multiple threads can try to write to the same position at the same time. The wrapper is responsible for preventing this.

Furthermore, the caller is responsible to write all positions of the acquired slices to make sure that the collection is gap free.

Note that although both methods are unsafe, it is much easier to achieve required safety guarantees with write_n_items; hence, it must be preferred unless there is a good reason to acquire mutable slices. One such example case is to copy results directly into the output’s slices, which could be more performant in a very critical scenario.

pub unsafe fn write_n_items<IntoIter>( &self, begin_idx: usize, num_items: usize, values: IntoIter, )

where IntoIter: IntoIterator<Item = T>,

Writes the num_items values to sequential positions starting from the begin_idx-th position.

• If the values iterator has more than num_items elements, the excess values will be ignored.
• The method will not complain; however, values iterator yielding less than num_items elements might lead to safety issues (see below).

Safety

This method makes sure that the values are written to positions owned by the underlying pinned vector. Furthermore, it makes sure that the growth of the vector happens thread-safely whenever necessary.

On the other hand, it is unsafe due to the possibility of a race condition. Multiple threads can try to write to the same position at the same time. The wrapper is responsible for preventing this.

This method can safely be used provided that the caller provides the following guarantees:

• multiple write or write_n_items calls which writes to the same idx must not happen concurrently.
• values iterator yielding less than num_items elements might lead to gaps in the bag, which would lead to gaps in the vector if not handled properly.

pub unsafe fn n_items_buffer_as_slices( &self, begin_idx: usize, num_items: usize, ) -> P::SliceIter<'_>

Reserves and returns an iterator of mutable slices for num_items positions starting from the begin_idx-th position.

The caller is responsible for filling all num_items positions in the returned iterator of slices with values to avoid gaps.

Safety

This method makes sure that the values are written to positions owned by the underlying pinned vector. Furthermore, it makes sure that the growth of the vector happens thread-safely whenever necessary.

On the other hand, it is unsafe due to the possibility of a race condition. Multiple threads can try to write to the same position at the same time. The wrapper is responsible for preventing this.

Furthermore, the caller is responsible to write all positions of the acquired slices to make sure that the collection is gap free.

Note that although both methods are unsafe, it is much easier to achieve required safety guarantees with write_n_items; hence, it must be preferred unless there is a good reason to acquire mutable slices. One such example case is to copy results directly into the output’s slices, which could be more performant in a very critical scenario.

pub unsafe fn n_items_buffer_as_mut_slices( &self, begin_idx: usize, num_items: usize, ) -> P::SliceMutIter<'_>

Reserves and returns an iterator of mutable slices for num_items positions starting from the begin_idx-th position.

The caller is responsible for filling all num_items positions in the returned iterator of slices with values to avoid gaps.

Safety

This method makes sure that the values are written to positions owned by the underlying pinned vector. Furthermore, it makes sure that the growth of the vector happens thread-safely whenever necessary.

On the other hand, it is unsafe due to the possibility of a race condition. Multiple threads can try to write to the same position at the same time. The wrapper is responsible for preventing this.

Furthermore, the caller is responsible to write all positions of the acquired slices to make sure that the collection is gap free.

Note that although both methods are unsafe, it is much easier to achieve required safety guarantees with write_n_items; hence, it must be preferred unless there is a good reason to acquire mutable slices. One such example case is to copy results directly into the output’s slices, which could be more performant in a very critical scenario.

pub unsafe fn clear(&mut self, prior_len: usize)

Clears the collection.

Safety

This method is unsafe since the concurrent pinned vector might contain gaps.

This method can safely be called if entries in all positions 0..len are written

impl<T, S> PinnedConcurrentCol<T, ConcurrentSplitVec<T, Doubling>, S>

where S: ConcurrentState<T>,

pub fn with_doubling_growth() -> Self

Creates a new concurrent bag by creating and wrapping up a new SplitVec<T, Doubling> as the underlying storage.

impl<T, S> PinnedConcurrentCol<T, ConcurrentSplitVec<T, Linear>, S>

where S: ConcurrentState<T>,

pub fn with_linear_growth( constant_fragment_capacity_exponent: usize, fragments_capacity: usize, ) -> Self

Creates a new concurrent bag by creating and wrapping up a new SplitVec<T, Linear> as the underlying storage.

Each fragment of the underlying split vector will have a capacity of 2 ^ constant_fragment_capacity_exponent.

fragments_capacity determines the initial maximum_capacity of the vector as follows: maximum_capacity * 2 ^ constant_fragment_capacity_exponent, which can be increased by reserve_maximum_capacity when necessary.

Panics

Panics if fragments_capacity == 0.

impl<T, S> PinnedConcurrentCol<T, ConcurrentFixedVec<T>, S>

where S: ConcurrentState<T>,

pub fn with_fixed_capacity(fixed_capacity: usize) -> Self

Creates a new concurrent bag by creating and wrapping up a new FixedVec<T> as the underlying storage.

Safety

Note that a FixedVec cannot grow; i.e., it has a hard upper bound on the number of elements it can hold, which is the fixed_capacity.

Pushing to the vector beyond this capacity leads to “out-of-capacity” error.

This maximum capacity can be accessed by PinnedConcurrentCol::maximum_capacity method.

Trait Implementations

impl<T, P, S> Debug for PinnedConcurrentCol<T, P, S>

where P: ConcurrentPinnedVec<T>, S: ConcurrentState<T> + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, P, S> Drop for PinnedConcurrentCol<T, P, S>

where P: ConcurrentPinnedVec<T>, S: ConcurrentState<T>,

fn drop(&mut self)

Executes the destructor for this type.