Nice write-up. It's easy to fall into the trap of assuming that things are "thread-safe" when writing under the iron fist of a Global Interpreter Lock.
Ruby threads seems to be a fairly narrow topic on which to base a book; I'll look forward to seeing what all the book covers.
AFAIK there is no spec. MRI is the reference implementation, but many things are experimental or intentionally unspecified.
Given that MRI ships with a GIL, the only core classes that are intentionally aware of multi-threading concerns are Mutex, ConditionVariable, and Queue.
Even a thread-aware collection where collection methods are synchronized on an internal lock (as in Java 1.0 — this was quickly dropped as it's effectively useless) wouldn't help here: having `[]` and `[]=` safe will not make calling `[]`, performing an addition and then calling `[]=` safe.
A GIL does not mean classes should ignore concurrency concerns, it's still possible to get odd behaviour from things like hash table implementations in a GIL based interpreter when inserting objects as you may end up thread switching mid operation.
What saves you most of the time is that it isn't worth switching threads too often so normally you get lucky.
Does ruby have a spec? If not, I don't really see this as a problem... synchronization, especially in a dynamic language that's already really slow, would just add more overhead.
This still doesn't explain why the MRI implementation is accidentally threadsafe. Why doesn't the interpreter switch threads after reading the value from the hash but before storing the updated value?
Due to the Global Interpreter Lock (GIL), your whole script is wrapped in one giant mutex. That means that you don't have code running in true parallel, so the data is not corrupted as it is in JRuby and Rubinius (which both implement real, true, parallel threads).
Not sure why someone chose to downvote this to 0, but here's how the OP put it:
The global lock is a feature of MRI that basically wraps a big mutex around all of your code. That's right, even if you're using multiple threads on a multi-core CPU, if your code is running on MRI it will not run in parallel.
OP is wrong, MRI will release the GIL (and yield to other threads) on IO and after running a bit (which can yield convoy effect actually lowering the performances). C extensions can also release the GIL when not manipulating VM structures.
Technically the GIL is there to protect the VM's internal state, so its operational semantics are that it's taken and released for each bytecode instruction.
However the efficiency would stink (short of awesome automatic lock elision or merging), so GIL-based VMs usually have a higher threshold, either based on some sort of instructions count (which may or may not map 1:1 to bytecode instructions) or an internal "wall clock" timer. I think MRI's the latter but don't quote me on it.
There are some very specific caveats that MRI makes for concurrent IO. If you have one thread that's waiting on IO (ie. waiting for a response from the DB or a web request), MRI will allow another thread to run in parallel.
If it's like CPython, the interpreter will release the GIL on IO or after a number of "ticks", but "ticks" are very loosely mapped to an expression or statement. So it will generally put all of (get value at index, increment value, store value) under a single lock.
So I'd expect that even on MRI the original code could in fact fail to yield 0 once in a while. That's what'd happen on CPython
Under the semantics described here, Java or C# core classes aren't "thread-safe" either and I'd expect the vast majority of standard libraries to completely fail the test (potential winners: Clojure using an immutable collection bound on an atom, as they have compare-and-swap semantics; and probably Haskell somehow), the example code requires performing the following actions atomically:
* Loading an instance-local collection
* Fetching a numeric value from the collection
* Incrementing or decrementing the numeric value
* Putting the incremented value back
Even if the collection is "synchronized" (each method call takes a collection-local lock), because the value is altered outside the collection there's no way for the change to be atomic unless it's wrapped in a transaction block or protected by a lock. As far as I can think, the only ways for core classes to "be thread-safe" considering the example (keeping mutable collections semantics) would be to either have collections dedicated specifically to the operation such as Java6's AtomicIntegerArray (http://docs.oracle.com/javase/6/docs/api/java/util/concurren...), or to have the collection apply the operation internally e.g. Hash#apply(key, &operation) used roughly like this:
def decrease item
@stock.apply(item) {|from| from - 1}
end
Pure values are not really relevant: you still need to update a binding somewhere to synchronize, and that's sufficient for your race. The clojure example wouldn't be safe if atoms weren't compare-and-set: have collection state A, thread one applies A->B, thread two applies A->C, the two threads set the atom (atomically but not CAS) and an increment has been lost even though all values are pure.
Yes, but the point is, that in a functional language, hash-tables need not be thread-safe, as they are immutable. Only the variable binding has to be transactional.
In a functional language, the code would be:
transaction {
local a = !x
local b = copy a with b[i] = a[i] + 1
x := b
}
where `!x` is referencing a transactional variable and `:=` is setting it.
> Yes, but the point is, that in a functional language, hash-tables need not be thread-safe
As I and you noted, that's irrelevant, making the collection "thread-safe" (in the usual acception of the term, namely that concurrent accesses to the collection will not put the collection in an incorrect state) would not fix the situation since the increment is done outside the collection.
> Only the variable binding has to be transactional.
My point being precisely that the binding still has to be transactional: pure values are not sufficient to save you.
> In a functional language, the code would be:
Erm... I know. And that's not "in a functional language" that's in haskell, other languages will use different solutions.
Mutating collections with shared state isn't what you do in pure Haskell, though. That's the difference between the now classic deterministic parallelism , and the newer side-effect oriented concurrency in Haskell using stm or mvars.
Without side effects your /parallel/ code cannot but be thread safe. Because the language requires the implementation to ensure side effects under the hood are not observable -- using cas for example on thunk updates, as GHC does.
A better title might have been, "true concurrent execution may reveal problems in your code that a GIL has hidden."
Having worked on a JVM port of a similar language and standard library what is most surprising is how much will still work in real world situations even when fundamental parts are not thread safe. It requires careful insertion of locks, and some quite heavy multithreaded testing to find and fix those problems, and that time may be better spent implementing new thread safe alternatives (or simply exposing the java concurrent collections) which encourage the programmer to write thread safe code, and putting locks in at the application level to fix concurrency issues.
> A better title might have been, "true concurrent execution may reveal problems in your code that a GIL has hidden."
Indeed (and as many Python developers have discovered trying to run their code on pypy, deterministic "garbage collection" schemes such as refcounting may do the same with resource leaks)
> Under the semantics described here, Java or C# core classes aren't "thread-safe" either and I'd expect the vast majority of standard libraries to completely fail the test (potential winners: Clojure using an immutable collection bound on an atom, as they have compare-and-swap semantics; and probably Haskell somehow)
Java's standard library includes Doug Lea's famous java.util.concurrent package written as part of JSR 166, which according to (http://jcp.org/en/jsr/detail?id=166) was finally released in late 2004. Never wrote C#, but I started typing [C# concurrent] into Google and it autocompleted and instantly searched for [C# ConcurrentDictionary], the first result being: http://msdn.microsoft.com/en-us/library/dd287191.aspx .
The "core collections" - a term you're defining yourself right now however you like, for the record - aren't threadsafe for a reason. They have different performance characteristics in Java! You need two versions of the collections in these languages because of their concurrency and memory models.
In Java, using Concurrent/Atomic classes is how you write idiomatic threadsafe code, and it has been for a decade. Bitching because the main list types aren't threadsafe only demonstrates deep, deep ignorance.
Wow, you went way off kilter there mate, I didn't "bitch because the main list types aren't threadsafe", in fact I didn't even emit the slightest criticism (let alone "bitch") on that front as it makes perfect sense, you're the guy getting all butthurt because I note in passing that Java's or C#'s core collections are no safer than Ruby's if you're using them in a stupid manner.
And it highlights the issue that thread safe collections and thread safe objects are very different things. ConcurrentHashMap may be thread safe but putting non atomic Integers in there still leaves you vulnerable to threading problems
It's not that Arrays are not thread safe; it's just that the code was written in a non-thread-safe way.
Writing
x[i] -= 1
actually means
x[i] = x[i] - 1
So, there's a read, a subtraction, and a write, and they all happen sequentially. Since they are not in a transaction or protected by a mutex, nothing guarantees that other thread don't mutate `x[i]` in the mean time.
This has nothing to do with Ruby, and nothing to do with multicore, either. Even on a single CPU core, threads might interleave and cause unexpected behavior.
I came to this comment thread specifically to point this out, but you beat me to it.
It has nothing to do thread safety, and everything to do with atomicity. This is not a single atomic operation, but rather three atomic (and thread-safe) operations which are bound together with the assumption that the entire thing is atomic when it is not.
# you might as well imagine this happening
original = x[i]
new_val = original - 1
x[i] = new_val
Which is why you need to use a mutex to make the entire operation atomic, at a small performance cost.
The Objective-C compiler actually adds a nice bit of syntax for this, you can simply wrap your code in @synchronized:
@synchronized(self) {
int original = x[i];
int new_val = original - 1;
x[i] = new_val;
}
If I understand correctly, this corresponds to `lock` in C#:
lock (_gate) {
x[i] --;
}
At least in C# it is considered preferable to lock on a private field, as opposed to locking on `this`, so nobody else also locks on your instance, potentially causing a deadlock.
I suppose this applies to `@synchronized` in Objective C as well.
I like that .NET Framework also provides some useful atomic methods, including this one:
Note that it's not a "simple array" here it's an associative one, a map. And of course it's not just access, it's the retrieval of a reference to an immutable cell, you can't just alter it in place unless you are certain no other reference to the cell exists in the system.
> Note that it's not a "simple array" here it's an associative one, a map. And of course it's not just access, it's the retrieval of a reference to an immutable cell, you can't just alter it in place unless you are certain no other reference to the cell exists in the system.
This still comes down the question of whether your language preferes references or values: a design decision in-scope for the original question. A language designer might quite reasonably choose to specify that `foo[i] -= 1` means “Get a reference to the object at position i in container foo and tell it to decrement”, in which case the container access is not a concurrency issue except for write / replacing the initial object. This approach can also be implemented atomically in many architectures because it's a simple arithmetic operation rather than retrieving and storing immutable objects.
It would also potentially be easier to scale if threads don't typically update the same elements because you could perform locking at the cell level rather than the entire container.
You only have to do it yourself once you decide to use threads.
And there is not really a way around that. If the language mandated that all primitive operations (for whatever reasonable operation of 'primitive') were atomic, most multi-threaded programs would slow down to a crawl.
Even ignoring that, having atomic primitives is not sufficient to prevent race conditions. Things like "if balance > withdrawal {balance -= withdrawal; ...} need larger ranges of locking, and no compiler is going to tell you how large they have to be.
The article seems to be wrong in several aspects ... First, the issue described has nothing to do with arrays; the same problem happens when using a plain number:
class Inventory
def initialize(nb)
@nb_items = nb
end
def decrease
@nb_items -= 1
end
def nb_items
@nb_items
end
end
@inventory = Inventory.new(4000)
threads = Array.new
400.times do
threads << Thread.new do
10.times do
@inventory.decrease
end
end
end
threads.each(&:join)
puts @inventory.nb_items
Second, the mutex in the OP's code synchronizes the whole block passed to a thread, i.e. there's no parallelism at all (the second thread waits until the first one finishes, and so on). It should rather be something like:
class Inventory
def initialize(nb)
@nb_items = nb
@lock = Mutex.new
end
def decrease
@lock.synchronize do
@nb_items -= 1
end
end
def nb_items
@nb_items
end
end
@inventory = Inventory.new(4000)
threads = Array.new
400.times do
threads << Thread.new do
10.times do
@inventory.decrease
end
end
end
threads.each(&:join)
puts @inventory.nb_items
Thanks for the comments about atomicity vs. thread-safety. Absolutely on point. The article started out demonstrating what happened with concurrent Array mutation, but then I put in that += operation and didn't address it. Sorry for not making the distinction. Atomicity is absolutely a different issue than a thread-safe collection. I'm publishing something new tomorrow that addresses this point.
To bring things back to code, the point I was originally trying to make is that this code is not thread-safe.
array = []
threads = []
10.times do
threads << Thread.new do
100.times { array.push(rand) }
end
end
threads.each(&:join)
# 10 threads each inserted 100 values, result should be 1000
puts array.size
Specifically, too many Ruby programmers won't think twice about this operation not being thread-safe:
array.push(item)
But there's no such guarantee. This is demonstrated nicely when this code example is run on an implementation with no global lock, try it on JRuby.
46 comments
[ 2.8 ms ] story [ 114 ms ] threadRuby threads seems to be a fairly narrow topic on which to base a book; I'll look forward to seeing what all the book covers.
Given that MRI ships with a GIL, the only core classes that are intentionally aware of multi-threading concerns are Mutex, ConditionVariable, and Queue.
What saves you most of the time is that it isn't worth switching threads too often so normally you get lucky.
The global lock is a feature of MRI that basically wraps a big mutex around all of your code. That's right, even if you're using multiple threads on a multi-core CPU, if your code is running on MRI it will not run in parallel.
Technically the GIL is there to protect the VM's internal state, so its operational semantics are that it's taken and released for each bytecode instruction.
However the efficiency would stink (short of awesome automatic lock elision or merging), so GIL-based VMs usually have a higher threshold, either based on some sort of instructions count (which may or may not map 1:1 to bytecode instructions) or an internal "wall clock" timer. I think MRI's the latter but don't quote me on it.
So I'd expect that even on MRI the original code could in fact fail to yield 0 once in a while. That's what'd happen on CPython
* Loading an instance-local collection
* Fetching a numeric value from the collection
* Incrementing or decrementing the numeric value
* Putting the incremented value back
Even if the collection is "synchronized" (each method call takes a collection-local lock), because the value is altered outside the collection there's no way for the change to be atomic unless it's wrapped in a transaction block or protected by a lock. As far as I can think, the only ways for core classes to "be thread-safe" considering the example (keeping mutable collections semantics) would be to either have collections dedicated specifically to the operation such as Java6's AtomicIntegerArray (http://docs.oracle.com/javase/6/docs/api/java/util/concurren...), or to have the collection apply the operation internally e.g. Hash#apply(key, &operation) used roughly like this:
By design - pure values are always thread safe.
In a functional language, the code would be:
where `!x` is referencing a transactional variable and `:=` is setting it.As I and you noted, that's irrelevant, making the collection "thread-safe" (in the usual acception of the term, namely that concurrent accesses to the collection will not put the collection in an incorrect state) would not fix the situation since the increment is done outside the collection.
> Only the variable binding has to be transactional.
My point being precisely that the binding still has to be transactional: pure values are not sufficient to save you.
> In a functional language, the code would be:
Erm... I know. And that's not "in a functional language" that's in haskell, other languages will use different solutions.
Without side effects your /parallel/ code cannot but be thread safe. Because the language requires the implementation to ensure side effects under the hood are not observable -- using cas for example on thunk updates, as GHC does.
Having worked on a JVM port of a similar language and standard library what is most surprising is how much will still work in real world situations even when fundamental parts are not thread safe. It requires careful insertion of locks, and some quite heavy multithreaded testing to find and fix those problems, and that time may be better spent implementing new thread safe alternatives (or simply exposing the java concurrent collections) which encourage the programmer to write thread safe code, and putting locks in at the application level to fix concurrency issues.
Indeed (and as many Python developers have discovered trying to run their code on pypy, deterministic "garbage collection" schemes such as refcounting may do the same with resource leaks)
Java's standard library includes Doug Lea's famous java.util.concurrent package written as part of JSR 166, which according to (http://jcp.org/en/jsr/detail?id=166) was finally released in late 2004. Never wrote C#, but I started typing [C# concurrent] into Google and it autocompleted and instantly searched for [C# ConcurrentDictionary], the first result being: http://msdn.microsoft.com/en-us/library/dd287191.aspx .
Irrelevant, java.util.concurrent.atomic.AtomicIntegerArray - which I mentioned — can not under any sensible definition be called a "core collection".
In Java, using Concurrent/Atomic classes is how you write idiomatic threadsafe code, and it has been for a decade. Bitching because the main list types aren't threadsafe only demonstrates deep, deep ignorance.
Chill and lay off the exclamation point.
Yes, thread-safety is hard in these languages. You have to think about code when you write it.
Writing
actually means So, there's a read, a subtraction, and a write, and they all happen sequentially. Since they are not in a transaction or protected by a mutex, nothing guarantees that other thread don't mutate `x[i]` in the mean time.This has nothing to do with Ruby, and nothing to do with multicore, either. Even on a single CPU core, threads might interleave and cause unexpected behavior.
It has nothing to do thread safety, and everything to do with atomicity. This is not a single atomic operation, but rather three atomic (and thread-safe) operations which are bound together with the assumption that the entire thing is atomic when it is not.
Which is why you need to use a mutex to make the entire operation atomic, at a small performance cost.The Objective-C compiler actually adds a nice bit of syntax for this, you can simply wrap your code in @synchronized:
I suppose this applies to `@synchronized` in Objective C as well.
I like that .NET Framework also provides some useful atomic methods, including this one:
They come in handy.That is itself a separate specification question: does simple array access trigger full load/store semantics or is it simply returning a reference?
This still comes down the question of whether your language preferes references or values: a design decision in-scope for the original question. A language designer might quite reasonably choose to specify that `foo[i] -= 1` means “Get a reference to the object at position i in container foo and tell it to decrement”, in which case the container access is not a concurrency issue except for write / replacing the initial object. This approach can also be implemented atomically in many architectures because it's a simple arithmetic operation rather than retrieving and storing immutable objects.
It would also potentially be easier to scale if threads don't typically update the same elements because you could perform locking at the cell level rather than the entire container.
And there is not really a way around that. If the language mandated that all primitive operations (for whatever reasonable operation of 'primitive') were atomic, most multi-threaded programs would slow down to a crawl.
Even ignoring that, having atomic primitives is not sufficient to prevent race conditions. Things like "if balance > withdrawal {balance -= withdrawal; ...} need larger ranges of locking, and no compiler is going to tell you how large they have to be.
Thanks for the comments about atomicity vs. thread-safety. Absolutely on point. The article started out demonstrating what happened with concurrent Array mutation, but then I put in that += operation and didn't address it. Sorry for not making the distinction. Atomicity is absolutely a different issue than a thread-safe collection. I'm publishing something new tomorrow that addresses this point.
To bring things back to code, the point I was originally trying to make is that this code is not thread-safe.
Specifically, too many Ruby programmers won't think twice about this operation not being thread-safe: But there's no such guarantee. This is demonstrated nicely when this code example is run on an implementation with no global lock, try it on JRuby.Otherwise, take a lock, or don't share data.
But first, let's figure out what we really mean.