Crate fn_graph

source ·
Expand description

Dynamically managed function graph execution.

This crate provides a FnGraph, where consumers can register a list of functions and their interdependencies. The graph can then return a stream of functions to iterate over either sequentially or concurrently. Any data dependencies required by the functions are guaranteed to not conflict according to borrowing rules.

There is additional flexibility that the type of functions is not limited to closures and functions, but any type that implements the FnRes and FnMeta traits.

Usage

Add the following to Cargo.toml

fn_graph = "0.9.0"

# Integrate with `fn_meta` / `interruptible` / `resman`
fn_graph = { version = "0.9.0", features = ["fn_meta"] }
fn_graph = { version = "0.9.0", features = ["interruptible"] }
fn_graph = { version = "0.9.0", features = ["resman"] }
fn_graph = { version = "0.9.0", features = ["fn_meta", "interruptible", "resman"] }

Rationale

Support there are three tasks, each represented by a function. Each function needs different data:

FunctionData
f1&a, &b
f2&a, &b, &mut c
f3&mut a, &b, &mut c

When scheduling parallel execution, it is valid to execute f1 and f2 in parallel, since data a and b are accessed immutably, and c is exclusively accessed by b. f3 cannot be executed in parallel with f1 or f2 as it requires exclusive access to both a and c.

For a small number of functions and data, manually writing code to schedule function execution is manageable. However, as the number of functions and data increases, so does its complexity, and it is desirable for this boilerplate to be managed by code.

Notes

The concept of a runtime managed data-dependency task graph is from shred; fn_graph’s implementation has the following differences:

  • Different API ergonomics and flexibility trade-offs.

    • Takes functions and closures as input instead of System impls.

    • Parameters are detected from function signature instead of SystemData implementation, but with a limit of 8 parameters. (manual SystemData implementation has arbitrary limit)

    • Return type is type parameterized instead of ().

  • Instead of grouping functions by stages to manage data access conflicts, fn_graph keeps a dependency graph of logic and data dependencies, and executes functions when the preceding functions are complete.

    This allows for slightly less waiting time for subsequent functions with data dependencies, as each may begin once its predecessors finish, whereas a staged approach may contain other functions that are still executing that prevent functions in the next stage from beginning execution.

See Also

  • fn_meta: Returns metadata about a function at runtime.
  • interruptible: Support for interruptible streams.
  • resman: Runtime managed resource borrowing.
  • shred: Shared resource dispatcher.

Re-exports

Structs

  • EdgeCounts
    Number of incoming and outgoing edges.
  • FnGraph
    Directed acyclic graph of functions.
  • FnGraphBuilder
    Builder for a FnGraph.
  • FnIdInner
    Type safe function ID for a FnGraph.
  • FnRef
    A reference to the function, which also signals when the reference is dropped.
  • FnWrapper
    Wraps the graph F function type to upper bind the 'graph lifetime to the 'iter lifetime.
  • FnWrapperMut
    Wraps the graph F function type to upper bind the 'graph lifetime to the 'iter lifetime.
  • R
    Read access to T.
  • Rank
    Rank of a function in the graph.
  • StreamOpts
    How to stream item from the graph.
  • StreamOutcome
    How a FnGraph stream operation ended and IDs that were processed.
  • StreamProgress
    State during processing a FnGraph stream, and the IDs that are processed.
  • W
    Write access to T.
  • WouldCycle
    An error returned by the Dag::add_edge method in the case that adding an edge would have caused the graph to cycle.

Enums

Traits

Type Aliases