Hacker News Reader

Comment by pcwalton | Hacker News Reader

It would require higher order control flow analysis like k-CFA, which would certainly fail to produce a bounded stack size on any nontrivial program.

The futures library is the control flow analysis. Because it uses the type system instead of higher order control flow analysis, it actually achieves precision.

View on HN

"It would require higher order control flow analysis like k-CFA, which would certainly fail to produce a bounded stack size on any nontrivial program."

You can actually do a pretty good job without k-CFA.

First, and i know you know this, when you say "fail to produce a bounded stack size", you really mean "a reasonable bounded stack size".

A bounded stack size of easy, and does not require context sensitive analysis: The stack size is just max sum of stack sizes of of meet over all paths in an acyclic graph :)

The cycles, you either can statically calculate the recurrence count or you can't.

Bounded heap size is pretty much impossible, but stack size is pretty easy.

Recursion is also not hard. You form strongly connected components. You try to prove how often the component is cycled. If you can, victory. If you can't, you can bound it unless it's truly dynamic.

More to the point, here's a paper on doing it with ADA in GCC in 2009 (IE with sticks and fire):

http://www.adacore.com/uploads/technical-papers/Stack_Analys...

Note they are within 2% on most cases, and can detect whether it's statically knowable, bounded, or dynamically changing.

Are you sure about that? First, many higher-order constructs boil down to simple first-order control flow after partial evaluation (see e.g. AnyDSL https://anydsl.github.io/#publications). Inferring stack size bounds in the presence of higher-order programming features is also possible, and was implemented (as the "static region optimization") in MLkit.

But the main point is that code in a high-level programming language looks very different from C or even Rust code. Sparks in Haskell, or processes in Erlang, or even individual goroutines in Go, are typically executing comparatively tiny programs. If the call graph of the program in question is acyclic, then it should be easy to get a bound on the maximum stack size.

To be clear, I agree with you that a 1:1 threading model is the better design for Rust, simply because it's the only design where you can guarantee zero overhead and don't need a complicated runtime. What I don't agree with is that the M:N threading model is inherently inferior. Especially for a high-level programming language, I would assume that you can reduce the overhead significantly through static analysis and a good implementation.

You can't get around page fault blocking with user-space M:N threading. It will be approximate until there is a way to do that.

I was thinking of a much lighter analysis, based on some optional restrictions. If a function:

- is not recursive

- does not call function pointers (ie trait objects)

- allocates only fixed-sized objects on the stack

- only calls functions with known stack requirements

then its stack requirement should be known, no? It feels like with these requirements, one can still write many programs (threads, really). And if one goes beyond the restrictions, then they just pay the cost of having to guess a large stack size.

Stack size analysis would be helpful for other applications as well, like embedded platforms.

No program beyond the most trivial will meet these requirements. The moment you call any function indirectly you lose.

Yes, but indirectly means "&Fn", but not "&F where F: Fn".

And a whole program doesn't need to conform, only individual threads. Presumably the ones you want to make a lot of.

(And if a little dynamicism was required, its expense could be paid for at the use, by creating a fresh necessary-sized stack at that point. But I'm probably opening up old split-stack wounds, sorry)

The problem with an optimization like this is that the current approach always gives you a guarantee on runtime cost. Heuristic based optimizations make performance harder to ensure, not to mention recovering performance when you fall outside the valid subset much more difficult. You can obviously provide another static analysis to warn you about violations, but this seems is more complex, and less flexible then the current approach.

Actually the "current approach" gives you no bound on the stack size. You guess, hope, and test (or do this analysis manually).

While your general objection is good to always keep in mind, it is a tradeoff. There is no perfect solution when you're up against the halting problem (unless you're proposing to change the language to only bounded recursion).

What I'm arguing for here is for more than the single problem the OP is solving, so it's not a case of choosing one or the other and calling it a day.

Reply on news.ycombinator.com