LongAdder with custom behavior?

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

LongAdder with custom behavior?

JSR166 Concurrency mailing list
While looking at LongAdder as a possible candidate for a concurrent counter, I noticed three things that made it seem surprising.  I am wondering what the rationale is for these since they don't make sense to me:

1.  LongAdder.sumThenReset seems to not be thread-safe.  If concurrent writes happen between reading and resetting of each Cell, then the write could get dropped.    This matches the behavior described in reset(), but makes the class less useful.   For instance, I would like sumThenReset to tally up all the mutations, and reset the counter back to zero without dropping mutations.  This would make it so I call sumThenReset later, and pick up any mutations I missed.

2.  Following up on the first point, the implementation of sumThenReset does two volatile operations on each Cell.value.  First it reads, followed by setting it to zero.  Why doesn't it use getAndSet on the value?  On the surface it would appear to be fewer synchronization points.   Also, it would nicely solve the first item.

3.   In the case that the LongAdder only ever increases in value (no resets), it would be possible to provide a means to see if it's equal to zero.  I believe this would be cheaper to implement than summing across all Cells.  The list of cells could be walked until there was a single nonzero cell, at which point it could return early.  This would be similar to the isEmpty() method on ConcurrentLinkedQueue, which doesn't need to walk the whole list.  

The reason I bring this up is that although the LongAdder class is non-final, there is no way to provide an isEmpty() myself.  All the access to the Cells and value are package private.  If I did implement this, I would have to give up the nice contention features.

Is LongAdder reusable or should I try making my own counter?  Also, were the issues I bring up now brought up during the design?

Carl

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list
Hi Carl,

On 12/01/2017 08:18 AM, Carl Mastrangelo via Concurrency-interest wrote:
While looking at LongAdder as a possible candidate for a concurrent counter, I noticed three things that made it seem surprising.  I am wondering what the rationale is for these since they don't make sense to me:

1.  LongAdder.sumThenReset seems to not be thread-safe.  If concurrent writes happen between reading and resetting of each Cell, then the write could get dropped.    This matches the behavior described in reset(), but makes the class less useful.   For instance, I would like sumThenReset to tally up all the mutations, and reset the counter back to zero without dropping mutations.  This would make it so I call sumThenReset later, and pick up any mutations I missed.

2.  Following up on the first point, the implementation of sumThenReset does two volatile operations on each Cell.value.  First it reads, followed by setting it to zero.  Why doesn't it use getAndSet on the value?  On the surface it would appear to be fewer synchronization points.   Also, it would nicely solve the first item.

You can achieve similar observable effect in the following way:

    public static long sumThenResetAtomic(LongAdder adder) {
        long sum = adder.sum();
        adder.add(-sum);
        return sum;
    }

This has better performance, because it does N reads and potentially only a single CAS which presents less disturbance to concurrent ongoing additions than N getAndSet(s) would.


3.   In the case that the LongAdder only ever increases in value (no resets), it would be possible to provide a means to see if it's equal to zero.  I believe this would be cheaper to implement than summing across all Cells.  The list of cells could be walked until there was a single nonzero cell, at which point it could return early.  This would be similar to the isEmpty() method on ConcurrentLinkedQueue, which doesn't need to walk the whole list. 

if you are talking about adder.isEmpty() being a cheaper variant of (adder.sum() == 0L), then all cells have to be summed in any case. Imagine an adder with 2 cells:

cell[0] == 42L
cell[1] == -42L

Regards, Peter


The reason I bring this up is that although the LongAdder class is non-final, there is no way to provide an isEmpty() myself.  All the access to the Cells and value are package private.  If I did implement this, I would have to give up the nice contention features.

Is LongAdder reusable or should I try making my own counter?  Also, were the issues I bring up now brought up during the design?

Carl


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list
Hi, 

responses inline:



On Fri, Dec 1, 2017 at 12:07 AM, Peter Levart <[hidden email]> wrote:
Hi Carl,

On 12/01/2017 08:18 AM, Carl Mastrangelo via Concurrency-interest wrote:
While looking at LongAdder as a possible candidate for a concurrent counter, I noticed three things that made it seem surprising.  I am wondering what the rationale is for these since they don't make sense to me:

1.  LongAdder.sumThenReset seems to not be thread-safe.  If concurrent writes happen between reading and resetting of each Cell, then the write could get dropped.    This matches the behavior described in reset(), but makes the class less useful.   For instance, I would like sumThenReset to tally up all the mutations, and reset the counter back to zero without dropping mutations.  This would make it so I call sumThenReset later, and pick up any mutations I missed.

2.  Following up on the first point, the implementation of sumThenReset does two volatile operations on each Cell.value.  First it reads, followed by setting it to zero.  Why doesn't it use getAndSet on the value?  On the surface it would appear to be fewer synchronization points.   Also, it would nicely solve the first item.

