Optimizing GoAWK with a bytecode compiler and virtual machine | Hacker News Reader

Optimizing GoAWK with a bytecode compiler and virtual machine

benhoyt.com

102 pointsbenhoyt23 comments

Instead of interpreters, if one has less of a "must be a full featured prog.lang" mentality and a fast compiler like Go or Nim [1] (or is willing to wait, for slow optimizing compiles to apply against big data sets) then an end-to-end simpler design for "one-liners" (or similarly simple programs) is the whole program generator. Maybe "big IFs", but also maybe not.

To back up my simplicity claim, consider rp [2] -- like 60 non-comment/import/signature lines of code for the generator. Generated programs are even smaller. But, you can deploy gcc or clang or whatever against them and make fast libraries in the host language.

Why, if you are willing to write those little generation command options in C99 then you can compile the harness with tcc [3] in about 1 millisecond which is faster than most interpreter start-up times - byte code or otherwise - and can link against gcc -O3 (or whatever) helper libraries.

Anyway, I only write this because in my experience few people realize how much development cost they buy into when then insist on a full featured prog.lang, not to criticize Ben's work. You also make users learn quirks of a new language instead of the quirks of a "harness" which may be fewer|easier. (EDIT: Awk is fairly well established, of course.)

[1] https://forum.nim-lang.org/

[2] https://github.com/c-blake/cligen/blob/master/examples/rp.ni...

[3] https://repo.or.cz/w/tinycc.git

rp looks like a very interesting and clever approach. I'll have to take a closer look. Is https://github.com/c-blake/cligen/blob/master/examples/rp.ni... the extent of rp's documentation?

> the extent of rp's "documentation"

Unfortunately, yes. My hope was that it would be compact/small enough to be "quasi-self-documenting" to the likes of "compiler writer types". Probably not to ordinary users. (The extra asterisks are to get nice ANSI SGR escape highlighting and/or rST markup out of the auto-documentation system.) {EDIT2: Also, I would be happy to add some rp.README if you want to contribute one. You seem a great explainer. }

FWIW, I think of this kind of generation as part of the Go mentality more generally, but I am not a Go user/in that community. So, maybe that is speaking out of turn.

I also have a C version of this that I call `crp` I could provide if anyone wants (and yes, short for "crap"). C is a kind of higher ceremony language for such things { EDIT1: but even more established than awk... :-) }

Code generation is used quite a bit in Go, though I haven't seen it used quite like this before. Now you've got me thinking what an rp-like tool would look like in Go. I think the error handling and statement vs expression distinction might get in the way a bit, but perhaps you could overcome that with helper functions.

