[concurrency-interest] Re : Composite compare-and-swap based on two values

Jeff Hain jeffhain at rocketmail.com
Thu Sep 8 19:14:03 EDT 2011


It would be more efficient to put bothstates(value and boundary) in a single atomic long
(I don't see the need for stamp either).


inc()/dec():

Why just "inc" and "dec", and not "increment" and "decrement" for homogeneity with other methods, and clarity?
The doc says it returns true "if counter was not reset", which could be interpreted either as "if counter's value previously was not boundary (value after reset)" or as "if counter's value did not get set to boundary".
Though, your implementation aims at something different, which is returning true if counter's value did "jump" to zero (inc) or boundary (dec).
Also, if boundaryCrossed is set to true and CAS fails, it will remain true whatever happens next.

setBoundary(int):
Should use newBoundary when creating "next".
Is it intentional not to bring back value in [0,boundary] range,
or throw an exception, if new boundary is < to value?

stampHolder could be created once and for all outside the loops.
I ~think~ that also applies to "next" (fields not final but CAS done beforeother threads can see it).

-Jeff


________________________________
De : Oleksiy Khilkevich <oleksiy.khilkevich at gmail.com>
À : dholmes at ieee.org
Cc : Concurrency-interest at cs.oswego.edu
Envoyé le : Jeudi 8 Septembre 2011 18h50
Objet : Re: [concurrency-interest] Composite compare-and-swap based on two values


Hi All

Getting back to this I'd like to present what I've came up with. I need a volunteer for code review.

I'm going to give a tech talk about java.util.concurrent soon, so The Right Way(tm) and bug-free code is critical  

Here is a piece of cyclic counter responsible for reset

    // CounterState is private nested class to hold value and boundary, see attached source
    @Override
    public boolean reset() {
        for (;;) {
            int[] stampHolder = new int[1];
            CounterState current = stateRef.get(stampHolder); // 1
            int currentStamp = stampHolder[0];

            if (current.value == current.boundary) return false;

            CounterState next = new CounterState(current.boundary, current.boundary);
            if (stateRef.compareAndSet(current, next, currentStamp, currentStamp + 1)) {
                return true;
            }
        }
    }

If I am not mistaken, at (!) i can't just access stateRef.getReference().value and stateRef.getReference.boundary, as stamp can change in between of that reads, so i need to get 

Also in general, the more complex is shared state, the more performance degradation would be on state writes, as there is more contention over the shared state. 

I've attached the source in case you may wanna look

Thanks and waiting for the feedback
Oleksiy

2011/9/7 David Holmes <davidcholmes at aapt.net.au>

 
>But I 
should add that this form of DCAS is no different to choosing to encode your two 
values into one variable.
> David
>-----Original Message-----
>>From: David Holmes  [mailto:davidcholmes at aapt.net.au]
>>Sent: Wednesday, 7 September 2011  7:48 AM
>>To: Oleksiy Khilkevich
>>Cc: Concurrency-interest at cs.oswego.edu
>>
>>Subject: RE:  [concurrency-interest] Composite compare-and-swap based on two  values
>>
>>
>>Sorry - yes I was mixing AtomicMarkableReference and  AtomicStampedreference. AtomicStampedReference does present itself in a form  similar to DCAS.
>> 
>>Good  luck.
>> 
>>David
>>-----Original Message-----
>>>From: Oleksiy Khilkevich  [mailto:oleksiy.khilkevich at gmail.com]
>>>Sent: Tuesday, 6 September  2011 10:46 PM
>>>To: dholmes at ieee.org
>>>Cc: Concurrency-interest at cs.oswego.edu
>>>Subject: Re:  [concurrency-interest] Composite compare-and-swap based on two  values
>>>
>>>I guess you mean AtomicMarkableReference. stamped  one indeed provides the versioning that can help - it stores the int as a  stamp. I think it's quite possible to emulate DCAS with help of these  classes. 
>>>
>>>
>>>Regarding the reset() i'm just trying to stick to the contract i've  imposed on it (so it return true if the counter value was really reset).  Without requirement to return change status, i'd not bother at  all 
>>>
>>>
>>>But surprisingly to provide more information out of reset() i faced  this interesting issue. The drawback is the performance drop on reset() due  to possible contention, but i expect value to be changed magnitudes more  frequently than boundary, so performance should not be a problem.
>>>
>>>
>>>TBH, I can't even imagine the practical case when i'd need reset() at  all, I am very short on useful and realistic concurrency examples. If  anybody has a treasure chest of such examples, I'd be infinitely  grateful.
>>>
>>>
>>>But since reset() it's there, I now can't ignore it :)
>>>
>>>
>>>Oleksiy
>>>
>>>
>>>2011/9/6 David Holmes <davidcholmes at aapt.net.au>
>>>
>>> 
>>>>DCAS is  double-compare-and-swap. It allows you to atomically check and update two  independent memory locations. No current hardware that I  know supports it. It makes some lock-free algorithms trivial to  implement in theory.
>>>> 
>>>>AtomicStampedReference is  a special variant of storing two logical values in one variable, but if I  recall correctly the second variable here is limited to 1-bit - a mark or  stamp bit. This could be implemented by using the unused address bits to  hold the stamp/mark while the variable holds the actual data. But in the  JDK it is just doned with locking. Some lock free algorthims are based on  having this kind of composite variable.
>>>> 
>>>>But based on your  description of the counter and the boundary it isn't clear to me that  reset() needs to be atomic, as the boundary or value could change the  instant after you set them anyway.
>>>> 
>>>>Cheers,
>>>>David
>>>>-----Original  Message-----
>>>>>From: Oleksiy Khilkevich [mailto:oleksiy.khilkevich at gmail.com]
>>>>>Sent: Tuesday,  6 September 2011 10:07 PM
>>>>>To: dholmes at ieee.org; Concurrency-interest at cs.oswego.edu
>>>>>Subject: Re: [concurrency-interest] Composite compare-and-swap based on two  values
>>>>>
>>>>>It just happens on occasion :)
>>>>>
>>>>>
>>>>>2011/9/6 Oleksiy Khilkevich <oleksiy.khilkevich at gmail.com>
>>>>>
>>>>>Hi David and folks
>>>>>>
>>>>>>
>>>>>>2011/9/6 David Holmes <davidcholmes at aapt.net.au>
>>>>>>
>>>>>> 
>>>>>>>You can not compose  CAS operations to get atomic updates to multiple variables. A DCAS  would solve your problem but we don't have one :)  AtomicStampedReference (as mentioned by Daniel) is a very restricted  form of DCAS and in fact is implemented by locking in the  JDK.
>>>>>>> 
>>>>>>Can you tell in more detail about DCAS concept? Maybe some  relevant link? Google is not of much help unfortunately. I'll try to  figure AtomicStampedReference in the meantime.
>>>>>>
>>>>>> 
>>>>>>You either need a  mutual exclusion mechanism that is applied to all variables (eg  locking), or you need a protocol that allows optimistic updates and  can account for conflicts/contention. Or you encode both variables  into a single atomic variable.
>>>>>>I thought about encoding the state in a single variable as well,  but I was also looking for some general approach to such case.  Single-state variable is not very scalable.  
>>>>>> 
>>>>>>>I must admit though  that I don't really understand the semantics of your reset()  operation, and I'm unclear why the value and the boundary can be  modified independently.
>>>>>>> 
>>>>>>The cyclic counter is supposed to incrementally decrease its  value from some boundary till zero and set it value again to boundary,  in my implementation, the boundary is supposed to be adjustable, so  you can increase or decrease counter value space in thread-safe  manner. the reset() is supposed to reset the counter value to it's  boundary.
>>>>>>
>>>>>>
>>>>>>I plan to reuse this interface further to implement work  schedulers and few similar things on top of it in my further journey  through java.util.concurrent.*
>>>>>>
>>>>>>
>>>>>>I've attached the interface so you have an idea about it.
>>>>>>
>>>>>>
>>>>>>@Viktor: no, am looking into it, transactional memory is  somewhere deep inside my learning backlog :o)
>>>>>> 
>>>>>>Thanks for all your answers
>>>>>>Oleksiy
>>>>>>
>>>>>>
>>>>>> 
>>>>>>David  Holmes 
>>>>>>> 
>>>>>>>-----Original  Message-----
>>>>>>>>From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu]On  Behalf Of Oleksiy Khilkevich
>>>>>>>>Sent: Tuesday, 6  September 2011 8:14 PM
>>>>>>>>To: Concurrency-interest at cs.oswego.edu
>>>>>>>>Subject: [concurrency-interest] Composite compare-and-swap based on  twovalues
>>>>>>>>
>>>>>>>>Hi Concurrency Champs 
>>>>>>>>
>>>>>>>>
>>>>>>>>I'm implementing non-blocking cyclic counter mostly for  learning purposes, and faced the following problem, which i'm not  sure how to solve.
>>>>>>>>
>>>>>>>>
>>>>>>>>The method in question implements the following 
>>>>>>>>
>>>>>>>>
>>>>>>>>    /**
>>>>>>>>     * Sets counter value to initial  (boundary) value
>>>>>>>>     * @return true if counter value was  changed
>>>>>>>>     */
>>>>>>>>    boolean reset();
>>>>>>>>
>>>>>>>>
>>>>>>>>The implementation I'm not sure about
>>>>>>>>
>>>>>>>>
>>>>>>>>    @Override
>>>>>>>>    public boolean reset() {
>>>>>>>>        for (;;) {
>>>>>>>>            int curValue =  value.get();
>>>>>>>>            int curBoundary =  boundary.get();
>>>>>>>>            if (curValue ==  curBoundary) return false;
>>>>>>>>
>>>>>>>>
>>>>>>>>            // TODO: if  boundary and value were not changed, set the value to  boundary
>>>>>>>>
>>>>>>>>
>>>>>>>>            return true;
>>>>>>>>        }
>>>>>>>>    }
>>>>>>>>
>>>>>>>>
>>>>>>>>Here I have two values which are both AtomicIntegers and  which may change - value can be incremented or decremented by  another thread, and boundary can be changed too. 
>>>>>>>>
>>>>>>>>
>>>>>>>>I'm not quite sure how to do this without introducing  critical sections. In general the question refers to any shared  state change based on values of several other shared states.
>>>>>>>>
>>>>>>>>
>>>>>>>>What is the correct way to implement such operation  atomically without critical sections? IS it possible to build  composite CAS operations based on AtomicInteger#compareAndSet  ?
>>>>>>>>
>>>>>>>>
>>>>>>>>Thank you and kindly waiting for your ideas
>>>>>>>>Oleksiy
>>>>>>>>
>>>>>>>>
>>>>>>
>>>>>
>>>

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20110909/6f3ea871/attachment-0001.html>


More information about the Concurrency-interest mailing list