I started playing with the atomics module this morning, but I hit a roadblock pretty quick. I've got two files in my project... a src file and a test file:
# src/OpenAddrTable.nim
import std/atomics
type
OpenAddrTable*[K, V] = object
primaryChunk: Atomic[seq[V]]
proc initOpenAddrTable*[K, V](): OpenAddrTable[K, V] =
result.primaryChunk.store(newSeq[V]())
# test/test1.nim
import unittest, OpenAddrTable
test "Set and retrieve values":
discard initOpenAddrTable[string, string]()
Running nimble test throws the following error:
Verifying dependencies for [email protected]
Compiling tests/test1 (from package OpenAddrTable) using c backend
tests/test1.nim(3, 6) template/generic instantiation of `test` from here
tests/test1.nim(4, 30) template/generic instantiation of `initOpenAddrTable` from here
src/OpenAddrTable.nim(8, 24) template/generic instantiation of `store` from here
~/.choosenim/toolchains/nim-1.6.2/lib/pure/concurrency/atomics.nim(378, 13) template/generic instantiation of `withLock` from here
~/.choosenim/toolchains/nim-1.6.2/lib/pure/concurrency/atomics.nim(367, 25) Error: attempting to call undeclared routine: 'testAndSet'
Tip: 1 messages have been suppressed, use --verbose to show them.
Error: Execution failed with exit code 1
... Command: .nimble/bin/nim c --noNimblePath -d:NimblePkgVersion=0.1.0 --hints:off -r --path:. tests/test1
Am I initializing the atomic wrong? I'm a bit stuck trying to figure out the next step to debug this
Thanks
Seems like you've been hit by a generic symbol resolution bug:
Here:
while location.guard.testAndSet(moAcquire): discard
It should probably be rewritten
while testAndSet(location.guard, moAcquire)
due to a limitation with method call syntax in templates.
That or you've been hit with the infamous generic sandwich bug (but I don't think so).
In any case, this is a code path that isn't really tested. I'm not sure i agree with it being in std/atomics, as it's straying away from the intent and canonical use of atomics. Furthermore it seems to suffer from the ABA problem.
In short, atomics guarantee consistency of the data before and after any operations. Concretely they guarantee that if you have 2 threads reading and writing at the same location:
This can only be guaranteed if the value has up to the native machine size, which is at most 64 on 64-bit CPUs. seq are 128 bits (pointer to the seq buffer and length/number of elements) so they can't be atomic.
Here: > while location.guard.testAndSet(moAcquire): discard > It should probably be rewritten > while testAndSet(location.guard, moAcquire)
Yup -- you're right about this. Updating the file locally resolved the issue.
This can only be guaranteed if the value has up to the native machine size, which is at most 64 on 64-bit CPUs. seq are 128 bits (pointer to the seq buffer and length/number of elements) so they can't be atomic.
Good to know. Seems like this is something that should be enforced by a compile time check in the atomics library
In any case, this is a code path that isn't really tested. I'm not sure i agree with it being in std/atomics, as it's straying away from the intent and canonical use of atomics
Which code path should I specifically be avoiding here? Anything "non Trivial" (per the language used in atomics itself)?
Now the real question is, what do you want to do?
My goal is to play with a lock free open address table implementation, but I obviously didn't get very far on that.
Concurrent lock-free datastructures are highly non-trivial and takes months to design and test and a hashtable is probably one of the most complex.
If you want a production one that has been well tested, you probably want to port the one from Facebook's Folly
If you're interested in lock-free programming, Herb Sutter 4+ hours talk: Weapons of <Atomic> Destruction is mandatory.
Then try to write a mutual exclusion (mutex) algorithm without locks using Nim atomics with one of the following Hello World of concurrency:
What mratsim says is all true, but @Nycto expressed a "messing around with"/learning context. As already observed, this is not possible with variable size string keys. So, one is already on a road of making assumptions toward other ends (simplicity, scalability, etc.).
So, it bears noting that this is an area where assumptions can reduce complexity a lot. E.g., if you support neither table resize nor delete/erase nor even checking if you have space and you have a constant sentinel key value (that cannot be a real key) then the situation can simplify to set & get in like 25 lines of C11. You just may not be able to fulfill all those assumptions in given use cases.
This is "the why" behind the design taking such effort..Adding features drops assumptions & near total redesign starts to be needed for each drop.
Atomics with sizeof(T) more than 8bytes use an implicit spinlock.
Also please use threading/atomics instead.
And that’s it. No iteration, which I’m hoping will simplify things.
I appreciate all the resources, by the way. I’m learning as I go here.
Also please use threading/atomics instead.
Thanks for the pointer, @planetis