Standard library · Time and concurrency

atomic

A counter and a flag that several threads can change safely without taking a lock by hand.

import atomic

For a simple counter that several threads increment, you do not have to build a lock yourself: I64 in this package does each operation in one indivisible step. CompareAndSwap is the base of most lock-free algorithms: it changes the value only if it is still the one you expected.

With gcc, clang and the LLVM backend each operation is one of the processor's atomic instructions. Under tcc, which lacks them, each cell is protected by a small lock instead; the results are the same, only slower.

There are two types: I64, a shared 64-bit whole number, and Flag, a shared true or false. Both are small handles to a cell on the heap, so passing one to a function or a thread by value shares the same cell. For anything bigger than one value, use sync; to pass values between threads, chan.

The things people get wrong:

  • Using a cell that was never created. atomic.I64 {} has no cell and crashes on the first Add; make it with NewI64 or NewFlag, for a global at the top of main.
  • Combining two operations. if Load(a) < 10: Add(a, 1) end is two steps, and another thread can act in between; that is what CompareAndSwap in a loop is for.
  • Destroying too early. DestroyI64 frees the cell for every copy of the handle; call it once, after every thread that uses it has been joined.

There is no subtract: Add(a, -1) counts down.

Hand out unique numbers

Add returns the value after the addition, and no two callers can get the same one. That makes it a ready made source of unique ids, ticket numbers or slot indexes, shared by any number of threads with no lock in sight.

atomic-guide-ids.salam
import atomic

mut next id := atomic.I64 {}
mut taken := Vector {} as Vector<i64>

func hand out():
    repeat 100:
        id := atomic.Add(next id, 1)
        taken.Set(id as int - 1, taken.Get(id as int - 1) + 1)
    end
end

func main:
    next id = atomic.NewI64(0)
    repeat 400:
        taken.Push(0)
    end
    a := spawn(hand out)
    b := spawn(hand out)
    c := spawn(hand out)
    d := spawn(hand out)
    join(a)
    join(b)
    join(c)
    join(d)
    mut twice := 0
    each n in taken:
        if n != 1:
            twice++
        end
    end
    println "last id:", atomic.Load(next id)
    println "ids given out more than once:", twice
    taken.Free()
    atomic.DestroyI64(next id)
end
Outputlast id: 400 ids given out more than once: 0

Four threads took 100 ids each, and every id from 1 to 400 was given out exactly once. Each thread then writes only to the slot its own id names, which is why the vector needs no lock either.

Update with CompareAndSwap

Some updates are not a plain addition: "keep the largest value seen so far" has to read the value, decide, and write. Doing that in two steps would let another thread slip in between. The answer is a loop: read the value, compute the new one, and ask CompareAndSwap to store it only if the value has not changed meanwhile. If it has, read again and retry.

atomic-guide-max.salam
import atomic

mut highest := atomic.I64 {}

func record(value: i64):
    mut seen := atomic.Load(highest)
    until value > seen:
        if atomic.CompareAndSwap(highest, seen, value):
            ret
        end
        seen = atomic.Load(highest)
    end
end

func low readings():
    repeat 500 in i:
        record((i * 7 % 900) as i64)
    end
end

func high readings():
    repeat 500 in i:
        record((i * 13 % 1000) as i64)
    end
end

func main:
    highest = atomic.NewI64(0)
    a := spawn(low readings)
    b := spawn(high readings)
    join(a)
    join(b)
    println "highest reading:", atomic.Load(highest)
    atomic.DestroyI64(highest)
end
Outputhighest reading: 993

The loop also stops as soon as the stored value is already at least as large, so most calls do not write at all.

A stop signal for a worker

A Flag is the simplest way to tell a long running thread to finish: the worker checks it each round, and the main thread sets it when it is time. A plain bool global is not enough, because nothing guarantees the worker ever sees the change.

atomic-guide-stop.salam
import atomic
import sync

mut stop := atomic.Flag {}
mut rounds := atomic.I64 {}

func worker():
    until not atomic.Get(stop):
        atomic.Add(rounds, 1)
        sync.SleepMs(1)
    end
end

func main:
    stop = atomic.NewFlag(false)
    rounds = atomic.NewI64(0)
    t := spawn(worker)
    until atomic.Load(rounds) < 20:
        sync.SleepMs(1)
    end
    atomic.Set(stop, true)
    join(t)
    println "worker ran at least 20 rounds:", atomic.Load(rounds) >= 20
    println "stop flag:", atomic.Get(stop)
    atomic.DestroyFlag(stop)
    atomic.DestroyI64(rounds)
end
Outputworker ran at least 20 rounds: true stop flag: true

Only the first one wins

