RE: An intro for AsyncFP--please review this if you can

Goodie – I had forgotten those… thanks

From: √iktor Ҡlang [mailto:viktor.klang@gmail.com]
Sent: October-21-11 5:34 AM
To: William la Forge
Cc: Razvan Cojocaru; Eric Kolotyluk; scala-user@googlegroups.com
Subject: Re: [scala-user] An intro for AsyncFP--please review this if you can

On Fri, Oct 21, 2011 at 11:00 AM, William la Forge <laforge49@gmail.com> wrote:

Well, if you had an immutable class I. Lets say there is a put(String, Any): I method on I. The lock-free mutable form of put would then return Unit I suspect. There would also be a get(String): Any method.

class MI(initial: I) {
  val ar[I] = new AtomicReference(initial)

  def put(key: String, value: Any) {
    var i = ar.get
    while (!ar.compareAndSet(i, i.put(key, value))) i = ar.get
  }

  def get(key: String) = ar.get.get(key)
}

case class Var[T](i: T) extends AtomicReference[T](i) {
  def mutate(m: T => T): T = {
     @tailrec def apply(): T = {
        val c = get
        val n = m(c)
        if (compareAndSet(c, n)) n else apply()
     }
     apply()
  }
}

scala> class Var[T](i: T) extends AtomicReference[T](i) {
     |   def mutate(m: T => T): T = {
     |      @tailrec def apply(): T = {
     |         val c = get
     |         val n = m(c)
     |         if (compareAndSet(c, n)) n else apply()
     |      }
     |      apply()
     |   }
     | }
defined class Var

scala> val v = new Var("String")
v: Var[java.lang.String] = String

scala> v mutate { _.toUpperCase }
res6: java.lang.String = STRING
 

