This post will be short (and unfortunately code-free), but I'd like to talk about lock-free algorithms and some of my initial thoughts looking into them.

A lock-free algorithm is an algorithm that is concurrently safe but doesn't use locks. These are particularly interesting in resource-constrained environments. Profiling many of my programs (especially in Go, where I tend to shove things in goroutines) shows the futex call as the place I spend most of my memory: this indicates that the program is spending a lot of time in locks.

Locks introduce resource contention problems (e.g. deadlocks), and they're a bottleneck. Lock-free algorithms solve this.

I haven't had time tonight to spend much time reading up on them, but I'd be interested to see how persistent data structures come into play. If two threads have two copies of a revision of a common ancestor, will there have to be merging? I'm not sure.

I hope this weekend to try my hand at implementing a lock-free queue; they seem like a natural fit for functional programming (I've also picked up a hard copy of PFDS to work through). That should give me some more insight into the topic.