diff options
| author | tv <tv@krebsco.de> | 2026-11-08 18:58:43 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-08 20:02:26 +0100 |
| commit | fe19de5220071cd33294b700a9d4b6a10b634137 (patch) | |
| tree | 2da6fdf60c14deb58bed1c3cb0880c41324db714 /src/api/dashboard/dashboard.html | |
| parent | 9b58d2e870fddb5f04e846b0566dd6a613d2f699 (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/api/dashboard/dashboard.html')
0 files changed, 0 insertions, 0 deletions
