ashvardanian / ashvardanian/ForkUnion

Map-Filter-Reduce for Rust and/or C++

Open
#2 3 comments 0 reactions 0 assignees Claimed by @ashvardanian View on GitHub
enhancement good first issue help wanted
Dominant language
C++
Stars
373
Forks
24
Avg merge
1h 9m
Merged PRs (30d)
1

Description

Transmuting pointers, using `unsafe` sections, and padding elements to different cache lines is quite tricky in Rust, and not always straightforward & safe in C++ too. The following "map-reduce"-like operations can be introduced:

```rs
pub fn try_map(
&self,
inputs: &[T],
map: F,
) -> Result, A>, ForkUnionError>
where ...
```

The full set of operations may include: `try_map`, `try_map_reduce`, `try_map_filter_reduce`. The `try_map_reduce` and `try_map_filter_reduce` should be much cheaper to run, than combining `try_map` with subsequent separate reduction. In optimized versions, we can keep just one "folding reduction result" privately per thread, and can be outputted into a smaller container the size of the thread pool - no the `inputs` container.

Relevant considerations:

- What kinds of `inputs` containers can be accepted, and have sub-linear iteration cost, so that we can cheaply split the work between multiple worker threads?
- Should we use the same allocator with which the `ForkUnion` was created or allow passing an additional one for the exported execution results?
- For non-flat `inputs`, should the method be called `try_flat_map`?

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the proposed try_map, try_map_reduce, and try_map_filter_reduce entry points, then review linked pull request #9. Determine the accepted input containers, allocator choice, and naming for non-flat inputs; done requires resolved design decisions and agreement between the issue and the pull request.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, rust
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.