quasigo

Transcript

1. A new Go interpreter VK Tech Talk 2022 quasigo 1
2. •Go compiler (Intel, Huawei) •KPHP compiler (VK) •Static analyzers (open source) •Developer tools like phpgrep About me 2
3. 3 Why does this talk exist? I’ll prove that it’s possible to create efficient interpreter in Go that can compete with interpreters written in C.
4. 4 Why bother? I needed an efficient Go interpreter in my ruleguard project.
5. An engine to execute dynamic rules for Go. It loads the rules written in Go DSL and then executes them over a given project. What is ruleguard? 5
6. ruleguard overview 6 style.go ruleguard src/ file1.go file1.go file1.go file1.go file1.go src/file.go -rules arg analysis target $ ruleguard -rules style.go src/...
7. 7 before after (ruleguard DSL) ruleguard in action
8. Why does ruleguard need an interpreter? 8
9. Matcher pipeline 9 m.Match(`string($x)`). Where( m["x"].Filter(f), ). Report("message")
10. Matcher pipeline 10 m.Match(`string($x)`). Where( m["x"].Filter(f), ). Report("message") 1. Find an AST (syntax) match
11. Matcher pipeline 11 m.Match(`string($x)`). Where( m["x"].Filter(f), ). Report("message") 1. Find an AST (syntax) match (if AST matched) 2. Apply filters to the match
12. Matcher pipeline 12 m.Match(`string($x)`). Where( m["x"].Filter(f), ). Report("message") 1. Find an AST (syntax) match (if AST matched) 2. Apply filters to the match (if filters accepted the match) 3. Perform an action
13. f could be a custom function Matcher pipeline 13 m.Match(`string($x)`). Where( m["x"].Filter(f), ). Report("message")
14. A custom filter example 14 func implementsStringer(ctx *dsl.VarFilterContext) bool { stringer := ctx.GetInterface(`fmt.Stringer`) // pointer to the captured, type, T -> *T ptr := types.NewPointer(ctx.Type) return types.Implements(ctx.Type, stringer) || types.Implements(ptr, stringer) }
15. A custom filter example 15 func implementsStringer(ctx *dsl.VarFilterContext) bool { stringer := ctx.GetInterface(`fmt.Stringer`) // pointer to the captured, type, T -> *T ptr := types.NewPointer(ctx.Type) return types.Implements(ctx.Type, stringer) || types.Implements(ptr, stringer) } How to execute?
16. Ruleguard resources Ruleguard by example Introduction article (RU, EN) Ruleguard workshop videos (RU) Ruleguard vs SemGrep vs CodeQL (EN) 16
17. Trying out existing interpreters 17
18. Ruleguard use case • A lot of calls to small functions Go -> interpreter • Filters call native bindings Interpreter -> Go calls Need performance in both directions 18
19. Yaegi Popular Reliable User-friendly, easy API github.com/traefik/yaegi 19
20. I built Gophers & Dragons game using yaegi. 20 My experience with yaegi
22. Yaegi interpretation model Yaegi builds an annotated AST and interprets it directly 22 X + Y + Y X
23. Yaegi performance issues reflection.Value as value type 23 Tons of heap allocations Direct AST interpretation
24. Interpreters comparison 24 Interpreter Eval performance Eval entry overhead Yaegi Very low High
25. To Yaegi or not to Yaegi? 25
26. Scriggo Fast Part of the template engine Younger than yaegi github.com/open2b/scriggo 26
27. Scriggo interpretation model Scriggo creates bytecode and then evaluates that 27 X + Y add res, x, y 0x30, 3, 5, 2
28. Scriggo multi stacks type Registers struct { Int []int64 Float []float64 String []string General []reflect.Value } 28
29. Scriggo multi stacks type Registers struct { Int []int64 // efficient! Float []float64 // efficient! String []string // efficient! General []reflect.Value } 29
30. Scriggo multi stacks type Registers struct { Int []int64 // also handles int8/16/32… Float []float64 String []string General []reflect.Value } 30
31. Scriggo multi stacks type Registers struct { Int []int64 Float []float64 String []string General []reflect.Value // slow } 31
32. Scriggo performance issues Some types have bad performance (e.g. [ ]byte) 32 Expensive Go->interpreter call costs
33. Interpreters comparison 33 Interpreter Eval performance Eval entry overhead Yaegi Very low High Scriggo High Very High
34. Quasigo interpreter 34
35. 35 Subset only quasigo principles
36. 36 Subset only Performance matters quasigo principles
37. 37 Subset only Performance matters Toolchain as a library quasigo principles
38. Sqrt benchmark 38 Interpreter Elapsed Yaegi 6.32s (x4.2) Scriggo 3.78s (x2.1) Quasigo 1.21s
39. Spectral norm benchmark 39 Interpreter Elapsed Yaegi 3.67s (x17.3) Scriggo 1.03s (x4.1) Quasigo 0.20s
40. Mandelbrot benchmark 40 Interpreter Elapsed Yaegi 7.37s (x3.7) Scriggo 11.93s (x6.6) Quasigo 1.57s
41. Sqrt benchmark (allocs) 41 Interpreter Count Bytes Yaegi 62985026 4013885208 Scriggo 8 29408 Quasigo 0 0
42. Spectral norm benchmark (allocs) 42 Interpreter Count Bytes Yaegi 19209002 793746584 Scriggo 55 69824 Quasigo 22 39416
43. 43 Interpreter Count Bytes Yaegi 1189064 11006432 Scriggo 1016 201016 Quasigo 3 147416 3 allocs 🔥 Mandelbrot benchmark (allocs)
44. Mandelbrot benchmark (allocs) 44 Interpreter Count Bytes Yaegi 1189064 11006432 Scriggo 1016 201016 Quasigo 3 147416 What is wrong with Scriggo here?
45. Why does Scriggo allocate a lot in Mandelbrot? 45 Mandelbrot size for benchmark is 1000, so numRows=1000
46. Why does Scriggo allocate a lot in Mandelbrot? 46 Scriggo stores [ ]byte in reflect.Value Slicing creates a new 24-byte allocation
47. Why quasigo is faster than Scriggo? Faster interpreter core (instructions dispatch) 47 Quasigo doesn’t shy away from unsafe package: Almost free native calls Efficient frames layout and slots representation Reflection-free access to arbitrary data 1 2 3 4
48. Is “unsafe” package usage justified here? Go runtime itself is written with a help of “unsafe”. It’s OK to use unsafe package in runtimes and low-level libraries that need all performance they can get. 48
49. Interpreters comparison 49 Interpreter Eval performance Eval entry overhead Yaegi Very low High Scriggo High Very High Quasigo Very high Very low
50. Interpreters comparison (more) 50 Interpreter Interpretation type Relies on Yaegi AST traversal reflection Scriggo Bytecode, reg VM reflection Quasigo Bytecode, reg VM unsafe
51. Quasigo runtime 51
52. VM stack frame 52 fn1 frame fn2 frame fn3 frame free space The stack grows this way
53. VM stack frame 53 fn1 frame fn2 frame fn3 frame free space Interpreter memory
54. VM stack frame 54 fn1 frame fn2 frame fn3 frame free space x y local0 local1 … func fn2(x, y int) int
55. VM stack frame 55 x y local0 local1 … func fn2(x, y int) int arg0 arg1 The call args are placed on the next func frame fn1 frame fn2 frame fn3 frame free space
56. VM stack frame 56 x y local0 local1 … arg0 arg1 These cells are called “slots” (or “virtual registers”) fn1 frame fn2 frame fn3 frame free space
57. VM stack frame 57 func fn2(x, y int) int { return x + y * 3 } LoadScalarConst local2 = 3 IntMul64 local1 = y local2 IntAdd64 local0 = x local1 ReturnScalar local0 fn2 frame x y local0 local1 local2
58. VM stack slots 58 type Slot struct { Ptr unsafe.Pointer Scalar uint64 Scalar2 uint64 }
59. VM stack slots type Slot struct { Ptr unsafe.Pointer Scalar uint64 Scalar2 uint64 } 59 sizeof(slot) == 24 bytes (on 64-bit platforms)
60. type Slot struct { Ptr unsafe.Pointer Scalar uint64 Scalar2 uint64 } Pointer types are stored in Pointer field VM stack slots: pointer types 60
61. type Slot struct { Ptr unsafe.Pointer Scalar uint64 Scalar2 uint64 } Simple numeric types are stored in Scalar field VM stack slots: scalar types 61
62. VM stack slots: strings type Slot struct { Ptr unsafe.Pointer Scalar uint64 Scalar2 uint64 } 62 Strings are stored in Ptr+Scalar. This matches the Go runtime string layout!
63. VM stack slots: slices type Slot struct { Ptr unsafe.Pointer Scalar uint64 Scalar2 uint64 } 63 Slices occupy all the slots. This matches the Go runtime slices layout!
64. VM stack slots: interfaces type Slot struct { Ptr unsafe.Pointer Scalar uint64 Scalar2 uint64 } 64 Interfaces are stored in Ptr+Scalar. Data and typeinfo pointers are swapped.
65. VM stack slots: structs type Slot struct { Ptr unsafe.Pointer Scalar uint64 Scalar2 uint64 } 65 Small structs are stored directly inside the slot, if possible. Otherwise they’re heap allocated and we store a pointer to it.
66. Quasigo compiler 66
67. Compiler architecture 67 Go code The input Go sources AST+types go/ast and go/types data IR Low-level intermediate representation bytecode The final compiler output
68. Go code AST+types IR Good for optimizations and transformations bytecode Good for the execution (it’s also compact) Compiler architecture 68
69. Bytecode instructions encoding Simple variadic-length scheme: • 1-byte opcode • 1 or 2 bytes per instruction argument • Constants are loaded from external slice using the index 3-address instruction format: dst + src1 + src2
70. Bytecode instructions encoding dst = x + y => IntAdd64 dst = x y • Opcode=IntAdd64 (1 byte) • Arg0 dst (1 byte) • Arg1 x (1 byte) • Arg2 y (1 byte) Frame slot index
71. LoadScalarConst local0.v0 = 1 LoadScalarConst local2.v0 = 1 IntAdd64 local1.v0 = local0.v0 local2.v0 LoadScalarConst local3.v0 = 1 IntAdd64 local2.v1 = local1.v0 local3.v0 LoadScalarConst local4.v0 = 1 IntAdd64 local3.v1 = local2.v1 local4.v0 ReturnScalar local3.v1 # function IR func f() int { x1 := 1 x2 := x1 + 1 x3 := x2 + 1 return x3 + 1 } Constant propagation 71
72. LoadScalarConst local0.v0 = 1 LoadScalarConst local2.v0 = 1 IntAdd64 local1.v0 = local0.v0 local2.v0 LoadScalarConst local3.v0 = 1 IntAdd64 local2.v1 = local1.v0 local3.v0 LoadScalarConst local4.v0 = 1 IntAdd64 local3.v1 = local2.v1 local4.v0 ReturnScalar local3.v1 # Slots have unique “versions” func f() int { x1 := 1 x2 := x1 + 1 x3 := x2 + 1 return x3 + 1 } Constant propagation 72
73. LoadScalarConst local0.v0 = 1 LoadScalarConst local2.v0 = 1 IntAdd64 local1.v0 = local0.v0 local2.v0 LoadScalarConst local3.v0 = 1 IntAdd64 local2.v1 = local1.v0 local3.v0 LoadScalarConst local4.v0 = 1 IntAdd64 local3.v1 = local2.v1 local4.v0 ReturnScalar local3.v1 # Same slots can have different # versions in a single block func f() int { x1 := 1 x2 := x1 + 1 x3 := x2 + 1 return x3 + 1 } Constant propagation 73
74. # Result bytecode LoadScalarConst local0 = 4 ReturnScalar local0 func f() int { x1 := 1 x2 := x1 + 1 x3 := x2 + 1 return x3 + 1 } Constant propagation 74
75. Len local2.v0 = s Zero local3.v0 ScalarEq local1.v0 = local2.v0 local3.v0 Not local0.v0 = local1.v0 JumpZero Label0 local0.v0 Jump condition optimizations 75 if !(len(s) == 0) { … }
76. Len local2.v0 = s Zero local3.v0 ScalarEq local1.v0 = local2.v0 local3.v0 Not local0.v0 = local1.v0 JumpZero Label0 local0.v0 # Can inverse the jump cond if !(len(s) == 0) { … } Jump condition optimizations 76
77. Len local2.v0 = s Zero local3.v0 ScalarEq local1.v0 = local2.v0 local3.v0 Not local0.v0 = local1.v0 JumpNotZero Label0 local1.v0 Jump condition optimizations 77 if !(len(s) == 0) { … }
78. Len local2.v0 = s Zero local3.v0 ScalarEq local1.v0 = local2.v0 local3.v0 JumpNotZero Label0 local1.v0 # Can inject the zero comparison # into the jump cond 78 if !(len(s) == 0) { … } Jump condition optimizations
79. Len local2.v0 = s Zero local3.v0 ScalarEq local1.v0 = local2.v0 local3.v0 JumpZero Label0 local2.v0 Jump condition optimizations 79 if !(len(s) == 0) { … }
80. # Result bytecode Len local2 = s JumpZero Label0 local2 Jump condition optimizations 80 if !(len(s) == 0) { … }
81. Other optimizations • Inlining (with post-inlining optimizations) • Some idioms and corner cases recognition • Frames trimming • Unused constants removal 81 Implemented:
82. Other optimizations • Comparisons fusing and rewrites • Jump threading • More peephole optimizations 82 Planned:
83. Where can I use quasigo? 83
84. Quasigo for game development Write a game in Go (using ebiten or other game library). Allow the users to write plugins/scripts for your game in Go, using quasigo as embedded interpreter. 84
85. Quasigo for query languages For example, a DB like tarantool, but written in Go and with Go as a query language instead of Lua. It’s also possible to use Go scripts as custom filtering lambdas for your internal services. 85
86. Quasigo for template engines Since Scriggo is used as a template engine core, I could imagine quasigo used in the same context. It will probably be at least as efficient as Scriggo in that domain. 86
87. Quasigo state Good enough for ruleguard Not ready for general purpose production use yet Alpha release can be expected in 4-6 months 87
88. Comparing with Lua 88
89. Interpreter Elapsed Lua5.3.3 5.95s Quasigo 5.13s (18% faster) Running spectral norm (n=1000) 89
90. 90 Running mandelbrot (size=1000) Interpreter Elapsed Lua5.3.3 2.40s Quasigo 1.57s (34% faster)
91. Lua vs quasigo 91 Interpreter Implemented in Target language Lua C Lua Quasigo Go Go
92. Creating interpreter in Go • Higher bytecode instruction dispatch cost • Harder to fine-tune runtime-related code without asm • Paying extra price to be Go GC friendly Overall, the raw performance can be ~20% slower for identically optimal interpreters of the same target language. 92 Cons:
93. Creating interpreter in Go • No need to use CGo to embed the interpreter • Getting a GC for free • Cheap interop with Go (in both directions) • Can use Go stdlib in the target language stdlib • Great benchmarking/testing/ profiling support 93 Pros:
94. But why is quasigo sometimes faster? • Statically typed values (therefore, instructions) • Go has true integer type (and unboxed scalars in general) • For array-like data, slices are better than Lua tables • Structs are better than Lua tables The raw performance is lower, but Go is “faster” than Lua. 94
95. Conclusions 1 Interpreters benefit from “unsafe” a lot
96. Conclusions 1 2 Interpreters written in Go can be quite fast if done right Interpreters benefit from “unsafe” a lot
97. Conclusions 1 2 3 Go is a good interpretation target language Interpreters written in Go can be quite fast if done right Interpreters benefit from “unsafe” a lot
98. Conclusions 1 2 3 4 You can embed Go instead of Lua in your Go apps Go is a good interpretation target language Interpreters written in Go can be quite fast if done right Interpreters benefit from “unsafe” a lot
99. Related resources SSA form alternative Efficient VM with JIT in Go 99
100. A new Go interpreter VK Tech Talk 2022 quasigo 100