You can achieve similar observable effect in the following way:

    public static long sumThenResetAtomic(LongAdder adder) {
        long sum = adder.sum();
        adder.add(-sum);
        return sum;
    }

This has better performance, because it does N reads and potentially only a single CAS which presents less disturbance to concurrent ongoing additions than N getAndSet(s) would.

This approach would work, but why wouldn't sumThenReset implement it that way?     It isn't clear to me that two volatile accesses is faster than a single CAS.

 



3.   In the case that the LongAdder only ever increases in value (no resets), it would be possible to provide a means to see if it's equal to zero.  I believe this would be cheaper to implement than summing across all Cells.  The list of cells could be walked until there was a single nonzero cell, at which point it could return early.  This would be similar to the isEmpty() method on ConcurrentLinkedQueue, which doesn't need to walk the whole list. 

if you are talking about adder.isEmpty() being a cheaper variant of (adder.sum() == 0L), then all cells have to be summed in any case. Imagine an adder with 2 cells:

cell[0] == 42L
cell[1] == -42L


Right.  I tried to clarify that the value only ever goes up (by throwing on increment() and negative arguments to add().  If positive numbers only ever go in, and there is no overflow, then this would be a safe assumption.   I realize LongAdder can't make this assumption generally, but it isn't even possible for me to extend the class to enforce it myself.



 

Regards, Peter


The reason I bring this up is that although the LongAdder class is non-final, there is no way to provide an isEmpty() myself.  All the access to the Cells and value are package private.  If I did implement this, I would have to give up the nice contention features.

Is LongAdder reusable or should I try making my own counter?  Also, were the issues I bring up now brought up during the design?

Carl


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
It seems straightforward to use VarHandle getAndSet methods in LongAdder (and Striped64) and should be strictly more efficient.   I would write sumThenReset like this:

    /**
     * Equivalent in effect to {@link #sum} followed by {@link #reset}.
     * This method may apply for example during quiescent points
     * between multithreaded computations.  If there are updates
     * concurrent with this method, the returned value is <em>not</em>
     * guaranteed to be the final value occurring before the reset.
     *
     * @return the sum
     */
    public long sumThenReset() {
        final Cell[] cells = this.cells;
        long sum = getAndSetBase(0L);
        if (cells != null)
            for (Cell cell : cells)
                if (cell != null)
                    sum += cell.getAndSet(0L);
        return sum;
    }

With the use of getAndSet, we can then consider using sumThenReset for concurrency control.  A consumer can "harvest" counts that have collected in the LongAdder in Semaphore style, without losing any concurrent counts.  The hard part is writing the spec!  Unfortunately the name sumThenReset becomes a bit of a misnomer as it strongly implies non-thread-safety and use of reset().


On Thu, Nov 30, 2017 at 11:18 PM, Carl Mastrangelo via Concurrency-interest <[hidden email]> wrote:
While looking at LongAdder as a possible candidate for a concurrent counter, I noticed three things that made it seem surprising.  I am wondering what the rationale is for these since they don't make sense to me:

1.  LongAdder.sumThenReset seems to not be thread-safe.  If concurrent writes happen between reading and resetting of each Cell, then the write could get dropped.    This matches the behavior described in reset(), but makes the class less useful.   For instance, I would like sumThenReset to tally up all the mutations, and reset the counter back to zero without dropping mutations.  This would make it so I call sumThenReset later, and pick up any mutations I missed.

2.  Following up on the first point, the implementation of sumThenReset does two volatile operations on each Cell.value.  First it reads, followed by setting it to zero.  Why doesn't it use getAndSet on the value?  On the surface it would appear to be fewer synchronization points.   Also, it would nicely solve the first item.

3.   In the case that the LongAdder only ever increases in value (no resets), it would be possible to provide a means to see if it's equal to zero.  I believe this would be cheaper to implement than summing across all Cells.  The list of cells could be walked until there was a single nonzero cell, at which point it could return early.  This would be similar to the isEmpty() method on ConcurrentLinkedQueue, which doesn't need to walk the whole list.  

The reason I bring this up is that although the LongAdder class is non-final, there is no way to provide an isEmpty() myself.  All the access to the Cells and value are package private.  If I did implement this, I would have to give up the nice contention features.

Is LongAdder reusable or should I try making my own counter?  Also, were the issues I bring up now brought up during the design?

Carl

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list
It looks like we should be taking advantage of other VarHandle features, e.g. calling getAndAddRelease

On Fri, Dec 1, 2017 at 11:18 AM, Martin Buchholz <[hidden email]> wrote:
It seems straightforward to use VarHandle getAndSet methods in LongAdder (and Striped64) and should be strictly more efficient.   I would write sumThenReset like this:

    /**
     * Equivalent in effect to {@link #sum} followed by {@link #reset}.
     * This method may apply for example during quiescent points
     * between multithreaded computations.  If there are updates
     * concurrent with this method, the returned value is <em>not</em>
     * guaranteed to be the final value occurring before the reset.
     *
     * @return the sum
     */
    public long sumThenReset() {
        final Cell[] cells = this.cells;
        long sum = getAndSetBase(0L);
        if (cells != null)
            for (Cell cell : cells)
                if (cell != null)
                    sum += cell.getAndSet(0L);
        return sum;
    }

With the use of getAndSet, we can then consider using sumThenReset for concurrency control.  A consumer can "harvest" counts that have collected in the LongAdder in Semaphore style, without losing any concurrent counts.  The hard part is writing the spec!  Unfortunately the name sumThenReset becomes a bit of a misnomer as it strongly implies non-thread-safety and use of reset().


On Thu, Nov 30, 2017 at 11:18 PM, Carl Mastrangelo via Concurrency-interest <[hidden email]> wrote:
While looking at LongAdder as a possible candidate for a concurrent counter, I noticed three things that made it seem surprising.  I am wondering what the rationale is for these since they don't make sense to me:

1.  LongAdder.sumThenReset seems to not be thread-safe.  If concurrent writes happen between reading and resetting of each Cell, then the write could get dropped.    This matches the behavior described in reset(), but makes the class less useful.   For instance, I would like sumThenReset to tally up all the mutations, and reset the counter back to zero without dropping mutations.  This would make it so I call sumThenReset later, and pick up any mutations I missed.

2.  Following up on the first point, the implementation of sumThenReset does two volatile operations on each Cell.value.  First it reads, followed by setting it to zero.  Why doesn't it use getAndSet on the value?  On the surface it would appear to be fewer synchronization points.   Also, it would nicely solve the first item.

3.   In the case that the LongAdder only ever increases in value (no resets), it would be possible to provide a means to see if it's equal to zero.  I believe this would be cheaper to implement than summing across all Cells.  The list of cells could be walked until there was a single nonzero cell, at which point it could return early.  This would be similar to the isEmpty() method on ConcurrentLinkedQueue, which doesn't need to walk the whole list.  

The reason I bring this up is that although the LongAdder class is non-final, there is no way to provide an isEmpty() myself.  All the access to the Cells and value are package private.  If I did implement this, I would have to give up the nice contention features.

Is LongAdder reusable or should I try making my own counter?  Also, were the issues I bring up now brought up during the design?

Carl

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list


On Fri, Dec 1, 2017 at 11:27 AM, Martin Buchholz <[hidden email]> wrote:
It looks like we should be taking advantage of other VarHandle features, e.g. calling getAndAddRelease

Hmmm, that's won't work because we use cas failure as a signal to create more cells.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Hi Carl,

Carl Mastrangelo je 01. 12. 2017 ob 20:12 napisal:


On 12/01/2017 08:18 AM, Carl Mastrangelo via Concurrency-interest wrote:
While looking at LongAdder as a possible candidate for a concurrent counter, I noticed three things that made it seem surprising.  I am wondering what the rationale is for these since they don't make sense to me:

1.  LongAdder.sumThenReset seems to not be thread-safe.  If concurrent writes happen between reading and resetting of each Cell, then the write could get dropped.    This matches the behavior described in reset(), but makes the class less useful.   For instance, I would like sumThenReset to tally up all the mutations, and reset the counter back to zero without dropping mutations.  This would make it so I call sumThenReset later, and pick up any mutations I missed.

2.  Following up on the first point, the implementation of sumThenReset does two volatile operations on each Cell.value.  First it reads, followed by setting it to zero.  Why doesn't it use getAndSet on the value?  On the surface it would appear to be fewer synchronization points.   Also, it would nicely solve the first item.

You can achieve similar observable effect in the following way:

    public static long sumThenResetAtomic(LongAdder adder) {
        long sum = adder.sum();
        adder.add(-sum);
        return sum;
    }

This has better performance, because it does N reads and potentially only a single CAS which presents less disturbance to concurrent ongoing additions than N getAndSet(s) would.

This approach would work, but why wouldn't sumThenReset implement it that way?     It isn't clear to me that two volatile accesses is faster than a single CAS.

The name I gave - 'sumThenResetAtomic' is not correct. There's nothing atomic about the method. If one wanted to use it as is in a concurrent environment it should at least be synchronized so that  concurrent threads calling it do the right thing - to support your use case.

So my answer is speculative: probably because it would require synchronization and LongAdder was designed to not use any locks. If one wants to do it that way, (s)he can. LongAdder is just a low-level primitive with which you can build your concurrent logic.

I'm wondering why you need a fail-fast isEmpty() method though. Do you need to call it frequently? Why?

Regards, Peter



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
On 12/01/2017 02:18 AM, Carl Mastrangelo via Concurrency-interest wrote:

>
> I would like sumThenReset to tally up all the mutations, and reset
> the counter back to zero without dropping mutations.  This would make
> it so I call sumThenReset later, and pick up any mutations I missed.

It sounds like you are looking for a SNZI (scalable non-zero indicator).
(Google it). We ought to consider supplying one.

>
> the implementation of sumThenReset does two volatile operations on
> each Cell.value.  First it reads, followed by setting it to zero.
> Why doesn't it use getAndSet on the value?

Yes; thanks. This should usually be faster. Changes are now in jsr166
CVS and should some day propagate.

-Doug

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list


On Sat, Dec 2, 2017 at 5:41 AM, Doug Lea via Concurrency-interest <[hidden email]> wrote:
On 12/01/2017 02:18 AM, Carl Mastrangelo via Concurrency-interest wrote:

>
> I would like sumThenReset to tally up all the mutations, and reset
> the counter back to zero without dropping mutations.  This would make
> it so I call sumThenReset later, and pick up any mutations I missed.

It sounds like you are looking for a SNZI (scalable non-zero indicator).
(Google it). We ought to consider supplying one.

>
> the implementation of sumThenReset does two volatile operations on
> each Cell.value.  First it reads, followed by setting it to zero.
> Why doesn't it use getAndSet on the value?

Yes; thanks. This should usually be faster. Changes are now in jsr166
CVS and should some day propagate.

So we've implemented this optimization and it might provide the concurrency control Carl is looking for, but we're reluctant to promise anything in the spec along these lines.  After these changes, sumThenReset can be used to "drain" a "queue" where there is no data associated with each queue element, only a total count of elements.  But the name of the method is wrong for that use case, and it is likely to be misused - most queue elements do actually need to provide some data.  I'm reminded of the Unix signal fiasco - signals were originally designed to be data free, and duplicates could be discarded, but I think that was a mistaken design, and now we have siginfos that could be lost if signals arrive concurrently. 

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: LongAdder with custom behavior?

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Inline responses

On Sat, Dec 2, 2017 at 4:00 AM, Peter Levart <[hidden email]> wrote:
Hi Carl,

Carl Mastrangelo je 01. 12. 2017 ob 20:12 napisal:


On 12/01/2017 08:18 AM, Carl Mastrangelo via Concurrency-interest wrote:
While looking at LongAdder as a possible candidate for a concurrent counter, I noticed three things that made it seem surprising.  I am wondering what the rationale is for these since they don't make sense to me:

1.  LongAdder.sumThenReset seems to not be thread-safe.  If concurrent writes happen between reading and resetting of each Cell, then the write could get dropped.    This matches the behavior described in reset(), but makes the class less useful.   For instance, I would like sumThenReset to tally up all the mutations, and reset the counter back to zero without dropping mutations.  This would make it so I call sumThenReset later, and pick up any mutations I missed.

2.  Following up on the first point, the implementation of sumThenReset does two volatile operations on each Cell.value.  First it reads, followed by setting it to zero.  Why doesn't it use getAndSet on the value?  On the surface it would appear to be fewer synchronization points.   Also, it would nicely solve the first item.

You can achieve similar observable effect in the following way:

    public static long sumThenResetAtomic(LongAdder adder) {
        long sum = adder.sum();
        adder.add(-sum);
        return sum;
    }

This has better performance, because it does N reads and potentially only a single CAS which presents less disturbance to concurrent ongoing additions than N getAndSet(s) would.

This approach would work, but why wouldn't sumThenReset implement it that way?     It isn't clear to me that two volatile accesses is faster than a single CAS.

The name I gave - 'sumThenResetAtomic' is not correct. There's nothing atomic about the method. If one wanted to use it as is in a concurrent environment it should at least be synchronized so that  concurrent threads calling it do the right thing - to support your use case.

So my answer is speculative: probably because it would require synchronization and LongAdder was designed to not use any locks. If one wants to do it that way, (s)he can. LongAdder is just a low-level primitive with which you can build your concurrent logic.

Adding locks would be tantamount to just not using LongAdder at all.
 

I'm wondering why you need a fail-fast isEmpty() method though. Do you need to call it frequently? Why?

Well, I would like to call it frequently.  I'm playing around with SPSC and MPSC queues, and I need an approximate size of the queue.  In the MPSC queue case (so called Vyukov queue) its possible for the queue to appear empty briefly while being updated, so having a size counter would be nice.  There may be better ways of doing what I want, but it seemed reasonably fast enough to use LongAdder.  

As for speed, I would like to call sumThenReset as much as 10 million times per second, so it should be not so expensive.
 

Regards, Peter




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest