Blog

The strict semantics of many concurrent data structures are often useful when designing algorithms. However, such semantics make achieving high degrees of parallelism problematic for data structures such as FIFO queues, where operations contend for a few shared access points (the head and tail in this case). Thus, such data structures suffer large synchronization overheads under high contention, severely limiting scalability.

Relaxed concurrent data structures were introduced as a way to alleviate such synchronization bottlenecks. They achieve this by weakening the ordering semantics of the data structure, essentially trading some order (in a controlled manner) for parallelism. This post introduces the d-CBO queue, which is a state-of-the-art relaxed FIFO queue.

Classical concurrent data structures such as FIFO queues are foundational in many different applications. It is very simple to implement such a queue by wrapping a sequential implementation in a mutex. However, lock-free designs are often preferred, as they can give better scalability and progress guarantees than ones relying on locks. The classic lock-free FIFO queue is the Michael-Scott queue (MS queue), which is a neat lock-free linked list. Lock-free designs are inherently tricky to implement, and linked lists are known to be troublesome in Rust, so this post details my journey of implementing this MS queue in Rust.

Almost two years ago, I listened to a podcast episode about custom keyboard layouts, such as Colemak, and building a custom keyboard with only 22 keys. It hit me at just the right time, and caused me to shortly afterward switch to Colemak (which I've happily been using since then, and wrote a post about here). Since then, I have been meaning to also build my own custom keyboard, and now I finally finished! This is a short recap on how I went about building the keyboard, as well as I configured it.

I recently had a great time attending my first conference, Euro-Par 2024, as a computer science PhD student. I presented my paper How to Relax Instantly: Elastic Relaxation of Concurrent Data Structures in front of around 200 people, managed to win Best Paper, and got to know some great people. I could not have hoped for a better first conference. In this post, I'll share my experience, offer tips for future conference attendees, and reflect on what I wish I'd known beforehand.

In the age of multicore computing, developers face the challenge of designing data structures that efficiently utilize the available hardware parallelism. One of the most important data structures is the priority queue, which is used in a variety of applications ranging from graph algorithms to data compression. Computer scientists often are taught some heap-based design of priority queues during university, where smart incremental updates enable good performance. However, trying to parallelize these designs is complex, as is often the case with strictly incremental algorithms. In this post, we will investigate the MultiQueue, which is a relaxed priority queue that trades strict sequential semantics for massively increased scalability.

There is something about graph algorithms - they are just always fun to think about! With that said, Graph Neural Netorks (GNN) are no exception. These are a form of neural network, but designed in a way to learn things about graphs. They have proven to be usefull for a plethora of graph learning problems in fields such as drug discovery, recommender systems, and protein folding. In this post, I will present the difficulty of directly applying neural networks (NN) to graphs, how message passing NN solves this, and end by looking at the expressive power of such GNN.

This was my fourth year doing Advent of Code, my second year trying to compete, and my first year appearing on the top 100 leaderboard (if only for a single day). Last year lit a fire in me to become faster, and since then I have built my programming language Zote, practiced some competitive programming, and learned to touch type using Colemak. This will be a short retrospective on this year's event, as well as my preparation leading up to it.

Do you lay awake at night contemplating the best scheme for variable bindings? Neither do I. However, I have thought a bit about it recently and realized it is not as simple or obvious as I once thought. In this post I give a short introduction to the late and early binding schemes and discuss their respective advantages and disadvantages.