Explaining Coroutines with Scala Native, Scala Days, Madrid, 2023.pptx

Wojciech Mazur explains different types of coroutines, as presented at the Scala Days conference in Madrid.

1. Wojciech Mazur Explaining Different Coroutine Flavours using Scala Native

2. AboutMe.md Scala 3 Compiler Team at VirtusLab Scala Native R&D Open Community Build, maintenance of Scala 3 Cooperation with LAMP EPFL

3. All the tasty flavours of routines

4. Routines routine

5. Subroutines Caller Function return routine subroutine call

6. Coroutines routine subroutine coroutine

7. Coroutines routine subroutine coroutine stackless stackfull

8. Coroutines execution flow Suspend by return ing to caller/resumer Nested suspensions requires all callers/resumer to be a coroutine Introduces function coloring Used for generators, iterators, async/await, etc Available in Kotlin, Swift, C++, Rust and more Implemented by function transformation in the compiler Caller Coro call suspend resume suspend Stackless

9. Stackless coroutines transformation State Machine based coroutines

10. Stackless coroutines transformation Continuation Passing Style coroutine

11. Coroutines execution flow Suspend by context-switch to caller/resumer Can suspend at any point Does not introduce function coloring Used for fibers and exception handling Available in Go, Java Caller Coro 1 Coro/Func 2 Coro/Func N call call call suspend return return return resume Stackfull

12. Suspendable? I wanted concurrency!

13. Asynchronous coroutines Any coroutine can potentially be made asynchronous Coroutine scheduler can manage concurrent execution of coroutines On suspend coroutine can: be scheduled for automatic resumption specify next coroutine to resume

14. How they work?

15. Subroutines f(x) local variables temp = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x8

16. Subroutines f(x) local variables temp = 9 params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0xF g(x) local variables params: x = 9 resumption address: f(x) + 0x18 pc = ???

17. Subroutines f(x) local variables temp = 9 params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0xF g(x) local variables params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x8 h (x) local variables params: x = 10 resumption address: g(x) + 0xF pc = ???

18. Subroutines f(x) local variables temp = 9 params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0xF g(x) local variables params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x8 h(x) local variables params: x = 10 resumption address: g(x) + 0xF pc = h(x) + 0x8

19. Subroutines f(x) local variables temp = 9 params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0xF g(x) local variables h.result = 20 params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0xF

20. Subroutines f(x) local variables temp = 9 g.result = 20 params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10

21. Stackless coroutines f(x) local variables: temp = 9 coro = ??? res1 = ??? res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10

22. Stackless coroutines f(x) local variables: temp = 9 coro = ??? res1 = ??? res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 g(x) local variables: tmp = 20 coroHandle = ??? params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x10

23. Stackless coroutines f(x) local variables: temp = 9 coro = ??? res1 = ??? res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 g(x) local variables: tmp = 20 coroHandle = 0xffab1234 params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x10 Stack Heap Coroutine Frame g(x) 0xffab1234 resumptionAddress : g(x) + 0x18 localVariabl es : tmp = 20 x = 9 coroState = 42 promise : 20 registers: rax = 0x1234 rdx = 0x1234

24. Stackless coroutines f(x) local variables: temp = 9 coro = 0xffab1234 res1 = ??? res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 Stack Heap Coroutine Frame g(x) 0xffab1234 resumptionAddress : g(x) + 0x18 localVariables : tmp = 20 x = 9 coroState = 42 promise : 20 registers: rax = 0x1234 rdx = 0x1234

25. Stackless coroutines f(x) local variables: temp = 9 coro = 0xffab1234 res1 = 20 res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 Stack Heap Coroutine Frame g(x) 0xffab1234 resumptionAddress : g(x) + 0x18 localVariables : tmp = 20 x = 9 coroState = 42 promise : 20 registers: rax = 0x1234 rdx = 0x1234

26. Stackless coroutines f(x) local variables: temp = 9 coro = 0xffab1234 res1 = 20 res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 Stack Heap Coroutine Frame g(x) 0xffab1234 resumptionAddress : g(x) + 0xF localVariables : tmp = 20 x = 9 coroState = 42 promise : 20 registers: rax = 0x1234 rdx = 0x1234 g(x) local variables: tmp = 20 coroHandle = 0xffab1234 params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x18

27. Stackless coroutines f(x) local variables: temp = 9 coro = 0xffab1234 res1 = 20 res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 Stack Heap Coroutine Frame g(x) 0xffab1234 resumptionAddress : g(x) + 0xF localVariables : tmp = 20 x = 9 coroState = 42 promise : 20 registers: rax = 0x1234 rdx = 0x1234 g(x) local variables: tmp = 20 coroHandle = 0xffab1234 params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x18 h(x) local variables params: x = 20 resumption address: g(x) + 0x20 pc = h(x) + 0x8

28. Stackless coroutines f(x) local variables: temp = 9 coro = 0xffab1234 res1 = 20 res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 Stack Heap Coroutine Frame g(x) 0xffab1234 resumptionAddress : g(x) + 0xF localVariables : tmp = 20 x = 9 coroState = 42 promise : 20 registers: rax = 0x1234 rdx = 0x1234 g(x) local variables: tmp = 20 coroHandle = 0xffab1234 h.result = 40 params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x20

29. Stackless coroutines f(x) local variables: temp = 9 coro = 0xffab1234 res1 = 20 res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 Stack Heap Coroutine Frame g(x) 0xffab1234 resumptionAddress : g(x) + 0xF localVariables : tmp = 20 x = 9 coroState = 42 promise : 20 registers: rax = 0x1234 rdx = 0x1234 g(x) local variables: tmp = 20 coroHandle = 0xffab1234 h.result = 40 $1 = -40 params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x28

