Algorithms
Algorithms and data structures: counting, ordering, compact IDs, binary data, address spaces and the tricks that make code smaller or faster.
Generating short ordered IDs with any insertion pattern
Giving ordered elements short IDs that reflect their position, whatever order they are inserted in: a naive approach, LSEQ and a tree of IDs.
4 May 2024Counting up to 2^256 unique values using only O(1 byte)
There are occasions when you need to know how many unique entries there are in an array or how many unique values have been seen in a stream, but do not need the exact number.
21 April 2024On address space sizes
We are well into the 64-bit era, and a 64-bit pointer allows for an addressable space of 2^64 bytes, or 16 exabytes.
7 April 2024Comparison of JavaScript binary data objects
There are a set of objects for dealing with binary data in JavaScript, which are slightly different on NodeJS and in the browser.
15 March 2023FastArray (draft)
A fast array is a trie-like data structure that allows for fast insertion and removal of elements at any index. It is useful for cases where you need to insert and remove elements at arbitrary indices in an array-like data structure.
15 March 2023Flattening 2D data
Write-up to come.
14 March 2023Program: a programming language
Write-up to come.
8 March 2023Parsing self-describing JavaScript code
It is possible to write code in a manner that allows you to choose whether to execute it or grab a description of what the code does as an Abstract Syntax Tree. All using the same code.
22 January 2023Self-describing code
It is possible to write code in a manner that allows you to choose whether to execute it immediately or grab a description of what the code does as an Abstract Syntax Tree. All using the same code.
19 January 2023A hash table you don't need to rehash
An immutable hash table that grows without ever being rehashed, and shares almost everything between one version and the next.
7 May 2022Exceptional parsing
Parsing is one of those intermediate-level algorithms, which, like state machines, you may not use on a day-to-day basis as a developer but their understanding helps with your mental model of programming.
11 March 2022ZSystem
A design for generating a whole universe from random seeds in C++, where every object is a function that builds its parts, tried out in three OpenGL test programs for Windows.
1 June 1998Fixed point maths in x86 assembly
Fractional maths with whole-number instructions, for fast 3D graphics on the PC.
27 November 1997