Strange parallelism scaling behavior

[Tad Glines]

While testing the performance of a lock free data structure, I've encountered some strange performance numbers.

The code is here: https://gist.github.com/tadglines/c1e3c93267dca31ffbef

Running "go test -run TestScale" produces results like this:

C = 1: Avg time for 20000000 operations = 565.572033ms, ops/sec = 35362427.477032

C = 2: Avg time for 20000000 operations = 1.704945s, ops/sec = 11730583.684518

C = 3: Avg time for 20000000 operations = 1.306999668s, ops/sec = 15302222.708751

C = 4: Avg time for 20000000 operations = 298.103992ms, ops/sec = 67090681.563231

This is on a late model MacBook Air (4-core i7).

When I run this in an 8-core VM on a different system I get similar results and values of C>4 show around 250-300ms.

Can anyone shed some light on why the performance drops for 2 and 3 threads and then doubles (compared to 1 thread) for 4 or more threads?

I was expecting the performance to remain steady or decline slightly. As more threads try and perform the same operation I expected there to be more atomic operation retries and a decline in performance, but the sudden jump with 4 or more threads is surprising.

[Dmitry Vyukov]

You do not check return values. With GOMAXPROCS=1 and >2, most of your
operations quickly fail, that's what you measure.
Btw, I believe your implementation is broken in several ways. E.g.
producer stores an item, then fails to execute the CAS, at this point
another goroutine consumes the item, then the producer overwrites
another item with zero. The same happens with producers.

> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Tad Glines]

On Wed, May 15, 2013 at 12:18 PM, Dmitry Vyukov <dvy...@google.com> wrote:

You do not check return values. With GOMAXPROCS=1 and >2, most of your
operations quickly fail, that's what you measure.

That was it.

When I change the buffer size to n*4 and fill it with n*3 items, the fail rate (call to put or get failed) drops to less than 6% and the performance numbers declines as C increases at about the rate I was expecting. I was trying to test the performance in the absence of any synchronization operations which is why I didn't include the use of a "chan struct{}" to prevent overflow/exhaustion.

 

Btw, I believe your implementation is broken in several ways. E.g.
producer stores an item, then fails to execute the CAS, at this point
another goroutine consumes the item, then the producer overwrites
another item with zero. The same happens with producers

All empty cells have a 0 value, so the first CAS only succeeds if it can change the value from 0 to non-zero and this claim "ownership" of the cell.

The second CAS only succeeds if the front (or back) index hadn't been changed in the interim. If the second CAS fails, the cell is zero'ed (released) and the whole operation is tried again.

The logic assumes that each item has a unique value and is non-zero.

[Dmitry Vyukov]

Concurrency does not work that way.
Consider the queue is empty.
Consider producer 1 checks that the queue is not full.
Then producer 2 checks that the queue is not full.
Then producer 1 puts element 1 into cell 0.
Then consumer 1 gets element 1 from cell 0 and sets front to 1.
Then producer 2 puts element 2 into cell 0 and sets back to 1.
Now producer 1 fails to increment back and overwrites element 2 in
cell 0 with 0.

The implementation is full of such races.

[Tad Glines]

Hmmm.. Yes, that's an scenario I didn't think through completely.

Thanks for pointing it out.

[Dmitry Vyukov]

It's not just a single scenario. Once you've made something visible
you can't generally roll it back. And the CAS verifies only 1
variable, while depends on several; well actually even that variable
can be changed under the feet. The algorithm combines both things, it
is fundamentally broken.
Here is a good one:
http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue

[Tad Glines]

Thank you for directing me to http://www.1024cores.net

It looks like a wonderful resource in general.

In fact I found this link (http://www.1024cores.net/home/lock-free-algorithms/introduction#performance) which makes the case that blocking algorithms are usually faster than lock free or wait free.

And, on that page I also found this link (http://cs.brown.edu/~mph/HerlihyLM03/main.pdf) which appears to be a lock-free dequeue implementation which is exactly what I was trying to do.