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 firstAdd; make it withNewI64orNewFlag, for a global at the top ofmain. - Combining two operations.
if Load(a) < 10: Add(a, 1) endis two steps, and another thread can act in between; that is whatCompareAndSwapin a loop is for. - Destroying too early.
DestroyI64frees 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.
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)
endFour 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.
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)
endThe 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.
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)
endOnly 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.
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)
endAtomic 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.
| Job | Function |
|---|---|
| Count events from many threads | Add(a, 1) |
| Take the next free number | Add, using its result |
| Read the latest value for a report | Load |
| Reset and get the old total | Swap(a, 0) |
| Any read, compute, write update | CompareAndSwap in a loop |
| Tell a thread to stop | Flag with Set and Get |
| Let exactly one thread do something | TestAndSet |
Types
I64
struct I64| Name | Type | Description |
|---|---|---|
cell | i64* | The address of the value. |
mu | sync.Mutex | The internal lock. |
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)
endFlag
struct Flag| Name | Type | Description |
|---|---|---|
cell | i64* | The address of the value. |
mu | sync.Mutex | The internal lock. |
The example for this item is shown with the ones above: atomic-I64.salam
Functions
NewI64
func NewI64(v: i64): I64The example for this item is shown with the ones above: atomic-I64.salam
Load
func Load(a: I64): i64The example for this item is shown with the ones above: atomic-I64.salam
Store
func Store(a: I64, v: i64)The example for this item is shown with the ones above: atomic-I64.salam
Add
func Add(a: I64, delta: i64): i64delta 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): i64The example for this item is shown with the ones above: atomic-I64.salam
CompareAndSwap
func CompareAndSwap(a: I64, expected: i64, next: i64): boolexpected, 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)The example for this item is shown with the ones above: atomic-I64.salam
NewFlag
func NewFlag(v: bool): FlagThe example for this item is shown with the ones above: atomic-I64.salam
Get
func Get(f: Flag): boolThe example for this item is shown with the ones above: atomic-I64.salam
Set
func Set(f: Flag, v: bool)The example for this item is shown with the ones above: atomic-I64.salam
TestAndSet
func TestAndSet(f: Flag): boolThe example for this item is shown with the ones above: atomic-I64.salam
DestroyFlag
func DestroyFlag(f: Flag)The example for this item is shown with the ones above: atomic-I64.salam