Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005935OCamlOCaml generalpublic2013-02-28 11:172013-11-26 15:30
Reporterfrisch 
Assigned Tofrisch 
PrioritynormalSeverityfeatureReproducibilityhave not tried
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version 
Target Version4.02.0+devFixed in Version4.02.0+dev 
Summary0005935: A faster version of "raise" which does not maintain the backtrace
DescriptionWhen backtraces are enabled, all raise statements result have some overhead associated to maintaining the trace. This can significantly reduce performances of code which relies on exception as "early exits".

Consider for instance:

============================================================
(* a specialized version of List.map which returns the original list (physically)
   if all elements are mapped to themselves (physically). *)

let map_phys_eq f xs =
  let rec map_same = function
    | [] -> raise Exit
    | x :: xs ->
        let y = f x in
        if y == x then y :: map_same xs
        else y :: map_not_same xs
  and map_not_same = function
    | [] -> []
    | x :: xs ->
        let y = f x in
        y :: map_not_same xs
  in
  try map_same xs
  with Exit -> xs

let () =
  let l = [1;2] in
  for i = 1 to 100000000 do
    ignore (map_phys_eq (fun x -> x) l)
  done
============================================================

Some timings:

 - ocamlopt: 2.65s
 - ocamlopt -g: 2.70s
 - ocamlopt -g + OCAMLRUNPARAM=b: 5.55s

Bad news: running the application with backtraces enabled really slows down this kind of code.
Good news: the runtime overhead of -g is very small.

One could try to dynamically disable the backtrace:

============================================================
let map_phys_eq f xs =
...
  in
  if Printexc.backtrace_status () then begin
    Printexc.record_backtrace false;
    try
      let l = map_same xs in
      Printexc.record_backtrace true;
      l
    with Exit ->
      Printexc.record_backtrace true;
      xs
  end else
    try map_same xs
    with Exit -> xs
============================================================

which gives:


 - ocamlopt: 3.42s
 - ocamlopt -g: 3.50s
 - ocamlopt -g + OCAMLRUNPARAM=b: 10.38s

This is much worse (probably because of the cost of registering/removing a global root in record_backtrace). Moreover, this approach does not work if the function [f] can raise exceptions (one should at least restore backtrace=true in that case, but we would loose backtraces for those exceptions).


I propose to add a new function Pervasives.quick_raise, which behaves as raise but does not guarantee that backtraces are correct. It would compile down to code that does not call caml_stash_backtrace even if backtrace are enabled. One must decide what to do when the exception is re-raised implicitly (when a try...with handler does not handle it). The simplest choice is to re-raise as usual (with backtrace capture) and I believe it is enough for the use cases of quick_raise. Another possibility would be to keep track (maybe next to caml_backtrace_last_exn) of whether the current exception has been raise with quick_raise or not. I'd say this is overkill.
TagsNo tags attached.
Attached Files

- Relationships
related to 0006203resolvedfrisch Lifting allocation of constant exception constructors? 
related to 0005899resolvedjacques-henri.jourdan Expose a way to inspect the current call stack 

-  Notes
(0008938)
chambart (developer)
2013-02-28 22:51

If the intended usage is quick escape from a loop, I would prefer some kind of variation over your static raise patch. Not being able to compile that kind of raise as a static raise is not necessarily a problem. Even if it is not the case, we still have the syntactic guaranty that exception does not escape.

In that particular example, only enclosing the function inside the try would be needed. Of course it limit a bit the refactoring possibilities, but I think the global win is worth it.
(0008940)
gasche (developer)
2013-03-01 11:03

Some of the maintainers resistance to exposing static raise is the idea that we enlarge the semantic surface of the language for concepts that are not necessary for expressivity, but motivated by intentional reasons (performance issues).

While I share your preference with static raise compared to this construct, I suspect part of Alain's reasoning is that this does not add a new concept to the language, only a primitive function, so arguably the language (especially if you ignore the intentional aspects) does not get more complex.

Note also that static raise does not subsume always-catched dynamic exception handling, as static raise imposes a static lexical scoping discipline that is not present here. Alain, being a true perfectionist (with a refreshingly distinct fitness function), probably wishes for efficient provably catched exceptions *both* in the static and dynamic cases.
(0008941)
frisch (developer)
2013-03-01 11:06

