Atomic IVar

[mighe]

Currently IVar are a bit brittle when shared between many writer threads:

i = IVar.new

Thread.new { i.set(42) }
Thread.new { i.set(43) }

one of them will fail due to MultipleAssignmentError

I was wondering about a safer method like IVar#set_unless_assigned returning true if the operation succeeded, false otherwise.

Given that IVars are a well defined entity in literature, do you think is a good idea to add this method to IVar or should we create a new entity (maybe called AtomicIVar or Probe)?

[chrisseaton]

Do you have a specific use case in mind?

Normally you'd only have one thread providing the value for an IVar. If you have two threads trying to provide a value, one of them is wasting their time.

I think a new construct would be better - and instead of concentrating on the fact that it's atomic, we could look at it as a kind of first-past-the-post IVar or dataflow node. I'm actually looking at this exact thing in some of my PhD research at the moment. There my use case is that I have two different algorithms trying to solve a problem, and I want the result from whichever finishes first. As a simple example, imagine trying two web services. I want a result from whichever web service can give it first. I don't care about the result that comes later, and so I send a notification in the opposite direction and tell the other task that is producing the IVar that I don't need it any more and it can stop working. This avoids any more wasted work.

In the literature this is called a lethon - as if it was some kind of lethal particle you send back up the dataflow graph to kill tasks. It might be a good idea to implement it here, but I don't believe it's ever been tried outside of academia.

@jdantonio might be able to relate this to Erlang processes somehow. Can you tell an Erlang process to stop because you don't need the work it's doing any more?

But this is all dependent on what you're actually trying to do? Maybe for simpler cases a set_if_unset is fine.

[mighe]

I'm implementing go-like channels.
Channel have a push method and a pop method; the writer thread will block until the reader is ready.

This is the easy part, that could be implemented easily with an exchanger or something like that.

For a better abstraction, channel can be selected, a blocking operation on an array of channel waiting for the first ready, very similar to your problem.

My idea is very simple:

• every channel has a probe set
• a probe is an assignable var (like and IVar)
• the select methods add the same probe to all channels
• when a writer is ready it takes a probe and sets its value
• cleanup

Imagine to have two channels and two writing threads at the same time: with an unlucky timing, both thread will get the same probe and sets the value. One of them will get the error.
Now, the thread that got the error should discard that probe and try again with the next one (or wait for a new one if the probe set is empty).

With set_if_unset this check is very very simple, otherwise we have to rescue the error.

This algorithm seems very effective: at worst the writing thread will retry probe.size times, but usually contention on channels is not so high and it will take just constant time (and takes only a few line of code 😊 )

I'd like to implement it and use it as a reference for better algorithm in future (if you know some algorithms for this problem we could try them!)

[jdantonio]

@chrisseaton Erlang processes can be sent an exit signal which will kill the process. If the reason for the exit is the atom normal then the process will not bubble the exit up to linked processes (meaning its exit will not be recognized as an error).

So in theory you could do what you suggest in Erlang. Start two processes with the same task and expect those processes to send a message back to the originating process when complete. Once a message from either child is received by the originating process signals the other child with a normal exit, shutting it down.

[chrisseaton]

@mighe Is your code on a branch yet? If you think you can get it working quickly with set_if_unset, you might as well implement that for now, but after you've got it working we might want to have a think about how to do this more elegantly. It might be that we want to create some new abstraction for it that will be useful in other places. Maybe a method to select from the first available IVar in an array, or to write to the first empty IVar from an array of them.

[mighe]

@chrisseaton Not yet, I've started coding today, I'll push the new branch very soon.

[mighe]

I've pushed the new branch just now, you can find everything is inside the new lib/channel folder.
As you can see, I opted to subclass IVar creating Probe with the new method.
I also added WaitableList, I start thinking concurrent data structure could be very useful in this gem (although they are not a priority)

[jdantonio]

@mighe I definitely agree that thread-safe data structures should be in this gem eventually. At the very least I would like to create BlockingHash and BlockingArray. If we include Enumerable in both it should be very easy to make very robust, safe collections.

[dsisnero]

It would be nice to have lock free datastructures also, not just
thread-safe locking datastructures

On Thu, Apr 3, 2014 at 7:10 AM, jdantonio notifications@github.com wrote:

@mighe https://github.com/mighe I definitely agree that thread-safe
data structures should be in this gem eventually. At the very least I would
like to create BlockingHash and BlockingArray. If we include Enumerablehttp://www.ruby-doc.org/core-2.1.1/Enumerable.htmlin both it should be very easy to make very robust, safe collections.

Reply to this email directly or view it on GitHubhttps://github.com//issues/43#issuecomment-39448571
.

[jdantonio]

@dsisnero So today is a day for me to learn something new. I'm not familiar with lock free concurrent data structures. But I'm very intrigued. Can you provide a link or two? Below are a few things I've Googled. Are they what you are referring to?

Also, are you familiar with the Hamster library of immutable Ruby data structures? Would that library solve any of the use cases you are thinking of?

• http://yinsochen.com/thread-safe-and-or-lockless-data-structures/
• http://www.addthis.com/blog/2013/04/25/the-secret-life-of-concurrent-data-structures/#.Uz2dKlFdXRs
• http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

[mighe]

Java - from 1.5 - implements many lock free structures.
Typically they are more efficient, but are harder to implement and sometimes they need to work very close to the edge of the memory model.
Given that, I'm doubtful about the possibility to implement correctly them in Ruby.

I have the same concerns about Hamster: it provides immutable data structurse, but in Ruby "immutable objects" is only "effectively immutable objects" without any memory consistency guarantees. In other words, immutability does not mean thread safe in Ruby.

That's way for the moment I prefer lock-based algorithm: under some conditions are less efficient than lock free ones, but they provide stronger guarantees about memory model.

(sooner or later I'll publish a brief article about immutability, draft is ready 😊 )

[jdantonio]

@mighe Cool. Thank you for the info. I'll look into Java's structures to get a better understanding of the concept.

[dsisnero]

Not lock-free but here are some persistent data structures that would be
good to have. Clojure and Scala provide these collections.

Here's some links explaining clojures persistent vector implementation

http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice.html

http://hypirion.com/musings/understanding-persistent-vector-pt-1
http://hypirion.com/musings/understanding-persistent-vector-pt-2

On Thu, Apr 3, 2014 at 12:13 PM, jdantonio notifications@github.com wrote:

@mighe https://github.com/mighe Cool. Thank you for the info. I'll look
into Java's structures to get a better understanding of the concept.

Reply to this email directly or view it on GitHubhttps://github.com//issues/43#issuecomment-39485295
.

[mighe]

With #49 Probes have been introduced.