Skip to content

Support for scopes #104

@davidlattimore

Description

@davidlattimore

I'm interesting in the possibility of trying out orx-parallel in the Wild linker, which currently uses rayon pretty heavily. From a bit of a look through the APIs, the two main things that stand out as missing is threadpool support (for which I see there's already an issue) and some way of dealing with graph algorithms.

Wild has two phases where it's effectively exploring a graph. These start with some initial nodes that need processing. As these nodes get processed, more nodes get added and so on until all reachable nodes have been processed. With rayon, this can be done using rayon::scope and scope.spawn. Each time a new node needs to be processed, we spawn a task to process it.

The rayon approach of allowing arbitrary tasks to be spawned into the scope is flexible, however comes with the cost that each spawned task needs to be separately heap-allocated. In many cases, all spawned work items are of the same type T and are processed by the same closure, so I could imaging having a more efficient kind of scope that was generic over T, allowing the per-task heap allocation to be avoided.

Implementation of this is a bit tricky, since threads may run out of work, but then later get more work to do as new parts of the graph are explored.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions