Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

Thanks Aleksey for that clarification of the naming convention.

I'll note that the class I developed, which subclasses ConcurrentLinkedQueue doesn't use locks except when you do a take on an empty queue. I'm using semaphores which use locks, this is true, but I'm combining them with some non-blocking techniques. As long as the queue is not empty then, you pretty much have the same speed as ConcurrentLinkedQueue.

Bill

On Thu, Oct 27, 2011 at 7:27 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill


2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill


2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill


2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill


2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

I woke up this morning and realized that there is a bug/limitation. This code will fail if more than one thread is reading. --Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill


2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

Sorry 'bout that. Code with some comments below. Also, I gave up on implementing BlockingQueue, partly because of syntax errors and partly because this isn't really a blocking queue--it is a semi-lock-free semi-blocking queue. :-)

Adding comments meant doing another code review which, with code like this, is always a good idea.

Bill

package org.agilewiki.blip

import java.util.concurrent._
import annotation.tailrec

/**
 * A ConcurrentLinkedQueue with a take method that doesn't block when the queue isn't empty.
 * Note that this code only supports a singe reader thread.
 */
class ConcurrentLinkedBlockingQueue[E]
  extends ConcurrentLinkedQueue[E] {
  private val ab = new atomic.AtomicBoolean //when true, take is requesting a permit
  private val s = new Semaphore(1) //to wake up a pending take

  s.drainPermits //start with no permits

  def put(e: E) {
    offer(e)
  }

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release //if there is a pending take, wake it up
    true
  }

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    //the queue may now be empty, so request a permit
    ab.set(true)
    rv = poll
    if (rv != null) { //the queue was not empty
      if (!ab.compareAndSet(true, false)) s.drainPermits //clear the permit that we didn't need
      return rv
    }
    s.acquire //wait for a permit
    take
  }
}


2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill


2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue. You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

Multithreaded tests need some planning to setup properly. You need a few hardware cores/threads.

 

You can cheaply rent an 8 core box for like 4$/hour from Rackspacecloud and easily freeze the image between tests. Pick a serious OS like Linux / Solaris – Windows may not be the best choice for MT tests… I think they got better since NT but I can’t vouch…

 

You also need to give the test threads sufficient reasons to yield in different places, to increase contention and simulate mistakes. Doing just put() or “1+2” they have no reason to yield. A normal application thread may log or do other stuff as well resulting in inconsistent yields all over the place.

 

I think all kinds of CPUs today have TAS and/or CAS, so their respective performance is probably consistent… unless you run on a phone ?

 

Cheers,

Razie

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of William la Forge
Sent: October-27-11 9:10 PM
To: √iktor Ҡlang
Cc: scala-user
Subject: Re: [scala-user] Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

 

I woke up this morning and realized that there is a bug/limitation. This code will fail if more than one thread is reading. --Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

 

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue.

You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

 

 

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

 

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

I believe in unittesting one cannot rely on randomness. Well, of course, data visibility quirks are hard to model; but mostly all we need is inject shims in the code and have full control over which thread runs after which or which actions run in parallel. Of course untill Eugene implements macros, all those shims should be later commented out.

What I want to say, testing should be deterministic.

Thanks,
-Vlad


2011/10/28 Razvan Cojocaru <pub@razie.com>

Multithreaded tests need some planning to setup properly. You need a few hardware cores/threads.

 

You can cheaply rent an 8 core box for like 4$/hour from Rackspacecloud and easily freeze the image between tests. Pick a serious OS like Linux / Solaris – Windows may not be the best choice for MT tests… I think they got better since NT but I can’t vouch…

 

You also need to give the test threads sufficient reasons to yield in different places, to increase contention and simulate mistakes. Doing just put() or “1+2” they have no reason to yield. A normal application thread may log or do other stuff as well resulting in inconsistent yields all over the place.

 

I think all kinds of CPUs today have TAS and/or CAS, so their respective performance is probably consistent… unless you run on a phone ?

 

Cheers,

Razie

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of William la Forge
Sent: October-27-11 9:10 PM
To: √iktor Ҡlang
Cc: scala-user
Subject: Re: [scala-user] Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

 

I woke up this morning and realized that there is a bug/limitation. This code will fail if more than one thread is reading. --Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

 

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue.

You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

 

 

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

 

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

On Fri, Oct 28, 2011 at 8:04 PM, Vlad Patryshev <vpatryshev@gmail.com> wrote:

I believe in unittesting one cannot rely on randomness. Well, of course, data visibility quirks are hard to model; but mostly all we need is inject shims in the code and have full control over which thread runs after which or which actions run in parallel. Of course untill Eugene implements macros, all those shims should be later commented out.

What I want to say, testing should be deterministic.

Then you need to switch to do Dataflow programming. All other multithreading I know of on the JVM is nondeterministic.
 

Thanks,
-Vlad


2011/10/28 Razvan Cojocaru <pub@razie.com>

Multithreaded tests need some planning to setup properly. You need a few hardware cores/threads.

 

You can cheaply rent an 8 core box for like 4$/hour from Rackspacecloud and easily freeze the image between tests. Pick a serious OS like Linux / Solaris – Windows may not be the best choice for MT tests… I think they got better since NT but I can’t vouch…

 

You also need to give the test threads sufficient reasons to yield in different places, to increase contention and simulate mistakes. Doing just put() or “1+2” they have no reason to yield. A normal application thread may log or do other stuff as well resulting in inconsistent yields all over the place.

 

I think all kinds of CPUs today have TAS and/or CAS, so their respective performance is probably consistent… unless you run on a phone ?

 

Cheers,

Razie

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of William la Forge
Sent: October-27-11 9:10 PM
To: √iktor Ҡlang
Cc: scala-user
Subject: Re: [scala-user] Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

 

I woke up this morning and realized that there is a bug/limitation. This code will fail if more than one thread is reading. --Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

 

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue.

You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

 

 

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

 

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

Not quite. We had a bug (well - many, but this one was interesting) we could only reproduce after running for precisely 6 hours at full load on a T2000 (64 hardware threads). It turned out to be a Sun JIT/JVM hardcore defect and we got a specific patch after a few weeks. I think 64 bit 1.6-18 for Solaris incorporates the fix – don’t remember the code. Sounds a bit surprising to find MT-bugs in the JVM eh?

 

Since it was always about 6 hours, do we call that deterministic ;) ? it was a few million transactions though, on about 500 threads on 64 cores/threads whatever…

 

Not a unit test, but reason for what we call 3-day stress testing, which is part of the normal release process.

 

As for unit tests – been burned a few times by moronic changes to complex code so now we have a few unit tests that test some MT-safe tables and tree structures by running a number of threads for 10 minutes doing all kinds of stuff. Not a guarantee, but better than nothing. 10 minutes is a very long time… Mr. Jenkins takes care of it for us…

 

Like the man says – synchronous data flow *may* be deterministic. All else in life isn’t.

 

Cheers,

Razie

 

From: Vlad Patryshev [mailto:vpatryshev@gmail.com]
Sent: October-28-11 2:04 PM
To: Razvan Cojocaru
Cc: William la Forge; √iktor Ҡlang; scala-user
Subject: Re: [scala-user] Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

 

I believe in unittesting one cannot rely on randomness. Well, of course, data visibility quirks are hard to model; but mostly all we need is inject shims in the code and have full control over which thread runs after which or which actions run in parallel. Of course untill Eugene implements macros, all those shims should be later commented out.

What I want to say, testing should be deterministic.

Thanks,
-Vlad

2011/10/28 Razvan Cojocaru <pub@razie.com>

Multithreaded tests need some planning to setup properly. You need a few hardware cores/threads.

 

You can cheaply rent an 8 core box for like 4$/hour from Rackspacecloud and easily freeze the image between tests. Pick a serious OS like Linux / Solaris – Windows may not be the best choice for MT tests… I think they got better since NT but I can’t vouch…

 

You also need to give the test threads sufficient reasons to yield in different places, to increase contention and simulate mistakes. Doing just put() or “1+2” they have no reason to yield. A normal application thread may log or do other stuff as well resulting in inconsistent yields all over the place.

 

I think all kinds of CPUs today have TAS and/or CAS, so their respective performance is probably consistent… unless you run on a phone ?

 

Cheers,

Razie

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of William la Forge
Sent: October-27-11 9:10 PM
To: √iktor Ҡlang
Cc: scala-user
Subject: Re: [scala-user] Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

 

I woke up this morning and realized that there is a bug/limitation. This code will fail if more than one thread is reading. --Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill

 

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

 

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue.

You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

 

 

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

 

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

 

Multithreading is nondeterministic, but while testing we can make it deterministic (mostly): controlling which thread runs and which thread yields, it's doable, is not it?

Thanks,
-Vlad


2011/10/28 √iktor Ҡlang <viktor.klang@gmail.com>

On Fri, Oct 28, 2011 at 8:04 PM, Vlad Patryshev <vpatryshev@gmail.com> wrote:

