Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Static exception handlers (i.e. well-disciplined gotos!) #5879

Closed
vicuna opened this issue Jan 9, 2013 · 27 comments
Closed

Static exception handlers (i.e. well-disciplined gotos!) #5879

vicuna opened this issue Jan 9, 2013 · 27 comments

Comments

@vicuna
Copy link

vicuna commented Jan 9, 2013

Original bug ID: 5879
Reporter: @alainfrisch
Assigned to: @alainfrisch
Status: resolved (set by @alainfrisch on 2017-03-02T15:32:38Z)
Resolution: won't fix
Priority: normal
Severity: feature
Category: language features
Tags: patch
Related to: #4800 #6242
Monitored by: @whitequark @Drup @bobzhang meyer @gasche meurer @lefessan @diml @ygrek @chambart @jberdine @jmeber @hcarty @avsm @Chris00 @yakobowski @alainfrisch

Bug description

There is a class of uses of exceptions within a single function body to express interesting control flows:

  1. Complex nested loops, with exceptional exit conditions.

  2. Sharing continuations / early returns , as in:

try
match ... with
| Int x -> raise (Cont (string_of_int x))
| String s -> raise (Cont s)
| Tuple -> ...
| Foo -> ...
with Cont s -> "lit:" ^ s

(An alternative in this specific example is to introduce a local function, which works well because the raise is in terminal position.)

However, exceptions have there own drawbacks:

  • It is more difficult to reason with them; there is always the risk of forgetting to catch them locally and have them escape from the function.

  • Runtime cost (even if exceptions are very quick, there is still an allocation for the exception and some overhead associated to the handler).

  • Exceptions must be declared. If the exception arguments depend on some of the local type variables in a polymorphic, the exception must be defined locally within a local module (using locally abstract types). This is heavy syntactically and induces some extra runtime cost.

These drawbacks motivate a proposal for lightweight static local exceptions: such exceptions can only be raised locally within the catch-block body (and not inside a nested function). Technically, this can be implemented using the Lstaticcatch/Lstaticraise already available in the Lambda internal representation. I attach a very quick and dirty proof of concept for this proposal, which piggy-backs the syntax for standard exceptions (try/raise) and polymorphic variants, so as to allow writing:

try
... raise (`A (foo, bar)) ...

with `A (x, y) -> x + y

File attachments

@vicuna
Copy link
Author

vicuna commented Jan 9, 2013

Comment author: @alainfrisch

Some micro-benchmarking:

===================================================
type t =
| A of int
| B of string
| C

exception Cont of int

let f1 a x =
try
match x with
| A i -> raise (Cont i) | B s -> raise (Cont 10)
| C -> 0
with `Cont i -> a * i + 1

let f2 a x =
try
match x with
| A i -> raise (Cont i)
| B s -> raise (Cont 10)
| C -> 0
with Cont i -> 2 * i + 1

let f3 a x =
let cont i = a * i + 1 in
match x with
| A i -> cont i
| B s -> cont 10
| C -> 0

let f4 a x =
match x with
| A i -> a * i + 1
| B s -> a * 10 + 1
| C -> 0

let () =
let x = A 10 in
for i = 1 to 1000000000 do
ignore (f1 2 x) (* f2, f3, f4 *)
done

Compiling with -inline 10000:

f1: 1.23s
f2: 6.02s
f3: 4.53s
f4: 1.23s

--> The solution based on static exception is as fast the the one with code duplication. The one based on exceptions or local functions are quite slower.

(Without -inline 1000:

f1: 3.29s
f2: 5.71s
f3: 4.52s
f4: 3.29s)

The solution with exceptions is even worse if we compile with -g and run with b=1:

f1: 1.20s
f2: 21.49s (!!!)
f3: 4.00s
f4: 1.23s

--> In an application which needs to be run with stacktrace enabled (which is common!), exceptions are not a decent option when performance matters.

@vicuna
Copy link
Author

vicuna commented Jan 10, 2013

Comment author: @alainfrisch

I've created a branch in the SVN (branches/static_exceptions) to experiment with this idea.

@vicuna
Copy link
Author

vicuna commented Jan 10, 2013

Comment author: @bobzhang

actually I have came across some bugs which the outer catch catches an inner exception(not I expected), this feature may help avoid such bugs

@vicuna
Copy link
Author

vicuna commented Jan 10, 2013

Comment author: @gasche

Could you maintain a specification of where static raises are valid? If I understand correctly, you currently explicit rule out static raises from function subexpressions, and try..with subexpressions. I must say I would more confident in an "opt-in" static validation (only explicitly selected forms are safe) rather than the current "opt-out" mechanism (explicitly forbid some constructs). I tried wreaking havoc with object methods, but they desugar into Pexp_function so they're safe by chance.

let test =
let module F (M : sig end) = struct let x = raise Foo end in let module M = struct end in try let module X = F(M) in () with Foo -> 0;;

Fatal error: exception Failure("Unbound static exception Foo")

I would suggest a post-translation validation pass, at the typed-tree level, that would just iterate on subexpressions of staticcatch and check that the raises are valid. That would allow to keep an implementation-specification simple and readable in one place, independently from the code sprinkled all along the Pexp->Texp translation pass.

@vicuna
Copy link
Author

vicuna commented Jan 10, 2013

Comment author: @alainfrisch

Static raises are also now explicitly disallowed under functors and classes.
I believe it could be possible to allow them under regular try...with, but this requires extra support in the bytecode and native compilers (to pop trap handlers before jumping to the static handler).

Indeed, it might be more robust to check well-formedness of static raises as a post-processing pass. Doing it on the typedtree will not be very different from doing the check during type-checking. I would rather do it on the Lambda code, where e.g. functors are already turned into functions. But we should then keep locations in the lambda code, which is not currently the case.

Anyway, apart from implementation choices, the first question is whether such a new control flow feature deserves to be included in the language.

@vicuna
Copy link
Author

vicuna commented Jan 11, 2013

Comment author: @alainfrisch

I've lifted the restriction on try...with blocks: a static raise can traverse normal exception handlers. This gives a nice way to escape a try...with block in order to preserve tail recursion:

let rec foo x =
try
...
...
raise (Cont e) with | Not_found -> .... | Cont x2 -> foo x2

@vicuna
Copy link
Author

vicuna commented Jan 11, 2013

Comment author: @gasche

If I understand correctly, the compilation strategy (either in bytecode or nativecode) is to, at the time of static raise, pops all the dynamic traps that where placed in the context since the static catch.

In particular, this change does not affect the code generated (and the performances) for static raises that are outside any dynamic exception trap, such as all the static raises currently produced by the pattern matcher compiler.

@vicuna
Copy link
Author

vicuna commented Jan 11, 2013

Comment author: @alainfrisch

Gabriel: yes, exactly.

@vicuna
Copy link
Author

vicuna commented Jan 11, 2013

Comment author: @alainfrisch

I've written a blog post about this proposal:

https://www.lexifi.com/blog/static-exceptions

@vicuna
Copy link
Author

vicuna commented Jan 15, 2013

Comment author: @Chris00

Just a silly question: why is the local function not inlined?

@vicuna
Copy link
Author

vicuna commented Jan 15, 2013

Comment author: @alainfrisch

Just a silly question: why is the local function not inlined?

This is not silly at all! My understanding is that the code of the local function is indeed inlined, but the reference to 'a' still points to the closure, which is thus still allocated.

@vicuna
Copy link
Author

vicuna commented Jan 26, 2013

Comment author: @bobzhang

I want to add that Stream parsers may benefit from such extension

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @gasche

As per my understanding, this feature got a big "meh" from the maintainers (with mention that OCaml exceptions are already much more efficient than the competion, you ungrateful folks!), so it's more or less on hold for now.

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @lefessan

Maybe an alternative approach would be:

  • An optimization scheme for local exceptions, detected as such:

    let module M = struct exception Found of int*int end in
    try
    for i = 1 to 100 do
    for j = 1 to 100 do
    if table.[i].[j] = 0 then raise (M.Found (i,j))
    done
    done;
    raise Not_found
    with M.Found (x,y) -> (x,y)

  • An annotation "localexc" on the definition of the exception, where new versions of the compiler will reject the program if the exception escapes.

By the way, I use local exceptions a lot...

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @alainfrisch

this feature got a big "meh" from the maintainers

Not from me! And apparently, Fabrice is also in favor of "something like that". Hongbo mentioned some interesting use for compiling stream parsers. So count at least three maintainers interested in the feature :-)

with mention that OCaml exceptions are already much more efficient than the competition

Performance is just one of the three reasons to motivate the feature (and we could add a forth one: avoid breaking tail-recursion); the most important one is in my opinion that the feature documents (i) the fact that the exception cannot escape; (ii) the fact that the exception is raised for control-flow with a well-defined target, not for error report with an unknown handler.

This is really a very useful control flow feature... I should probably have called the proposal "intra-procedural gotos with arguments" instead of "local exceptions" (and used a different syntax as well). I would most often use it to share a "default" continuation in code like:

try
match ... with
| ... ->
begin match ... with
| ... -> ...
| ... -> raise CONT end | ... -> raise CONT
with `CONT ->
...

(sometimes with arguments)

where I would certainly not introduce an exception...

Maybe an alternative approach would be:

I don't see the point of hiding a useful and light feature (no declaration) into a more heavy syntax, which changes the behavior (w.r.t. tail-recursion, backtrace) of an existing feature. If we add support something to the compiler, the best way to document it is with a proper syntax.

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @gasche

I think the "code sharing" aspect could be successfully worked around by an escape analysis for local function that are only used for code sharing in this way. It should be reliable (use the exact same static criterion to decide which call places are correct) and efficient.

I'm a bit less convinced about the real-world use of the exception escape analysis for those that are really used for control flow instead of just avoiding code duplication in tail positions. Local exceptions are not idiomatic for now (you have my support on #5955, though), what I've seen in the wild is Exit, and in this case you must forbid any external calls, which I think rules out most code that could benefit from the feature (short of a much too serious may-raise analysis). That could still be interesting, so I'm not saying that nobody should consider working on it :-)

On a more general point, Alain, here is "the point" you say you don't see: adding a fresh new feature to a language increases its width, which is the number of different concepts one must understand to work reasonably with code found in the wild or that oneself writes naturally. Each new feature addition must be weighted in terms of the added expressiveness vs. the cost of a feature addition (this increased "width", plus risk of implementation bugs, tools update, etc.). The C# language designers, for example, have an informal "-100" rule ( http://blogs.msdn.com/b/ericgu/archive/2004/01/12/57985.aspx ) where discussion of a new feature don't begin in the state "I don't know whether we want this feature", but in the state "We don't want it.": it is not enough for a language feature to simply be an improvement over not having it for the specific programs it was designed for.

One "bad" thing with your feature is that it adds no new dynamic semantics, it doesn't allow to write shorter programs to do harder things, it is only motivated by "intentional" performance considerations (that in some designer's books are not part of the semantics surface of a programming language; they are in fact, but they're still the vilain petit canards of language design): it's not about what the programs compute, but how. If it is easy to get the same performance benefits by static analysis of an already-existing feature, there is absolutely no reason not to: you get the good performance bonus, without the bad enlargment of your language definition.

On the other hand, some language feature allow "exponential" gain in expressivity: they are not expressible in a local way otherwise, or not having them badly breaks composability. For example, getting rid of first-order functions requires non-local transformations (not reasonable to expect of an user by hand). Even for "intentional" performance-oriented features, composability of the performance model can be important: getting rid of unboxed array and record for floats, relying instead only on the local-reference heuristic for float unboxing, breaks composability as you cannot anymore split a computation handling unboxed floats across several modules.

I personally like static raises (and have thought about them before, but never dared to suggest that as a surface level feature) -- I'm the kind of people that likes the idea of an explicit "tail" keyword ("tail f x") for guaranteed-terminal calls. But it is in the middle ground between the features that are easy to replace by local optimization and a small compromize (I think the "code sharing" part of it fits this description), and those that cannot be expressed as local optimizations for composability reasons (I think the exception escape analysis part of it may be in this category, even though it might be reasonable with local exceptions; the fact that the feature fundamentally relies on static exceptions not crossing function boundaries forbids any kind of composability). So I understand that opinions differ, and that there are people for and people against the feature, with none of them being wrong. That said, it is a great feature for an intermediate language to have.

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @alainfrisch

I think the "code sharing" aspect could be successfully worked around by an escape analysis for local function that are only used for code sharing in this way.

This would cover the example I gave, but not:

try
match ... with
| ... ->
let x =
match ... with
| ... -> ...
| ... -> raise CONT in ... | ... -> raise CONT
with `CONT ->
...

Also, how would you support:

try
match ... with
| ... ->
begin try
match ... with
| ... -> ...
| ... -> ...
| ... -> raise CONT with Not_found -> ... end | ... -> raise CONT
with `CONT ->
...

If you replace the static raise by local function, you won't be able to express that the body of this local function is not covered by the (regular) exception handler. In addition (and related) to the semantical change, there is also the fact that if the shared continuation does a tail call, it might end up in non-tail position.

But fundamentally, yes, I agree that a better compilation of local functions used to share continuations would already be an excellent thing.

Each new feature addition must be weighted in terms of the added expressiveness vs. the cost of a feature addition

Expressiveness is not the only good property of a language. Being able to express explicitly important invariants (checked by the compiler) and proposing a style which avoids programming mistake (unlike using "raise Exit" only to discover later that the exception can also escape from an inner function call; or using a local function, which will end up covered by an inner exception handler) and encourage code sharing are important as well.

The fact that the same construction have these two qualities, plus a natural compilation scheme (and predictable performance, unlike compiler optimizations), while reusing existing machinery in the compiler back-end, is a good indication that this feature deserves to be considered as a first-class construction.

it is only motivated by "intentional" performance considerations

I don't know how many times I'll have to repeat that performance consideration is not the only reason for the proposal.

If it is easy to get the same performance benefits by static analysis of an already-existing feature, there is absolutely no reason not to: you get the good performance bonus, without the bad enlargment of your language definition.

I can understand that people are not convinced, and I won't push too much for the feature, but I don't accept the "there is absolutely no reason". Yes, there are reasons to prefer an explicit construction. It makes the code more self-describing and more robust to future evolutions which could break the optimization. One reason I like OCaml is that I can get a good idea of the performance profile without having to understand potentially complex (and often ill-documented) automatic optimizations. Another reason is that it allows me to express invariants (like immutability of some data structures), even if this doesn't change expressiveness of the language or its performance.

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @gasche

Pardon me if I wasn't clear, the "there is no reason not to" part was of course not aimed at this precise language feature, for which I believe your reasons are well-articulated and convincing. It was an abstract remark of language features that are trivially subsumed by a static analysis (of which we don't have many examples of, as they tend to never become language features in the first place).

Your latter examples are interesting but vicious :p. You mess with the difference between local sharing functions, that can only be optimized in tail contexts, and the static raises that in some sense create the tail contexts by themselves, making them applicable in some more cases.

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @alainfrisch

Your latter examples are interesting but vicious :p.

You know you can always count on me :-)

You mess with the difference between local sharing functions, that can only be optimized in tail contexts, and the static raises that in some sense create the tail contexts by themselves, making them applicable in some more cases.

The way I see it is that encoding the shared continuations as local functions is just a "trick", which works only in some cases and has negative side-effects (like breaking tail context).

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @gasche

Good points.

It might be possible to also generate good code for local functions in non-tail contexts (with a 'call' and 'ret' but less heavy stuff in the middle), but we probably don't want to go into that.

@vicuna
Copy link
Author

vicuna commented Nov 18, 2013

Comment author: @alainfrisch

Cf #6242 for a proposal to improve compilation of local functions used to share a continuation.

@vicuna
Copy link
Author

vicuna commented Dec 19, 2013

Comment author: @alainfrisch

I've attached local_exn.diff, which extends the language with a new construction to create a local exception:

let exception A of .... in
...

It implements a simplification (in bytecomp/simplif.ml, enabled only in native code) to turn such exceptions into static ones (Lstaticcatch/Lstaticraise). For each declaration, the simplifier attempts to rewrite all try...with blocks in its scope in order to turn raises into staticraises (and eliminate the handler from the try...with block, and potentially the try..with block itself if it becomes empty). If this process allows to remove all occurrences of the exceptions, this is assumed to be valid. Otherwise, no optimization is done for the local exception. I'm confident (but not 100% sure) that this is sound.

