Yegor Wienski wienski

(Originally written as a reply to an HN submission of this article: https://www.cs.virginia.edu/~lat7h/blog/posts/434.html)

There's a simple recipe for arithmetically encoding recursive algebraic data types (in the functional programming sense) which is related to this.

What you might have seen is Goedel numbering where a finite sequence of natural numbers a_0, a_1, ..., a_n (where n isn't fixed but can vary per sequence) is mapped bijectively onto p_0^a_0 a_1^p_1 ... a_n^p_n where p_0, p_1, ... is an enumeration of the primes.

However, if you want to represent trees instead of sequences, you have a better, simpler option. The key is the existence of a bijective pairing function between N^2 and N, which you can write as <m, n> for m, n in N.

You have a lot of choices for how to construct the pairing function. But a curious fact is that there is essentially one polynomial pairing function and it's the one you saw in class when you learned that the rationals are countable: https://en.wikipedia.org/wiki/Fuet

Garbage collection with zero cost at non-GC time

Every once in a while I investigate low-level backend options for PL-s, although so far I haven't actually written any such backend for my projects. Recently I've been looking at precise garbage collection in popular backends, and I've been (like on previous occasions) annoyed by limitations and compromises.

I was compelled to think about a system which accommodates precise relocating GC as much as possible. In one extreme configuration, described in this note, there

	// We have five kinds of nodes: literal, negate, not, add, xor.
	// In this case we only need 3 bits for the tag but you can use as many as you need.

	enum Tag {
	LIT,
	NEG,
	NOT,
	ADD,
	XOR,
	};

	// Length-segregated string tables for length < 16. You use a separate overflow table for length >= 16.
	// By segregating like this you can pack the string data in the table itself tightly without any padding. The datapath
	// is uniform and efficient for all lengths < 16 by using unaligned 16-byte SIMD loads/compares and masking off the length prefix.

	// One of the benefits of packing string data tightly for each length table is that you can afford to reduce the load factor
	// on shorter length tables without hurting space utilization too much. This can push hole-in-one rates into the 95% range without
	// too much of a negative impact on cache utilization.

	// Since get() takes a vector register as an argument with the key, you want to shape the upstream code so the string to be queried
	// is naturally in a vector. For example, in an optimized identifier lexer you should already have a SIMD fast path for length < 16

	#include <assert.h>

	#include <tuple>
	#include <vector>
	#include <string>

	typedef uint32_t Str;

	std::vector<const char*> strs;

	INLINE
	u32 index(Ref r) {
	return r >> 4;
	}

	INLINE
	u32 tag(Ref r) {
	return r & 15;
	}

	// This can grow a Robin Hood linear probing hash table near word-at-a-time memcpy speeds. If you're confused why I use 'keys'
	// to describe the hash values, it's because my favorite perspective on Robin Hood (which I learned from Paul Khuong)
	// is that it's just a sorted gap array which is MSB bucketed and insertion sorted per chain:
	// https://pvk.ca/Blog/2019/09/29/a-couple-of-probabilistic-worst-case-bounds-for-robin-hood-linear-probing/
	// The more widely known "max displacement" picture of Robin Hood hashing also has strengths since the max displacement
	// can be stored very compactly. You can see a micro-optimized example of that here for small tables where the max displacement
	// can fit in 4 bits: Sub-nanosecond Searches Using Vector Instructions, https://www.youtube.com/watch?v=paxIkKBzqBU
	void grow(Table *table) {
	u64 exp = 64 - table->shift;
	// We grow the table downward in place by a factor of 2 (not counting the overflow area at table->end).

	# I happened to be looking at some of Cranelift's code, and I noticed that their constant-time dominates()
	# check was using a somewhat more ad-hoc version of a hidden gem from the data structures literature called the
	# parenthesis representation for trees. As far as I know, this was invented by Jacobson in his 1989 paper
	# Space-Efficient Static Trees and Graphs. I first learned about it from the slightly later paper by Munro and Raman
	# called Succinct Representations of Balanced Parentheses and Static Trees. I figured I'd give it an extremely
	# quick intro and then show how it leads to a (slightly better) version of Cranelift's algorithm.
	#
	# This parenthesis representation of trees is surprisingly versatile, but its most striking feature is that
	# it lets us query the ancestor relationship between two nodes in a tree in constant time, with a few instructions.
	# And the idea is extremely simple and intuitive if you just draw the right kind of picture.