Sterling has too many projects

Blogging about Raku programming, microcontrollers & electronics, 3D printing, and whatever else...

Compare-and-swap Your Scalars

Previously, I discussed the compare-and-swap operation as an operation to perform on atomicint variables. That’s just the tip of the iceberg. While most of the atomic emoji ⚛️ operators are only for atomicints, the cas function, atomic-fetch (or prefix ⚛️ operator), and atomic-assign (or ⚛️= operator) can all be used on any kind of Scalar variable.

First, we need to make sure we know what a Scalar is. In Raku, every variable name is associated with a container. If you want the full description of how that works, I recommend reading the language docs on Containers. For our purpose it will suffice to say that almost every regular variable starting with $ sigil is contained by a Scalar. If you do something special to initialize such a variable, it may not have a Scalar container.

Here’s a quick example that will should clarify enough for our purposes here:

# Any typical $ sigil variable represents a Scalar container
my $value = 42;

# Each index of an array is normally a Scalar container
my @array;
@array[0] = 10;

# Binding directly to Int, so this is NOT a Scalar.
my $constant := 100; # NOT Scalar

# Binding direclty on an array index is also NOT a Scalar.
@array[1] := 20; # NOT Scalar

# Proxy containers are NOT Scalar containers
my $special := Proxy.new(
    FETCH => method () { 10 }
    STORE => method ($v) { 10 }
)

If you try to use cas on a non-Scalar container, Raku will throw an exception that says something like “A Proxy container does not know how to do atomic compare and swap” so it should be pretty obvious what went wrong in most instances.

Enough of that. How do you use it? Let’s try an example:

my $atomic-string = '';
start {
    loop {
        cas $atomic-string, -> $v {
            if $v.ends-with('A') { "$vB" }
            else { $v }
        }
        sleep rand;
    }
}
start {
    loop {
        cas $atomic-string, -> $v {
            if $v eq '' || $v.ends-with('B') { "$vA" }
            else { $v }
        }
        sleep rand;
    }
}
start {
    loop {
        given ⚛️$atomic-string {
            if .ends-with('B') && .chars %% 10 { .say }
        }
        sleep rand;
    }
}

sleep 10;

This is kind of a useless program, but it demonstrates what you can do. We have just a regular variable storing an empty string to start. We then have three tasks running concurrently. The first uses a cas operation to see if the string ends with an “A” and adds a “B”, if so. The second uses the cas operation to see if the string is empty or ends with a “B” and adds a “A”, if so. The third will only output the string if it ends with a “B” and has a length that is a multiple of 10. It runs for 10 seconds and quits. It is an inefficient program and one run on my laptop had output like this:

ABABABABAB
ABABABABAB
ABABABABAB
ABABABABABABABABABAB
ABABABABABABABABABABABABABABAB

Essentially, every Scalar has access to an atomicint internally, which is used to lock the scalar while the change is being made. These can be more efficient than using Lock objects. When contention for access to some data is high, cas is likely to lose because each thread trying to work with the data will be busy waiting. However, when contention for the item is low and you don’t need to efficiently block and resume threads, a cas operation can be more efficient. It may require some AB testing of each approach to determine which is most efficient for your particular case.

Later this month, I plan to demonstrate in greater detail how this cas operation can be used to implement data structures without locks. So we will return to this topic again soon.

Cheers.