30. Stackless coroutines f(x) local variables: temp = 9 coro = 0xffab1234 res1 = 20 res2 = ??? res3 = ??? params: x = 3 resumption address: main() + 0x42 pc = f(x) + 0x10 Stack Heap Coroutine Frame g(x) 0xffab1234 resumptionAddress : g(x) + 0x38 localVariables : tmp = 20 x = 9 coroState = 37 promise : -40 registers: rax = 0x2456 rdx = 0x2456 g(x) local variables: tmp = 20 coroHandle = 0xffab1234 h.result = 40 $1 = -40 params: x = 9 resumption address: f(x) + 0x18 pc = g(x) + 0x30

31. Stackless coroutines Saves only the state of current activation frame Creates a snapshot of required data on the heap Ephemeral local data on the stack Heap allocation can be optimized out by the compiler

32. Fibers f(x) local variables: task = 0xffab1234 params: x = 4 resumption address: main() + 0x42 pc = f(x) + 0x100 Stack Heap 0xffab1234 Fiber Context: f$anonfun$0(x) resumptionAddress: anonfun$0 + 0x00 state = new promise : ??? stack = null registers: rsp =??? rbp = ??? rdx = ???

33. F i bers f(x) local variables: task = 0xffab1234 params: x = 4 resumption address: main() + 0x42 pc = f(x) + 0x100 Stack Heap 0xffab1234 Fiber Context: f$anonfun$0(x) resumptionAddress: anonfun$0 + 0x00 state = active promise : stack = 0xbadcafe registers: rsp = 0xbad123 rbp = 0x1234 rdx = 0xcafe42 f$anonfun$0(x) local variables: temp=8 g.result = ??? params: x = 4 resumption address: f() + 0x108 pc = f$anonfun$0 + 0x18 resumption address: f$ anonfun$0 () + 0x20 pc = g(x) + 0x30 g(x) resumption address: g(x) + 0x38 pc = anonfun$1 + 0x50 anonfun$1(x) resumption address: anonfun$1(x) + 0x58 pc = anonfun$2 + 0x40 anonfun$2(x)

34. Fibers f(x) local variables: task = 0xffab1234 x = 0 params: x = 4 resumption address: main() + 0x42 pc = f(x) + 0x100 Stack Heap 0xffab1234 Fiber Context: f$anonfun$0(x) resumptionAddress: anonfun$0 + 0x00 state = suspended promise : stack = 0xbadcafe registers: rsp = 0xbad123 rbp = 0x1234 rdx = 0xcafe42 Stack snapshot: 0xbadcafe f$anonfun$0(x) local variables: temp=8 g.result = ??? params: x = 4 resumption address: f() + 0x108 pc = f$anonfun$0 + 0x18 resumption address: f$ anonfun$0 () + 0x20 pc = g(x) + 0x30 g(x) resumption address: g(x) + 0x38 pc = anonfun$1 + 0x50 anonfun$1(x) resumption address: anonfun$1(x) + 0x58 pc = anonfun$2 + 0x40 anonfun$2(x)

35. Fibers f(x) local variables: task = 0xffab1234 x = 0 params: x = 4 resumption address: main() + 0x42 pc = f(x) + 0x100 Stack 0xffab1234 Fiber Context: f$anonfun$0(x) resumptionAddress: anonfun$0 + 0x00 state = active promise : stack = 0xbadcafe registers: rsp = 0xbad123 rbp = 0x1234 rdx = 0xcafe42 f$anonfun$0(x) local variables: temp=8 g.result = ??? params: x = 4 resumption address: f() + 0x108 pc = f$anonfun$0 + 0x18 resumption address: f$ anonfun$0 () + 0x20 pc = g(x) + 0x30 g(x) resumption address: g(x) + 0x38 pc = anonfun$1 + 0x50 anonfun$1(x) resumption address: anonfun$1(x) + 0x58 pc = anonfun$2 + 0x40 anonfun$2(x)

36. Fibers Possible stack provision: Eager fiber stack allocated on creation Lazily copied to the heap on suspend Typically 1-10x slower suspend/resume then stackless coroutines Still way faster then thread context-switch

37. Quick summary Stackfull Coroutines Fibers Context switching Suspension at any point Subroutines Ordinary function No special mechanism No suspension Stackless Coroutines Generators State machine / Continuation Passing Style Only top-level suspension

38. Coroutines a’la Scala Native

39. LLVM stackless coroutines Coroutines Lowering Switch-Resume Async Returned-Continuation

40. LLVM stackless coroutines

41. LLVM stackless coroutines Transformed into state machine by LLVM Body needs to be inlined Transformed to cleanup function Transformed into ramp function

42. LLVM stackless coroutines

43. LLVM stackless coroutines

44. LLVM stackless coroutines

45. LLVM stackless coroutines

46. LLVM stackless coroutines tinyurl.com/ stackless-coroutines

47. Fibers, threads and user context

48. Switching-context: assembly Non portable Different registers available depending on CPU architecture and OS Hard to maintain

49. Switching-context: ucontext_t POSIX specific Simple API Deprecated and removed in latest APIs

50. Switching-context: setjmp/longjmp Portable between Unix/Windows Can implement exception handling Not available on some platforms (WebAssembly)

51. Switching-context: setjmp/longjmp

52. boundary-suspend Snapshot of context for each handler and continuation Create snapshot of continuation before moving control to handler Restore snapshot before resumption Greatly simplified!

53. boundary-suspend tinyurl.com/ boundary -suspend

54. boundary-suspend tinyurl.com/ boundary-suspend