Recent content on richardlupton.com
My new ZBook G1a comes with AVX-512 instructions and a healthy memory bandwidth (200GB/s allegedly), so one of the first things I did was write a little kernel to see how fast it can really go. This was my first time using AVX-512 instructions, and so I also wanted to see what new things it can do. A toy SIMD problem I’ve played with before (see here, here and here) involves deleting…
Introduction I’ve just bought a laptop, having had my current machine for around a decade. I decided I wanted to get a machine built around AMDs Zen 5 architecture, partly because they seem to be very powerful, cores numerous, and to get access to the AVX-512 instruction set that Zen 5 makes available (usually these are only really available on higher end server processors). In the end, I…
Introduction Compilers are full of strings, and resolving entities by name winds up being a common operation. This in turn entails comparing strings for equality, which if done naively, is not especially efficient. In order to avoid doing byte-for-byte comparisons between strings, compilers (and interpreters) often use a symbol table, a data structure which maps each string (that the compiler is…
This post documents a small technique I invented (in the sense that I haven’t seen if before, although I wouldn’t be surprised if there is prior art) for packing small sparse arrays into dense arrays. It’s part of the class of techniques using bit operations (on x86_64 for example tzcnt, popcnt) not natively supported in C/C++ and which require use of compiler builtins or…
Wirecode is a library and wire format I’ve been working on for simple serialization and deserialization of data in C. It can be used as a single header library (provided the compiler supports the non-standard mandatory tail call optimization – in practice clang is the only compiler I’m aware of at the moment that does), or used with an object file of optimized assembly routines.…
Some of the software I’ve written or I’m working on. Very far from complete, and with a strong recency bias. Projects orion - project to build a new programming language and compiler. Compiles from source to object files. Written in C, with only the standard library as dependencies. It has a home-grown backend for code generation which provides a static-single-assignment intermediate…
broot is a small utility I wrote specialized to build sandboxing on linux. A certain amount can be done with containers already, but I wanted something simpler and more specialized, with the aim of being able to check out a codebase, drop network access (because blindly pulling dependencies from the internet is dumb), and then build anything within that codebase (most of my personal code is in a…
Sometimes its useful to understand how a procedure receives its arguments, and returns values it computes. This protocol, known as the Application Binary Interface (ABI) is usually standardized for a given operating system and architecture. This standardization allows libraries to be linked and/or loaded into a binary (mostly) without explicitly declaring how the procedures in that library need to…
I would like to add an ARM64 backend to my compiler project, but a prerequisite for that is learning ARM64 assembly sufficiently well that I can get something basic stood up. My personal machines are all x86_64 (and some old 32-bit ARM Raspberry Pis), and while I’ll want to test on a real ARM machine reasonably often, for everyday development work I’d prefer something I can quickly…
Compilers are full of cute little data structure and algorithm problems. The following is a neat example of the kind of problem that emerges in a number of places, for example, shuffling values around in registers during code generation. It’s also a demonstration of a neat kind of abstraction that got distilled from solving a few related problems. These problems had solutions which…
OpenBSD has the capability of restricting permissible syscall origins addresses. Over the last few days there have been some interesting demos here and here, demonstrating how to do this with statically linked binaries. This is nice if you want to make use of this security feature (if you believe it has value) but don’t want to make use of libc 1. The way this feature appears to work is that…
Following on from previous investigations into deleting characters, and deleting characters using MMX instructions it remains to be seen what can be done using the full 16-byte with of SSE registers. There are two approaches to consider - building a mask using SSE instructions and using two pext instructions to place the 64-bit upper and lower pieces together again (an extension of the SSE variant…
In a discussion on Twitter somebody pointed out to me that the pext instruction on AMD processors is much slower than on Intel, up until fairly recent processors (Zen 3). I lost the thread for this, but I learned from that that pext can be emulated using shuffle instructions and a lookup table for shuffles. This explores and measures this approach using the character deletion example from a…
A small devlog of a Christmas project. Done in odd hours here and there. 2024-12-23 Day 1 Only got a couple of hours in on the first day, but setup a basic project (build script and C file), and got an OpenGL enabled window up using X and GLX. Only one file so far, and the screen is filled with a solid color. 2024-12-24 Day 2 A light restructure to separate the platform layer (GLX setup and…
My language and compiler (“orion”) is getting to the point I could use it to write some vaguely real software. This year it got a new backend and intermediate representation which ought to make it easier for me to a) add new features and b) get greater leverage and consistency across existing features. However, the language still feels a bit rough to use in many (most?) areas, so…
I’m setting up my workstation with a fresh install. This is a record of the details for future replication/repair. This workstation is intended to be used (as it has before) for heavy programming work, and I expect it to become very specialized to that task. I want to keep the system simple to administer, but also have quite a particular userspace. The aim here is to end up with a Debian…
I learned a cool things from Justine Tunney’s work (I’m a great admirer), in particular from her work on redbean. Zip files are recognized by a record at the end of a file, and are designed to be tacked on to other binary blobs. Many file types, including pretty well all binary formats for executables are recognized from records at the beginning of the binary (on linux and the BSDs,…
Intel’s vector instruction sets (SSE, AVX etc.) are well known, but Intel has added various other instruction set extensions specialised for other tasks. One such task is operating on integer register bitsets. One toy problem I came across was removing all instances of a character from a string (basically, tr -d), and I got curious about how quickly this might be done. In particular, I…
Introduction movemask instructions take a vector register of values, and construct an integer where the ith bit is set precisely when the higher order byte of the ith lane is set. For example, the pmovmskb instruction (_mm_movemask_epi8 intrinsic) from the SSE2 instruction set takes a register of 16 bytes, and constructs an integer where the ith bit is set when the high-order bit of the ith byte…
On and off over the last year or two I’ve been trying to learn more about doing sophisticated things with SIMD instructions. There is a quite a gap between the easy examples (doing arithmetic on big batches of data in a purely lanewise fashion), and validating utf-8 encoded bytes, and not a lot of readable material to bridge the gap. I’ve been on the lookout for examples between the…
Small sets of small integers can often be packed into single integers by using the bits to mark presence or non-presence of elements. This can often be useful for compactly storing changing sets which can be processed simply when needed. A place I’ve found this useful is in the register allocator/code generator of my compiler project. The compiler (at time of writing) uses a simple linear…
TL;DR: On OpenBSD, while testing, set MALLOC_OPTIONS="SCFGJRU" in your environment. Linux, Windows, and even FreeBSD have C compilers which provide sanitizers to help catch common errors with memory allocation (use-after-free, buffer overflows etc), and undefined behaviour (signed integer overflow, for example). These are often useful to catch silly mistakes quickly, and address sanitization even…
Aside from the usual error handling in C, gotos can be convenient for the first pass on some programs. I’ve found them quite useful for writing simple parsers of sequences of things. Consider for example parsing initializers for a struct literal, a = { x = 5, y = 5 }; b = { x = 5, y = 5, }; // Allow trailing commas This can be built up quite naturally using labels and gotos.
The following are source code snippets for showing how to blit pixels directly using X11. They are a little hardcode-y, since I wrote them as quick programs to figure out roughly how to use the X11 APIs (a living note, essentially). You can get a lot more information on how to use the X11 APIs by reading the documentation, possibly using the following as a guide for procedures to start looking at.
I like interfaces which permit fuzzy matching. I always imagined the algorithms for fuzzy matching over a large body of data to be quite sophisticated (I suppose they can be), but realised you can get a reasonable way with very little. The following implements a very basic fuzzy matcher. This was inspired by a skim of the fzf source code (or at least one of the comments), but is not quite the same…
General This is my personal site for dumping whatever I want. So far its mostly bits of thinking about software (mostly outdated), and notes I made on things when working out how they worked, or that I wish to remember in future. My GitHub page contains some things (not the best things), but this is not up-to-date. I write a bunch of stuff for fun and utility, mostly in C.
Condensed notes on how to use git subtrees to vendor in source code. Basics (add, pull, push) Pull in a new repository to dir/: $ git subtree add --prefix dir/ REMOTE REMOTE-BRANCH --squash The squash flag can be elided if the subtrees history is wanted. To pull in updates: $ git subtree pull --prefix dir/ REMOTE REMOTE-BRANCH --squash If changes need to be pushed back upstream $ git subtree push…
Introduction Tracepoints provide a way to instrument running programs dynamically in order to aid debugging. When no probe is attached, they are low cost (a single no-op instruction in the instruction stream). When a probe is attached, the no-op is replaced with a debug trap, and the probe provides a small BPF program which runs at that point. This means that these tracepoints can be left on…
Linked lists aren't necessarily the first data structure you might reach for, but if you need them, it's nice to not have to keep reimplementing the structures and operations. An intrusive linked list is a minimal list structure which is embedded in other structures to link them. The greater structure can be recovered from the list address using basic pointer arithmetic and the offsetof macro, but…
Sometimes it's nice to be able to allocate a bunch of different linked structures in one go, instead of making separate allocations. An example of where this kind of thing can be useful is when implementing interface like structures to enable a degree of polymorphism: typedef struct interface { void* ctx; void action(void* ctx); } interface; void interface_act(interface* iface) {…
We'll measure the impact of false-sharing on a simple spinlock. Our spinlock is the simplest possible implementation: // spinlock.h #pragma once #include <stdatomic.h> #include <stdbool.h> #define SPINLOCK_INIT \ (spinlock) { 0 } enum spinlock_status { LOCK_ACQUIRED, LOCK_BUSY }; typedef struct spinlock { _Atomic(bool) locked; } spinlock; static inline enum spinlock_status…
A pithy a terse account of memory models and lock-free programming. Further references are linked. Currently work-in-progress. Let's start by describing the high-level concerns of atomic variables, as they appear in relatively high-level system programming languages (function names are taken from the C11 API in stdatomic.h). We'll examine why these concerns arrive at the hardware level later, as…
I've decided to start a new site. I intend to use this as a place to write about things that interest me, with no particular adherence to any theme. Let's see where this goes. Currently I'm building this using hugo with a custom theme I wrote for my first and concurrent brain-dump pure-hack.com. It's hosted on a small OpenBSD server, to keep nonsense low, and management easy and efficient.
One of the often recognized issues with object-oriented programming is that it's often hard to write multithreaded software well. Why should this be the case? One of the core principles of object-oriented programming is that objects own the state which they manage internally. Objects present an API which can maintain a set of internal invariants. Methods on the object mutate state to ensure these…
Introduction Haskell is one of my (if not my) favourite language. Like all languages it has its warts, and one which I have always found particularly annoying is the fact that record names of data types can't be overloaded (they are just functions, after all). I haven't been writing as much Haskell as I would like lately, and certainly haven't been messing around with the more cutting edge type…
Introduction st is a simple terminal emulator from suckless tools. It provides the core features you need from a virtual terminal without being a bloated mess. While I like urxvt, st is smaller, simpler and a touch faster. Like most suckless tools, st provides a minimal feature set, with the expectation that users will patch in additional features as wanted, or compose st with other tools (e.g.…
I recently converted one of my machines from a parabola installation to a Debian 10 system. I started from a text only interface - the bare minimum of packages - and installed the rest by hand. For reasons that aren't entirely clear, the default font rendering is pretty hideous. It took me a while to track down how to properly configure font rendering. Perhaps this isn't an issue for installs…
Introduction Recursion is central to functional programming, as a clearer alternative to loops as other control structures typical of imperative languages. Functional programming encourages programmers to study recursion in greater depths. I first encountered the Y combinator in the mind-bending penultimate chapter of the wonderful The Little Schemer, which explores recursion in great depth. In an…
NixOS isn't a libre distribution by any means, but it comes close, and maintains a clear distinction between free and non-free packages (and in fact, different license types). This makes it possible to configure the system to exclude non-free packages, and with the addition of a libre kernel, allows us to turn NixOS into a libre platform. Of course, this isn't the same as leveraging an FSF…
Here I’ll outline how I managed to get DragonFly BSD to boot from a single slice (Linux: partition) by chainloading the DragonFly bootloader boot1. Note: for clarity’s sake, I’ll stick to the BSD terminology here. Slice refers to what Linux would dub a partition, and partition refers to a Linux “partition of a partition”. Linux’s sda1 would therefore be slice 0 of disk sda (BSD counts from 0),…
This is an account of things I've learned day-by-day. Some are things I've looked up and maybe even used before, and subsequently forgot. Some entries are mostly links to good articles that I've read. May 2020 [2020-05-12 Tue] date can be used to convert between timezones For example: $ date --date='TZ="US/Pacific" 09:00 next Fri' Fri 15 May 17:00:00 BST 2020 [2020-05-13 Wed] Assembly and C…