[concurrency-interest] Lock-free implementation of min including assignment

Martin Buchholz martinrb at google.com
Tue Jan 24 16:20:21 EST 2012


Suggestions for further documentation improvement are welcome.

If and when lambdas arrive in jdk-land, we can consider adding methods like

long transformAndGet(lambda(long): long)

On Mon, Jan 23, 2012 at 03:33, Markus Jevring <m.jevring at iontrading.com>wrote:

>  Martin,
>
> I actually see now that both your and my implementation are identical.
> While mine has two different calls to CAS, yours has one, except it's
> essentially the same, as transform basically takes care of the if-statement
> that, in my code, differentiated between the two cases.
>
> Just thought I should clarify this, in case someone stumbles across my
> code, and thinks it's fine to simply remove the else-CAS.
>
> Markus
>
>
> On 19/01/2012 14:36, Martin Buchholz wrote:
>
>
>
> On Wed, Jan 18, 2012 at 23:48, Markus Jevring <m.jevring at iontrading.com>wrote:
>
>>  So, by paraphrasing what you have there, if I wanted something like
>> getAndMin(AtomicLong var, long l),
>> I would define transform() as: "return Math.min(current, l)" to get the
>> desired effect, right?
>>
>
>  Right.
>
>
>>  In essence, I'd be able to skip the cas operation in my else-case?
>>
>>
>  Right. Skipping the CAS when current == next is just an optimization,
> but an important one for transformations like min or max where current ==
> next is the common case.
>
>
>>  Similarly, minAndGet(AtomicLong var, long l) would simply return "next"
>> instead of "current", right?
>>
>>
>  Right.
>
>
>>  As other people have pointed out, both 'current' and 'min', as it were,
>> may have become obsolete by the time the function returns, but as long as
>> we keep the smallest value in 'var', we should be fine, right?
>>
>>
>  Right.
>
>
>>  Markus
>>
>>
>> On 18/01/2012 21:23, Martin Buchholz wrote:
>>
>>
>>
>> On Wed, Jan 18, 2012 at 06:16, Markus Jevring <m.jevring at iontrading.com>wrote:
>>
>>> If it does, I'm surprised it's not plastered all over the internet.
>>
>>
>>  We've written something here:
>>
>> http://g.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/atomic/package-info.java?view=co
>>
>>   * <p>It is straightforward to define new utility functions that, like
>>  * {@code getAndIncrement}, apply a function to a value atomically.
>>  * For example, given some transformation
>>  * <pre> {@code long transform(long input)}</pre>
>>  *
>>  * write your utility method as follows:
>>  *  <pre> {@code
>>  * long getAndTransform(AtomicLong var) {
>>  *   while (true) {
>>  *     long current = var.get();
>>  *     long next = transform(current);
>>  *     if (var.compareAndSet(current, next))
>>  *         return current;
>>  *   }
>>  * }}</pre>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120124/b24d60fa/attachment.html>


More information about the Concurrency-interest mailing list