I believe in unittesting one cannot rely on randomness. Well, of course, data visibility quirks are hard to model; but mostly all we need is inject shims in the code and have full control over which thread runs after which or which actions run in parallel. Of course untill Eugene implements macros, all those shims should be later commented out.

What I want to say, testing should be deterministic.

Then you need to switch to do Dataflow programming. All other multithreading I know of on the JVM is nondeterministic.
 

Thanks,
-Vlad


2011/10/28 Razvan Cojocaru <pub@razie.com>

Multithreaded tests need some planning to setup properly. You need a few hardware cores/threads.

 

You can cheaply rent an 8 core box for like 4$/hour from Rackspacecloud and easily freeze the image between tests. Pick a serious OS like Linux / Solaris – Windows may not be the best choice for MT tests… I think they got better since NT but I can’t vouch…

 

You also need to give the test threads sufficient reasons to yield in different places, to increase contention and simulate mistakes. Doing just put() or “1+2” they have no reason to yield. A normal application thread may log or do other stuff as well resulting in inconsistent yields all over the place.

 

I think all kinds of CPUs today have TAS and/or CAS, so their respective performance is probably consistent… unless you run on a phone ?

 

Cheers,

Razie

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of William la Forge
Sent: October-27-11 9:10 PM
To: √iktor Ҡlang
Cc: scala-user
Subject: Re: [scala-user] Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

 

I woke up this morning and realized that there is a bug/limitation. This code will fail if more than one thread is reading. --Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

 

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue.

You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

 

 

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

 

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

2011/10/29 Vlad Patryshev <vpatryshev@gmail.com>

Multithreading is nondeterministic, but while testing we can make it deterministic (mostly): controlling which thread runs and which thread yields, it's doable, is not it?

How do you deterministically provoke half-reads/half-writes to longs/doubles using this technique?
How do you trigger reordering-effects?
How do you avoid memory sync (test code makes code work, without test code it has visibility problems)?
 

Thanks,
-Vlad


2011/10/28 √iktor Ҡlang <viktor.klang@gmail.com>

On Fri, Oct 28, 2011 at 8:04 PM, Vlad Patryshev <vpatryshev@gmail.com> wrote:

I believe in unittesting one cannot rely on randomness. Well, of course, data visibility quirks are hard to model; but mostly all we need is inject shims in the code and have full control over which thread runs after which or which actions run in parallel. Of course untill Eugene implements macros, all those shims should be later commented out.

What I want to say, testing should be deterministic.

Then you need to switch to do Dataflow programming. All other multithreading I know of on the JVM is nondeterministic.
 

Thanks,
-Vlad


2011/10/28 Razvan Cojocaru <pub@razie.com>

Multithreaded tests need some planning to setup properly. You need a few hardware cores/threads.

 

You can cheaply rent an 8 core box for like 4$/hour from Rackspacecloud and easily freeze the image between tests. Pick a serious OS like Linux / Solaris – Windows may not be the best choice for MT tests… I think they got better since NT but I can’t vouch…

 

You also need to give the test threads sufficient reasons to yield in different places, to increase contention and simulate mistakes. Doing just put() or “1+2” they have no reason to yield. A normal application thread may log or do other stuff as well resulting in inconsistent yields all over the place.

 

I think all kinds of CPUs today have TAS and/or CAS, so their respective performance is probably consistent… unless you run on a phone ?

 

Cheers,

Razie

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of William la Forge
Sent: October-27-11 9:10 PM
To: √iktor Ҡlang
Cc: scala-user
Subject: Re: [scala-user] Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

 

I woke up this morning and realized that there is a bug/limitation. This code will fail if more than one thread is reading. --Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

 

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue.

You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

 

 

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

 

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

I know what you mean... We do that "behavior code" sometimes to simulate errors from the database whatnot. But that is at best a positive functional test case , while the issue here is the risks which are all negative... And non-deterministic

Thanks,Razvan
On 2011-10-28, at 6:09 PM, Vlad Patryshev <vpatryshev@gmail.com> wrote:

Multithreading is nondeterministic, but while testing we can make it deterministic (mostly): controlling which thread runs and which thread yields, it's doable, is not it?

Thanks,
-Vlad


2011/10/28 √iktor Ҡlang <viktor.klang@gmail.com>

On Fri, Oct 28, 2011 at 8:04 PM, Vlad Patryshev <vpatryshev@gmail.com> wrote:

