Effect Handlers in Multicore OCaml

1. Effect Handlers in Multicore OCaml “KC” Sivaramakrishnan
2. • Adds native support for concurrency and parallelism to OCaml Multicore OCaml
3. • Adds native support for concurrency and parallelism to OCaml Multicore OCaml Overlapped execution A B A C B Time
4. • Adds native support for concurrency and parallelism to OCaml Multicore OCaml Overlapped execution A B A C B Time Simultaneous execution A B C Time
5. • Adds native support for concurrency and parallelism to OCaml Multicore OCaml Overlapped execution A B A C B Time Simultaneous execution A B C Time Effect Handlers
6. • Adds native support for concurrency and parallelism to OCaml Multicore OCaml Overlapped execution A B A C B Time Simultaneous execution A B C Time Effect Handlers Domains
7. • Adds native support for concurrency and parallelism to OCaml Multicore OCaml Overlapped execution A B A C B Time Simultaneous
8. Concurrency is not parallelism Parallelism is a performance hack whereas concurrency is a program structuring mechanism
9. Concurrency is not parallelism • OS threads give you parallelism and concurrenc y ✦ Too heavy weight for concurrent programmin g ✦ Http server with 1 OS thread per request is a terrible idea Parallelism is a performance hack whereas concurrency is a program structuring mechanism
10. Concurrency is not parallelism • OS threads give you parallelism and concurrenc y ✦ Too heavy weight for concurrent programmin g ✦ Http server with 1 OS thread per request is a terrible idea • Programming languages provide concurrent programming mechanisms as primitives ✦ async/await, generators, coroutines, etc. Parallelism is a performance hack whereas concurrency is a program structuring mechanism
11. Concurrency is not parallelism • OS threads give you parallelism and concurrenc y ✦ Too heavy weight for concurrent programmin g ✦ Http server with 1 OS thread per request is a terrible idea • Programming languages provide concurrent programming mechanisms as primitives ✦ async/await, generators, coroutines, etc. • Often include different primitives for concurrent programmin g ✦ JavaScript has async/await, generators, promises, and callbacks!! Parallelism is a performance hack whereas concurrency is a program structuring mechanism
12. Concurrent Programming in OCaml
13. Concurrent Programming in OCaml • OCaml does not have primitive support for concurrent programming
14. Concurrent Programming in OCaml • OCaml does not have primitive support for concurrent programming • Lwt and Async - concurrent programming libraries in OCam l ✦ Callback-oriented programming with monad synta x ✦ But do not satisfy monad laws
15. Concurrent Programming in OCaml • OCaml does not have primitive support for concurrent programming • Lwt and Async - concurrent programming libraries in OCam l ✦ Callback-oriented programming with monad synta x ✦ But do not satisfy monad laws • Suffers many pitfalls of callback-oriented programmin g ✦ No backtraces, exceptions can’t be used, monadic syntax
16. Concurrent Programming in OCaml • OCaml does not have primitive support for concurrent programming • Lwt and Async - concurrent programming libraries in OCam l ✦ Callback-oriented programming with monad synta x ✦ But do not satisfy monad laws • Suffers many pitfalls of callback-oriented programmin g ✦ No backtraces, exceptions can’t be used, monadic syntax • Go (goroutines) and GHC Haskell (threads) have better abstractions — lightweight threads
17. Concurrent Programming in OCaml • OCaml does not have primitive support for concurrent programming • Lwt and Async - concurrent programming libraries in OCam l ✦ Callback-oriented programming with monad synta x ✦ But do not satisfy monad laws • Suffers many pitfalls of callback-oriented programmin g ✦ No backtraces, exceptions can’t be used, monadic syntax • Go (goroutines) and GHC Haskell (threads) have better abstractions — lightweight threads Should we add lightweight threads to OCaml?
18. Effect Handlers • A mechanism for programming with user-de f i ned effects
19. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines
20. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines • Effect declaration separate from interpretation (c.f. exceptions)
21. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines • Effect declaration separate from interpretation (c.f. exceptions) effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 "
22. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines • Effect declaration separate from interpretation (c.f. exceptions) effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " effect declaration
23. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines • Effect declaration separate from interpretation (c.f. exceptions) effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " computation effect declaration
24. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines • Effect declaration separate from interpretation (c.f. exceptions) effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " computation handler effect declaration
25. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines • Effect declaration separate from interpretation (c.f. exceptions) effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " computation handler suspends current computation effect declaration
26. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines • Effect declaration separate from interpretation (c.f. exceptions) effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " computation handler delimited continuation suspends current computation effect declaration
27. Effect Handlers • A mechanism for programming with user-de f i ned effects • Modular basis of non-local control- f l ow mechanism s ✦ Exceptions, generators, lightweight threads, promises, asynchronous IO, coroutines • Effect declaration separate from interpretation (c.f. exceptions) effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " computation handler delimited continuation suspends current computation resume suspended computation effect declaration
28. Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp
29. Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp
30. comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp parent Fiber: A piece of stack + effect handler
31. comp comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp parent 0
32. comp comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k 0
33. comp comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k 0
34. comp comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k 0
35. comp comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k 0 1
36. comp comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k 0 1
37. comp comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k parent 0 1
38. comp comp Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k parent 0 1 2
39. Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k 0 1 2 3
40. Stepping through the example effect E : string let comp () = print_string "0 "; print_string (perform E); print_string "3 " let main () = try comp () with effect E k -> print_string "1 "; continue k "2 "; print_string “4 " pc main sp k 0 1 2 3 4
41. effect A : unit effect B : unit let baz () = perform A let bar () = try baz () with effect B k -> continue k () let foo () = try bar () with effect A k -> continue k () Handlers can be nested foo bar baz sp parent parent pc
42. effect A : unit effect B : unit let baz () = perform A let bar () = try baz () with effect B k -> continue k () let foo () = try bar () with effect A k -> continue k () Handlers can be nested foo bar baz sp parent parent pc
43. effect A : unit effect B : unit let baz () = perform A let bar () = try baz () with effect B k -> continue k () let foo () = try bar () with effect A k -> continue k () Handlers can be nested foo bar baz sp parent pc k
44. effect A : unit effect B : unit let baz () = perform A let bar () = try baz () with effect B k -> continue k () let foo () = try bar () with effect A k -> continue k () Handlers can be nested foo bar baz sp parent pc k • Linear search through handler s • Handler stacks shallow in practice
45. Lightweight Threading effect Fork : (unit -> unit) -> unit effect Yield : unit
46. Lightweight Threading effect Fork : (unit -> unit) -> unit effect Yield : unit let run main = ... (* assume queue of continuations *) let run_next () = match dequeue () with | Some k -> continue k () | None -> () in let rec spawn f = match f () with | () -> run_next () (* value case *) | effect Yield k -> enqueue k; run_next () | effect (Fork f) k -> enqueue k; spawn f in spawn main
47. Lightweight Threading effect Fork : (unit -> unit) -> unit effect Yield : unit let run main = ... (* assume queue of continuations *) let run_next () = match dequeue () with | Some k -> continue k () | None -> () in let rec spawn f = match f () with | () -> run_next () (* value case *) | effect Yield k -> enqueue k; run_next () | effect (Fork f) k -> enqueue k; spawn f in spawn main let fork f = perform (Fork f) let yield () = perform Yield
48. Lightweight threading let main () = fork (fun _ -> print_endline "1.a"; yield (); print_endline "1.b"); fork (fun _ -> print_endline "2.a"; yield (); print_endline “2.b") ;; run main
49. Lightweight threading let main () = fork (fun _ -> print_endline "1.a"; yield (); print_endline "1.b"); fork (fun _ -> print_endline "2.a"; yield (); print_endline “2.b") ;; run main 1.a 2.a 1.b 2.b
50. Lightweight threading let main () = fork (fun _ -> print_endline "1.a"; yield (); print_endline "1.b"); fork (fun _ -> print_endline "2.a"; yield (); print_endline “2.b") ;; run main 1.a 2.a 1.b 2.b • Direct-style (no monads) • User-code need not be aware of effects
51. Generators
52. Generators • Generators — non-continuous traversal of data structure by yielding value s ✦ Primitives in JavaScript and Python
53. Generators • Generators — non-continuous traversal of data structure by yielding value s ✦ Primitives in JavaScript and Python function* generator(i) { yield i; yield i + 10; } const gen = generator(10); console.log(gen.next().value); // expected output: 10 console.log(gen.next().value); // expected output: 20
54. Generators • Generators — non-continuous traversal of data structure by yielding value s ✦ Primitives in JavaScript and Python • Can be derived automatically from any iterator using effect handlers function* generator(i) { yield i; yield i + 10; } const gen = generator(10); console.log(gen.next().value); // expected output: 10 console.log(gen.next().value); // expected output: 20
55. Generators: effect handlers module MkGen (S :sig type 'a t val iter : ('a -> unit) -> 'a t -> unit end) : sig val gen : 'a S.t -> (unit -> 'a option) end = struct
56. Generators: effect handlers module MkGen (S :sig type 'a t val iter : ('a -> unit) -> 'a t -> unit end) : sig val gen : 'a S.t -> (unit -> 'a option) end = struct let gen : type a. a S.t -> (unit -> a option) = fun l -> let module M = struct effect Yield : a -> unit end in let open M in let rec step = ref (fun () -> match S.iter (fun v -> perform (Yield v)) l with | () -> None | effect (Yield v) k -> step := (fun () -> continue k ()); Some v) in fun () -> !step () end
57. Generators: List module L = MkGen (struct type 'a t = 'a list let iter = List.iter end)
58. Generators: List module L = MkGen (struct type 'a t = 'a list let iter = List.iter end) let next = L.gen [1;2;3] next() (* Some 1 *) next() (* Some 2 *) next() (* Some 3 *) next() (* None *)
59. Generators: Tree type 'a tree = | Leaf | Node of 'a tree * 'a * 'a tree let rec iter f = function | Leaf -> () | Node (l, x, r) -> iter f l; f x; iter f r module T = MkGen(struct type 'a t = 'a tree let iter = iter end)
60. Generators: Tree type 'a tree = | Leaf | Node of 'a tree * 'a * 'a tree let rec iter f = function | Leaf -> () | Node (l, x, r) -> iter f l; f x; iter f r module T = MkGen(struct type 'a t = 'a tree let iter = iter end) (* Make a complete binary tree of depth [n] using [O(n)] space *) let rec make = function | 0 -> Leaf | n -> let t = make (n-1) in Node (t,n,t)
61. Generators: Tree type 'a tree = | Leaf | Node of 'a tree * 'a * 'a tree let rec iter f = function | Leaf -> () | Node (l, x, r) -> iter f l; f x; iter f r module T = MkGen(struct type 'a t = 'a tree let iter = iter end) let t = make 2 let next = T.gen t next() (* Some 1 *) next() (* Some 2 *) next() (* Some 1 *) next() (* None *) 2 1 1 (* Make a complete binary tree of depth [n] using [O(n)] space *) let rec make = function | 0 -> Leaf | n -> let t = make (n-1) in Node (t,n,t)
62. Static Semantics
63. Static Semantics • No effect safet y ✦ No static guarantee that all the effects performed are handled (c.f. exceptions ) ✦ perform E at the top-level raises Unhandled exception
64. Static Semantics • No effect safet y ✦ No static guarantee that all the effects performed are handled (c.f. exceptions ) ✦ perform E at the top-level raises Unhandled exception • Effect system in the work s ✦ See also Eff, Koka, Links, Heliu m ✦ Track both user-de f i ned and built-in (ref, io) effect s ✦ OCaml becomes a pure language (in the Haskell sense)
65. Static Semantics • No effect safet y ✦ No static guarantee that all the effects performed are handled (c.f. exceptions ) ✦ perform E at the top-level raises Unhandled exception • Effect system in the work s ✦ See also Eff, Koka, Links, Heliu m ✦ Track both user-de f i ned and built-in (ref, io) effect s ✦ OCaml becomes a pure language (in the Haskell sense) let foo () = print_string "hello, world" val foo : unit -[ io ]-> unit Syntax is still in the works
66. Static Semantics • No effect safet y ✦ No static guarantee that all the effects performed are handled (c.f. exceptions ) ✦ perform E at the top-level raises Unhandled exception • Effect system in the work s ✦ See also Eff, Koka, Links, Heliu m ✦ Track both user-de f i ned and built-in (ref, io) effect s ✦ OCaml becomes a pure language (in the Haskell sense) let foo () = print_string "hello, world" val foo : unit -[ io ]-> unit Syntax is still in the works • Today, Multicore OCaml effect handler static semantics is simple
67. Static Semantics (* OCaml extensible variant type *) type 'a eff = .. type _ eff = E : string -> int eff gets translated to effect E : string -> int The declaration
68. Static Semantics type ('a,'b) continuation argument type result type val perform: 'a eff -> 'a val continue: ('a,'b) continuation -> 'a -> 'b
69. Static Semantics match e with | None -> false | Some b -> b | effect (E s) k1 -> e1 | effect (F f) k2 -> e2 match_with (fun () -> e) { retc = (function None -> false | Some b -> b); effc = (function | (E s) -> (fun k1 -> e1) | (F f) -> (fun k2 -> e2) | e -> (fun k -> continue k (perform e)); } (* Internal API *) type 'a comp = unit -> ‘a type ('a,'b) handler = { retc: 'a -> 'b; (* value case *) effc: 'c.'c eff -> ('c,'b) continuation -> 'b; (* effect case *) } val match_with: 'a comp -> ('a,'b) handler -> ‘b compiled to assuming we have
70. Comparison to shift/reset • Effect handlers equivalent in expressive power to other delimited control operator s ✦ Forster et al, “On the expressive power of user-de f i ned effects: Effect handlers, monadic re f l ection, delimited control”, JFP 201 9 ✦ Macro-expressible to each other (ignoring types)
71. Comparison to shift/reset • Effect handlers equivalent in expressive power to other delimited control operator s ✦ Forster et al, “On the expressive power of user-de f i ned effects: Effect handlers, monadic re f l ection, delimited control”, JFP 201 9 ✦ Macro-expressible to each other (ignoring types) • Nicer to program with thanks to the handler syntax goto : while loop :: shift/reset : effect handlers - Andrej Bauer
72. Retro f i tting Challenges • Millions of lines of legacy cod e ✦ Written without non-local control- f l ow in min d ✦ Cost of refactoring sequential code itself is prohibitive
73. Retro f i tting Challenges • Millions of lines of legacy cod e ✦ Written without non-local control- f l ow in min d ✦ Cost of refactoring sequential code itself is prohibitive • Low-latency and predictable performanc e ✦ Fast exceptions, FFI
74. Retro f i tting Challenges • Millions of lines of legacy cod e ✦ Written without non-local control- f l ow in min d ✦ Cost of refactoring sequential code itself is prohibitive • Low-latency and predictable performanc e ✦ Fast exceptions, FFI • Excellent compatibility with debugging and pro f i ling tool s ✦ gdb, lldb, perf, libunwind, etc.
75. Retro f i tting Challenges • Millions of lines of legacy cod e ✦ Written without non-local control- f l ow in min d ✦ Cost of refactoring sequential code itself is prohibitive • Low-latency and predictable performanc e ✦ Fast exceptions, FFI • Excellent compatibility with debugging and pro f i ling tool s ✦ gdb, lldb, perf, libunwind, etc. Backwards compatibility before fancy new features
76. Defensive Programming • OCaml is a systems programming languag e ✦ Manipulates resources such as f i les, sockets, buffers, etc.
77. Defensive Programming • OCaml is a systems programming languag e ✦ Manipulates resources such as f i les, sockets, buffers, etc. • OCaml code is written in defensive style to guard against exceptional behaviour and clear up resources
78. Defensive Programming • OCaml is a systems programming languag e ✦ Manipulates resources such as f i les, sockets, buffers, etc. • OCaml code is written in defensive style to guard against exceptional behaviour and clear up resources let copy ic oc = let rec loop () = let l = input_line ic in output_string oc (l ^ "\n"); loop () in try loop () with | End_of_file -> close_in ic; close_out oc | e -> close_in ic; close_out oc; raise e
79. Defensive Programming • OCaml is a systems programming languag e ✦ Manipulates resources such as f i les, sockets, buffers, etc. • OCaml code is written in defensive style to guard against exceptional behaviour and clear up resources let copy ic oc = let rec loop () = let l = input_line ic in output_string oc (l ^ "\n"); loop () in try loop () with | End_of_file -> close_in ic; close_out oc | e -> close_in ic; close_out oc; raise e raises End_of_file at the end
80. Defensive Programming • OCaml is a systems programming languag e ✦ Manipulates resources such as f i les, sockets, buffers, etc. • OCaml code is written in defensive style to guard against exceptional behaviour and clear up resources let copy ic oc = let rec loop () = let l = input_line ic in output_string oc (l ^ "\n"); loop () in try loop () with | End_of_file -> close_in ic; close_out oc | e -> close_in ic; close_out oc; raise e raise Sys_error when channel is closed raises End_of_file at the end
81. Defensive Programming • OCaml is a systems programming languag e ✦ Manipulates resources such as f i les, sockets, buffers, etc. • OCaml code is written in defensive style to guard against exceptional behaviour and clear up resources let copy ic oc = let rec loop () = let l = input_line ic in output_string oc (l ^ "\n"); loop () in try loop () with | End_of_file -> close_in ic; close_out oc | e -> close_in ic; close_out oc; raise e We would like to make this code transparently asynchronous raise Sys_error when channel is closed raises End_of_file at the end
82. Asynchronous IO effect In_line : in_channel -> string effect Out_str : out_channel * string -> unit let input_line ic = perform (In_line ic) let output_string oc s = perform (Out_str (oc,s)) let run_aio f = match f () with | v -> v | effect (In_line chan) k -> register_async_input_line chan k; run_next () | effect (Out_str (chan, s)) k -> register_async_output_string chan s k; run_next ()
83. Asynchronous IO effect In_line : in_channel -> string effect Out_str : out_channel * string -> unit let input_line ic = perform (In_line ic) let output_string oc s = perform (Out_str (oc,s)) let run_aio f = match f () with | v -> v | effect (In_line chan) k -> register_async_input_line chan k; run_next () | effect (Out_str (chan, s)) k -> register_async_output_string chan s k; run_next () • Continue with appropriate value when the asynchronous IO call returns
84. Asynchronous IO effect In_line : in_channel -> string effect Out_str : out_channel * string -> unit let input_line ic = perform (In_line ic) let output_string oc s = perform (Out_str (oc,s)) let run_aio f = match f () with | v -> v | effect (In_line chan) k -> register_async_input_line chan k; run_next () | effect (Out_str (chan, s)) k -> register_async_output_string chan s k; run_next () • Continue with appropriate value when the asynchronous IO call returns • But what about termination identi f i ed by End_of_file and Sys_error exceptions?
85. Discontinue • We add a discontinue primitive to resume a continuation by raising an exceptio n • On End_of_file and Sys_error, the asynchronous IO scheduler uses discontinue to raise the appropriate exception val discontinue: ('a,'b) continuation -> exn -> 'b
86. Linearity
87. Linearity • Resources such as sockets, f i le descriptors, channels and buffers are linear resource s ✦ Created and destroyed exactly once
88. Linearity • Resources such as sockets, f i le descriptors, channels and buffers are linear resource s ✦ Created and destroyed exactly once • When calling an OCaml function, the caller expects the callee to return exactly once either with a value or an exceptio n ✦ Defensive programming already guards against exceptional return cases
89. Linearity • With effect handlers if the captured continuation is dropped on the f l oor, then any function call may only return at-most onc e ✦ This breaks resource-safe legacy code
90. Linearity • With effect handlers if the captured continuation is dropped on the f l oor, then any function call may only return at-most onc e ✦ This breaks resource-safe legacy code effect E : unit let foo () = perform E let bar () = let ic = open_in "input.txt" in match foo () with | v -> close_in ic | exception e -> close_in ic; raise e let baz () = try bar () with | effect E _ -> () (* leak *)
91. Linearity • We assume that well-formed programs resume captured continuations exactly once either using continue or discontinu e ✦ Someone please add linear types to OCaml :-)
92. Linearity • We assume that well-formed programs resume captured continuations exactly once either using continue or discontinu e ✦ Someone please add linear types to OCaml :-) • Linear use of continuations ensures that non-local control- f l ow and resources work well togethe r ✦ No need for Scheme dynamic-wind
93. Linearity • We assume that well-formed programs resume captured continuations exactly once either using continue or discontinu e ✦ Someone please add linear types to OCaml :-) • Linear use of continuations ensures that non-local control- f l ow and resources work well togethe r ✦ No need for Scheme dynamic-wind • Core and Base provide unwind-protect implemented using exception s ✦ Backwards compatibility of resourceful code ensured thanks to linearity and defensive programming
94. Foreign-function interface (* meander.ml *) external ocaml_to_c : unit -> int = "ocaml_to_c" exception E1 exception E2 let c_to_ocaml () = raise E1;; Callback.register "c_to_ocaml" c_to_ocaml;; let omain () = try (* h1 *) try (* h2 *) ocaml_to_c () with E2 -> -42 with E1 -> 42;; assert (omain () = 42) /* meander.c */ #include <caml/mlvalues.h> #include <caml/callback.h value ocaml_to_c (value unit) { caml_callback(*caml_named_value("c_to_ocaml"), Val_unit); return Val_int(0); }
95. Stack Management (* meander.ml *) external ocaml_to_c : unit -> int = "ocaml_to_c" exception E1 exception E2 let c_to_ocaml () = raise E1;; Callback.register "c_to_ocaml" c_to_ocaml;; let omain () = try (* h1 *) try (* h2 *) ocaml_to_c () with E2 -> -42 with E1 -> 42;; assert (omain () = 42) /* meander.c */ #include <caml/mlvalues.h> #include <caml/callback.h value ocaml_to_c (value unit) { caml_callback(*caml_named_value("c_to_ocaml"), Val_unit); return Val_int(0); } Stock OCaml
96. Stack Management Stock OCaml Multicore OCaml • Stack over f l ow check s ✦ Reallocate with 2x stack spac e • FFI requires stack switch
97. DWARF stack unwinding Stock OCaml
98. DWARF stack unwinding • DWARF bytecode is a Turing complete language
99. DWARF stack unwinding • DWARF bytecode is a Turing complete language • In Multicore OCaml, we’ve encoded DWARF unwinding across callbacks, external calls and effect handler s ✦ gdb, lldb, perf continue to work!
100. DWARF stack unwinding • DWARF bytecode is a Turing complete language • In Multicore OCaml, we’ve encoded DWARF unwinding across callbacks, external calls and effect handler s ✦ gdb, lldb, perf continue to work! • Veri f i ed that the unwind tables are correct using an automated too l ✦ Basitien et al, “Reliable and Fast DWARF-Based Stack Unwinding”, OOPSLA 2019
101. No effects performance
102. No effects performance coq irmin menhir alt-ergo
103. No effects performance coq irmin menhir alt-ergo • ~1% faster than stock (geomean of normalised running times ) ✦ Difference under measurement noise mostl y ✦ Outliers due to difference in allocators
104. Performance
105. Performance let foo () = (* a *) try (* b *) perform E (* d *) with effect E k -> (* c *) continue k () (* e *)
106. Performance let foo () = (* a *) try (* b *) perform E (* d *) with effect E k -> (* c *) continue k () (* e *) Instruction Sequence a to b b to c c to d d to e Signi f i cance Create a new stack & run the computation Performing & handling an e f f ect Resuming a continuation Returning from a computation & free the stack • Each of the instruction sequences involves a stack switc h • Intel(R) Xeon(R) Gold 5120 CPU @ 2.20GH z ★ For reference, memory read latency is 90 ns (local NUMA node) and 145 ns (remote NUMA node)
107. Performance let foo () = (* a *) try (* b *) perform E (* d *) with effect E k -> (* c *) continue k () (* e *) Instruction Sequence a to b b to c c to d d to e Signi f i cance Create a new stack & run the computation Performing & handling an e f f ect Resuming a continuation Returning from a computation & free the stack Time (ns) 23 5 11 7 • Each of the instruction sequences involves a stack switc h • Intel(R) Xeon(R) Gold 5120 CPU @ 2.20GH z ★ For reference, memory read latency is 90 ns (local NUMA node) and 145 ns (remote NUMA node)
108. Performance: Generators • Traverse a complete binary-tree of depth 2 5 ✦ 226 stack switches
109. Performance: Generators • Traverse a complete binary-tree of depth 2 5 ✦ 226 stack switches • Iterator — idiomatic recursive traversal
110. Performance: Generators • Traverse a complete binary-tree of depth 2 5 ✦ 226 stack switches • Iterator — idiomatic recursive traversal • Generato r ✦ Hand-written generator (hw-generator ) ✤ CPS translation + defunctionalization to remove intermediate closure allocatio n ✦ Generator using effect handlers (eh-generator)
111. Performance: Generators Variant Time (milliseconds) Iterator (baseline) 202 hw-generator 837 (3.76x) eh-generator 1879 (9.30x) Multicore OCaml
112. Performance: Generators Variant Time (milliseconds) Iterator (baseline) 202 hw-generator 837 (3.76x) eh-generator 1879 (9.30x) Multicore OCaml Variant Time (milliseconds) Iterator (baseline) 492 generator 43842 (89.1x) nodejs 14.07
113. Performance: WebServer • Effect handlers for asynchronous I/O in direct-styl e ✦ https://github.com/kayceesrk/ocaml-aeio/ • Variant s ✦ Go + net/http (GOMAXPROCS=1 ) ✦ OCaml + http/af + Lwt (explicit callbacks ) ✦ OCaml + http/af + Effect handlers (MC ) • Performance measured using wrk2
114. Performance: WebServer • Effect handlers for asynchronous I/O in direct-styl e ✦ https://github.com/kayceesrk/ocaml-aeio/ • Variant s ✦ Go + net/http (GOMAXPROCS=1 ) ✦ OCaml + http/af + Lwt (explicit callbacks ) ✦ OCaml + http/af + Effect handlers (MC ) • Performance measured using wrk2
115. Performance: WebServer • Effect handlers for asynchronous I/O in direct-styl e ✦ https://github.com/kayceesrk/ocaml-aeio/ • Variant s ✦ Go + net/http (GOMAXPROCS=1 ) ✦ OCaml + http/af + Lwt (explicit callbacks ) ✦ OCaml + http/af + Effect handlers (MC ) • Performance measured using wrk2 • Direct style (no monadic syntax)
116. Thanks! • Multicore OCaml — https://github.com/ocaml-multicore/ocaml- multicore • Effects Examples — https://github.com/ocaml-multicore/effects- examples • Sivaramakrishnan et al, “Retro f i tting Parallelism onto OCaml", ICFP 2020 • Dolan et al, “Concurrent System Programming with Effect Handlers”, TFP 2017 $ opam switch create 4.10.0+multicore \ --packages=ocaml-variants.4.10.0+multicore \ --repositories=multicore=git+https://github.com/ocaml-multicore/multicore-opam.git,default Install Multicore OCaml