4 ms·
Any data structure that isn't explicitly designed for concurrent access will not work when used concurrently. Since a concurrent map (aka. Dictionary aka. Hash
by alkonaut 11y ago
Any data structure that isn't explicitly designed for concurrent access will not work when used concurrently.
Since a concurrent map (aka. Dictionary aka. Hashtable) is a lot more complex and slow than a non concurrent one, it's very very unlikely that Go would ship with its standard map type being a concurrent one. It would be a huge waste.
More likely there is a separate concurrent map type. It's exactly the same in other languages with mutable collections (Java, .NET, C++, ...).
- chrisseaton 11y ago> Since a concurrent map (aka. Dictionary aka. Hashtable) is a lot more complex and slow than a non concurrent one, it's very very unlikely that Go would ship with its standard map type being a concurrent one. It would be a huge waste. We should develop a system where maps are unsynchronised by default, but when you access them from a second thread they are then converted transparently by the runtime to a thread-safe implementation.
- tomp 11y agoI'm not sure that's possible. If the first thread isn't explicitly synchronizing the memory, it won't even detect when the map was changed (made thread-safe) by the second thread! A half-solution could be using very lightweight synchronization (e.g. a MVar containing an unsynchronized map) that's later converted as you describe, but it would still incur some cynchronization overhead (even for single-threaded use).
- chrisseaton 11y agoYou could use the existing hardware memory protection mechanism, if you can do that per-thread. Each thread allocates into memory protected from other threads by default, and on a page fault caused by access from another thread it's then moved into shared memory, and converted to concurrent if needed. You could then profile allocation sites so that if a map is frequently converted to concurrent, you then start allocating it as concurrent in the first place.
- tomp 11y agoBut how would the first thread know when the map/data structure has been moved? I guess you could cause a page-fault in the first thread after the move, although that would rely on inter-CPU synchronizaiton of kernel memory maps...
- chrisseaton 11y agoThe same way a thread learns about an object being moved by the GC - change all the pointers to point to the new one when you move it. Do this in a safepoint so access to the object is not interrupted.
- tomp 11y agoSo... the second thread needs to wait for the GC in order to modify the map concurrently? I mean, it is an optimization for the most common case (single-threaded access), but it imposes a quite high penalty for concurrent access... Although I could imagine a similar "signaling" mechanism, where each thread would periodically read a single snychronized variable, to check if there's any additional "re-synchronisation" work it needs to do. But I'm guessing that CPUs are implemented that way anyways.
- chrisseaton 11y ago> So... the second thread needs to wait for the GC in order to modify the map concurrently? No nobody needs to wait for a GC, but we use the same mechanism that the GC does. > Although I could imagine a similar "signaling" mechanism, where each thread would periodically read a single synchronised variable And that's how the GC already works. Except instead of a variable normally a 'test' instruction is used on a page of memory, and instead of setting the variable, the permission on the page are changed triggering a page fault.
- tomp 11y ago> Except instead of a variable normally a 'test' instruction is used on a page of memory, and instead of setting the variable, the permission on the page are changed triggering a page fault. Which GCs do that? The only one I know is Azul's Pauseless JVM GC, but that's a kind of a special case, given that it needs support from the kernel.
- lmm 11y agoYou can't do that retroactively. And it would make performance very hard to reason about or measure.
- chrisseaton 11y agoWhy not? If a GC can move an object, why can't I change its representation? We do this all the time for code - compiling and deoptimising in a JIT - why not for data as well?
- lmm 11y agoBecause you can't reliably detect when it happens. For two threads to communicate they have to do some level of synchronization, which will inevitably have some level of performance impact. You can do actual locking (but then you might as well just synchronize the map in the first place) or you can do best-effort communication (which is good enough for warning people about bugs, but not reliable enough for production code).
- Matthias247 11y agoNo we shouldn't. I would even go further and would say if it's accessed from a different thread it should better fail immediatly with a hard error that everybody can see. Multithreading isn't something that should be implicit. Either you design your whole module/library/application around to be used from multiple threads (with all the extra work for synchronization and typically also well defined thread boundaries) or you stay with single threading.