One argument in favor of local exceptions is that they cannot escape. This can be guaranteed by a very strong syntactic constraint that they must be raised within the try...with block but not under an abstraction. In the example of the ticket, this constraint is not satisfied and some more advanced static analysis would be required to ensure that indeed, the exception cannot escape from the handler.

Another argument for local exceptions is about performance, and this indeed is what I'm interested here. But the extremely good performance of local exceptions comes from the fact that they can be compiled as a simple jump. This cannot be the case for the example of the ticket, because the intermediate list is build on the stack during the recursion, and the raise needs to pop all of them and returns control to a different function. Not a simple jump.

So while I still believe that local exceptions are useful, I also think that it is useful to provide a quicker variant of raise which does not maintain the backtrace, for cases where the non-static aspect is useful (cutting the control flow across functions, in a non-static way) but backtraces are not (because one can convince ourselves that the exception does not escape *and* its backtrace is not used).
(0008942)
frisch (developer)
2013-03-01 11:08

> Some of the maintainers resistance to exposing ... is the idea that we enlarge the semantic surface of the language for concepts that are not necessary for expressivity, but motivated by intentional reasons.

Like "static types" :-) ?
(0009152)
jacques-henri.jourdan (manager)
2013-04-16 22:18

Note that this function can easily be implemented by some user code.

If one puts the following code in a separate file :

let quickRaise e = raise e

And compile this file with -inline 0 but without -g (even if the rest of the code uses -g).

Then, a call to quickRaise is very cheap. In most of the cases, it will even be in terminal position, so that the only additional cost compared to an optimized raise is a jump.
(0009153)
frisch (developer)
2013-04-16 22:23

> Note that this function can easily be implemented by some user code.

Indeed, this is a good point, and it shows that there is nothing difficult in adding the primitive.
(0010449)
frisch (developer)
2013-10-10 12:32

Possible approaches:

 - New function in Pervasives.

 - Attribute on the raise.
(0010472)
frisch (developer)
2013-10-14 16:45

I've created a branch "raise_variants" in the SVN to experiment with this feature. A new function Pervasives.raise_notrace is available. Using it instead of raise in the code example gives the same speed when running with or without trace enabled (OCAMLRUNPARAM=1).

(The branch also adds an explicit "reraise" internal primitive, used by the compiler when it re-raise implicitly an exception not caught by a given handler, or when the programmer applies "raise" within an handler on the caught exception.)
(0010481)
frisch (developer)
2013-10-14 19:04

Side note: the version of the benchmark where the 'Exit' exception value is shared (by a global "let exit = Exit" declaration) gives an extra 4% speedup. This is related to 0006203.
(0010630)
frisch (developer)
2013-11-13 15:02

raise_variants branch has been merged into trunk (rev 14289).

- Issue History
Date Modified Username Field Change
2013-02-28 11:17 frisch New Issue
2013-02-28 22:51 chambart Note Added: 0008938
2013-03-01 11:03 gasche Note Added: 0008940
2013-03-01 11:06 frisch Note Added: 0008941
2013-03-01 11:08 frisch Note Added: 0008942
2013-04-15 11:54 lefessan Status new => acknowledged
2013-04-16 17:24 gasche Relationship added related to 0005899
2013-04-16 22:18 jacques-henri.jourdan Note Added: 0009152
2013-04-16 22:23 frisch Note Added: 0009153
2013-04-29 16:50 frisch Severity minor => feature
2013-10-10 12:23 doligez Relationship added related to 0006203
2013-10-10 12:32 frisch Note Added: 0010449
2013-10-11 09:48 frisch Assigned To => frisch
2013-10-11 09:48 frisch Status acknowledged => assigned
2013-10-11 09:48 frisch Target Version => 4.02.0+dev
2013-10-14 16:45 frisch Note Added: 0010472
2013-10-14 19:04 frisch Note Added: 0010481
2013-11-13 15:02 frisch Note Added: 0010630
2013-11-13 15:02 frisch Status assigned => resolved
2013-11-13 15:02 frisch Fixed in Version => 4.02.0+dev
2013-11-13 15:02 frisch Resolution open => fixed


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker