What’s faster than locks? Compare-and-swap. Modern CPUs have multiple cores. As such, all modern CPUs must have tools for performing absolutely atomic operations to allow those multiple cores to work together. One of those operations is the compare-and-swap or cas operation.

In the abstract, a cas operation takes three arguments, a variable to modify, a given value, and a new value. The variable is set to the new value modified only if the current value held by the variable is equal to the given value. And this is performed as a single operation guaranteed to be safe from interference by any other concurrent operation. Along the way, the system sets a flag marking the success or failure of the operation. If the variable has a different value than expected, the variable is left unchanged and the operation fails. To complete an atomic change, you repeatedly run a calculation and end with a cas operation until it succeeds. That may not sound very efficient, but it turns out that in most cases, it is faster than locks.

Raku provides direct access to this operation through the cas function on the atomicint type and also through a number of operators which help you perform these atomic changes.

To demonstrate one possible use of atomicint, let’s first consider the ATM problem. Two people have access to a bank account. Let’s say the account has $1000 in it at the beginning of the day. Person One withdraws $100 from an ATM in city center and Person Two deposits $250 at the ATM in the airport. At the end of the day, we clearly want the new balance to be $1150. However, if both transactions happen simultaneously, that is not guaranteed unless we take some care to guarantee it.

Let’s start by writing our code in the naïve way:

my Int $balance = 1000;
start { $balance = $balance - 100 } # one
start { $balance = $balance + 250 } # two
say $balance;

Unfortunately, it is now possible to end up with a balance that is different form $1150. This is because if these two tasks actually run simultaneously, they perform operations that could be interleaved like this:

1. Block one reads a $balance of 1000.
2. Block two reads a $balance of 1000.
3. Block one subtracts 100 from 1000 to get 900.
4. Block two adds 250 to 1000 to get 1250.
5. Block one sets the $balance to 900 for one.
6. Block two sets the $balance to 1250 for two.

The read and write operations must be executed sequentially in order for this to code to work correctly. We could use a lock or semaphore or some other traditional construct to form a critical section around modifications to the variable, but these are typically pretty dang slow.

Instead, we can use a cas operation to perform the operation sequentially. So, if we rewrite the above code using atomicint we end up with this:

my atomicint $balance = 1000;
start { $balance ⚛️= ⚛️$balance - 100 } # one
start { $balance ⚛️= ⚛️$balance + 250 } # two
say $balance;

Here the result will always be the expected 1150. Let’s assume these two tasks run simultaneously exactly as before, but the final assignment is a compare-and-swap operation rather than a regular set. It would play out like this:

1. Block one reads a $balance of 1000.
2. Block two reads a $balance of 1000.
3. Block one subtracts 100 from 1000 to get 900.
4. Block two adds 250 to 1000 to get 1250.
5. Block one performs compare-and-swap $balance from 1000 to 900 and succeeds.
6. Block two performs compare-and-swap $balance from 1000 to 1250 and fails.
7. Block two reads a $balance of 900.
8. Block two adds 250 to 900 to get 1150.
9. Block two performs compare-and-swap $balance from 900 to 1150 and succeeds.

The extra steps 7-9 occur because in a cas operation, the resolution of failure requires repeating the operation until it succeeds. Unless the levels of contention for write to a single variable are extreme, this should not lead to any task failing indefinitely.

If you don’t like emoji in your code, that’s fine. There’s a Texas function for performing each of the operations provide by an atomic emoji operator. The atomicint provides the following operations:

• atomic-assign or ⚛️=
• atomic-fetch or the ⚛️ prefix for performing atomic reads of the value
• atomic-fetch-inc or ⚛️++ postfix
• atomic-fetch-dec or ⚛️– postfix
• atomic-fetch-add or ⚛️+=
• atomic-fetch-sub or ⚛️-=
• atomic-inc-fetch or ++⚛️ prefix
• atomic-dec-fetch or –⚛️ prefix
• cas

Let’s quickly consider the cas function itself which underlies the implementation for the other operators. This operation allows you to implement any operation that involves a compare-and-swap of an atomicint. It two basic forms and just to demonstrate how they work, we can re-implement our ATM problem from above using both forms.

First, consider this program using the cas function:

my atomicinc $balance = 1000;
sub update-balance($change-by) {
    my $new-balance;
    loop {
        my $old-balance = $balance;
        $new-balance = $balance + $change-by;
        if cas($balance, $old-balance, $new-balance) == $old-balence {
            last;
        }
    }
    return $new-balance;
}
start update-balance(-100); # one
start update-balance(250);  # two
say $balance;

This is functionally identical, though more verbose, than the operation above. This is basically giving you direct access to the cas operation itself and lets you control the number of retries and the specific operation performed. This function works something like this, though the entire operation is atomic:

multi sub cas(atomicint $target is rw, int $expected-value, int $new-value --> int) {
    my int $seen = $target;
    if $seen == $expected-value {
        $target = $new-value;
    }
    return $seen;
}

That means it will return the value it saw in every case, but will have changed the value stored in the target when what it saw matches what you expected.

There is a second version of this method, which can help streamline your code a bit by performing the looping for you. To write the ATM problem yet again, we can also write it like this:

my atomicint $balance = 1000;
sub update-balance($change-by) {
    cas $balance, -> $seen-value { $seen-value + $change-by }
}
start update-balance(-100); # one
start update-balance(250);  # two
say $balance;

This greatly shortens the code required to implement this operation. It does so by performing the given operation repeatedly in a loop until the cas operation succeeds. In this case, the cas function is defined like this, but again, using atomic operations where appropriate:

multi sub cas(atomicint $target is rw, &operation) {
    loop {
        my int $seen = $target;
        my $new-value = operation($seen);
        if $seen == $target { # still equal?
            $target = $new-value;
        }
        return $new-value;
    }
}

Be aware that the cas subroutine alternative that takes a function returns the new value that was set, while the cas that takes two integers returns the value that was seen. That is, this second and compact form treats the return value like an assignment operation, but the way the other form works does not allow for that treatment.

I’d really like to share with you how cas can be used on any scalar value in Raku, but this post has already gone long. I will cover that later this Advent.

Cheers.