Ruby core classes aren't thread safe(jstorimer.com)
jstorimer.com
Ruby core classes aren't thread safe
http://www.jstorimer.com/newsletter/ruby-core-classes-arent-thread-safe.html
46 comments
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.
The Objective-C compiler actually adds a nice bit of syntax for this, you can simply wrap your code in @synchronized:
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
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#:
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:
lock (_gate) {
x[i] --;
}
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:
Interlocked.Decrement (ref x[i]);
That's not quite true. The language spec can mandate that the -= be atomic (the X86 equivalent is mandating a LOCK).
Technically it'd have to mandate that []-= be atomic, there's a load from and a store to a k:v collection, not just from and to memory.
> there's a load from and a store to a k:v collection
That is itself a separate specification question: does simple array access trigger full load/store semantics or is it simply returning a reference?
That is itself a separate specification question: does simple array access trigger full load/store semantics or is it simply returning a reference?
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.
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.
Totally agreed. Why do I have to lock it myself (even on a high level language like Ruby)? I'm not programming for C!
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.
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.
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:
* 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}
endA 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.
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)
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)
> and probably Haskell somehow
By design - pure values are always thread safe.
By design - pure values are always thread safe.
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:
In a functional language, the code would be:
transaction {
local a = !x
local b = copy a with b[i] = a[i] + 1
x := b
}
> 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.
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.
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.
> 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 .
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 .
> Java's standard library includes Doug Lea's famous java.util.concurrent package written as part of JSR 166
Irrelevant, java.util.concurrent.atomic.AtomicIntegerArray - which I mentioned — can not under any sensible definition be called a "core collection".
Irrelevant, java.util.concurrent.atomic.AtomicIntegerArray - which I mentioned — can not under any sensible definition be called a "core collection".
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
> ConcurrentHashMap may be thread safe but putting non atomic Integers in there still leaves you vulnerable to threading problems
Yes, thread-safety is hard in these languages. You have to think about code when you write it.
Yes, thread-safety is hard in these languages. You have to think about code when you write it.
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.
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.
Chill and lay off the exclamation point.
Chill and lay off the exclamation point.
[deleted]
Hi. OP here.
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.
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
array.push(item)
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
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_itemsNice 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.
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.
Let's ban this term "thread safe" and instead say what we really mean.
But first, let's figure out what we really mean.
But first, let's figure out what we really mean.
[deleted]
There is one core library class that's thread safe, and it's Queue.
Otherwise, take a lock, or don't share data.
Otherwise, take a lock, or don't share data.
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?
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
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
[deleted]
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).
That doesn't explain it. The runtime execution could still be like this:
thread #1:
local a = x[i]
a = a + 1
context_switch()
thread #2:
local b = x[i]
b = b + 1
x[i] = b
context_switch()
thread #1:
x[i] = a
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.
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.
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.
Correct. Later on I say:
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.Does the spec mandate thread safety? (I guess I should ask if there's a spec or is MRI the reference implementation)
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.
Given that MRI ships with a GIL, the only core classes that are intentionally aware of multi-threading concerns are Mutex, ConditionVariable, and Queue.
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.
What saves you most of the time is that it isn't worth switching threads too often so normally you get lucky.
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.
There is an ISO spec, but it's not really relevant to the future of the language.
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.