Some comments on overhead of measuring:
We measure here very common, and very fast operations. I don't know how fast next() could be, but if everything is in memory, it could be faster than 600 ns. I measured the fastest measured operation was processed at 0.091904 milliseconds , that would be 91904 nanoseconds. Measures was this divided by 256, so just 359 nanoseconds.
System.nanoTime() can be slower than that, according to this older article it can be 650 nanoseconds. We need to call it twice to measure, so 1'300 nanoseconds. Meaning, measuring in the worst case seens so far slows down the operation by factor 4.6 (worst case seen so far).
What we could do is use org.apache.jackrabbit.oak.stats Clock.Fast, which has a much lower overhead than calling System.nanoTime(). The name "Fast" is somewhat of a misnomer: the clock isn't really faster than other clocks, it's just less overhead. So getting the current time is fast. Resolution is low, but that wouldn't be a problem in our case, it's just that most of the time, operations would be 0 ns, and rarely 100s of ns. On average, that would even out (same as with the sampling it is using right now). The problems with Clock.Fast are:
Hard to get a hand on this instance.
It uses a thread pool executor service, which is problematic. If the same service is used by other threads that take milliseconds, then the clock is extremely inaccurate. I would be better to use a simple, separate daemon thread.