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.