> By applying the longest-chain bound and the extreme-cut shortcut, the compile-time cliff in GHC’s optimal path can be effectively eliminated— and the dense worst case that survives is, satisfyingly, deeply mirrors nature’s own computational machinery.
So this can actually be implemented in GHC? I've only read through this once so far and not understood more than ¼, but the section right before the conclusion made it seem like the best you can do is O(n^2.82) along with a huge constant.
Author here: yeah the end result is that you wouldn’t actually want to do it in practice. Who wants to build a load of linear algebra into GHC, after all? But it was pleasing to show that you could make the algorithm subcubic if you really wanted. to.
This is monotone min-plus, so you can do it with even better running time than what you listed (which is just min-plus).
Also, if all numbers are at most k, you can even get running time related to k too, replacing n with k is obviously possible, but more can be done too. I feel this might be likely in practice where k might be small?
Those kinds of dependency chains look subject to a depth first search like Tarjan's strongly connected components algorithm, at least to my naive first pass reading. I've used it all over the place in e.g. analyzing foreign dependencies in database tables, or makefiles/rakefiles for task dependencies
It's always fun when someone asks an interview question that's even tangentially related and I get to go deep about the relative tradeoffs of a simpler algorithm like Tarjan's/Dijkstra's, over one of the more modern and faster but conceptually more challenging versions.
> By applying the longest-chain bound and the extreme-cut shortcut, the compile-time cliff in GHC’s optimal path can be effectively eliminated— and the dense worst case that survives is, satisfyingly, deeply mirrors nature’s own computational machinery.
So this can actually be implemented in GHC? I've only read through this once so far and not understood more than ¼, but the section right before the conclusion made it seem like the best you can do is O(n^2.82) along with a huge constant.
Author here: yeah the end result is that you wouldn’t actually want to do it in practice. Who wants to build a load of linear algebra into GHC, after all? But it was pleasing to show that you could make the algorithm subcubic if you really wanted. to.
This is monotone min-plus, so you can do it with even better running time than what you listed (which is just min-plus). Also, if all numbers are at most k, you can even get running time related to k too, replacing n with k is obviously possible, but more can be done too. I feel this might be likely in practice where k might be small?
Those kinds of dependency chains look subject to a depth first search like Tarjan's strongly connected components algorithm, at least to my naive first pass reading. I've used it all over the place in e.g. analyzing foreign dependencies in database tables, or makefiles/rakefiles for task dependencies
It's always fun when someone asks an interview question that's even tangentially related and I get to go deep about the relative tradeoffs of a simpler algorithm like Tarjan's/Dijkstra's, over one of the more modern and faster but conceptually more challenging versions.