[concurrency-interest] Stricter read ordering

Tobias Lindaaker thobes at gmail.com
Wed Apr 23 11:28:36 EDT 2014


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> 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> 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> 
>> wrote:
>>> It will not scale, though, if there are many concurrent readers, 
>>> because of the CAS in read path.
>>> 
>>> -Roman

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140423/035989ec/attachment.html>


More information about the Concurrency-interest mailing list