Databases
StackOverflow2013
Postsdbo
POIs it possible to efficiently implement a seqlock in Java?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIs it possible to efficiently implement a seqlock in Java?
    primarykey
    data
    text
    <p>Another <a href="https://stackoverflow.com/q/14660529/149138">question</a> made me wonder if the <a href="http://en.wikipedia.org/wiki/Seqlock" rel="nofollow noreferrer">seqlock</a> can be efficiently implemented with a volatile version counter in Java.</p> <p>Here's a prototypical implementation, for the case there will only ever be a single writer thread:</p> <pre><code>class Seqlock { private volatile long version = 0; private final byte[] data = new byte[10]; void write(byte[] newData) { version++; // 1 System.arraycopy(newData, 0, data, 0, data.length); // 2 version++; // 3 } byte[] read() { long v1, v2; byte[] ret = new byte[data.length]; do { v1 = version; // 4 System.arraycopy(data, 0, ret, 0, data.length); // 5 v2 = version; // 6 } while (v1 != v2 || (v1 &amp; 1) == 1); } } </code></pre> <p>The basic idea is to increment the version number before and after writing, and for readers to check they got a "consistent" read by verifying that the version numbers were the same and even, as odd indicates a "write in progress".</p> <p>There are all sorts of happens-before relationships between the key actions in the writer thread and readers threads since version is volatile.</p> <p>I can't, however, see what prevents the write at (2) from moving up above (1) and thus cause a reader to see a write in progress.</p> <p>For example, the following synchronization order of volatile reads and writes, using the labels in the comments next to each line (showing also the <code>data</code> reads and writes which are not volatile and thus not part of the synchronization order, indented):</p> <pre><code>1a (version is now 1) 2a (not part of the synchronization order) 3 (version is now 2) 4 (read version == 2, happens before 3) 5 (not part of the synchronization order) 6 (read version == 2, happens before 4 and hence 3) 1b (second write, version is now 3) 2b (not part of the synchronization order) </code></pre> <p>ISTM that there is no happens-before between 5 (the read of the data) and 2b (the second write of the data, so it is possible for 2b to occur before the read and wrong data to be read.</p> <p>If that's true, does declaring <code>write()</code> as <code>synchronized</code> help?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USBeeOnRope
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIs it possible to efficiently implement a seqlock in Java?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIs it possible to efficiently implement a seqlock in Java?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POIs it possible to efficiently implement a seqlock in Java?
      1. USjmetcalfe
      1. VTFavorite
    1. COi can answer the last question easily: declaring the write synchronized is meaningless if read is not synchronized. as for whether or not volatile works on its own, i'm still pondering that one.
      singulars
      1. POIs it possible to efficiently implement a seqlock in Java?
      1. USjtahlborn
    2. COmay not be what you are looking for, but you can solve this problem very simply in java (with the same guarantees) using a simple volatile reference to a byte[] which is assigned in the `write()` method.
      singulars
      1. POIs it possible to efficiently implement a seqlock in Java?
      1. USjtahlborn
    3. COI cannot understand your "synchronization order". How many threads do you have there? In the fourth line, what exactly do you mean by `4 (read version == 2, happens before 3)`? What is happening first? I'd suggest that you draw a "table", each column is a thread, each line is "an instant".
      singulars
      1. POIs it possible to efficiently implement a seqlock in Java?
      1. USBruno Reis
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload