Mantis Bug Tracker
Main | My View | View Issues | Change Log | Roadmap
  

View Issue Details [ Jump to Notes ] [ Issue History ] [ Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005879OCamlOCaml generalpublic2013-01-09 12:122013-04-16 17:14
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
TagsNo tags attached.
Attached Filesdiff file icon static_exn.diff [^] (7,690 bytes) 2013-01-09 12:13 [Show Content]

- Relationships
related to 0004800acknowledged native compilation optimization of tuple assignment 

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

- 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

Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker