Skip to content

Instantly share code, notes, and snippets.

View algebraic_data_type_numeral_encoding.md

(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

View ast_intern.c
#include <assert.h>
#include <tuple>
#include <vector>
#include <string>
typedef uint32_t Str;
std::vector<const char*> strs;
View assert_default_params.c
void assert_func(int cond, const char *msg) {
if (!cond) {
fprintf(stderr, "assert failed: %s\n", msg);
abort();
}
}
#define assert_helper(x, y, ...) assert_func(x, y)
#define assert(x, ...) assert_helper((x), ## __VA_ARGS__, #x)
View segregated_tables.c
// 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
View ast_tagged_index.c
// 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,
};
View simd_bucket_hash_discrim.c
// The two sweetspots are 8-bit and 4-bit tags. In the latter case you can fit 14 32-bit keys in
// a cacheline-sized bucket and still have one leftover byte for metadata.
// As for how to choose tags for particular problems, Google's Swiss table and Facebook's F14 table
// both use hash bits that weren't used for the bucket indexing. This is ideal from an entropy perspective
// but it can be better to use some particular feature of the key that you'd otherwise check against anyway.
// For example, for 32-bit keys (with a usable sentinel value) you could use the 8 low bits as the tag
// while storing the remaining 24 bits in the rest of the bucket; that fits 16 keys per bucket. Or if the keys
// are strings you could store the length as the discriminator: with an 8-bit tag, 0 means an empty slot,
// 1..254 means a string of that length, and 255 means a string of length 255 or longer. With a 4-bit tag
View mark_coalesce_gc.c
// This is another take on the mark-compact collector from https://gist.github.com/pervognsen/7fe51bef8977cb249ac4c6f830f818a5
// To avoid having to do global compaction, our object indices will have two parts: a block index and a block offset.
// Within a block we have the same linear older-to-newer ordering by offset. But now blocks are allowed to have different ages.
// The block ages are defined by their position in a linked list: There's oldest_block and newest_block indices and then
// previous_block[block_index] for each block. This enables newest-to-oldest block iteration and the linked-list structure
// means that we can free an empty block by unlinking it. When a block is reused, it becomes the newest_block. Now, instead
// of only compacting within a block we will actually be coalescing across an age range of blocks. By doing so, we will usually
// be able to empty out entire blocks from the newer part of that age range, so they can be reused. This should have very similar
// performance characteri
View linear_gc.c
// Linear-scan mark-compact collector for causal data structures, i.e. the reference graph is acyclic and the objects
// are ordered by age in the heap (which happens if you use a linear allocator) so they are automatically topologically sorted.
// This algorithm has very high memory-level parallelism which can be exploited by modern out-of-order processors, and should
// be memory throughput limited.
void collect(void) {
// Initialize marks from roots.
memset(marks, 0, num_nodes * sizeof(uint32_t));
int newest = 0, oldest = num_nodes;
for (int i = 0; i < num_roots; i++) {
marks[roots[i]] = 1;
View self_validating_handles.c
struct Object {
Tag tag; // The tag is any piece of data that uniquely identifies the object.
// ...
};
struct Handle {
Tag tag;
Index index; // This caches a speculative table index for an object with the corresponding tag.
};
View graph_separators.txt
A grid graph is a directed graph where the vertices are arranged in k rows each
containing k vertices, where k is a positive integer. Let v[i,j] denote the jth
vertex in the ith row. Let s = v[1,1]. A grid graph has the following vertices and edges:
V = {v[i,j] | 1 <= i <= k and 1 <= j <= k}
E = {(v[i,j], v[i,j+1]) | 1 <= i <= k and 1 <= j < k} union
{(v[i,j], v[i,j-1]) | 1 <= i <= k and 1 < j <= k} union
{(v[i,j], v[i+1,j]) | 1 <= i < k and 1 <= j <= k}