Are Go maps sensitive to data races? • Hacker News Board

Re: Are Go maps sensitive to data races?

#61

Post by tomp » Mon, Dec 07, 2015, 1:05 PM UTC

chrisseaton wrote: post #48

tomp wrote: post #42

Earlier quoted context omitted.

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 alloca…

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...

Re: Are Go maps sensitive to data races?

#62

Post by chrisseaton » Mon, Dec 07, 2015, 1:05 PM UTC

lmm wrote: post #59

chrisseaton wrote: post #34

Earlier quoted context omitted.

> 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…

You can't do that retroactively. And it would make performance very hard to reason about or measure.

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?

Re: Are Go maps sensitive to data races?

#63

Post by chrisseaton » Mon, Dec 07, 2015, 1:08 PM UTC

tomp wrote: post #61

chrisseaton wrote: post #48

Earlier quoted context omitted.

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 alloca…

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.

Re: Are Go maps sensitive to data races?

#64

Post by tomp » Mon, Dec 07, 2015, 1:19 PM UTC

chrisseaton wrote: post #63

tomp wrote: post #61

Earlier quoted context omitted.

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.

Re: Are Go maps sensitive to data races?

#65

Post by chrisseaton » Mon, Dec 07, 2015, 1:29 PM UTC

tomp wrote: post #64

chrisseaton wrote: post #63

Earlier quoted context omitted.

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"…

> 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.

Re: Are Go maps sensitive to data races?

#66

Post by lmm » Mon, Dec 07, 2015, 1:51 PM UTC

chrisseaton wrote: post #62

lmm wrote: post #59

Earlier quoted context omitted.

You can't do that retroactively. And it would make performance very hard to reason about or measure.

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).

Re: Are Go maps sensitive to data races?

#67

Post by 4ad » Mon, Dec 07, 2015, 1:53 PM UTC

lmm wrote: post #60

AYBABTME wrote: post #22

Earlier quoted context omitted.

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.

So does the race detector.

Re: Are Go maps sensitive to data races?

#68

Post by alkonaut » Mon, Dec 07, 2015, 2:02 PM UTC

lmm wrote: post #60

AYBABTME wrote: post #22

Earlier quoted context omitted.

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 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.

Re: Are Go maps sensitive to data races?

#69

Post by muraiki » Mon, Dec 07, 2015, 2:33 PM UTC

khgvljhkb wrote: post #50

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 commun…

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. :)

[0] http://martintrojer.github.io/clojure/2013/07/07/coreasync-a...

Re: Are Go maps sensitive to data races?

#70

Post by JoeAltmaier » Mon, Dec 07, 2015, 2:40 PM UTC

muraiki wrote: post #69

khgvljhkb wrote: post #50

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 commun…

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 i…

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).