[concurrency-interest] Stricter read ordering

Peter Levart peter.levart at gmail.com
Wed Apr 23 17:25:42 EDT 2014


Hi Tobias,

I you don't mind keeping 2 mirrored variants of your state (two mirrored 
memory mapped files in your case, or one file with duplicate/striped 
records) and applying all modifications to both copies, then the 
following might interest you:

http://sourceforge.net/projects/ccfreaks/files/papers/LeftRight/leftright-extended.pdf


Regards, Peter

On 04/23/2014 05:28 PM, Tobias Lindaaker wrote:
> Yes, exactly, writes tend to get more expensive, so avoiding them for 
> the read case is desired.
>
> As I wrote in my reply to Peter Kaiser, the actual state that is 
> guarded is a ByteBuffer.
> This ByteBuffer contains multiple records, and readers read one record 
> and need that to be consistent, while writers typically update 
> multiple records at once.
>
> And to answer Peters most recent question:
>
>
>     On 23 Apr 2014, at 17:00 , Kaiser, Peter
>     <Peter.Kaiser at compuware.com <mailto:Peter.Kaiser at compuware.com>>
>     wrote:
>>     Ok, I see. Do the reader threads apply any modifications to the
>>     state, so that they each need an individual copy of the state?
>>     As the state has to be copied anyway to keep the program
>>     correctly synchronized there would have to be some very good
>>     arguments to use advanced synchronization mechanisms for a
>>     problem like this.
>>     If the state could be provided as an immutable snapshot to the
>>     readers moving all the logic to the update method would seem to
>>     be a good solution to me. Also that way reads wouldn't be able to
>>     cause any memory problems by creating too much instances of the
>>     state object. If it's not possible to store the state in an
>>     immutable object, then would simply cloning it in the read method
>>     be a possibility for you? Of course you would have one more
>>     instance of the state object, but would that be a problem?
>
>
> The reader threads do not apply any modifications to the state, they 
> do computation based on the state, which might later result in writes 
> back.
>
> Perhaps I shouldn't have simplified the code so much, but rather kept 
> it closer to what it actually is, here is another version, where the 
> state is closer to what it is in our actual application, but the data 
> stored in it is still simplified:
>
>     class VersionedData {
>       // this is the overhead I use to manage consistency
>       private final volatile long written;
>       private final volatile long next;
>
>       // the protected data, this typically a memory mapped file
>       private final ByteBuffer buffer;
>       VersionedData( ByteBuffer buffer ) { this.buffer = buffer; }
>       public synchronized void update( Iterable<DataCarrier> data ) {
>         long next = this.next + 1;
>         this.next = next;
>         for (DataCarrier cursor : data) {
>           int offset = data.offset * 8;
>           buffer.putInt( offset    , data.x );
>           buffer.putInt( offset + 4, data.y );
>         }
>         this.written = next;
>       }
>
>       public void read(DataCarrier cursor) {
>         // I allow multiple readers, so this method is not synchronized
>         int x, y, offset = cursor.offset * 8;
>         long version;
>         do {
>           version = this.written;
>           x = buffer.getInt(offset);
>           y = buffer.getInt(offset + 4);
>         } while ( version != this.next );
>         cursor.x = x;
>         cursor.y = y;
>       }
>     }
>
>
> Reading snapshots from different versions does not matter, but x and y 
> have to be consistent with one another.
>
> Readers typically instantiate one DataCarrier and do multiple reads 
> using the same instance, changing the offset of it in between, this to 
> avoid creating too many objects since neither escape analysis nor 
> garbage collection is as good as anyone would want it to be. Again 
> this being the sad truth about coding for the JVM, the happy truth of 
> course being that many many other things are absolutely amazing.
>
> -tobias
>
> On 23 Apr 2014, at 16:58 , Aleksey Shipilev 
> <aleksey.shipilev at oracle.com <mailto:aleksey.shipilev at oracle.com>> wrote:
>
>> +1. Dragging us back to StampedLock example, the rationale for doing
>> ordered reads is to avoid writes on the read path.
>>
>> Barring the locks (scalability hit), volatile writes / releasing stores
>> (still a potential scalability hit), or putting (x, y) into a wrapper
>> instance (cache misses, yay!), the only thing you are left with is
>> ordering the reads with fences.
>>
>> If reads greatly out-weight writes, plus the data is encapsulateable
>> into the single instance, plus one possible cache miss is not an issue,
>> I would prefer to have the actual wrapper instance, though. I think
>> that's Peter Kaiser's point, although OP's example is greatly
>> simplified, and OP's non-simplified case may invalidate any of these
>> prerequisites.
>>
>> -Aleksey.
>>
>> On 04/23/2014 06:29 PM, Tobias Lindaaker wrote:
>>> That is one of the approaches we have in our benchmark suite for
>>> this, and we also concluded that the CAS in read() would have a too
>>> substantial impact on the scalability of the algorithm.
>>>
>>> -tobias
>>>
>>> On 23 Apr 2014, at 16:16 , Roman Elizarov <elizarov at devexperts.com 
>>> <mailto:elizarov at devexperts.com>>
>>> wrote:
>>>> It will not scale, though, if there are many concurrent readers,
>>>> because of the CAS in read path.
>>>>
>>>> -Roman
>
>
>
> _______________________________________________
> 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/20140423/fa596644/attachment.html>


More information about the Concurrency-interest mailing list