"no, there is nothing wrong with Go’s map implementation."
"Getting your locking wrong will corrupt the internal structure of the map."
Ahem.
If you have a non-concurrency-safe map implementation in a language that's advertised as being good for concurrency, there is definitely something wrong.
From HashMap JavaDoc:
Note that the fail-fast behavior of an iterator cannot be guaranteed
as it is, generally speaking, impossible to make any hard guarantees in the
presence of unsynchronized concurrent modification. Fail-fast iterators
throw ConcurrentModificationException on a best-effort basis.
Therefore, it would be wrong to write a program that depended on this
exception for its correctness: the fail-fast behavior of iterators
should be used only to detect bugs.
So even while Java tries to find concurrency bugs, it does not promise it.
Indeed it doesn't promise it. But in practice it's very good at it - the reason they have to put that note in there is because if you made a program whose correctness depended on it, it would be a long time before you saw the bug.
That check probably comes at a performance cost that the Go standard library designers found unacceptable. You don't even need to be modifying it concurrently to read inconsistent state, it's enough to write on one thread and read on another, while the map is updating internally. So in order to prevent inconsistent reads you would have to check for concurrent access on all reads. The .NET BCL Dictionary is just like the Go one: it does no checking for you and will silently corrupt or return an inconsistent view if you access it concurrently.
The whole reason there are two implementations of the dictionary (Concurrent and Non concurrent) is that the performance cost of the concurrent implementation is too high to carry for the non-concurrent one. Depending on the cost of checking for concurrent access, a lot of the gain of using a simpler non-concurrent one could be lost.
Like you suggest you can make a cheap check that sometimes triggers an exception. Or an expensive check that always triggers on all concurrent access. As far as I can see in the java HashMap source, the concurrent modification check is actually only done for the enumerator (?) so the problem of multiple concurrent insertions, or even reading-while-inserting will never be caught anyway. Just like Go, or .NET.
A check for single thread access (which is even stricter than non-concurrent access which allows several threads as long as they aren't used concurrently) would be pretty cheap: store the thread ID on creation and then verify on reads and writes.
Failing on concurrent access otherwise on all reads and writes would basically mean that you add a lock to the write operation, and fail any reads while anyone is writing. This however is close enough to making it a full concurrent map, so it isn't worth it.
A Java Hastable is threadsafe, and is documented to be so
A Java HashMap is not threadsafe and is documented to be so, and can silently corrupt data, can go into an infinite loop etc. if you mess with it from several threads.
Both leaves you with a lot of potential for races in application logic though.
"If you have a non-concurrency-safe map implementation in a language that's advertised as being good for concurrency, there is definitely something wrong".
If we accept his premise, then the fact that "they wasn't designed for that" is no excuse. It's like selling a kids toy that has tiny choke-inducing parts. In that case, just saying: "It wasn't designed to be eaten by kids" is not really an excuse.
I think there is a big difference between "being good for concurrency" and preventing all concurrent programming problems - concurrency is hard and while go does seem to provide a lot of nice structures to make it more straightforward it can't, and doesn't appear to claim to, hide all the complexities of concurrency from developers.
First, that statement was not present in grandparent's post when the parent posted his message.
Second, that premise is completely untrue. Go, and most other languages give you more-or-less orthogonal primitives and let you combine them. It's okay for your types not to be thread safe, if by combining them with some other primitive you can make them thread safe.
Every other language does this. Some offer you a concurrent map along with a non-concurrent map. For many reasons I won't get into, Go only has one kind of map and lets the user do the rest (which is an extremely easy idiom in Go). Note that even though many languages conveniently offer concurrent maps, no languages with mutable state that I know of offer concurrent integer and concurrent structs. The user is still responsible for ensuring the safety of those.
This is perfectly fine because the grandparent's premise is wrong. In concurrent language, by far the most common case is by data to be owned by a goroutine/thread/whatever. It's very easy to reason about code this way, and it's the way you are encouraged to write code.
Only when you need to share data you need to worry about concurrency-safety, and in that scenario you have available all the tools to ensure it.
A lot of comments that just seem to ignore the fact that noone would actually want standard collections to be thread safe! Concurrent collections are slow. That's why class libraries use different types for a therad safe collection and a regular non-thread safe collection. If you are using concurrency you have to use concurrent collections.
You could argue that if most Go code is concurrent then the regular collections should be the thread safe ones, and for code that is known to be single threaded there would be simpler/faster non-concurrent collections. That is a completely valid argument to make, but I think that design would be too confusing for new Go developers, since in most other languages the standard collections are the non-concurrent ones, and the concurrent ones are special, and it's an explicit design goal of Go to be easy to adopt coming from another language.
They're really not though. Java has ConcurrentHashMap and isn't slow. Clojure has its persistent HashMap and it isn't slow. Scala has, TWO (?) concurrent hash maps in its core and neither is slow.
You know, two thirds of the way through the second decade of the 21st century, it's okay to spend a few cycles not corrupting your data structures.
There are both memory and performance considerations. For a server/db web application this may not be a problem, but for e.g. some logic in a game engine that runs every frame on a mobile device, then using 16 extra locks per map for example isn't a good idea. Nor is having 5% performance overhead.
I can agree with an argument that thread-safe should be default and specialized/fast collections should be optional though.
That's just not true. Regardless of language there is always a portion of the code where you need to be careful with performance. I have spent endless hours tweaking map performance in .NET, for example.
Maps are not concurrency-safe, you know what else isn't? Integers, floats, pointers, structs. And not only in Go, but in pretty much almost all languages with mutable state, like C and C++.
The map implementation in Go is consistent with the rest of the language, plus it allows for great performance under some rather common scenarios.
But I guess it's fashionable to snark on message boards than rather understand all these facts.
I apologise for expecting better of language designers. After all, the solutions to these sorts of issues has only been around for a couple of decades. Far too soon.
All the language designer can do is throw in a lock that you may or may not need if you're already locking properly. ConcurrentModificationException is nice, but comes at a performance cost.
This is a library thing, not a language thing. And it's a performance tradeoff: they could have shipped with a concurrent map only, that is 1/10 as fast as the current one, but never causes a data race. However everyone that isn't doing anything concurrently would be paying for it. Not very clever. I trust the class library designers thought this through. They reached the same conclusion as pretty much every other library designer in every other language. For the same reasons.
You are not expecting better. You are expecting worse. Plenty of use cases involve maps without concurrent modification, e.g., when used as a local variable. Your "better" version of maps will slow down all of them.
Actually Java guarantees atomic accesses for integer-sized fields and references at the language level. They aren't race-free, but they are atomic. And really, atomicity is the main property that the OP had in mind when posting. Since you mentioned C++, it also does guarantee certain-sized certain-alignment loads and stores are atomic.
In Java there is also the plethora of thread safe data structures available in java.util.concurrent. They are written by experts and are pretty darn fast (TM). It might have been reasonable to use one of these as the basis for Go map implementations, but the language designers chose to assume unsynchronized access to shared maps is a design bug in applications.
Java chooses safety over performance. It is not free to check for concurrent access in a non-concurrent structure. In some languages, we let the programmer take on the choice of which costs to bear. There is not very much that I like about Go, but there is nothing wrong with having non-concurrent data structures that are documented as such and fail in non-defined ways when there is shared data access.
Thanks for the reference, I knew about C11 atomic types, and, I should have use a better phrasing. Note that C11 atomics are still not applicable to multi-word aggregate types, like structs. You'd use atomics in C11 (in the type system), for what you'd use sync/atomic (like other poster mentioned) in Go (outside the type system).
32 bit data types are read and written atomically on the CLR. Pointers are read/written atomicly on most ANY platform, or you couldn't build any kind of higher level concurrency abstraction. If not, the language could never provide memory safety.
You need a way to do atomic reads and writes, but you don't need to have atomic types. In Go you just use sync/atomic which implements atomicity outside the type system.
When you use "regular" operations, you don't get atomicity, but what you get is well-defined, and explained here: https://golang.org/ref/mem.
I see nothing wrong with how Go's map implementation was described. Go has never claimed to be completely safe for concurrent operations. Deadlocks, inconsistent state, etc are more than easy to accomplish. But, it still stands up to a "good for concurrency" claim by offering nice primitives for writing concurrent code, a race detector and explicitly stating in the stdlib documentation which libraries are thread-safe -- libraries are to be considered not safe unless explicitly said to be.
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++, ...).
> 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.
I'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).
You 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.
But 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...
The 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.
So... 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.
> 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.
> 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.
Also note that Azul almost certainly has the same mechanism to do things like stop the world for dynamic class loading, even if it isn't using it for GC when running the pauseless collector.
Why 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?
Because 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).
No 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.
I'm increasingly convinced that Go is the new PHP, designed and used by the kind of people who know just enough to be incredibly dangerous to themselves and everyone else they touch.
I don't understand why someone would write a blog post about a collection type not being thread safe? Why not just look at the documentation and simply confirm that it isn't thread safe?
Edit: Ok one reason could be that the documentation sucks and there are no mentions of the concurrency guarantees of the standard library types...
Possibly because the Go "authorities" are now trying to attract the kind of programmers who need "trigger warnings" and "safe spaces", for some reason. Just look at the new community CoC. I apologize if this constitutes a micro- or nano-aggression.
More seriously, it's probably just a frequent mistake and they try to educate people proactively to help code quality in the long run.
Edit: the non-atomic map updates are mentioned in the FAQ, but you're right, the documentation could be improved in that regard (possibly triggering many criticisms of the language from people who've never used it, just browsed the docs for reasons not to use it).
You say that, while also suggesting that Java's best effort ConcurrentModificationException (something that will be thrown if you're lucky) is better. Suggests to me that you know just enough to be dangerous.
Java's ConcurrentModificationException shows up very quickly if you test at all (probably 99% of the time). It is very good at helping beginners not make these mistakes.
Javas HashMap<K,V> has no checking for concurrent modification at all, it's only a check that is made during Iteration In the internal HashIterator type. It only checks that the collection wasn't modified while that iterator was iterating.
There is nothing there to prevent the HashMap itself from corrupting completely with multiple writers, or from data racing while fetching single items on multiple threads.
So there is no way you can use the ConcurrentModificationException as a way of ensuring that your HashMap is actually working in a concurrent scenario, it only handles one scenario: reads, and even only reads when iterating.
A concurrent map is the top of my wants list for go by a long stretch. The next thing on that list is a high performance concurrent queue. That these things aren't available is a direct result of the decision to not support user defined generics in go.
A channel is a simple abstraction around a giant mutex. It does not scale throughput very well and has terrible latency performance to boot.
Something like the disruptor (https://lmax-exchange.github.io/disruptor/) is more along the lines of what I was thinking of. Without generics support you have to write it over and over again for each use case.
A go channels implemented using a mutex? I would be surprised if that was the case (but it might be). I would imagine such a fundamental construct built into the language would be lock-free.
The other reason: things inside maps are often pointer types with mutable data. Even if access to the map is properly locked, if two threads take a pointer out of it and directly or indirectly keep a reference (for example, re-slicing a slice without copying it), then one can stomp on the data the other is reading.
The fixes for this are subtle and annoying. Either you have to lock around your data, make it somehow immutable, or force copying rather than referencing (by making it "value" data).
Go would really benefit from a port of Clojure's data structures.
You need to make sure that once you've done with the item and passed it on, you don't have any overt, tacit, or deeply-buried pointers into the item you just let go of.
Golang devs should have a look at Clojure and it's `core.async` library. It works very similarly to Go (heavily inspired by the good stuff), but all data structures are persistent, meaning you will never have problems with concurrent mutations (because there there are no mutations in the API, only internally).
I recommend Go users to install the boot utility, and playing around with Clojure & core.async. These communities can share many things.
It's been a while since I used Clojure, so I apologize if what I'm saying is wrong or out of date. Having used both Clojure and Go there are some significant differences in how coroutines work in each.
For instance, in Go making a blocking system call inside of a goroutine "just works" as Go will create additional goroutines as necessary. But if you do the equivalent in Clojure, you risk thread starvation.
"However if you are using go blocks and blocking IO calls you're in trouble. You will in fact often get worse performance than using threads (in the normal case) since you will quickly hog all the threads in the go block thread pool and block out any other work! ... Since the go block thread pool is quite small, it's easy to block all the threads and thus stopping all 'go processing'."[0]
Now there are some ways around this; I think that you can use promises for blocking IO inside of a Clojure coroutine. But this is one area where you don't have to worry about this kind of thing in Go, even if you do have to know that the default map implementation isn't thread safe. :)
Its problematic to mix blocking and message-based paradigms together. Its kind of worse than either one alone, because added complexity. Yet its so hard to come up with an entirely blockless design, especially since OSs won't cooperate (rarely have non-blocking APIs throughout).
Which types in Go are goroutine safe? Do we need to use sync.Mutex for all global variables which are read and written in goroutines? My understanding is only read-only variables are goroutine safe.
80 comments
[ 5.5 ms ] story [ 137 ms ] thread"Getting your locking wrong will corrupt the internal structure of the map."
Ahem.
If you have a non-concurrency-safe map implementation in a language that's advertised as being good for concurrency, there is definitely something wrong.
Do you know what they do? They throw a ConcurrentModificationException.
Do you know what they don't do? Silently corrupt themselves.
So even while Java tries to find concurrency bugs, it does not promise it.
The whole reason there are two implementations of the dictionary (Concurrent and Non concurrent) is that the performance cost of the concurrent implementation is too high to carry for the non-concurrent one. Depending on the cost of checking for concurrent access, a lot of the gain of using a simpler non-concurrent one could be lost.
A check for single thread access (which is even stricter than non-concurrent access which allows several threads as long as they aren't used concurrently) would be pretty cheap: store the thread ID on creation and then verify on reads and writes.
Failing on concurrent access otherwise on all reads and writes would basically mean that you add a lock to the write operation, and fail any reads while anyone is writing. This however is close enough to making it a full concurrent map, so it isn't worth it.
https://github.com/golang/go/commit/50c5042047be3af36e7bb478...
A Java HashMap is not threadsafe and is documented to be so, and can silently corrupt data, can go into an infinite loop etc. if you mess with it from several threads.
Both leaves you with a lot of potential for races in application logic though.
"If you have a non-concurrency-safe map implementation in a language that's advertised as being good for concurrency, there is definitely something wrong".
If we accept his premise, then the fact that "they wasn't designed for that" is no excuse. It's like selling a kids toy that has tiny choke-inducing parts. In that case, just saying: "It wasn't designed to be eaten by kids" is not really an excuse.
Second, that premise is completely untrue. Go, and most other languages give you more-or-less orthogonal primitives and let you combine them. It's okay for your types not to be thread safe, if by combining them with some other primitive you can make them thread safe.
Every other language does this. Some offer you a concurrent map along with a non-concurrent map. For many reasons I won't get into, Go only has one kind of map and lets the user do the rest (which is an extremely easy idiom in Go). Note that even though many languages conveniently offer concurrent maps, no languages with mutable state that I know of offer concurrent integer and concurrent structs. The user is still responsible for ensuring the safety of those.
This is perfectly fine because the grandparent's premise is wrong. In concurrent language, by far the most common case is by data to be owned by a goroutine/thread/whatever. It's very easy to reason about code this way, and it's the way you are encouraged to write code.
Only when you need to share data you need to worry about concurrency-safety, and in that scenario you have available all the tools to ensure it.
Java does for integer http://docs.oracle.com/javase/8/docs/api/java/util/concurren...
You can find similar classes in the java.util.concurrent.atomic package. http://docs.oracle.com/javase/8/docs/api/java/util/concurren...
I'm not sure what requirements you have for a concurrent struct, but Java has classes to atomically manipulate int and long fields of a class.
I'm not arguing your general point (in fact, I agree with it), I'm just supplying some extra information of a language that you apparently don't know.
You could argue that if most Go code is concurrent then the regular collections should be the thread safe ones, and for code that is known to be single threaded there would be simpler/faster non-concurrent collections. That is a completely valid argument to make, but I think that design would be too confusing for new Go developers, since in most other languages the standard collections are the non-concurrent ones, and the concurrent ones are special, and it's an explicit design goal of Go to be easy to adopt coming from another language.
You know, two thirds of the way through the second decade of the 21st century, it's okay to spend a few cycles not corrupting your data structures.
I can agree with an argument that thread-safe should be default and specialized/fast collections should be optional though.
Maps are not concurrency-safe, you know what else isn't? Integers, floats, pointers, structs. And not only in Go, but in pretty much almost all languages with mutable state, like C and C++.
The map implementation in Go is consistent with the rest of the language, plus it allows for great performance under some rather common scenarios.
But I guess it's fashionable to snark on message boards than rather understand all these facts.
In Java there is also the plethora of thread safe data structures available in java.util.concurrent. They are written by experts and are pretty darn fast (TM). It might have been reasonable to use one of these as the basis for Go map implementations, but the language designers chose to assume unsynchronized access to shared maps is a design bug in applications.
Yet manages to be faster than golang.
Also, the two need not be mutually exclusive as you're implying.
Not that I disagree with your comment in general, but atomic values do exist in many languages.
When you use "regular" operations, you don't get atomicity, but what you get is well-defined, and explained here: https://golang.org/ref/mem.
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++, ...).
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.
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).
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.
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.
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.
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.
http://dl.acm.org/authorize.cfm?key=N98613
Also note that Azul almost certainly has the same mechanism to do things like stop the world for dynamic class loading, even if it isn't using it for GC when running the pauseless collector.
And Section 4 and 5 of this paper talks a bit more about it's implemented http://chrisseaton.com/rubytruffle/icooolps15-safepoints/saf....
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.
Edit: Ok one reason could be that the documentation sucks and there are no mentions of the concurrency guarantees of the standard library types...
More seriously, it's probably just a frequent mistake and they try to educate people proactively to help code quality in the long run.
Edit: the non-atomic map updates are mentioned in the FAQ, but you're right, the documentation could be improved in that regard (possibly triggering many criticisms of the language from people who've never used it, just browsed the docs for reasons not to use it).
There is nothing there to prevent the HashMap itself from corrupting completely with multiple writers, or from data racing while fetching single items on multiple threads.
So there is no way you can use the ConcurrentModificationException as a way of ensuring that your HashMap is actually working in a concurrent scenario, it only handles one scenario: reads, and even only reads when iterating.
That's called a channel in Go.
Something like the disruptor (https://lmax-exchange.github.io/disruptor/) is more along the lines of what I was thinking of. Without generics support you have to write it over and over again for each use case.
Lines 28, 152, 401
The fixes for this are subtle and annoying. Either you have to lock around your data, make it somehow immutable, or force copying rather than referencing (by making it "value" data).
Go would really benefit from a port of Clojure's data structures.
https://golang.org/doc/codewalk/sharemem/
You need to make sure that once you've done with the item and passed it on, you don't have any overt, tacit, or deeply-buried pointers into the item you just let go of.
I recommend Go users to install the boot utility, and playing around with Clojure & core.async. These communities can share many things.
For instance, in Go making a blocking system call inside of a goroutine "just works" as Go will create additional goroutines as necessary. But if you do the equivalent in Clojure, you risk thread starvation.
"However if you are using go blocks and blocking IO calls you're in trouble. You will in fact often get worse performance than using threads (in the normal case) since you will quickly hog all the threads in the go block thread pool and block out any other work! ... Since the go block thread pool is quite small, it's easy to block all the threads and thus stopping all 'go processing'."[0]
Now there are some ways around this; I think that you can use promises for blocking IO inside of a Clojure coroutine. But this is one area where you don't have to worry about this kind of thing in Go, even if you do have to know that the default map implementation isn't thread safe. :)
[0] http://martintrojer.github.io/clojure/2013/07/07/coreasync-a...
Which types in Go are goroutine safe? Do we need to use sync.Mutex for all global variables which are read and written in goroutines? My understanding is only read-only variables are goroutine safe.