ITADN

Autoedge Big-O performance improvements

#861Openpurpleidea 创建于 2026-02-07
hacker
P
purpleideacommented
Our autoedge algorithm is likely currently O(n^2) ish or worse. We think we can improve it to O(n * log n) or even O(n). This will involve some clever algorithmist work. This will help if we've got very large resource graphs. It's not necessarily a blocker atm, but enabling fast autoedges for very large resource graphs would have long-term benefits. Here are some suggested approaches one might take. Please feel free to suggest additional ideas as well. Some initial research work was done by @frebib in https://github.com/frebib/mgmt/commit/1b4fb059cc663f79293763918b2a8e5f702fc4b7 * Improve the core autoedges algorithm. I'm not a great algorithmist, and while I think it's correct, a smarter computer scientist might know of a better approach. * Add caching to the graph lookup operations that the algorithm uses. Repeated lookups that are similar could be cached. * Add engineering approaches to minimize search size. We might be able to extend the autoedges API to statically know which resource kind's can edge together or not. This would reduce the search size. Remember to include the match against both same kind of resource and differing kind of resources. * Consider parser tricks to skip attempting to autoedge resources with existing dependencies. In situations where we already know there is a dependency between two or more resources, adding a new edge might not be beneficial. In the transistive example where we have A -> B, and B -> C, it's no use adding A -> C for example. This would offer speed up be initially reducing the graph size substantially. * Delta optimizations during graph transitions. When swapping from one resource graph to a subsequent one, we essentially re-run the autoedge code. It might be helpful to look at the previous result to determine if we can reuse some of that work. An algorithmist might want to be present to ensure we don't do something wildly more inefficient here. * Extra edge prevention. We don't want to add more edges than absolutely necessary. Extra edges technically increase memory usage and reduce parallelism, so we should not add anything that isn't absolutely necessary. * Tests. We'd definitely love to have more tests here both for correctness and performance. In particular, when we're doing edges involving send/recv we want to make sure not to break the logical data flows. Additional ideas and discussion welcome.
5 条评论