v3

This PR includes a major change in the backing queue of the recursive concurrent iterator.

Prior queue is revised and preserved behind the "experimental" feature. The new backend is replaced with crossbeam-deque with "std" and with crossbeam-queue in no-std builds.

Benchmarks extended.

Extend signature is relaxed from requiring an exact size iterator to just an iterator. Internal extnsion still makes use of the known length when size_hint provides an exact length, falls back to the flexible extension otherwise.

Overall, these changes stabilize the recursive iterator, which was simpler; however, might lead to poor performance when consumed by many threads.

More Flexible Extension

More Flexible Extension

Recursive behavior of the iterator is defined by the extend function that is provided on construction.

In the prior version, this function had the following signature:

E: Fn(&T) -> I,
I: IntoIterator<Item = T>,
I::IntoIter: ExactSizeIterator,

The idea behind this depended on the assumption that it is always better to extend children all together rather than pushing them one at a time.

However, the computation experiments orxfun/computation-experiments#5 showed that this not always the case.

Sometimes, it is difficult to create an exact size iterator for children. For instance, the children might not be pre-allocated. Or we might need to filter on them. Furthermore, in some cases it is more important to immediately push the element to the queue and make it available to all threads rather than using extend to reduce parallelization overhead. In these scenarios, having only the extend option led to a big limitation.

In this version after a major revision, the extend function has the following signature:

E: Fn(&T, &Queue<T, P>),

So, we provide a reference to Queue that can be used by the caller to define the extension. Queue is a wrapper around the ConcurrentQueue with a limited set of methods. Only two methods are exposed:

• fn push(&self, element: T) to add items one-by-one.
  • (+) makes new children available as soon as available.
  • (+) does not require allocation.
  • (-) might have greater parallelization overhead.
• fn extend<I>(&self, elements: I) to push all elements at once.
  • (+) will have the minimum parallelization overhead.
  • (-) might require allocation for processing each node when an exact sized iterator of children is not readily available.

As described in the pros and cons above, the new api provides these options to the caller allowing optimizations depending on the use case.

Exact Sized Recursive Iterator

Two variants are introduced:

• [ConcurrentRecursiveIter]. This is equivalent to the prior implementation with unknown size. Size refers to the total number of elements that will be returned by the iterator, which is the total of initial elements and all elements created by the recursive extend calls.
• [ConcurrentRecursiveIterExact]: This is the recursive concurrent iterator where the size is known ahead of time before recursively extending for each element. This is critical in achieving performant parallelization when the recursive concurrent iterator is used as an input of a parallel iteration.

Accordingly, From queue implementations are updated. In particular additional implementations are provided to allow for creating exact sized iterators from concurrent queues using any kind of pinned vector for storage.

Upgrades PinnedVec for improved safety guarantees: https://github.com/orxfun/orx-pinned-vec/releases/tag/3.21.0

Upgrades ConcurrentIter for fused iterator behavior of the concurrent iter implementation: https://github.com/orxfun/orx-concurrent-iter/releases/tag/3.3.0. With this update is_completed_when_none_returned implementation is provided to allow callers make sure that the iterator is completely consumed.