Performance of LispZeroGo vs LispZero (C)

James Craig Burley edited this page Sep 8, 2018 · 1 revision

To get an idea of how the GoLang ("Go") language and runtime environment compares to those of the C language, the LispZero program (a single source file, to ease transpiling) was converted to Go.

This conversion process started by iterating over use of c2go, an automated C-to-Go transpiler, and modifying lisp-zero-single.c to be "digestible" by c2go, such that an increasingly correct result (lisp-zero-single.go) was obtained.

It continued by debugging and doing performance analysis on the result, sometimes in conjunction with similar activities on the original, and on the test-input generation and build-process mechanisms themselves.

Finally, remaining "unsafe" constructs were removed from the Go version, as well as the use of (hash) maps not present in the original and not needed. ("unsafe" constructs likely contributed to semi-random crashes and other strange behavior experienced during the overall conversion process; use of hash maps to perform mere int->bool conversions adversely impacted runtime performance.)

The result is a reasonably "native", if somewhat naive, Go port of the original C code, and its performance is excellent, sitting somewhat in between that of the unoptimized and optimized (-O3) C code, according to my circa-2017 MacBook Pro:

craig@pony:~/github/LispZero (master u=)$ xtime ./lisp-zero-single -q zero-test.lisp
u=0.42 s=0.00 r=0.43 cpu=99% kBresavg=0 kBresmax=1664 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=546 vol=0 invol=50 signals=0 swaps=0
  rc=0 ./lisp-zero-single -q zero-test.lisp
craig@pony:~/github/LispZero (master u=)$ xtime ./lisp-zero-single -q zero-test.lisp
u=0.41 s=0.00 r=0.41 cpu=99% kBresavg=0 kBresmax=1664 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=546 vol=0 invol=41 signals=0 swaps=0
  rc=0 ./lisp-zero-single -q zero-test.lisp
craig@pony:~/github/LispZero (master u=)$ xtime ./lisp-zero-single -q zero-test.lisp
u=0.42 s=0.00 r=0.42 cpu=99% kBresavg=0 kBresmax=1676 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=549 vol=0 invol=44 signals=0 swaps=0
  rc=0 ./lisp-zero-single -q zero-test.lisp
craig@pony:~/github/LispZero (master u=)$ xtime LispZeroGo -q zero-test.lisp
u=0.19 s=0.00 r=0.20 cpu=98% kBresavg=0 kBresmax=4152 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=1173 vol=0 invol=167 signals=0 swaps=0
  rc=0 LispZeroGo -q zero-test.lisp
craig@pony:~/github/LispZero (master u=)$ xtime LispZeroGo -q zero-test.lisp
u=0.19 s=0.00 r=0.19 cpu=98% kBresavg=0 kBresmax=4192 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=1183 vol=0 invol=136 signals=0 swaps=0
  rc=0 LispZeroGo -q zero-test.lisp
craig@pony:~/github/LispZero (master u=)$ xtime LispZeroGo -q zero-test.lisp
u=0.20 s=0.00 r=0.21 cpu=99% kBresavg=0 kBresmax=4180 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=1181 vol=0 invol=143 signals=0 swaps=0
  rc=0 LispZeroGo -q zero-test.lisp
craig@pony:~/github/LispZero (master u=)$ xtime ./lisp-zero-single-opt -q zero-test.lisp
u=0.01 s=0.00 r=0.02 cpu=90% kBresavg=0 kBresmax=1616 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=1 pfmin=533 vol=0 invol=29 signals=0 swaps=0
  rc=0 ./lisp-zero-single-opt -q zero-test.lisp
craig@pony:~/github/LispZero (master * u=)$ xtime ./lisp-zero-single-opt -q zero-test.lisp
u=0.01 s=0.00 r=0.02 cpu=90% kBresavg=0 kBresmax=1576 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=524 vol=0 invol=5 signals=0 swaps=0
  rc=0 ./lisp-zero-single-opt -q zero-test.lisp
craig@pony:~/github/LispZero (master * u=)$ xtime ./lisp-zero-single-opt -q zero-test.lisp
u=0.01 s=0.00 r=0.02 cpu=90% kBresavg=0 kBresmax=1576 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=524 vol=0 invol=6 signals=0 swaps=0
  rc=0 ./lisp-zero-single-opt -q zero-test.lisp
craig@pony:~/github/LispZero (master * u=)$

That's for the one validation file tested against a "gold" version during the build of the respective programs. While not itself designed as a performance test, it proved useful in finding and fixing performance issues in both, such as by replacing a simple list-walking algorithm for symbol lookup with a proper hash.

A suite of primitive performance tests, simple repeating cons invocations involving unique and repeated quoted symbols, offers insights into the baseline performance of Lisp readers in general. These tests were originally used on other implementations, including GNU Common Lisp, Guile, MIT-Scheme, GNU Emacs, Clojure, ClojureScript via Lumo, and Joker -- a Clojure interpreter written in Go, whose performance and project goals inspired the present effort.

Here are more results, involving one of these tests, containing one million (ultimately useless) cons and 2-item list-build operations:

craig@pony:~/github/LispZero/perftests (master u=)$ xtime ../lisp-zero-single -q 1M.out
u=6.69 s=0.17 r=6.89 cpu=99% kBresavg=0 kBresmax=350672 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=87798 vol=3 invol=1335 signals=0 swaps=0
  rc=0 ../lisp-zero-single -q 1M.out
craig@pony:~/github/LispZero/perftests (master u=)$ xtime ../lisp-zero-single -q 1M.out
u=6.69 s=0.16 r=6.86 cpu=99% kBresavg=0 kBresmax=350668 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=87797 vol=2 invol=825 signals=0 swaps=0
  rc=0 ../lisp-zero-single -q 1M.out
craig@pony:~/github/LispZero/perftests (master u=)$ xtime ../lisp-zero-single -q 1M.out
u=6.68 s=0.16 r=6.85 cpu=99% kBresavg=0 kBresmax=350660 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=87795 vol=0 invol=873 signals=0 swaps=0
  rc=0 ../lisp-zero-single -q 1M.out
craig@pony:~/github/LispZero/perftests (master u=)$ xtime LispZeroGo -q 1M.out
u=5.38 s=0.11 r=4.67 cpu=117% kBresavg=0 kBresmax=208092 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=52200 vol=0 invol=2128 signals=0 swaps=0
  rc=0 LispZeroGo -q 1M.out
craig@pony:~/github/LispZero/perftests (master u=)$ xtime LispZeroGo -q 1M.out
u=5.67 s=0.11 r=4.47 cpu=129% kBresavg=0 kBresmax=204956 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=51413 vol=0 invol=2645 signals=0 swaps=0
  rc=0 LispZeroGo -q 1M.out
craig@pony:~/github/LispZero/perftests (master u=)$ xtime LispZeroGo -q 1M.out
u=5.30 s=0.11 r=4.54 cpu=119% kBresavg=0 kBresmax=207848 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=52138 vol=0 invol=2166 signals=0 swaps=0
  rc=0 LispZeroGo -q 1M.out
craig@pony:~/github/LispZero/perftests (master u=)$ xtime ../lisp-zero-single-opt -q 1M.out
u=3.19 s=0.17 r=3.38 cpu=99% kBresavg=0 kBresmax=350676 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=87798 vol=0 invol=1194 signals=0 swaps=0
  rc=0 ../lisp-zero-single-opt -q 1M.out
craig@pony:~/github/LispZero/perftests (master * u=)$ xtime ../lisp-zero-single-opt -q 1M.out
u=3.04 s=0.15 r=3.20 cpu=99% kBresavg=0 kBresmax=350656 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=1 pfmin=87793 vol=0 invol=458 signals=0 swaps=0
  rc=0 ../lisp-zero-single-opt -q 1M.out
craig@pony:~/github/LispZero/perftests (master * u=)$ xtime ../lisp-zero-single-opt -q 1M.out
u=2.94 s=0.16 r=3.11 cpu=99% kBresavg=0 kBresmax=350660 kBundata=0 kBunstack=0 kBtext=0 Bpagsiz=4096 kBavgtot=0
  fsin=0 fsout=0 sockrcv=0 socksnt=0 pfmaj=0 pfmin=87795 vol=0 invol=505 signals=0 swaps=0
  rc=0 ../lisp-zero-single-opt -q 1M.out
craig@pony:~/github/LispZero/perftests (master * u=)$

Again, the Go program (which is optimized by default) is a little faster than the unoptimized C program, but somewhat slower than the optimized C program.

Note that the Go executable is reported to use less memory (kBresmax) than the C executables, above; whereas the zero-test.lisp input, shown previously, indicates the Go version using substantially more memory.

I suspect Go's runtime is GC'ing away the useless cons (low-level Lisp objects) sufficiently aggressively that it uses less memory than the C version, which makes no attempt whatsoever to free object memory (it neither includes a GC implementation nor any Lisp-object-related free() calls, which are made solely by the included map.c code and probably rarely actually hit).

By contrast, zero-test.lisp consists of code that builds up the basic Lisp language from "scratch" (the few constructs implemented by the C code) and then tests it in various ways.

That means much of what is read and evaluated is not eligible for GC. And what is eligible might not actually be GC'ed, as the test case is short and small enough that GC might not be triggered before the program exits.

Further, the C version uses a union for the cdr field of each cons (and all the Lisp objects that are implemented are cons objects, in essence), with the car field used to tell the difference between an atom or symbol, a compiled (C-implemented) function, and a true cons (in the classic Lisp sense).

But while the transpiled Go code also effectively used a union, persistent problems appearing with large inputs suggested the removal of all unsafe constructs would be necessary, so the union was replaced with a struct (and the problems went away).

Use of a struct, instead of union, of three pointer-sized (8-byte) fields, probably explains much, if not all, of the additional memory used by the Go version when reading zero-test.lisp.

Thanks to Elliot Chance and supporters for creating c2go, and to the many developers of the Go language, for creating useful, performant, and enjoyable software!

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.