I believe in unittesting one cannot rely on randomness. Well, of course, data visibility quirks are hard to model; but mostly all we need is inject shims in the code and have full control over which thread runs after which or which actions run in parallel. Of course untill Eugene implements macros, all those shims should be later commented out.

What I want to say, testing should be deterministic.

Then you need to switch to do Dataflow programming. All other multithreading I know of on the JVM is nondeterministic.
 

Thanks,
-Vlad


2011/10/28 Razvan Cojocaru <pub@razie.com>

Multithreaded tests need some planning to setup properly. You need a few hardware cores/threads.

 

You can cheaply rent an 8 core box for like 4$/hour from Rackspacecloud and easily freeze the image between tests. Pick a serious OS like Linux / Solaris – Windows may not be the best choice for MT tests… I think they got better since NT but I can’t vouch…

 

You also need to give the test threads sufficient reasons to yield in different places, to increase contention and simulate mistakes. Doing just put() or “1+2” they have no reason to yield. A normal application thread may log or do other stuff as well resulting in inconsistent yields all over the place.

 

I think all kinds of CPUs today have TAS and/or CAS, so their respective performance is probably consistent… unless you run on a phone ?

 

Cheers,

Razie

 

From: scala-user@googlegroups.com [mailto:scala-user@googlegroups.com] On Behalf Of William la Forge
Sent: October-27-11 9:10 PM
To: √iktor Ҡlang
Cc: scala-user
Subject: Re: [scala-user] Semaphore & compareAndSet magic: ConcurrentLinkedBlockingQueue

 

I woke up this morning and realized that there is a bug/limitation. This code will fail if more than one thread is reading. --Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

2011/10/27 William la Forge <laforge49@gmail.com>

Victor,
I believe the capacity restrictions do not apply to a linked queue. ConcurrentLinkedQueue.offer always returns true: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html#offer%28E%29

I'm sure there are bugs, but this isn't one of them.

I'm just trying to lure out the train of thought since the code is fully void of comments or sensible naming :-)
 

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

William,

2011/10/27 William la Forge <laforge49@gmail.com>

Viktor,

BlockingQueue.take: http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#take%28%29
(take is not defined on Queue)

Yes I read it. Take does a wait. But put/add/offer only does it as needed, which is why it can run as fast as ConcurrentLinkedQueue. Hmm. I should look at implementing the interface for BlockingQueue! :-)

I've defined two variables in this subclass of ConcurrentLinkedQueue:

  private val ab = new atomic.AtomicBoolean
  private val s = new Semaphore(1)

The code for put/add/offer then conditionally uses a semaphore:

  def put(e: E) {
    offer(e)
  }

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer%28E%29

"Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions"
 

  override def offer(e: E) = {
    super.offer(e)
    if (ab.compareAndSet(true, false)) s.release
    true
  }

I see atleast one bug. ;)
 

(The add method in ConcurrentLinkedQueue just calls offer.)

The semaphore in put/add/offer then is only used when the queue is empty and a take has been called.


The code for take is where it gets interesting:

  @tailrec final def take(): E = {
    var rv = poll
    if (rv != null) return rv
    ab.set(true)
    rv = poll
    if (rv != null) {
      if (!ab.compareAndSet(true, false)) s.drainPermits
      return rv
    }
    s.acquire
    take
  }

Like put/add/offer, take also does not use locking unless the queue is empty. I've already shown how to speed up message passing between threads when the receiver's thread is empty. This is the complimentary case. :-)

Hope you like it. I'll look into implementing the BlockingQueue interface tomorrow. (It being Diwali and all, I was up until 4am last night. So I'm off to bed early tonight.)

With all appreciation,

Bill

2011/10/27 √iktor Ҡlang <viktor.klang@gmail.com>

 

On Thu, Oct 27, 2011 at 4:56 PM, William la Forge <laforge49@gmail.com> wrote:

Nothing is wrong with ConcurrentLinkedQueue. I like it a lot. I just added a take method to it. --Bill

Did you read the contract of Queue.take?
 

 

On Thu, Oct 27, 2011 at 7:52 PM, Patrik Andersson <pandersson@gmail.com> wrote:

What's wrong with java.util.concurrent.ConcurrentLinkedQueue ?

 

On Thu, Oct 27, 2011 at 3:57 PM, Aleksey Nikiforov <lexn82@gmail.com> wrote:

Java concurrent package adheres to the following terminology. When a class is called "Blocking" it implies that implementation is using some sort of locks. And "Concurrent" implies that implementation uses non-blocking algorithms. So finding a lock in LinkedBlockingQueue should not be surprising. The non-blocking queue in java is called ConcurrentLinkedQueue.

You may want to consider renaming ConcurrentLinkedBlockingQueue into something else to avoid any confusion.

 

 

On Thu, Oct 27, 2011 at 8:10 AM, William la Forge <laforge49@gmail.com> wrote:

Semaphores and compareAndSet can get quite interesting when used together.

Last night I was looking at LinkedBlockingQueue and was quite surprised that the put method used a lock. That's just plain wrong, because it is too slow. Really, since this class was in the java.util.concurrent package I had expected better. After the work I had done these last few days with compareAndSet combined with Semaphores, I was sure a better answer could be found. Today I wrote that better answer. I call it ConcurrentLinkedBlockingQueue.

My first test was to pass messages one at a time. This tests the empty queue logic, which is the most difficult when you are trying to be clever. I learned that ConcurrentLinkedBlockingQueue runs at about the same speed for this test as LinkedBlockingQueue, which on my old laptop is about 5 microseconds per message. That's fine, at least it wasn't any worse.

Now I ran another test on CurrentLinkedBlockingQueue, this time with bursts of 1,000 messages at a time. This test should run faster, and it did. On my computer it is running about 112 nanoseconds per message--about a 40 fold improvement.

Note that I have only done limited testing with 2 threads. Feel free to report any test results--I am again releasing this code into the public domain: https://raw.github.com/laforge49/Asynchronous-Functional-Programming/master/Blip/src/main/scala/org/agilewiki/blip/ConcurrentLinkedBlockingQueue.scala (This is only 36 lines of code. :-)

Bill La Forge

 

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

 

 

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

On 28/10/2011 23:17, √iktor Ҡlang wrote:

> How do you deterministically provoke half-reads/half-writes to longs/doubles
> using this technique?
> How do you trigger reordering-effects?
> How do you avoid memory sync (test code makes code work, without test code
> it has visibility problems)?

Let alone the fact that the OS will have it's own ideas about which
threads run when...

2011/10/29 √iktor Ҡlang <viktor.klang@gmail.com>

2011/10/29 Vlad Patryshev <vpatryshev@gmail.com>

Multithreading is nondeterministic, but while testing we can make it deterministic (mostly): controlling which thread runs and which thread yields, it's doable, is not it?

How do you deterministically provoke half-reads/half-writes to longs/doubles using this technique?
How do you trigger reordering-effects?
How do you avoid memory sync (test code makes code work, without test code it has visibility problems)?
 

This tool looks promising:
Adversarial Memory for Detecting Destructive Races

It relies on code instrumentation to stretch the JMM and perform runtime analysis. It is not deterministic but it should make testing and reproducing concurrency related errors a lot simpler (and faster).

Cheers,
Sébastien

2011/10/29 Sébastien Bocq <sebastien.bocq@gmail.com>

2011/10/29 √iktor Ҡlang <viktor.klang@gmail.com>

2011/10/29 Vlad Patryshev <vpatryshev@gmail.com>

Multithreading is nondeterministic, but while testing we can make it deterministic (mostly): controlling which thread runs and which thread yields, it's doable, is not it?

How do you deterministically provoke half-reads/half-writes to longs/doubles using this technique?
How do you trigger reordering-effects?
How do you avoid memory sync (test code makes code work, without test code it has visibility problems)?
 

This tool looks promising:
Adversarial Memory for Detecting Destructive Races

It relies on code instrumentation to stretch the JMM and perform runtime analysis. It is not deterministic but it should make testing and reproducing concurrency related errors a lot simpler (and faster).

Thanks for the link!
 

Cheers,
Sébastien

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

Oh; the right stuff!

Thanks,
-Vlad


2011/10/29 Sébastien Bocq <sebastien.bocq@gmail.com>

2011/10/29 √iktor Ҡlang <viktor.klang@gmail.com>

2011/10/29 Vlad Patryshev <vpatryshev@gmail.com>

Multithreading is nondeterministic, but while testing we can make it deterministic (mostly): controlling which thread runs and which thread yields, it's doable, is not it?

How do you deterministically provoke half-reads/half-writes to longs/doubles using this technique?
How do you trigger reordering-effects?
How do you avoid memory sync (test code makes code work, without test code it has visibility problems)?
 

This tool looks promising:
Adversarial Memory for Detecting Destructive Races

It relies on code instrumentation to stretch the JMM and perform runtime analysis. It is not deterministic but it should make testing and reproducing concurrency related errors a lot simpler (and faster).

Cheers,
Sébastien