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:
template<typename T_1, typename T_2, ..., typename T_m>
struct F_Array {
std::tuple<T_1, T_2, ..., T_m> array;
};
However, in practice it is most likely the case that the array is useful if the types are the same (that is, $T_1 = T_2 = \dots = T_m$).
First let’s go over the API they introduced:
// applies op to the i'th element of the array.
void update(op, i);
// computes some function f on the whole array. (Assume f returns a value of type T)
T read();
Examples & Applications
So let’s give some examples of problems we can solve with an $f$-array.
1. The Max/Min of an Array
Suppose we have an array and we wish to compute the max of the values in that array. Here we set:
$$f(A_1, A_2, \dots, A_m) = \max(A_1, A_2, \dots, A_m)$$
Note: Technically, the above notation isn’t super precise since it implies we have at least elements $1$ and $2$, but I think it’s easier to process than $\max_{i \in {1, \dots, m}} A_i$, and it gets the point across.
And we let all the elements of the array be integers.
That way read() returns the max of the array, and update(op, i) applies op to the
integer at index i (op can be an increment, replacing the value, etc.).
Same case for min—just swap max with min.
2. Multi-Writer Snapshot Array
In case you don’t know, a multi-writer snapshot array is an array where multiple
threads can concurrently write to any index i, and any thread can take a
snapshot of the array at the time (this is usually called a scan).
To build this with an $f$-array, simply set $f$ as
$$f(A_1, A_2, \dots, A_m) = (A_1, A_2, \dots, A_m)$$
Then update(write(v), i) writes v to index i, and read() returns a
consistent snapshot of all $m$ elements at once.
Implementing an $f$-Array
In this section, we go over optimizing a simple naive implementation all the way to the one presented in the paper. Similar to the Lazy List post (I think these sections are pretty fun lol).
1. Lock-Based $f$-Array
Alright, let’s start with the simplest possible implementation. Slap a lock around everything.
T read() {
lock();
for (int j = 1; j <= m; j++) {
v_j = read(A_j);
}
T res = f(v_1, v_2, ..., v_m);
unlock();
return res;
}
void update(op, i) {
lock();
A_i = op(A_i);
unlock();
}
In the above code, a read() takes $O(m)$ time to run. There’s a clear optimization we can do if we want the
read() to be fast. We can cache it, just put a lot of the overhead on update.
T read() {
return cached;
}
void update(op, i) {
lock();
A_i = op(A_i);
for (int j = 1; j <= m; j++) {
v_j = read(A_j);
}
cached = f(v_1, v_2, ..., v_m);
unlock();
}
Assuming cached is read and written atomically, read() is now $O(1)$ and even wait-free! Every read() just returns the latest cached value, while update() takes $O(m)$ time.
2. Lock-Freedom
Locks aren’t very scalable. When there’s a lot of contention, each thread needs to wait in a line to obtain the lock. Thus, let’s liberate ourselves from locks!
To do this, we first introduce the concept of LL/SC.
LL/SC (Load-Linked / Store-Conditional)
Here is a brief summary of how (idealized) LL/SC works:
LL(x)reads the current value ofxand starts “watching” it.SC(x, val)attempts to storevalintox, returningtrueif it succeeds andfalseotherwise.
The catch is that SC(x, val) only succeeds if no other thread has
successfully executed SC on x since this thread’s LL(x).
If another thread sneaks in a successful SC in between, our SC does nothing and returns false.
Below is a diagram which should explain what I mean. (I had Gemini generate this diagram from my beautiful ASCII 😌)
Thread 1: LL(x) ──────────────────────► SC(x, v1) ✗ fails
▲
│ breaks T1's link
Thread 2: LL(x) ──────────► SC(x, v2) ✓ succeeds
Lock-free Update
We can use LL/SC to make our update() function lock-free. You might wonder
why we can’t just use a CAS instead, and the reason for that is the ABA
problem (see the Appendix below for the explanation).
So the idea is simple: once we have atomically committed our change to $A_i$, we need to ensure that cached reflects it. We do this by introducing a function refresh() which “refreshes” cached so that it sees our update on $A_i$.
bool refresh() {
LL(cached);
for (int j = 1; j <= m; j++) {
v_j = read(A_j);
}
return SC(cached, f(v_1, v_2, ..., v_m));
}
T read() {
return cached;
}
void update(op, i) {
A_i = op(A_i);
while (!refresh()) {
// someone else updated cached while we were scanning, retry!
}
}
We wrap refresh in a retry loop to ensure that cached is calculated with our
updated $A_i$.
The reason for the retry is for the case of a concurrent update.
When a concurrent update occurs, it might’ve read $A_i$ before our update occurred. How do we know when cached is calculated with our value? Well we know for certain that if we run SC ourselves, then it used our updated $A_i$ value since we read our updated $A_i$ in refresh(). Hence, we stop the retry
when the SC succeeded.
3. Wait-Freedom
Lock-free is nice, but an unlucky thread could theoretically get stuck retrying the while (!refresh()) loop forever if other threads keep beating it to SC(cached).
Is there a way to improve it? Well, we’re in luck cause the paper introduced this one weird trick (readers hate him for this one trick):
Refresh at most TWICE.
void update(op, i) {
A_i = op(A_i);
if (!refresh()) {
refresh();
}
}
Wait… why is calling refresh() twice enough? For this, I’ll give a short proof:
Proof:
First, we know that no two successful
refresh()are concurrent. This is because the later SC will fail causing the refresh associated with that SC to fail. Keep this in mind for later.Trivial Case: If either of our
refresh()calls succeeds, thencachedwas computed using our updated $A_i$ (or a newer value).If both refreshes fail: For our first
refresh()to fail, some otherrefresh()(call it $S_1$) must have executed a successful SC after our firstrefresh()started its LL.For our second
refresh()to fail, anotherrefresh()(call it $S_2$) must have executed a successful SC during our secondrefresh().Because $S_1$ and $S_2$ both succeeded, $S_2$’s LL must have occurred after $S_1$’s SC (otherwise $S_1$ would have invalidated $S_2$). Since our first
refresh()is concurrent with $S_1$, then $S_2$ occurred after our first refresh which is after we updated $A_i$.Thus $S_2$ has read our updated value of $A_i$, essentially helping us complete our propagation. QED.
4. Turning It Into a Tree
Great, so that’s it right? Well kind of… The paper made another observation. They realized that most functions $f$ are decomposable (not sure if that’s the correct term lol). But essentially, this property:
$$f(a, b, c, d) = f(f(a,b), f(c,d))$$
With this in mind, they came up with the following idea. Hey we can make our array a tree where each subtree is an $f$-array.
In fact, our previous implementation is also a tree. Just a very short one,
in which root is the variable cached in our code before.
graph TB
root((root))-->A1((A_1))
root-->A2((A_2))
root-->A3((A_3))
root-->A4((A_4))
See it’s a very short tree, why don’t we make it taller!
graph TB
root((root))-->l1((C_1))
root-->l2((C_2))
l1-->A1((A_1))
l1-->A2((A_2))
l2-->A3((A_3))
l2-->A4((A_4))
Notice that you can think of each of C_1 and C_2 as its own smaller $f$-array. Same with the
root node where C_1 and C_2 are the elements of that array. This is
also why the decomposable property I mentioned matters!
To adapt our code to a balanced binary tree, refresh(node) now only reads a node’s two children instead of scanning all $m$ leaves, and update() walks up the tree from the leaf leaf(i) to root (read() simply loads the value at root):
bool refresh(Node* node) {
LL(node->val);
T left = node->left->val;
T right = node->right->val;
return SC(node->val, f(left, right));
}
void update(op, i) {
A_i = op(A_i)
Node* curr = leaf(i);
while (curr != root) {
curr = parent(curr);
if (!refresh(curr)) {
refresh(curr);
}
}
}
Because update() only traverses one root-to-leaf path and each refresh() reads just two children, our runtime is much faster!
Assuming a balanced binary tree and an $O(1)$ function $f$, update() now takes $O(\log m)$ time.
As an aside, we can also introduce a get(i) API which returns the element at
index i. This isn’t mentioned in the paper, but it seems pretty simple to add:
T get(i) {
T res = A_i;
Node* curr = leaf(i);
while (curr != root) {
curr = parent(curr);
if (!refresh(curr)) {
refresh(curr);
}
}
return res;
}
Note, we cannot just return $A_i$ directly, because this would cause a linearization bug. In fact, let’s segue into that!
Correctness
Let’s show that the data structure is linearizable. We can do this by specifying the linearization points.
For read() the linearization point is simply the time we read the root node.
For update() the linearization point is when our value has propagated all the
way to root. The paper describes this in more detail, but the gist of it is that
once $A_i$’s value is read and propagated up to root. Whether this is done by another thread’s refresh() or ourselves, we linearize there. (If another update overwrites $A_i$ before our value ever reaches root, our update linearizes right before that overwriting update’s value reaches root.)
Similarly, the get(i) API we introduced has the same linearization point
as update(). We can’t just return $A_i$ directly without propagating it up to root: if we did, a subsequent read() that starts after get(i) returns could still see the stale root value from before $A_i$ was propagated, violating linearizability.
Appendix
Feel free to stop reading. I’m adding this section as a nice-to-know.
Why we need LL/SC and why a CAS is not enough.
The main issue is the ABA problem. Suppose we use a CAS that compares the old
value of cached and swaps it with a new one.
Something like CAS(cached, old_cached, val). Here’s a counterexample:
suppose $A = [0, 0]$ and $f = \max$, so initially cached = 0.
- Thread 1 calls
update(set(0), 2). It writes $A_2 = 0$, readsold_cached = 0, and then gets paused by the OS. - Thread 2 sets $A_1 = 10$ and updates
cached = 10. - Thread 1 wakes up, scans $A = [10, 0]$, computes
val = 10, and pauses again before its CAS. - Thread 2 runs another update, setting $A_1 = 0$ (so $A = [0, 0]$) and updating
cached = 0, then finishes. - Thread 1 finally wakes up and executes
CAS(cached, 0, 10). Becausecachedis0again (matchingold_cached), the CAS succeeds (ABA!) and writes10tocached. Causingread()to return10even though $A = [0, 0]$.
I’d make an animation for this, but I’m kinda lazy rn…