search

lf-lang / reactor-rs

Reactor runtime implementation in Rust
MIT License
9 stars 5 forks source link

Replace level assignment algo #31

Closed oowekyala closed 2 years ago

oowekyala commented 2 years ago

I suspected the algorithm is exponential for some types of graph, and measured that this is the case. This PR replaces the algo with something that stays linear. I also compared with the algorithm used by the C++ runtime (ported to Rust). The Rust algorithm of this PR scales better on this specific type of graph, but I didn't do any tests on more normal graphs. This is anyway not a performance critical part of the runtime, but this TODO comment had been irking me for a while....

Here's a graph produced by the benhmarking framework. The "old" curve is the current algorithm, the "new" one is the one introduced in this PR. The graph is similar to the chain of diamonds described in the removed TODO comment (see changes). The chain length is the x axis of the graph.

lines

cmnrd commented 2 years ago

Cool! Can you share any details about the dependency graph structure that you used for your experiments?

oowekyala commented 2 years ago

The dependency graph looks like this: Bildschirmfoto vom 2022-09-19 10-12-07

It is a chain of small identical subgraphs, which each contain a long path and a short path from the source to the exit. The number of these subgraphs is the parameter for the test (in the screenshot, 3, but in the benchmark 10 to 120). The old algorithm is bad with this structure because it performs breadth first search, and its frontier set grows much more than necessary. It starts with the root, but after 3 iterations the frontier set contains Reaction(r[0]/1) and Port(r[0]/out) (red nodes), because the shortest path from the root to these nodes has length 3. The successors of each of these will be explored separately, which duplicates work. After 6 iterations the frontier set is all the turquoise nodes (nodes reachable in three steps from any red node), and it keeps growing.