[HN Gopher] Optimizing GoAWK with a bytecode compiler and virtua...
___________________________________________________________________
Optimizing GoAWK with a bytecode compiler and virtual machine
Author : benhoyt
Score : 87 points
Date : 2022-02-03 09:23 UTC (13 hours ago)
(HTM) web link (benhoyt.com)
(TXT) w3m dump (benhoyt.com)
| silasdavis wrote:
| 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 wrote:
| 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 wrote:
| 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.
| deckarep wrote:
| 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.
| cb321 wrote:
| 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
| pjmlp wrote:
| 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.
| cb321 wrote:
| 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). :-)
| benhoyt wrote:
| 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?
| cb321 wrote:
| > 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... :-) }
| benhoyt wrote:
| 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.
| cb321 wrote:
| 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"
| cb321 wrote:
| 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. }
| cb321 wrote:
| 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. }
| cb321 wrote:
| 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.
| ogogmad wrote:
| 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
| mihaitodor wrote:
| Really handy when running AWK scripts via https://benthos.dev :)
| eatonphil wrote:
| 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.
| v3gas wrote:
| Great post!
___________________________________________________________________
(page generated 2022-02-03 23:03 UTC)