hayley-patton

gencgc uses software protection on some but not all architectures -- I recall x86-64 and MIPS but not ARM though. On x86-64 with SBCL 2.3.8 for example:

    * (disassemble #'(setf svref))
    ; disassembly for (SETF SVREF)
    ; Size: 39 bytes. Origin: #x5349B00D                          ; (SETF SVREF)
    ; 0D:       483B77F9         CMP RSI, [RDI-7]
    ; 11:       731D             JAE L0
    ; 13:       488D44B701       LEA RAX, [RDI+RSI*4+1]
                                 ↓ card marking here
    ; 18:       48C1E80A         SHR RAX, 10
    ; 1C:       25FFFF0F00       AND EAX, 1048575
    ; 21:       41C6040400       MOV BYTE PTR [R12+RAX], 0
                                 ↓ pointer store here
    ; 26:       488954B701       MOV [RDI+RSI*4+1], RDX
    ; 2B:       C9               LEAVE
    ; 2C:       F8               CLC
    ; 2D:       C3               RET
    ; 2E:       CC10             INT3 16                          ; Invalid argument count trap
    ; 30: L0:   CC24             INT3 36                          ; INVALID-VECTOR-INDEX-ERROR
    ; 32:       1C               BYTE #X1C                        ; RDI(d)
    ; 33:       19               BYTE #X19                        ; RSI(a)

SBCL now uses the "write-bitmap"/"card marking" scheme on some platforms, which is a tiny bit faster (1-2% mentioned on sbcl-devel). More interesting is that doing the touch-detection in software allows for finer grained precision (e.g. #+mark-region-gc uses 128 byte cards) than hardware (e.g. 4kiB pages on x86-64, 16kiB on M1) which can drastically affect scavenging time [0]. The precision is also really nice for non-moving generational schemes: if old and new objects exist on the same card, writes to new objects (which are more common too!) will cause old objects to needlessly be scanned by GC, which is called "card pollution" by Demers et al [1], so reducing the card size reduces the likelihood of that happening.

[0] https://tschatzl.github.io/2022/02/15/card-table-card-size.h...

[1] https://dl.acm.org/doi/pdf/10.1145/96709.96735

You probably want to read and not write, as writing will cause a lot of cache ping-pong and slow the mutator down when it doesn't SEGV on the dummy access <https://users.cecs.anu.edu.au/~steveb/pubs/papers/yieldpoint...>

Gladly!

https://github.com/robert-strandh/SICL (which I wrote a decent chunk of the compiler backend of.)

Trivia pattern matches (a la ML, probably weaker than tree regular expressions) on data structures/trees, PPCRE regular expressions on strings.

TAL does use garbage collection; verifying that a GC behaves is another can of worms.

Compile to typed assembly language?

https://www.cs.cornell.edu/talc/

> Compiled programs have some disadvantages for modern software development. Every time a developer makes a change, the compiler must be invoked to recreate the executable file.

Executable files are inessential to compilation.

The mark-region GC has worse throughput with really large heaps compared to the live set (as the cost model doesn't work out), and always had* worse latency on Kandria. But generally throughput with more than two cores tends to be better.

* I expect latency to be better with compacting, but I haven't benchmarked, so I haven't a clue.

There are still pauses, but the pauses are faster by using multiple cores to collect, which is nice for both throughput- and latency-sensitive apps. No-pause ("on-the-fly") collectors exist, but sufficiently-short pause ("concurrent") collectors still do wonders with sub-millisecond latency.

It should be pretty portable, porting is just a matter of time and interest. The main thing is that the compiler needs to use a (more precise, lower overhead) software write barrier rather than using the (coarser, slower) hardware write barrier which was around the longest. I also have to wonder how well the bit-scanning algorithms fare on big-endian, or is that taking "all CPU architectures" too far?

I have yet to benchmark it again; my setup was sloppy as I had to run the same part of the game over and over, because record/replay didn't work. (Nor do I have the time and energy now; have to survive the last semester of university now.) But I suspect it should help, by reducing the sweeping and scavenging times which were pretty bad.

I'm not sure I agree with the comment about "up to the task for real-time games", but maybe my standards are low for video games, and I have an abnormally fast machine and am likely biased there too.

Please note that the paper was published before I implemented incremental compaction; the GC in SBCL 2.3.8 can compact.

CakeML is a formally verified implementation of a subset of Standard ML which generates native code. Not sure about what it optimises though.

It does: "Nevertheless, implicit mutation of heap objects is rife at runtime, thanks to the implementation of lazy evaluation (which, we admit, is somewhat ironic)." says <https://www.microsoft.com/en-us/research/wp-content/uploads/...>

Drepper's "What every programmer should know about memory", though you mightn't find it all interesting. https://gwern.net/doc/cs/hardware/2007-drepper.pdf

For what it's worth, compaction with my mark-region GC for SBCL follows "An algorithm for parallel incremental compaction" <https://dl.acm.org/doi/10.1145/773039.512442> which instead logs all references to the objects we want to move while tracing, rather than using forwarding pointers. Well, not quite - the runtime likes to eagerly copy lists to get them contiguous after copying, and so we still use forwarding pointers to avoid copying cons cells twice.

(The mutator also won't ever see forwarding pointers regardless, if you have a STW GC. And if that GC works.)

> That's a fun benchmark to have. Seems like gencgc is better than the new GC anyway wrt pause times?

At that time the GC didn't compact, and so much time was wasted scavenging and sweeping the old objects. Old objects aren't contiguous due to not moving objects, though we try to avoid reading from the heap; we only twiddle metadata tables when sweeping and only read objects that we must scan for old->new references while scavenging. Here that wasn't sufficient:

> As a result, scavenging took 2.9 milliseconds on average, tracing took 1.9 milliseconds, and sweeping took 1.6 milliseconds.

Ideally scavenging and sweeping would take much less time than tracing. I think it should behave better now with compaction, but haven't benchmarked; and my approach to benchmarking Kandria is pretty sloppy in any case.

> Having a bump-pointer arena for this which is reset per-frame would probably be quite nice.

Indeed SBCL has support for arenas (though AIUI no stable user-facing interface at the moment), but it still takes some effort to work out what goes in the arena, and the current interface in SBCL also requires all libraries to know about arenas which isn't great for retrofitting.

> The Acknowledgements section is crazy haha, with mentions such as Cliff Click (OG Hotspot JIT compiler architect) and Larry Masinter (Xerox PARC Interlisp) along with the nice SBCL and Kandria devs.

I can't take much of the blame for much of the design; much of it was collaborated in the #lispcafe channel on Libera, which ostensibly is the "off topic" channel. Well. Also worth mentioning that Cliff Click also worked on parallel/concurrent GC and other parallel algorithms, so he was most helpful with interpreting the performance of this GC.

> Lisp machines are long gone.

They also had assembly and microcode (and Maclisp got scoping wrong until CL, anyway). So those weren't much better if you want to measure "purity".

> Tell people to implement a Lisp down on the imperative language of the machine. ...

Somehow there is no end to the difficulty of mapping an imperative language to another, as evidenced by the size of LLVM. One picks one's poison, I guess.

That's still a fine GC. Although ridiculous, consider performing a tracing GC after every assignment - that system would provide the same immediacy (or better, due to cycle detection).

Rc is reference counting, which is garbage collection, although not tracing garbage collection. Though optimizing RC throughput tends to involve deferral (and optimising tracing latency tends to involve more upfront work on the mutator) <https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-...>

In your defense, I recall Self did use unaligned traps to deal with dispatching on heap object/immediate, when immediates didn't usually appear at a call site.

> so car and cdr are implemented with one instruction and are safe (that is, throw an exception if applied to something they don't work on) even in code compiled at (safety 0).

It is? By default x86 will happily do unaligned accesses, and I'm pretty sure SBCL doesn't change that. Not sure about other instruction sets.

SBCL also uses double-word alignment and 4-bit tags, so you could CDR (expecting lowtag #b0111) a structure object (lowtag #b1111).

One can re-align when accessing; this is how SBCL e.g. handles tagging. e.g. the first slot would be accessed by MOV RAX, [RBX - 1].

JVM, Python and WASM are more like the SECD [0], not a plain stack machine, by use of a local environment. BEAM (for Erlang) is a register machine. And the JVM and WASM get compiled to code for register machines, with the VM stack not present (in a concrete form) at runtime.

> a stack-based VM is relatively easy to optimise for a register CPU.

You get SSA for almost free (just phi the stacks at control joins), but after making SSA everything is the same regardless of stack- or register- VM.

[0] https://academic.oup.com/comjnl/article/6/4/308/375725?login...

> which explains why Robert Fripp played guitar with The Damned while King Crimson was on hiatus

"The Stranglers and Friends" is an excellent live album of punks and prog figures (including Fripp) playing with the Stranglers while Hugh Cornwell was in jail. Though the Stranglers themselves were quite sophisticated, with Dave Greenfield (RIP) playing keyboards and Jet Black (also RIP) having been a jazz drummer beforehand.

Fripp's debut solo album Exposure, Daryl Hall's Sacred Songs and Peter Gabriel II constituted a sort of trilogy of...interesting rock.

Edit: Sandinista! by The Clash and the first four Simple Minds albums are also musically interesting "punk" albums.

The author notes Fripp disbanding King Crimson in 1974, but doesn't mention the 80s reformation at all (with Discipline, Beat and Three of a Perfect Pair). Or the 90s ("double trio") reformation, or the 00s ("double duo") reformation, or the 10s ("seven-headed beast") reformation.

Though Tony Levin hints that it's over now in <https://tonylevin.com/road-diaries/king-crimson-2021-tour-pa...>.

Mine has a dodgy power connection somehow, and will refuse to turn on most of the time (depending on star alignment and where it was plugged in). Maybe if I could remove the power cable, I could check if that's the issue.

Okay, I guess anything's removable if you try hard enough.

Whyever the dangling parens? The OpenGOAL decompilation has many dangling parens too - they're a rather odd sight when moving around S-expressions (dodging the issue of if it's "Lisp" or not). I guess WAST and SMT-LIB producers are a mixed bag too.

But I'm my own worst enemy, and blocking the event loop is unpleasant even when I do it myself. Once I had to pass compute-intensive tasks (hashing some data, which took long enough to matter) to a thread pool, to not hurt latency for other tasks in the event loop.

> I’d say that just awaiting on PMT task completion is much more convenient that setting up locking primitives.

Don't use the primitives then - write e.g. a parbegin/parallel-map atop thread primitives, and use that.