Without forking this thread too much, I read your post a few months back (the link you posted is dead though!). One of the questions I had is that WRP still synchronizes all of the writers in writerCriticalSectionEnter, since they all will have to contend on the long. My question is if it's possible to shard that counter somehow, since presumably the number of writers is high, and they enter the writer critical section significantly more than the reader does? (and if it is possible, was this unnecessary for WRP?)
On Wednesday, October 17, 2018 at 5:34:09 AM UTC-7, Gil Tene wrote: > > See "WriterReaderPhaser: A story about a new (?) synchronization > primitive" > <http://gil-says.blogspot.com/2014/11/writerreaderphaser-story-about-new.html>. > > WriterReaderPhaser (WRP) was designed for the common pattern of speed or > latency critical writers writing and accumulating data into a data > structure (e.g. a stats collecting like a histogram), and less-critical > background threads occasionally or periodically gathering up that > accumulated data is a lossless manner, and provides for wait-free writers > and potentially blocking readers. It's a common pattern used and needed > when e.g. logging of metrics or other stats is performed periodically, and > I've used the pattern often enough that I decided it needs a new > synchronization primitive. > > For a full code example of how to use this synchronization primitive in > e.g. a classic double-buffered approach around a simple data structure, you > can see how an implementation of WriterReaderPhaser > <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/WriterReaderPhaser.java> > > is used in HdrHistogram's SingleWriterRecorder > <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/SingleWriterRecorder.java> > and Recorder > <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/Recorder.java> > classes, > both of which record data into an interval histogram, and provide for > lossless reading of that interval histogram. Those are classic examples of > stats written by latency critical writers in a wait-free manner, and > collected by a non-latency critical background thread, and > WriterReaderPhaser can be similarly used to coordinate this sort of work > around any sort of stats-gathering data structure. The WRP's current > implementation has the writer use an atomic increment (which translates to > a LOCK XADD on x86) to enter > <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/WriterReaderPhaser.java#L73> > > and leave > <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/WriterReaderPhaser.java#L91> > > the critical section. Single writer cases need no further synchronization, > and multi-writer cases would need to coordinate on writing to the common > data structure (e.g. a AtomicHistogram > <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/Recorder.java#L314> > or > ConcurrentHistogram > <https://github.com/HdrHistogram/HdrHistogram/blob/master/src/main/java/org/HdrHistogram/Recorder.java#L326> > > in Recorder, depending on whether or not auto-resizing of the histogram is > needed). > > A java implementation of WRP currently lives in HdrHistogram (which is > available on maven central). It is too small for its own package and > probably needs a better home. If interest in it grows, Martin can probably > find it a home in Agrona. Other implementations have been built in e.g. > other language versions of HdrHistogram (e.g. C > <https://github.com/HdrHistogram/HdrHistogram_c/tree/master/src>, .NET > <https://github.com/HdrHistogram/HdrHistogram.NET/blob/9d82f46d3abfd07d20df901e3fbcf015a8baf665/HdrHistogram/Utilities/WriterReaderPhaser.cs> > ). > > > On Tuesday, October 16, 2018 at 4:33:03 AM UTC-4, Mohan Radhakrishnan > wrote: >> >> Hi, >> There is streaming data everywhere like trading data , JVM >> logs.etc. Retrieval of statistics of this data need fast data structures. >> Where can I find the literature on such fast data structures to store and >> retrieve timestamps and data in O(!) time ? Should this always be >> low-level Java concurrent utilities ? >> >> Thanks, >> Mohan >> > -- You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
