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

A faster version of "raise" which does not maintain the backtrace #5935

Closed
vicuna opened this issue Feb 28, 2013 · 10 comments
Closed

A faster version of "raise" which does not maintain the backtrace #5935

vicuna opened this issue Feb 28, 2013 · 10 comments
Assignees
Milestone

Comments

@vicuna
Copy link

vicuna commented Feb 28, 2013

Original bug ID: 5935
Reporter: @alainfrisch
Assigned to: @alainfrisch
Status: closed (set by @xavierleroy on 2015-12-11T18:25:20Z)
Resolution: fixed
Priority: normal
Severity: feature
Target version: 4.02.0+dev
Fixed in version: 4.02.0+dev
Category: ~DO NOT USE (was: OCaml general)
Related to: #5899 #6203
Monitored by: @gasche mfp sweeks @jmeber @yakobowski

Bug description

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

@vicuna
Copy link
Author

vicuna commented Feb 28, 2013

Comment author: @chambart

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.

@vicuna
Copy link
Author

vicuna commented Mar 1, 2013

Comment author: @gasche

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.

@vicuna
Copy link
Author

vicuna commented Mar 1, 2013

Comment author: @alainfrisch

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

@vicuna
Copy link
Author

vicuna commented Mar 1, 2013

Comment author: @alainfrisch

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" :-) ?

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @jhjourdan

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.

@vicuna
Copy link
Author

vicuna commented Apr 16, 2013

Comment author: @alainfrisch

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.

@vicuna
Copy link
Author

vicuna commented Oct 10, 2013

Comment author: @alainfrisch

Possible approaches:

  • New function in Pervasives.

  • Attribute on the raise.

@vicuna
Copy link
Author

vicuna commented Oct 14, 2013

Comment author: @alainfrisch

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

@vicuna
Copy link
Author

vicuna commented Oct 14, 2013

Comment author: @alainfrisch

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

@vicuna
Copy link
Author

vicuna commented Nov 13, 2013

Comment author: @alainfrisch

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

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