Anyway, this allows to use the existing notion of exception and get the benefits of my original proposal. One would certainly need some way to force the compiler to complain if a given local exception cannot be turned into a static one, though, because the optimization is rather fragile (e.g. we only need an inner "try..with" block with a catch-all case to prevent the simplification).

This is a quick hack, very lightly tested. Comments are still welcome!

@vicuna
Copy link
Author

vicuna commented Dec 19, 2013

Comment author: @gasche

I think that, from a language design aspect, this is a good path to take (when you design for inclusion in an existing language). It would indeed be nice to have extension_points attributes for "this must be a local-raise" and "this must be tail-rec".

@vicuna
Copy link
Author

vicuna commented Dec 19, 2013

Comment author: @lpw25

Would it not be simpler to detect all raises that are surrounded statically by a matching try..with block, and turn those into static raises? That would seem to be a more robust optimisation, and would work for exceptions that are not defined locally.

This also seems somewhat related to Pierre's unboxing and inlining work, maybe it would fit in with the proposed new compilation phase.

@vicuna
Copy link
Author

vicuna commented Dec 19, 2013

Comment author: @alainfrisch

Would it not be simpler to detect all raises that are surrounded statically by a matching try..with block, and turn those into static raises?

Unfortunately, it's not that easy (and this is why I still consider that having a dedicated language feature would be a better solution):

  • Since you cannot really know that the same exception couldn't also be raised by another point in the try...with block, you need to keep the dynamic handler as well. There is a cost associated to it, and also to the fact that you want to share the dynamic and the static with clauses. I've done some tests, and it seems we loose most of the benefit related to static exceptions, at least for the case of a constant exception (which is now much faster because it doesn't allocated any more).

  • As a special case of the remark above, consider:

let rec f x =
try
if ... then raise Foo else f ...
with Foo ->
...

If you cannot remove the try...with block (and you cannot do it if you don't control the Foo exception),
the recursive call cannot be made tail-recursive.

  • In a case such as:

    try

    try .... raise Foo ... with Bar -> ...
    

    with Foo -> ...

(It's very useful to be able to escape from one or several try...with blocks like that.)

or even:

try
raise Foo
with Bar -> 1 | Foo -> 2

It's very hard to turn the "raise Foo" into a jump to the Foo handler. This assumes that Foo and Bar are different exceptions, but there is usually no way to prove it. Having the exception defined locally and enough restrictions to ensure it cannot escape seems to be a natural solution.

@vicuna
Copy link
Author

vicuna commented Mar 2, 2017

Comment author: @damiendoligez

See also:
#2657 ( #260 )
#2698 ( #301 )
#3039 ( #638 )

@vicuna
Copy link
Author

vicuna commented Mar 2, 2017

Comment author: @alainfrisch

Resolving as "won't fix". There is no strong support for adding a dedicated language feature that corresponds directly to the internal static jump construction. We will rather look into compiling existing idioms (locally-defined exceptions, local functions used only in tail position, etc) to make use of static jumps.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants