#async #batch #dispatch #function #graph

fn_graph

Dynamically managed function graph execution

9 releases (4 breaking)

Uses new Rust 2021

0.5.4 Aug 1, 2022
0.5.2 Jul 5, 2022
0.2.0 Mar 19, 2022
0.1.0 Dec 11, 2021

#139 in Data structures

Download history 38/week @ 2022-06-13 24/week @ 2022-06-20 6/week @ 2022-06-27 75/week @ 2022-07-04 41/week @ 2022-07-11 95/week @ 2022-07-18 50/week @ 2022-07-25 179/week @ 2022-08-01 68/week @ 2022-08-08 89/week @ 2022-08-15 119/week @ 2022-08-22 150/week @ 2022-08-29 58/week @ 2022-09-05 130/week @ 2022-09-12 84/week @ 2022-09-19 112/week @ 2022-09-26

384 downloads per month
Used in 9 crates (2 directly)

MIT/Apache

100KB
2K SLoC

🧬 fn_graph

Crates.io docs.rs CI Coverage Status

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.5.4"

# Integrate with `fn_meta` and/or `resman`
fn_graph = { version = "0.5.4", features = ["fn_meta"] }
fn_graph = { version = "0.5.4", features = ["resman"] }
fn_graph = { version = "0.5.4", features = ["fn_meta", "resman"] }

Rationale

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

Function Data
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.
  • resman: Runtime managed resource borrowing.
  • shred: Shared resource dispatcher.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Dependencies

~3.5MB
~62K SLoC