Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005879OCamlOCaml generalpublic2013-01-09 12:122014-12-21 23:42
Reporterfrisch 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityhave not tried
StatusacknowledgedResolutionopen 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0005879: Static exception handlers (i.e. well-disciplined gotos!)
DescriptionThere 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
Tagspatch
Attached Filesdiff file icon static_exn.diff [^] (7,690 bytes) 2013-01-09 12:13 [Show Content]
diff file icon local_exn.diff [^] (26,330 bytes) 2013-12-19 17:03 [Show Content]

- Relationships
related to 0004800acknowledged native compilation optimization of tuple assignment 
related to 0006242acknowledged Better compilation of local functions only used for tail calls 

-  Notes
(0008728)
frisch (developer)
2013-01-09 17:37

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.
(0008734)
frisch (developer)
2013-01-10 14:57

I've created a branch in the SVN (branches/static_exceptions) to experiment with this idea.
(0008735)
hongboz (developer)
2013-01-10 15:57

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
(0008736)
gasche (developer)
2013-01-10 16:34
edited on: 2013-01-10 16:35

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.

(0008737)
frisch (developer)
2013-01-10 17:43

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.
(0008739)
frisch (developer)
2013-01-11 11:08

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
(0008740)
gasche (developer)
2013-01-11 15:22

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.
(0008741)
frisch (developer)
2013-01-11 16:15

Gabriel: yes, exactly.
(0008742)
frisch (developer)
2013-01-11 17:21

I've written a blog post about this proposal:

https://www.lexifi.com/blog/static-exceptions [^]
(0008753)
Christophe Troestler (reporter)
2013-01-15 14:05

Just a silly question: why is the local function not inlined?
(0008754)
frisch (developer)
2013-01-15 14:11

> 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.
(0008800)
hongboz (developer)
2013-01-26 17:09

I want to add that Stream parsers may benefit from such extension
(0009132)
gasche (developer)
2013-04-16 11:56

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.
(0009135)
lefessan (developer)
2013-04-16 12:07

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...
(0009136)
frisch (developer)
2013-04-16 12:28

> 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.
(0009139)
gasche (developer)
2013-04-16 14:26
edited on: 2013-04-16 14:30

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 PR#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.

(0009142)
frisch (developer)
2013-04-16 15:04

> 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.
(0009143)
gasche (developer)
2013-04-16 15:17

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.
(0009144)
frisch (developer)
2013-04-16 15:30

> 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).
(0009149)
gasche (developer)
2013-04-16 17:14

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.
(0010641)
frisch (developer)
2013-11-18 16:48

Cf 0006242 for a proposal to improve compilation of local functions used to share a continuation.
(0010753)
frisch (developer)
2013-12-19 17:10

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!
(0010754)
gasche (developer)
2013-12-19 17:33
edited on: 2013-12-19 17:33

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".

(0010755)
lpw25 (developer)
2013-12-19 21:12
edited on: 2013-12-19 21:16

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.

(0010757)
frisch (developer)
2013-12-19 23:02

> 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.

- Issue History
Date Modified Username Field Change
2013-01-09 12:12 frisch New Issue
2013-01-09 12:12 frisch File Added: static_exn.ml
2013-01-09 12:13 frisch File Deleted: static_exn.ml
2013-01-09 12:13 frisch File Added: static_exn.diff
2013-01-09 17:37 frisch Note Added: 0008728
2013-01-10 14:57 frisch Note Added: 0008734
2013-01-10 15:57 hongboz Note Added: 0008735
2013-01-10 16:34 gasche Note Added: 0008736
2013-01-10 16:34 gasche Note Edited: 0008736 View Revisions
2013-01-10 16:35 gasche Note Edited: 0008736 View Revisions
2013-01-10 17:43 frisch Note Added: 0008737
2013-01-11 11:08 frisch Note Added: 0008739
2013-01-11 15:22 gasche Note Added: 0008740
2013-01-11 16:15 frisch Note Added: 0008741
2013-01-11 17:21 frisch Note Added: 0008742
2013-01-15 13:40 frisch Relationship added related to 0004800
2013-01-15 14:05 Christophe Troestler Note Added: 0008753
2013-01-15 14:11 frisch Note Added: 0008754
2013-01-26 17:09 hongboz Note Added: 0008800
2013-04-15 12:23 xleroy Severity minor => feature
2013-04-16 11:56 gasche Note Added: 0009132
2013-04-16 11:56 gasche Status new => acknowledged
2013-04-16 12:07 lefessan Note Added: 0009135
2013-04-16 12:28 frisch Note Added: 0009136
2013-04-16 14:26 gasche Note Added: 0009139
2013-04-16 14:27 gasche Note Edited: 0009139 View Revisions
2013-04-16 14:30 gasche Note Edited: 0009139 View Revisions
2013-04-16 15:04 frisch Note Added: 0009142
2013-04-16 15:17 gasche Note Added: 0009143
2013-04-16 15:30 frisch Note Added: 0009144
2013-04-16 17:14 gasche Note Added: 0009149
2013-11-18 16:44 frisch Relationship added related to 0006242
2013-11-18 16:48 frisch Note Added: 0010641
2013-12-16 13:53 doligez Tag Attached: patch
2013-12-19 17:03 frisch File Added: local_exn.diff
2013-12-19 17:10 frisch Note Added: 0010753
2013-12-19 17:33 gasche Note Added: 0010754
2013-12-19 17:33 gasche Note Edited: 0010754 View Revisions
2013-12-19 21:12 lpw25 Note Added: 0010755
2013-12-19 21:16 lpw25 Note Edited: 0010755 View Revisions
2013-12-19 21:16 lpw25 Note Edited: 0010755 View Revisions
2013-12-19 23:02 frisch Note Added: 0010757


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker