On Wednesday, October 17, 2018 at 7:47:05 PM UTC-4, Carl Mastrangelo wrote: > > Without forking this thread too much, I read your post a few months back > (the link you posted is dead though!). >
I fixed the link in the post. Thx. > 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. > While this technically is synchronization, it is wait free synchronization. The writers remain to wait-free (on architectures that support atomic increments, e.g. x86) while contending for write access to the cache line containing the long epoch counter. One processor will push through at a time, but there are no retry loops or other wait situations involved. 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?) > Yes, implementations that use wider forms of counters (e.g. using a LongAdder <https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/LongAdder.html> instead of volatile longs and atomic updaters) are certainlyu possible, and would not change the algorithm in any way. I found that in most use cases the number of writers is low enough and the rate of writing low enough enough (even when it is in the millions per second) that reducing contention on the counters is not worth the extra indirection cost of AtomicAdder. But you can implement variosus equivalent-logic striped scheme sthat ar > > 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://stuff-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.
