orxfun/orx-concurrent-iter

A thread-safe, ergonomic and lightweight concurrent iterator trait and efficient implementations.

Hi, I'm Uğur Arıkan

👋 𝙰𝚋𝚘𝚞𝚝 𝙼𝚎

• Operations Research (OR) Scientist / Practitioner (wiki)
• Middle East Technical University & Singapore University of Technology and Design
• Located in Bonn Germany, working at DHL
• | github | email | linkedin | cv | crates | nuget |

🤟 I like

All things OR, optimization, networks, routing, algorithms, multi objective decision making.

Programming, algorithms, data structures, speed, efficiency and recently concurrency.

Also love programming languages:

• rust 🤟 every day, to stay for a long time
• c#, react, typescript 👍 quiet often
• go, f# 👌🏽 zig, nim 🤔 watching closely

🎈 𝙸'𝚖 currently 𝚞𝚙 𝚝𝚘

mathematical programming / modeling

An expressive, efficient and productive mathematical programming / modeling crate for rust.

• macro-free and concise api which does not require more lines than model-on-paper has
• concise, simple, solver agnostic, immutable, type safe
• with a separation of model and data, and hence, enable abstraction over inputs
• with reusable & composable model components
• below is a demo of my attempt in C# and here is the documentation

concurrent programming and parallel processing

Working more and more on concurrent programming and parallel processing in rust. One thing lead to another, and I got more and more interested:

• First, worked on defining the PinnedVec trait and its implementations such as the SplitVec and FixedVec. A pinned vector is nothing but a vector which keeps its elements pinned in their memory locations.
• Turns out this feature is very useful in defining concurrent collections such as ConcurrentBag, ConcurrentVec or ConcurrentOrderedBag. This allows to write outputs of a computation concurrently.
• Then, the missing piece is to provide inputs concurrently with the convenience of an iterator. And hence, the ConcurrentIter.
• Having concurrent readers and concurrent writers, we can have a very simple yet very performant parallel iterator Par.

self referential collections

Working on convenient and efficient self referential collections.

• Such collections are common building blocks of data structures used in many algorithms, but they are tricky to build in rust, certainly trickier than garbage collected languages.
• The goal is to define how to create such collections safely and efficiently in rust.
• Again the PinnedVec serves as the starting point since we want our references to stay valid.
• Second goal is to define and provide core functionalities of such collections. SelfRefCol aims to serve as the core structure for self referential collection.
• As the first consumer, worked on building the famously tricky LinkedList on top of SelfRefCol, which turned out to be very efficient.
• Efficient & flexible trees 🌴 and graphs are in progress. To continue with graphs.

also

• working on efficient data structures as I need in algorithms, such as PriorityQueue trait and efficient d-ary heap implementations.
• and whenever I have time, I am trying some experimental ideas such as Closure and FunVec.

Mathematical Modeling Demo

mathematical modeling in action 🔎

orx-concurrent-iter's Issues

BufferedIter of range iterator depends on start to be zero

Conversion of `ConcurrentIter` back to wrapped type by `into_inner`

Remove trait bound `Default` for consuming iterators

Default is added to be able to use std::mem::take. However, it is actually okay to std::mem::replace with an Uninit value since the value will never be read.

`ConIterOfRange` must have trait bound `Idx: std::iter::Step`

Currently, we cannot use this directly because the Step trait is unstable. The issue can be tracked here: rust-lang/rust#42168

This causes adding manual and very noisy trait bounds:

where
    Idx: Send
        + Sync
        + Clone
        + Copy
        + From<usize>
        + Into<usize>
        + Add<Idx, Output = Idx>
        + Sub<Idx, Output = Idx>
        + Ord,

which could simply be replaced by

where
    Idx: Send + Sync + Step

A bigger problem is the implementation of the fetch_n method which even affects the type of the returned iterator.

• If we could use Idx: Step trait bound, we could have simply returned begin_value..end_value.
• However, now we need to return (begin_idx..end_idx).map(Idx::from)

Update docs wrt scoped-threads not requiring to take extra reference

`has_more` method

Not all iterators have this information exactly due to multiple reasons.

• ExactSizeConcurrentIters know exactly how many elements are there to yield. Therefore, they can give an exact answer.
• ConcurrentIters built out of non-exact size Iterators, such as iterators with a filter, does not exactly know how many more elements to be iterated over.
  • If the underlying iterator has not yet ended, it might or might not yield any more elements.
  • However, when the underlying iterator terminated, it can give the exact "no" answer.

In either case, the concurrent iterator is able to provide an exact "no" answer. This answer is already very useful for parallel processing, which could prevent spawning unnecessary threads.

An idea could be to return the following enum:

enum HasMore {
    Yes,
    Maybe,
    No,
}

Sequential iter of a `ConcurrentIter` must yield the same type elements

Concurrent range iter returns wrong `into_seq_iter` when starting value is nonzero

Allow converting any `ExactSizeIterator` into `ExactSizeConcurrentIter`

ExactSizeConcurrentIter provides much nicer ergonomics than ConcurrentIter when iterating in chunks. The more we can have it the better. Besides, there is no reason not to have it for an arbitrary ExactSizeIterator. We must likely need a wrapper to store the initial length of the iterator to be wrapped.

Can we remove the trait bounds `T: Send + Sync`

The concurrent iterator implements Send and Sync and is shared among multiple threads. Multiple threads concurrently iterate and pull elements of T. However, it is guaranteed that each element is pulled exactly by one thread and is never shared among threads. The question is do we need the requirement on the elements that T: Send + Sync?