I think the design is just about 100X easier for mere mortals { in bogus "effortmeters" ;-) }, but it is absolutely true that some backend languages are more suited than others. It is also true that having real optimizing compilers (in whatever lang) as backends will always result in faster running programs (if data is big enough that amortizing optimizer costs is worth it). {EDIT: i.e. "so, trade-offs, costs, YMMV, etc., etc. }

I'll go ahead and post crp.nim here. pjmlp rightly (and often here) observes that people become very trapped in their thinking about PLs. It perhaps helps to emphasize that the whole program generator need not be in the same PL as the generated program. But for the record, I do not think C is a compiled language very well suited to these one-liner tasks. There are probably better ones than Nim, too. My point is mostly about system design. One can probably say that the best backend is probably syntactically non-noisy and easy for whoever your users are. If you are your only user, go nuts some afternoon. :-)

    import std/[strutils,os,hashes,sets],cligen/[osUt,mslice] #% exec* mdOpen split
    from cligen/parseopt3 import optionNormalize

    proc toDef(fields, delim, genF: string): string =
      result.add "char const * const rpNmFields = \"" & fields & "\";\n"
      let sep = initSep(delim)
      let row = fields.toMSlice
      var s: seq[MSlice]
      var nms: HashSet[string]
      sep.split(row, s) # No maxSplit - define every field; Could infer it from the
      for j, f in s:    #..highest referenced field with a `where` & `stmts` parse.
        let nm = optionNormalize(genF % [ $f ])   # Prevent duplicate def errors..
        if nm notin nms:                          #..and warn users about collision.
          result.add "int const " & nm & " = " & $j & ";\n"
          nms.incl nm
        else:
          stderr.write "crp: WARNING: ", nm, " collides with earlier field\n"

    proc crp(prelude="", begin="", where="1", stmts:seq[string], epilog="",
             fields="", genF="$1", comp="", run=true, args="", outp="/tmp/crpXXX",
             input="/dev/stdin", delim=" \t", uncheck=false, maxSplit=0): int =
      ## Gen+Run *prelude*,*fields*,*begin*,*where*,*stmts*,*epilog* row processor
      ## against *input*.  Defined within *where* & every *stmt* are:
      ##   *s[idx]* & *row* => C strings, *i(idx)* => int64, *f(idx)* => double.
      ##   *nf* & *nr* (like *AWK*);  NOTE: *idx* is **0-origin**.
      ## A generated program is left at *outp*.c, easily copied for "utilitizing".
      ## If you know *AWK* & C, you can learn *crp* PRONTO.  Examples (need data):
      ##   **crp 'printf("%s %s\\n", s[1], s[0]);'**         # Swap field order
      ##   **crp -w'nr % 100==0' 'printf("%s\\n", row);'**   # Prn each 100th row
      ##   **crp -b'int t=0' t+=nf -e'printf("%d\\n", t)'**  # Prn total field count
      ##   **crp -b'int t=0' -w'i(0)>0' 't+=i(0)' -e'printf("%d\\n", t)'** # Total>0
      ##   **crp 'float x=f(0)' 'printf("%g\\n", (1+x)/x)'** # cache field 0 parse
      ##   **crp -d, -fa,b,c 'printf("%s %g\\n",s[a],f(b)+i(c))'**  # named fields
      ## Add niceties (eg. `#include "mystuff.h"`) to *prelude* in ~/.config/crp.
      let fields = if fields.len == 0: fields else: toDef(fields, delim, genF)
      let check  = if fields.len == 0: "    " elif not uncheck: """
        if (nr == 0) {
          if (strcmp(row, rpNmFields) == 0) {
            nr++; continue; // {fields} {!uncheck}
          } else {
        exit(2);
      }
      while ((rpNmRead = getline(&row, &rpNmAlloc, rpNmFile)) != -1) {
        row[rpNmRead - 1] = '\0';       // chop newline
    ${6}s = rpNmSplit(s, &rpNmAlloc, row, "$3", $7, &nf); // {delim,maxSplit}
        if ($8) { // {where} auto ()s?
    """ % [prelude, fields, delim, indent(begin, 2), input, check, $maxSplit, where]
      for i, stmt in stmts:
        program.add "      " & stmt & "; // {stmt" & $i & "}\n"
      if stmts.len == 0:
        program.add "      /**/;\n"
      program.add "    }\n    nr++;\n  }\n"
      program.add indent(epilog, 2)
      program.add "; // {epilogue}\n}\n"
      let mode = if run: "-run" else: ""
      let args = if args.len > 0: args else: "-I$HOME/s -O"
      let digs = count(outp, 'X')
      let hsh  = toHex(program.hash and ((1 shl 16*digs) - 1), digs)
      let outp = if digs > 0: outp[0 ..< ^digs] & hsh else: outp
      let comp = if comp.len > 0: comp else: "tcc $1 $2 -o$3 $4" % [
                                             mode, args, outp, outp & ".c"]
      let f = mkdirOpen(outp & ".c", fmWrite)
      f.write program
      f.close
      execShellCmd(comp & (if run: " < " & input else: ""))

    when isMainModule:
      import cligen; include cligen/mergeCfgEnv
      dispatch crp,help={"prelude" : "Nim code for prelude/imports section",
                         "begin"   : "Nim code for begin/pre-loop section",
                         "where"   : "Nim code for row inclusion",
                         "stmts"   : "Nim stmts to run under `where`",
                         "epilog"  : "Nim code for epilog/end loop section",
                         "fields"  : "`delim`-sep field names (match row0)",
                         "genF"    : "make field names from this fmt; eg c$1",
                         "comp"    : "\"\" => tcc {if run: \"-run\"} {args}",
                         "run"     : "Run at once using tcc -run .. < input",
                         "args"    : "\"\" => -I$HOME/s -O",
                         "outp"    : "output executable; .c NOT REMOVED",
                         "input"   : "path to read as input",
                         "delim"   : "inp delim chars for strtok",
                         "uncheck" : "do not check&skip header row vs fields",
                         "maxSplit": "max split; 0 => unbounded"}, cmdName="crp"

Oh, btw, all that "Nim code for XYZ" in the crp,help={} section at the end should be "C code". Oops. { Sorry. I mostly just ported the rp.nim to crp.nim to time how fast tcc could make a pure C backend run and didn't change that part. }

I should have said, those help strings at the very bottom of the file are also part of the "documentation" to the extent the variable names in the proc signature are not self explanatory.

The problem with that approach is that it tends to create the false belief on developers inexperienced with compiler development that C is a must have for doing compilers.

Then one needs to go around explaining, that no, some one programming language could have been chosen and it was just a matter of convinience why C was picked up.

This is fair, but argument in favor of the approach is that it is so simple it really could be done with any backend language {EDIT: by a 1st year CS student in an afternoon, um, maybe.. ;-)}..Go, Pascal, Ada, even slow running ones like Python/Perl/etc. or slow compiling ones like Rust. So, were the design to be more common people might not be so prone to make that assumption. OTOH, getting people to not make wrong assumptions is an eternal challenge. :-)

My own view is that awk was done more or less for these one-liner/simple purposes but by people like Aho for whom full featured languages are barely more thinking than my 60 lines (in either doing the parser or using). :-)

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.

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!

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.

I was looking at this earlier and noticed the tree walking interpreter. Nice work with the upgrade!

For folks not familiar, basically every major interpreter today compiles to bytecode and runs on a bytecode VM. People will squabble about the term "compiler" saying it only applies to generating binary files directly but I still think it's fun almost every major interpreter is a compiler in the general sense.

The only major interpreters that do tree walking AFAIK are shells like bash.

Awesome blog post Ben! Question: how did you come up with your list of opcodes?

I ask because while some opcodes are obviously needed others as not so obvious and coming up with a balanced instruction set is somewhat difficult design problem.

Good question. A bit of experience, some guesswork, and a lot of testing and benchmarking along the way. I separated out global and local opcodes originally because I wanted individual variable accesses to be fast (why do at runtime what you can do at compile time). As I mention in the article, originally I had all the builtin functions as separate opcodes, but that was slower due to the sheer number of opcodes and Go's current binary tree approach to "switch". I also used Go's profiling tools a bunch to see where the hotspots where. I'm sure there's significant room for improvement, but it's hard, because sometimes when you improve one benchmark, something else suffers.

What tools did you use for timing and benchmarking beyond the tools included in the go distribution?

Just the Go benchmarking tools built into "go test", as well as a couple of scripts of my own just using "time ./goawk 'BEGIN { ... test script ... }'" and that kind of thing. Nothing fancy!

Is it possible to write an interpreter for this bytecode language using RPython, so as to get a JIT speedup?

I think if you write an interpreter in RPython, and annotate it with some directives, you can get a JIT compiler for free. But it wouldn't be "GoAWK" anymore!

https://rpython.readthedocs.io/en/latest/examples.html

Really handy when running AWK scripts via https://benthos.dev :)

Looks like much of the effort is working around basic Go language limitations. Coding the virtual machine interpreter in Go seems like a mistake.

Compiling straight to Go, and then compiling that the normal way, seems like it would do better, and be simpler. Assuming you really wanted to keep it all in Go.

Go isn't the most efficient language for these sorts of things, but it's also not bad (and Go itself is not really the bottleneck for real-world AWK scripts). That said, GoAWK is useful mainly when you want to use AWK scripts in a Go program (the Benthos stream processor does this: https://www.benthos.dev/docs/components/processors/awk/).

I also did a project recently, creatively called AWKGo, that compiles (a subset of) AWK scripts to Go source code: https://benhoyt.com/writings/awkgo/

Great post!

Reply on news.ycombinator.com