f-Arrays for Noobs.

This post is about the $f$-array data structure, which was introduced by Prasad Jayanti in f-arrays: implementation and applications (PODC 2002). What is it? An $f$-array is a data structure that can be thought of as similar to a regular array, except it provides a read() operation. This read operation returns the value of some function $f$ applied to the whole array. Furthermore, the types of the elements in the array need not be the same, so a mental model I have for the array is something like the following: ...

November 20, 2026 · 1934 words

Lazy List for Noobs.

This is the first post in which I go over random concurrent data structures. This post is based on the Lazy List data structure introduced here: https://people.csail.mit.edu/shanir/publications/Lazy_Concurrent.pdf Ideally this post can help you understand at a high level how we can optimize a regular set data structure and eventually end up with the one described in the paper. What is it? The data structure presented in the paper is known as the Lazy List. It functions like a regular sequential set in which as a user you can call the following APIs: ...

November 13, 2026 · 1675 words