Posts from purplesyringa's blog.
Say you’re writing a Windows IPC library for Rust, and you want to pass a handle to a child process. Maybe it’s a pipe, maybe it’s a file, maybe it’s a broker process handle. It turns out that there’s no correct way to do so due to Rust’s idiosyncrasies. WinAPI trivia time! The CreateProcess function, which is used to spawn a process, takes two parameters that determine which handles are inherited…
About two months ago, I found the Teal programming language , which describes itself as a statically-typed dialect of Lua. It transpiles to Lua and runs typecheck on the developer’s machine, so it fills roughly the same niche as TypeScript. It’s used by quite a few projects, including LuaRocks and inspect . For better or worse, I am trying to write Lua without feeling like it’s year 2010, and Teal…
I found the post SIMD in Pure Python by retr0id about optimizing Game of Life and thought it’s a good opportunity to yap about SWAR. Make sure to read that post before continuing here! Or at least skim it.
If a > b > 1 and x > 1 , you can prove that log a x < log b x . (As a reminder, log a x denotes the value t such that x = a t .) This is very intuitive if you think about it: for “normal” numbers, the greater a , the smaller t you will need to get the same x . Yet if you ask PHP what it thinks, it will tell you you’re wrong in a couple rare cases: <?php $x = 2.93 ; $a = 10 + 2 ** - 49 ; $b =…
I need a place to describe this algorithm, since it seems to be undocumented on the 'net, so here it is. SRC is a replacement for MTF in BWT -based compressors. According to OpenBWT , it’s the best known MTF replacement measured by compression ratio, if you don’t want to use context modeling.
So I was optimizing a domain-specific compressor the other day , as one does. One important problem was chunking the input string and optimally choosing the most compact encoding for each chunk (different encodings compress different characters better, so where to split is not immediately obvious). The previous post describes the algorithm if you’re interested, but it boils down to finding the…
This problem arose when I was writing a specialized data compressor. Say you want to encode a byte stream, and bytes can be encoded in different formats, e.g. optimized for ASCII, numbers, raw binary, etc. These formats prioritize better compression of a specific type of data. Realistic byte streams may contain all of them at different points, so we want to switch between formats on the fly…
I blog because I want to share knowledge. That’s how I have fun. It feels rewarding to sit down and formulate your thoughts after spending a week researching a topic for a side project. Oftentimes, such topics are largely unexplored: with the basics being too obvious and other topics laid out clearly, the remains are bound to be unconventional. To me, that’s a positive thing. It’s my chance to…
Intended audience: data compression geeks. The Burrows-Wheeler transform takes a string as an input and rearranges its characters, grouping them by context. It is invertible with 𝒪 ( 1 ) additional input, and together these properties give it a place in data compression and genome alignment. What Wikipedia doesn’t tell you is that there are actually two variants of BWT, with subtly different…
This is a guest post by Yuki about some tricks we use for Lua code compression in our shared ComputerCraft pet project . I’ve written about how we adapted bzip2 for this purpose earlier; this story is an installment that takes place in the same context. If you want to read more stuff from her, here’s an Atom feed and the blog .
2945 bytes. Less than 0.006% of Wasmtime , smaller than a C “Hello, world!”. Zero dependencies, no cheating: just a static x86-64 Linux executable . Scan the QR code above with zbarimg --raw -Sbinary or another QR decoder that supports binary data, or directly download the program from the GitHub repo , and you’re good to go.
This post assumes basic familiarity with arithmetic coding . I’ve written an arithmetic coder, like, three times in my life, so the mistake I want to highlight is likely amateurish. But since I didn’t have a clue that my understanding was incomplete, I figured I needed to write a post about it.
Everyone knows Wasm is a stack machine. Wikipedia says so, the official Wasm design specification says so, you get it. I thought so too. That is, until I started writing Wasm code – not compiling for Wasm, but writing the instructions by hand. And I found out that there exists a major difference between Wasm and all other stack-based languages, that makes this claim misleading.
I needed to convert file status flags between operating systems yesterday. They are the values you pass as the second argument to open – O_NONBLOCK , O_NOATIME , O_SYNC , O_DSYNC , and so on: int open ( const char *path, int flags, /* mode_t mode */ ) ; So naturally I wrote it like this: int dst_flags = 0 ; if (src_flags & SRC_O_NONBLOCK) dst_flags |= DST_O_NONBLOCK; if (src_flags & SRC_O_NOATIME)…
The appearance of Mythos – a private LLM allegedly capable of finding a multitude of 0-days – has made people concerned about being denied powerful tools . This seems to be a turning point in the mainstream discourse, and it motivated me to complete the think piece I’ve been meaning to write for a while. I have a related, intimate worry regarding LLMs. Just so that we’re clear, it’s not a common…
In case you’re unaware, I’m not a developer. I’m actually an autistic catgirl annoyed by suboptimal use of computing power, and fixing that happens to involve programming. Crucially, it also includes discussing foundational technology with people behind the scenes, and apparently that makes me more aware of social aspects of this sphere. So, I have opinions about criticism of crates.io for…
What came to your mind when you read “hash functions” in the title? If you’re pragmatic, you probably remembered SHA-256 or MD5 . Those are cryptographic hash functions, and they work fast and well for arbitrary inputs, even if they are supplied by malicious actors. Or at least they’re designed to. That’s the exact opposite of what I want to talk about. I want to talk about the cheapest,…
This is a rant about how broken everything Web is based on is. You know, the usual. No offence intended towards framework developers, I’m glad this technology exists, but I’m sure you know this feeling. It gets too much sometimes. I’ve been meaning to improve this blog’s technology for a while. It’s held together by two hacky scripts as opposed to a typical template engine, and that’s very…
Minecraft generates a bedrock floor at the bottom of the world from a random noise. Since it’s random, it can contain naturally generated unescapable regions – prisons. While small prisons are common, larger ones are hard to find – a Minecraft world is about 60 million by 60 million blocks, so locating these boxes is computationally difficult. So when I saw Bamboo Bot’s video on this concept…
Two years ago, I was pondering ways to enhance borrowck with proof-based analysis. At the time, I was only aware of formal verification tools for functional languages, while Rust is impure. For the purposes of borrow checking, though, we can almost pretend that impurity doesn’t exist, with the notable exception of mutable references. Can mutable references be simulated in a functional language?…
The story goes like this. ComputerCraft is a mod that adds programming to Minecraft. You write Lua code that gets executed by a bespoke interpreter with access to world APIs, and now you’re writing code instead of having fun. Computers have limited disk space, and my /nix folder is growing out of control, so I need to compress code. The laziest option would be to use LibDeflate , but its decoder…
Last year, Lemire wrote about an optimized variation of the Euclidean algorithm for computing the greatest common divisor of two numbers, called binary Euclidean algorithm or Stein’s algorithm . It’s a best-of-class implementation, though it’s currently only used by libc++. The post also briefly mentions the extended Euclidean algorithm , a related algorithm most often used to compute the modular…
Functions in binary files need to have unique names, so Rust needs to decide what to call its functions and static s. This format needs to be standardized so that debuggers and profilers can recover the full names (e.g. alloc::vec::Vec instead of just Vec ). About a month ago, Rust switched to symbol mangling v0 on nightly . The linked announcement describes some benefits of the new scheme…
This article is a technical counterpart of my previous post Finding duplicated code with tools from your CS course . It is deliberately written in a terse manner, and I’m not going to hold your hand. Consider reading the previous post first and coming back here later.
Recently I was scrolling through brson’s Rust quote database and stumbled upon a link to the official Rust tutorial from the very beginning of 2013. It says Rust 0.6 in the corner, but it lists many things that were removed in 0.6, so it’s likely closer to 0.5. I heard tales of old Rust before, but not of how the language felt to programmers. So I thought it’d be cool to give a (relatively) quick…
Say you want to send a list of consumer records to another microservice over network via JSON. There are three concepts at play in this process: A logical value, which is how we humans treat the data. In this example, this would be “a list of consumer records”. This description does not specify how it’s represented in the computer, or whether you’re using a computer at all. A data type, e.g.…
Suppose that you’re writing a static analyzer and you want to write a diagnostic for match arms with equal bodies: match number { 1 => { // <-- let x = 1 ; f (x) } 2 => f ( g ( h ())), 3 => "" , 4 => { // <-- let x = 1 ; f (x) } _ => unreachable! (), }
Some time ago, I played around with decompiling Java class files in a more efficient manner than traditional solutions like Vineflower allow. Eventually, I wrote an article on my approach to decompiling control flow, which was a great performance boost for my prototype. At the time, I believed that this method can be straightforwardly extended to handling exceptional control flow, i.e. decompiling…
A few days ago, I stumbled upon a Hacker News discussion about the expression problem – a conundrum that occasionally arises in software design. Some of the commenters noted that Rust completely avoids this problem thanks to trait objects, and initially I agreed with them, but I’m now realizing it’s not at all as straightforward as it looks. The goal of this post is to explain what the expression…
Fenwick trees and interval trees are well-known data structures in computer science. Interval trees in particular are commonly used in bioinformatics and computational geometry, and Fenwick trees are useful for keeping statistics. This post describes how the two can be merged to obtain a worst-case faster implementation of an interval tree. This approach is probably not very useful in these areas…
Here, read the intro of the Wikipedia page for Command pattern with me: In object-oriented programming, the command pattern is a behavioral design pattern in which an object is used to encapsulate all information needed to perform an action or trigger an event at a later time. You know what I call this? A function. This information includes the method name, the object that owns the method and…
In contemporary “AI” discourse, people often make a point that LLM output cannot be trusted, since it contains hallucinations, often doesn’t handle edge cases properly, causes vulnerabilities, and so on. This is seen as an argument to never use LLM-generated code in production. Others argue that the benefits AI grants them are worth the risk. These groups are talking past each other. The problem…
This is a tech phenomenon that I keep getting blindsided by no matter how much I try to anticipate it. Physical work feels difficult. You can look at someone and realize you don’t have nearly as much stamina, and even if you did, it still feels demanding. Research feels difficult. You’re tasked with thinking about something no one else has considered yet. That rarely happens even outside of…
I’m making progress on the Java decompiler I’ve mentioned in a previous post , and I want to share the next couple of tricks I’m using to speed it up. Java bytecode is a stack-based language, and so data flow is a bit cursed, especially when the control flow is complicated. I need to analyze data flow globally for expression inlining and some other stuff. Single-static assignment produces…
This post is about a popular but niche technique I can never find a succinct reference for. I didn’t invent it, I just need a page I can link when giving optimization advice. Integer ↔ float casts that utilize specialized processor instructions, i.e. those that compilers use by default, typically have worse throughput and higher latency than alternatives based on applying bit tricks to the…
I’m working on a Java decompiler because I’m not satisfied with the performance of other solutions. I’ve always heard that decompiling JVM bytecode is a solved problem, but I’ve concluded that the decompilation methods used by CFR and Vineflower are hacky, inefficient, and sometimes don’t even work. The existing solutions are haphazard and inadequate compared to alternative approaches.…
I’m not talking about skill, knowledge, or convincing a world focused on radical acceleration that optimization is necessary. Performance optimization is hard because it’s fundamentally a brute-force task, and there’s nothing you can do about it. This post is a bit of a rant on my frustrations with code optimization. I’ll also try to give actionable advice, which I hope enchants your experience.
Null pointers look simple on the surface, and that’s why they’re so dangerous. As compiler optimizations, intuitive but incorrect simplifications, and platform-specific quirks have piled on, the odds of making a wrong assumption have increased, leading to the proliferation of bugs and vulnerabilities. This article explores common misconceptions about null pointers held by many programmers,…
The RAM myth is a belief that modern computer memory resembles perfect random-access memory. Cache is seen as an optimization for small data: if it fits in L2, it’s going to be processed faster; if it doesn’t, there’s nothing we can do. Most likely, you believe that code like this is the fastest way to shard data (I’m using Python as pseudocode; pretend I used your favorite low-level language):…
In languages like Python, Java, or C++, values are hashed by calling a “hash me” method on them, implemented by the type author. This fixed-hash size is then immediately used by the hash table or what have you. This design suffers from some obvious problems, like: How do you hash an integer? If you use a no-op hasher (booo), DoS attacks on hash tables are inevitable. If you hash it thoroughly,…
* If you don’t take whitespace into account. My friend challenged me to find the shortest solution to a certain Leetcode-style problem in Python. They were generous enough to let me use whitespace for free, so that the code stays readable. So that’s exactly what we’ll abuse to encode any Python program in 24 bytes, ignoring whitespace.
Four days ago, the Rust Foundation released a new draft of the Rust Language Trademark Policy. The previous draft caused division within the community several years ago, prompting its retraction with the aim of creating a new, milder version. Well, that failed. While certain issues were addressed (thank you, we appreciate it!), the new version remains excessively restrictive and, in my opinion,…
Three months ago, I wrote about why you might want to use panics for error handling . Even though it’s a catchy title, panics are hardly suited for this goal, even if you try to hack around with macros and libraries. The real star is the unwinding mechanism , which powers panics. This post is the first in a series exploring what unwinding is, how to speed it up, and how it can benefit Rust and C++…
Demoscene is the art of pushing computers to perform tasks they weren’t designed to handle. One recurring theme in demoscene is the shadow-art animation “Bad Apple!!”. We’ve played it on the Commodore 64, Vectrex (a unique game console utilizing only vector graphics), Impulse Tracker , and even exploited Super Mario Bros. to play it. But how about Bad Apple!!.. in Minecraft?
Коллизии в играх обнаруживаются тяжелыми алгоритмами. Для примера попробуйте представить себе, насколько сложно это для просто двух произвольно повернутых кубов в пространстве. Они могут контактировать двумя ребрами, вершиной и гранью или еще как-то более сложно. В майнкрафте вся геометрия хитбоксов параллельна осям координат, т.е. наклона не бывает. Это сильно упрощает поиск коллизий. Я бы такое…
I want to provide a smooth experience to my site visitors, so I work on accessibility and ensure it works without JavaScript enabled. I care about page load time because some pages contain large illustrations, so I minify my HTML. But one thing makes turning my blog light as a feather a pain in the ass.
Developers don’t usually divide numbers all the time, but hashmaps often need to compute remainders modulo a prime. Hashmaps are really common, so fast division is useful. For instance, rolling hashes might compute u128 % u64 with a fixed divisor. Compilers just drop the ball here: fn modulo (n: u128 ) -> u64 { (n % 0xffffffffffffffc5 ) as u64 } modulo: push rax mov rdx , - 59 xor ecx , ecx call…
I have recently done some performance work and realized that reading about my experience could be entertaining. Teaching to think is just as important as teaching to code , but this is seldom done; I think something I’ve done last month is a great opportunity to draw the curtain a bit. serde is the Rust framework for serialization and deserialization. Everyone uses it, and it’s the default among…
The sentinel trick underlies a data structure with the following requirements: Read element by index in O ( 1 ) , Write element by index in O ( 1 ) , Replace all elements with a given value in O ( 1 ) . It is not a novel technique by any means, but it doesn’t seem on everyone’s lips, so some of you might find it interesting.
Rust’s approach to error handling comes at a cost. The Result type often doesn’t fit in CPU registers, and callers of fallible functions have to check whether the returned value is Ok or Err . That’s a stack spill, a comparison, a branch, and a lot of error handling code intertwined with the hot path that just shouldn’t be here , which inhibits inlining, the most important optimization of all.…