godotengine
GDScript: Optimize `match`
- Closes #63719.
- Closes #75682.
Optimize match with jump tables whenever possible. I want to use two kinds of tables:
OPCODE_JUMP_TABLE_RANGE. Can be used for continuous (or with a little sparsity) ranges of integers (such as enums). For example, from 0 to 10, or from 2 to 12. Instead of doing N comparisons (in the worst case), the jump address is calculated using the value, offset, and size.OPCODE_JUMP_TABLE_BSEARCH. Can be used to binary search in a constant array sorted at compilation. Suitable when the value is not an integer or the range is very sparse.
When using variable patterns, destructuring (and match guards in the future), the old bytecode will be preserved (or the branches will be divided into subgroups in which optimizations can be performed).
TODO
Parser
- [x] (Bonus) Allow
passinmatch. - [x] Add warning
REDUNDANT_PATTERN(multiple patterns with a wildcard pattern). - [ ] Add the ability to ignore warnings in
match.
Analyzer
- [x] Add error on type mismatch for typed variables. Reduces the impact of the non-obvious comparison difference from
==operator described in #74462. - [ ] Add warning
DUPLICATE_PATTERN.
Codegen, VM, disassembler
- [x] Add opcodes
OPCODE_JUMP_TABLE_RANGEandOPCODE_JUMP_TABLE_BSEARCH.
Compiler
- [ ] Do not perform unnecessary operations if the type is known.
- [ ] Optimize
matchwith jump tables. - [ ] Remove unreachable branches?
Miscellaneous
- [ ] Add tests.
- [ ] Make benchmarks: PR vs master vs
if-elif-else.
My project uses a lot of match in performance-critical sections where GDScript is a bottleneck, so it would be nice to know if I can expect a free speedup in them anytime soon. Is this PR abandoned?
Is this PR abandoned?
As far as I remember, I stopped because of #58878. I implemented a workaround with SafeVariantSort, but this did not seem elegant enough to me, since I had to create a separate table variant_vector_constants. Also, the compiler part is unfinished, but I think it is doable.