This is the first entry of a series of articles about designing an efficient byte pair encoder (BPE) tokenizer. The tokenized text is then used to train an n-gram model for the task of synthesizing placeholder text. These articles are for sharing the design decisions and optimization techniques I applied. For the first entry, I wanted to talk about an overview of the algorithm and an efficient decoder implementation.
Struct of Arrays (SoA) is the bread and butter and textbook example of Data-oriented design. It’s mostly popular in game development due to enhanced performance in many gamedev specific operations. You might also encounter SoAs in analytic and processing heavy databases such as Pandas or DuckDB. Of course, in the web development space nobody cares about data layout and optimization. Despite that, I wrote an SoA library in TypeScript, not for the performance gain, but for trying out TypeScript’s type-level metaprogramming.
Let’s face it, determinism is boring. I’ve been using Pseudo-random number generators (PRNGs) for as long as I can remember. My usual PRNG is PCG-32 with a fixed increment, but it’s time for me to pick a larger PRNG for 64-bit output and multithreaded generation.
In computer science, the problems that captivate me the most are the ones that are just a bit more difficult to optimally solve with current hardware limitations. They often require careful engineering and strategic trade-off considerations to come up with suboptimal, but good-enough solutions.
One such problem is finding the shortest solution to the 15-puzzle. With the state space size of 10^13, average branching factor of 2, and longest solution length of 80, it’s impossible to find the shortest solution using conventional search algorithms. However, I implemented an algorithm that can optimally solve a vast majority of random instances pretty quickly.
NixOS makes it very hard to run dynamically linked application, to the point where packaging is the path of least resistance. I don’t consider this a problem of NixOS, but rather a problem of dynamic linking. This is why when I distribute a compiled application to a NixOS system, I usually do one of the following:
To do either of these, a cross-compiling NixOS environment is required, so this article documents my process of setting that up for Rust, Zig, C, and C++.
Usually, people write this kind of post somewhere at the end of the year. But I had another deadline and haven’t collected my thoughts yet, so this post came quite late. Nonetheless, I really wanted to look back at 2024 because it’s been quite an interesting year for me.
I’m a massive tinkerer, I love breaking things to see why it broke and how to fix them. I prefer breaking software because if it goes too far, I can just reinstall everything. It was a great learning experience, and I’m glad that I had the time and opportunity to do it. As I grow up, messing with software is no longer just for fun and learning, it’s had become a way for me to optimize my workflow, to be more in tune with technology.
I use switch statements a lot in C and even C++. The syntax sucks, but the alternatives are either too verbose (table of function pointers) or don’t express the intention well (if-else chain). It was sad, but I accepted long ago that switch statements only work on numeric types and usually use the alternatives on strings and arrays. But switching on a string has become a common operation for me, and I recently ended up with a reasonably good solution for it.
I use trigonometric functions extremely often, ever since I started doing programming. They show up everywhere, especially in graphics, and while they’re not the most efficient operation, they are widely available in programming languages. This is not the case if you’re programming in embedded systems or WebAssembly, so I tried to compute them myself.
I’ve been using WebAssembly (WASM) for quite a while, and the learning resources are sparse and incomplete. This is especially true for freestanding WASM, or using WASM directly without using tools that make interacting with the web easier. This is an attempt for me to reflect on what I discovered and hopefully introduce more people to this weird intersection of system programming and web development.
ZSH has been my shell of choice since I started my command-line-centric workflow. It’s a popular shell with a large community and an unprecedented level of customizability. ZSH is also POSIX-compliant, which was very important to me for some reason. However, after some reconsideration, I decided to port my config to the Fish shell, and this is why.
A drawback that people often mention when programming in C is the lack of RAII. This is sometimes good as it causes me to avoid small, random allocations and incentivize grouping data into large, contiguous memory regions to make them faster and more manageable. However, small, random allocations are sometimes unavoidable, and there should still be a way to manage them. Instead of grouping data into arrays, we can instead group data by their lifetime, and this is where the “arena” allocator comes in.
I recently programmed a large chunk of the game from scratch for a university course project. This is one of a few projects that I delivered with enough quality and presentability. So I wanted to document my process of making it, what I learned, and how I applied my knowledge from and outside the course.
From breadth-first search to task scheduling, queues are extremely useful in computer programming. Although many programming languages support them, I think that it’s important to understand and know how to implement them. I like to implement data structures on-the-fly and customize them for the problem I’m trying to solve. A more practical reason to understand queues is that JavaScript doesn’t have an efficient queue implementation.
When I first heard about run-time polymorphism in C++ using virtual methods, my first thoughts were like, “This is cool and all, but why would I ever use this?” Then I continued to ignore it because I could always just work around it instead of using it. Until recently, my college lecturer told me that using virtual methods is great for designing and maintaining applications with thousands of objects. I figured that I should write about what run-time polymorphism is, and why I still think that I don’t need it.
I already have a website hosted on GitHub pages. It was built around 2 years ago as a way to quickly browse and access my web projects. Basically, it was just a grid of project thumbnails, which is pretty boring. During the last 2 years, I changed bits and pieces of it, but it’s still the same boring layout with only a list of projects and some basic information.