Graph Algorithms in Rayon
4 months ago
- #rust
- #parallelism
- #rayon
- The Wild linker uses rayon for parallelism, primarily through `par_iter`, but faces challenges with graph exploration where work isn't known in advance.
- Initial approach: `spawn_broadcast` with custom work sharing and job control. Complex and incompatible with other rayon features.
- Second approach: Scoped spawning with `rayon::scope`. More expensive due to heap allocations but simpler than custom job control.
- Third approach: Channel + `par_bridge`. Reduces heap allocations but introduces complexity and potential deadlocks with `par_iter`.
- Composition issues with channel-based approach, especially with mutable borrows and combining different work queues.
- Potential solution: Async/await could offer better task management and avoid thread-stealing issues seen with rayon.
- Considering a return to scoped spawning despite heap allocations, due to better composability.
- Future interest in reducing heap allocations, possibly through rayon modifications for small closures.
- Acknowledgments to sponsors supporting Wild's development.