aboutsummaryrefslogtreecommitdiffstats
path: root/src/swarm/peer/inbound.rs
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-08 18:58:43 +0000
committertv <tv@krebsco.de>2026-11-08 20:02:26 +0100
commitfe19de5220071cd33294b700a9d4b6a10b634137 (patch)
tree2da6fdf60c14deb58bed1c3cb0880c41324db714 /src/swarm/peer/inbound.rs
parent9b58d2e870fddb5f04e846b0566dd6a613d2f699 (diff)
screen: changes put in order in one pass
bench_screening showed screening growing quadratically: 1 000 changes took 29 ms on top of applying them, 10 000 took 2.8 s, and 100 000 didn't finish in minutes. in_order placed changes in rounds, each taking those, in hash order, whose dependencies were placed: a chain received in one delta, its hashes in no order of their own, took about as many rounds as changes, each over all of them. It now counts, for each change, its dependencies among those received not placed yet, and places the smallest hash of those with none left, then those building on it as their counts reach zero (Kahn's algorithm): n log n, and still the same order on every node, whatever order the changes came in. One with a dependency neither in the document nor among them, and what builds on it, still wait.
Diffstat (limited to 'src/swarm/peer/inbound.rs')
0 files changed, 0 insertions, 0 deletions