As I was saying, this is only good with low contention. But it is a lock-free data structure created from an immutable and compareAndSet. (And no, I didn't compile this code.)

I think this is kinda cool, because now it is easy to create mutable lock-free data structures that can be safely shared across threads just like immutable data structures! (Well, not so safely actually. There's always those nitty little application-specific consistency issues. But hey, you can always create application specific structures to handle those details, hmm?)

Bill

 

On Thu, Oct 20, 2011 at 9:13 PM, Razvan Cojocaru <pub@razie.com> wrote:

I was saying that you could create a lock-free mutable structure very easily by building on compareAndSet and an immutable structure.

 

How?

 

 

From: William la Forge [mailto:laforge49@gmail.com]
Sent: October-21-11 12:07 AM
To: Razvan Cojocaru
Cc: Eric Kolotyluk; scala-user@googlegroups.com

Subject: Re: [scala-user] An intro for AsyncFP--please review this if you can

 

Razvan, 

You are right that immutable structures can be freely shared since they don't change. I was saying that you could create a lock-free mutable structure very easily by building on compareAndSet and an immutable structure. Of course, this assumes contention is low.

This is what got me inspired: http://www.cse.chalmers.se/~tsigas/papers/Haakan-Thesis.pdf

OK?

Bill

On Thu, Oct 20, 2011 at 8:46 PM, Razvan Cojocaru <pub@razie.com> wrote:

Hold the phone - I need some clarification…

 

AFAIK:

 

TAS is a low-level processor instruction normally used to implement semaphores and other such things – which are fast IF they don’t trigger a yield().

 

Immutable data structures do not change, thus they should not be locked  -can freely and cheaply be shared across threads.

 

The reason why it may be expensive to share mutable data between threads is that the threads may need to sync before, meaning that one or more of them can loose CPU and yield() out. This is not inherently expensive unless contention goes up.

 

For instance, something stupid like a poorly designed Log4J appender (i.e. the default one) that causes too much contention on a 64 core box with 1000 threads… you can increase performance by 30% just by re-designing the appender…

 

Is there any other relationship here, between mutable/immutable/sharing and TAS?

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of William la Forge
Sent: October-20-11 10:58 PM
To: Eric Kolotyluk
Cc: scala-user@googlegroups.com
Subject: Re: [scala-user] An intro for AsyncFP--please review this if you can

 

Eric,

Your comments are extremely helpful. Your mention of non-blocking data structures absolutely blew me away. Wow! So easy to convert any immutable data structure to a lock-free structure with a simple compare-and-set. Suddenly I am passionate about immutable data structures!!!

Ho! But your question about the use of non-blocking data structures for message passing. I would have thought Scala reactors already did that. I know a lot of work has been done to make sure Scala Actors/Reactors are as fast as possible. Scala has not been so constrained by backward compatibility issues as Java that the developers of Scala would be unlikely to hesitate to make the change if they had not already.

Hmm. Another thought is to replace the Scala Reactor in the mailbox with a dedicated thread and a non-blocking message queue. The argument against dedicating threads to mailboxes is weaker than the argument against dedicating threads to shared mailboxes--there are fewer of them.

Thanks very much Eric.

Bill

On Thu, Oct 20, 2011 at 6:30 AM, Eric Kolotyluk <eric.kolotyluk@gmail.com> wrote:

While I think you have something important to say, some of your statements are too sweeping and general, and as such lack veracity. I think you could avoid this by speaking to specific instances of what you are trying to say about performance and/or narrowing the scope to something like Scala Actors (and what their problems are),

Comments below...

On 2011-10-20 3:07 AM, William la Forge wrote:

I don't think there is anything harder than writing an introduction. This is my first attempt at introducing AsyncFP and I would very much appreciate any help you can give in the way of suggestions or criticisms.

Thanks!

Bill La Forge

. . . . . .

Why do we need a new approach to programming? On the one hand, Solid State Disk (SSD) has shifted the balance between I/O and CPU. [good point, especially wrt FusionIO and similar devices] Where before there might not have been much benefit to faster code, that is simply no longer the case. Improvements in execution speed can now significantly improve program performance.

On the other hand, computers are getting fatter, not faster. An i9 chip has 12 hardware threads. A Sparc T4 chip has 64. But writing programs that actually run faster as you add more hardware threads is difficult [very true, this is a sine qua non of your point I believe]--most software runs much faster with a single thread then when organized to use multiple threads. [not true, the point of reorganizing software to use mutiple threads is to make it faster. What you may mean is that they do not run as efficiently on a single thread, which is a scaling issue] This Passing data between threads is inherently slow. [not true because threads share memory, and non-blocking data structures the use Test And Set or Compare And Swap can make that particularly fast. If you want to stick by this claim you need to elaborate on what you mean] Programs which work well with multiple threads typically pass data between threads in large chunks, e.g. data-flow based software. [again, not true for the previous reasons] So moving everything to an asynchronous model like actors is unlikely to work well when a lot of messages are involved. [assuming you are confining yourself to a message based design]

One thing that really throws a monkey wrench into all this is scalability. [very true, writing scalable code can sometimes be even harder than just writing faster code] Consider for example an application server. If we dedicate a thread to servicing one request at a time and attempt to service requests as they arrive we could be using a lot of threads. Thread stack space is usually rather large, so we can easily run short of resources. [partially true - stacks do not need to be large, unless you are using deeply recursive code, which is why tail recursion is particularly important. If the number of thread stacks is the same order as hardware threads avaiable this is not a large overhead] Something like actors, which do not have dedicated threads, are a real win in this case. [very true, especially if your design needs many more actors than hardware threads]

With current technology we end up developing programs with an architecture specific to the problem at hand. And re-architect our programs as the requirements change. This is a labor-intensive approach that minimizes code reuse. [another sine qua non of what you are trying to say I believe - you want to be able to write code that has similar efficiency running on one hardware thread as dozens, hundreds, or many more] What seems to be needed is something like the approach used by the E Language, which allows actors to exchange messages both synchronously and asynchronously.

To maximize reuse, an actor should neither know nor care if the exchange of messages with another actor is synchronous or asynchronous. And if most message exchanges are synchronous, we can have many small actors working at a fairly low-level without slowing the program down to a crawl.

The way this is achieved is by separating an actor from its mailbox (incoming message queue), and allowing multiple actors to share the same mailbox. Actors with the same mailbox always use the same thread, with data being moved between threads only when the actors have different mailboxes. We can then re-architect a program to meet those ever-evolving requirements simply by changing which actors share a common mailbox. [have you ruled out using non-blocking data structures for mailbox message passing?]

This all sounds reasonable, but there is one catch. How do you write code that sends messages to other actors and that doesn't care if the message exchange is synchronous or asynchronous? The obvious [why is this obvious?] answer is to use anonymous callback functions to handle responses and to guarantee that there is always a response message returned by every request message unless an exception is thrown. [and now comes the heart of what you are trying to say I think...] But now we can use actors to handle more messages, and we'll want to employ a functional programming approach, e.g. find, map, filter etc., to keep our code clear and readable. And to employ state machines to linearize what would otherwise be ugly and deeply nested. This is the focus of the AsyncFP project. [...so you need to say more about this to make your introduction meaningful]

 

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang