3 ms·

The binary search in a case statement is annoying for stack machines like this. How would implementing your own jump table as a hashmap to functions perform her

The binary search in a case statement is annoying for stack machines like this. How would implementing your own jump table as a hashmap to functions perform here vs a case statement? I'm guessing the function calls make it a lot slower as you mention in the comparison with the tree walking.

benhoyt 5y ago
Yeah, I discuss something similar in the article, except I use an array of functions (search for "array of functions"), which is significantly faster than hashing and a hash table lookup. It was very slightly faster than switch, but I decided not to use it: > This only gave me a 1-2% speed increase on GoAWK’s microbenchmarks (see results and code). In the end I decided I’d rather stick with the simpler switch code and find other ways to improve the speed. And when the Go compiler supports jump tables for switch, I’ll get a 10% improvement by doing nothing!
- jonstewart 5y ago
  I wrote a niche grep library (in C++) that uses the byte code approach. I’m not a Go programmer, and am gobsmacked about how switch works—the jump table switch in C/C++ is a huge part of the benefit of a byte code VM. Also, my guess is that you may see a disproportionate performance increase (>18%) between the AST interpreter and the byte code backend with larger AWK programs, due to the latter’s better cache characteristics. YMMV with computed goto. It was an important technique but modern processors with their crazy branch predictors can yield disappointing results today. It didn’t help my VM. I would -not- write your own regex library. Doesn’t RE2 have a Go port? Or maybe something else? It’s a world of pain. Given AWK’s usage as a string processor, I’d sell out hard for string processing. Maybe an opcode specifically for “hardcoded string op” with a secondary operand denoting which type of string op that you dispatch to through an array? Then just load that up with beefy functions and the VM is used to glue together the string operations. Also, not sure how possible this is in Go, but if it allows for unions, packed structs, and bitfields, you can get some benefit from having 32 bit instructions where the opcodes are a byte and then have the other three bytes available for operands, and additionally allowing for some instructions to be multiword (so a jump could have a second word following that’s the target address, for a full 32 bits). Condensing your byte code without incurring other costs (bit access, compression) is key to improving your L1 cache rate. A cache line can then fit 16 instructions. Preallocating as much memory as possible is helpful, too. Even if there are necessary conditionals for growing arrays and whatnot, they’re likely to be false and thus handled by branch prediction with no cost.

benhoyt 5y ago

Yeah, I discuss something similar in the article, except I use an array of functions (search for "array of functions"), which is significantly faster than hashing and a hash table lookup. It was very slightly faster than switch, but I decided not to use it: > This only gave me a 1-2% speed increase on GoAWK’s microbenchmarks (see results and code). In the end I decided I’d rather stick with the simpler switch code and find other ways to improve the speed. And when the Go compiler supports jump tables for switch, I’ll get a 10% improvement by doing nothing!

jonstewart 5y ago
I wrote a niche grep library (in C++) that uses the byte code approach. I’m not a Go programmer, and am gobsmacked about how switch works—the jump table switch in C/C++ is a huge part of the benefit of a byte code VM. Also, my guess is that you may see a disproportionate performance increase (>18%) between the AST interpreter and the byte code backend with larger AWK programs, due to the latter’s better cache characteristics. YMMV with computed goto. It was an important technique but modern processors with their crazy branch predictors can yield disappointing results today. It didn’t help my VM. I would -not- write your own regex library. Doesn’t RE2 have a Go port? Or maybe something else? It’s a world of pain. Given AWK’s usage as a string processor, I’d sell out hard for string processing. Maybe an opcode specifically for “hardcoded string op” with a secondary operand denoting which type of string op that you dispatch to through an array? Then just load that up with beefy functions and the VM is used to glue together the string operations. Also, not sure how possible this is in Go, but if it allows for unions, packed structs, and bitfields, you can get some benefit from having 32 bit instructions where the opcodes are a byte and then have the other three bytes available for operands, and additionally allowing for some instructions to be multiword (so a jump could have a second word following that’s the target address, for a full 32 bits). Condensing your byte code without incurring other costs (bit access, compression) is key to improving your L1 cache rate. A cache line can then fit 16 instructions. Preallocating as much memory as possible is helpful, too. Even if there are necessary conditionals for growing arrays and whatnot, they’re likely to be false and thus handled by branch prediction with no cost.