TestAndSet turns the flag on and tells you whether you were the one who did it. When several threads race for one job, such as sending a single alert or doing a one time cleanup, exactly one of them gets true.

atomic-guide-first.salam
import atomic

mut claimed := atomic.Flag {}
mut winners := atomic.I64 {}
mut losers := atomic.I64 {}

func attempt claim():
    if atomic.TestAndSet(claimed):
        atomic.Add(winners, 1)
    else:
        atomic.Add(losers, 1)
    end
end

func main:
    claimed = atomic.NewFlag(false)
    winners = atomic.NewI64(0)
    losers = atomic.NewI64(0)
    mut threads := Vector {} as Vector<i64>
    defer threads.Free()
    repeat 8:
        threads.Push(spawn(attempt claim))
    end
    each t in threads:
        join(t)
    end
    println "winners:", atomic.Load(winners), "losers:", atomic.Load(losers)
    atomic.DestroyFlag(claimed)
    atomic.DestroyI64(winners)
    atomic.DestroyI64(losers)
end
Outputwinners: 1 losers: 7

Atomic or a lock?

An atomic value is right when the shared state is one number or one flag. As soon as two values must change together, such as a balance and a history, use a sync.Mutex: two atomic operations in a row are not atomic together. For setup that must run once, sync.Once is clearer than a hand made flag.

JobFunction
Count events from many threadsAdd(a, 1)
Take the next free numberAdd, using its result
Read the latest value for a reportLoad
Reset and get the old totalSwap(a, 0)
Any read, compute, write updateCompareAndSwap in a loop
Tell a thread to stopFlag with Set and Get
Let exactly one thread do somethingTestAndSet

Types

I64

struct I64
A 64-bit whole number shared between threads.
NameTypeDescription
celli64*The address of the value.
musync.MutexThe internal lock.
atomic-I64.salam
import atomic

mut counter := atomic.I64 {}

func worker():
    repeat 1000:
        atomic.Add(counter, 1)
    end
end

func main:
    counter = atomic.NewI64(0)
    a := spawn(worker)
    b := spawn(worker)
    join(a)
    join(b)
    println atomic.Load(counter)
    atomic.Store(counter, 10)
    println atomic.Swap(counter, 20), atomic.Load(counter)
    println atomic.CompareAndSwap(counter, 20, 30), atomic.CompareAndSwap(counter, 20, 40), atomic.Load(counter)
    atomic.DestroyI64(counter)
    flag := atomic.NewFlag(false)
    println atomic.TestAndSet(flag), atomic.TestAndSet(flag), atomic.Get(flag)
    atomic.Set(flag, false)
    println atomic.Get(flag)
    atomic.DestroyFlag(flag)
end
Output2000 10 20 true false 30 true false true false

Flag

struct Flag
A true or false flag shared between threads.
NameTypeDescription
celli64*The address of the value.
musync.MutexThe internal lock.

The example for this item is shown with the ones above: atomic-I64.salam

Functions

NewI64

func NewI64(v: i64): I64
A new cell with an initial value.

The example for this item is shown with the ones above: atomic-I64.salam

Load

func Load(a: I64): i64
Reads the current value.

The example for this item is shown with the ones above: atomic-I64.salam

Store

func Store(a: I64, v: i64)
Writes a new value.

The example for this item is shown with the ones above: atomic-I64.salam

Add

func Add(a: I64, delta: i64): i64
Adds delta and returns the new value.

The example for this item is shown with the ones above: atomic-I64.salam

Swap

func Swap(a: I64, v: i64): i64
Writes a new value and returns the old one.

The example for this item is shown with the ones above: atomic-I64.salam

CompareAndSwap

func CompareAndSwap(a: I64, expected: i64, next: i64): bool
If the current value equals expected, sets it to next and returns true; otherwise it leaves it alone.

The example for this item is shown with the ones above: atomic-I64.salam

DestroyI64

func DestroyI64(a: I64)
Releases the cell.

The example for this item is shown with the ones above: atomic-I64.salam

NewFlag

func NewFlag(v: bool): Flag
A new flag with an initial value.

The example for this item is shown with the ones above: atomic-I64.salam

Get

func Get(f: Flag): bool
The flag's value.

The example for this item is shown with the ones above: atomic-I64.salam

Set

func Set(f: Flag, v: bool)
Sets the flag's value.

The example for this item is shown with the ones above: atomic-I64.salam

TestAndSet

func TestAndSet(f: Flag): bool
If the flag is off, turns it on and returns true; if it was already on, returns false. Only one thread wins.

The example for this item is shown with the ones above: atomic-I64.salam

DestroyFlag

func DestroyFlag(f: Flag)
Releases the flag.

The example for this item is shown with the ones above: atomic-I64.salam