These are chat archives for HdrHistogram/HdrHistogram

6th
Mar 2016
Gil Tene
@giltene
Mar 06 2016 00:59
@marshallpierce It helps to start with visualizing the buckets and sub-buckets. Lets start with the requirements:
We are given a number of decimal points of accuracy that we need to maintain. This means that results need to be accurate to within one unit up to the decimal point range given. So e.g. given a 3 decimal point accuracy, the expectation is obviously for "+/- 1 unit at 1000". It also means that it's "ok to be +/- 2 units at 2000". The "tricky" thing (the reason for that 2x you ask about) is that it is NOT ok to be +/- 2 units at 1999. Only starting at 2000. So we internally, we need to maintain single unit resolution to 2x 10^decimalPoints.
Gil Tene
@giltene
Mar 06 2016 01:04
When this is converted internally to powers of two, the same 2x thing is maintained. Hence 2 * (long) Math.pow(10, numberOfSignificantValueDigits);
And subBucketCountMagnitude = (int) Math.ceil(Math.log(largestValueWithSingleUnitResolution)/Math.log(2));
With that part hopefully explained (i.e. a bucket has 2 x 1024 sub buckets in it if we are using 3 decimal points), you need to imagine how the buckets (each of which has 2048 sub-buckets) overlap:
The 0'th bucket covers from 0...2047
Gil Tene
@giltene
Mar 06 2016 01:09
The 1'th bucket covers from 2048..4097 in multiples of 2
The 2'h bucket covers from 4096..8191 in multiple of 4
...
Bucket 0 is "special" here. It is the only one that has 2048 entires. All the rest have 1024 entries (because their bottom half overlaps with and is already covered the previous buckets).
We can think of this as needed storage for N+1 buckets, each with enough slots to hold 1/2 of the largestValueWithSingleUnitResolution (the lower half is covered by previous buckets), and the +1 being used for the lower half of the 0'th bucket.
Gil Tene
@giltene
Mar 06 2016 01:18
The indexing math in AbstractHistogram#countsArrayIndex uses a trick where it subtracts subBucketHalfCount from subBucketIndex when computing the index. This subtraction will result in a positive value in all buckets except the 0th bucket (since a value is only in one of those bucket if it is larger than half the bucket's starting-at-0 range). For bucket 0, the negative result works because the bucketBaseIndex for bucket 0 is half-way through it's sub-buckets...
Make sense?
Marshall Pierce
@marshallpierce
Mar 06 2016 02:02
I'll read through, scribble on my bucket diagrams, and report back. :)
(context: I'm working on a Rust port)
Marshall Pierce
@marshallpierce
Mar 06 2016 02:17
This does all make sense. Thanks for the clarification. I'll keep digging. Also, I'll make a PR to add all this info in javadoc in the relevant places in AbstractHistogram if you'd want that.
Marshall Pierce
@marshallpierce
Mar 06 2016 02:40
Seems like largestValueWithSingleUnitResolution could be (2 * 10^(precision)) - 1, though that's probably going to make a difference almost never
Gil Tene
@giltene
Mar 06 2016 04:34
Re: the -1 of
On the
Marshall Pierce
@marshallpierce
Mar 06 2016 04:36
I'll enqueue another question -- I'm not clear on why leadingZeroCountBase is defined the way it is. Is it because it represents the number of leading zeros of the largest value that can fit in bucket 0, namely 64 - (subBucketHalfCountMagnitude + 1)?
Gil Tene
@giltene
Mar 06 2016 04:37
LargestValueWith... Thing: you are technically correct. But (a) larger than required is ok (smaller than required would be incorrect). And (b) since we limit decimal points to 5 or 6, and we round up to nearest power of 2, it will matter exactly never...
Marshall Pierce
@marshallpierce
Mar 06 2016 04:37
Ah, indeed. Limiting the decimal points to 5ish is nice also because you know subBucketCount will never get too crazy, so you don't have to worry about overflowing
Gil Tene
@giltene
Mar 06 2016 04:37
If you put together a rust port, we should add it as a repo like the others (c, Python, erlang).
Marshall Pierce
@marshallpierce
Mar 06 2016 04:38
Yep, I'll send it your way once it's more complete
If you want to gaze into the pile of rubble, it's currently at https://github.com/ogeagla/HdrHistogram_Rust
Gil Tene
@giltene
Mar 06 2016 04:38
Please make sure to go all the way to supporting the logging format. Having all the variants be able to share a wire format is very helpful.
Marshall Pierce
@marshallpierce
Mar 06 2016 04:38
Yep, definitely. I want to get Phaser support in there too.
My long term goal (which I'd love to pick your brain on some time) is to build a statistically sound way of handling all metrics, which for histogram-suitable metrics would mean that the wire format would be how histograms are reported to the mothership, and are then aggregated into longer timeframes there
My thoughts on that aren't fully formed yet, but basically it comes down to everything can be viewed as a (possibly discontinuous) function, and for certain types of data, we can effectively compress it to a single number (e.g. we may record only max queue depth over the last minute because we do not care about other numbers). I talked a little to a statistician and they told me that I wasn't crazy.
Gil Tene
@giltene
Mar 06 2016 04:42
Yup. A time series database for latency information should use histogram wire format blobs as its basic value type.
Marshall Pierce
@marshallpierce
Mar 06 2016 04:45
Really what's bothering me about current metrics processing systems is that they have no way to express the semantics that are valid for a given sort of data. Numbers aren't all the same. You can't do the same things with a number like queue depth (a point-in-time assessment of a single attribute of a complex system that depends on all previous time) that you can with, say, 99.9%tile service time.
Gil Tene
@giltene
Mar 06 2016 04:46
Check out Khronus on github (use that exact spelling).
Marshall Pierce
@marshallpierce
Mar 06 2016 04:46
Noted.
Gil Tene
@giltene
Mar 06 2016 04:47
We really need a JavaScript port of HdrHistogram so that statd
Marshall Pierce
@marshallpierce
Mar 06 2016 04:47
Ye gods. It'll do pretty crazy things on 32bit platforms with the silent conversion to floats...
Gil Tene
@giltene
Mar 06 2016 04:47
statsd would work
Marshall Pierce
@marshallpierce
Mar 06 2016 04:48
oh right, not a browser.
Typed arrays could probably be made to work.
Gil Tene
@giltene
Mar 06 2016 04:48
(Btw, sitting on a plane to London, typing on an iPhone, which is why this text works out badly)
Marshall Pierce
@marshallpierce
Mar 06 2016 04:48
No problem, I appreciate your time. :)
Did I get it right w.r.t. leadingZeroCountBase?
Gil Tene
@giltene
Mar 06 2016 04:51
Re: your leadingZeroCountBaee question: the math works out this way. The reason I define this as a computed-at-I it-time variable is so that the hot path won't have to do the extra operations.
The hot path is pretty fast. In Java on my i7 haswell MacBook Pro can do >200M recordValue() calls per second.
Marshall Pierce
@marshallpierce
Mar 06 2016 04:54
Hm. I still don't really understand the reason for the -1. Also, wouldn't that get weird when subBucketCountMagnitude = 0, and therefore == subBucketHalfCountMagnitude
(I'm assuming, because in all other cases, sBHCM = sBCM - 1)
Gil Tene
@giltene
Mar 06 2016 04:58
It's 64 - subBucketMagnitude.
Marshall Pierce
@marshallpierce
Mar 06 2016 05:00
OK. So, would this be a good description then: "the number of leading zeros for the biggest value that will fit in bucket 0"
Gil Tene
@giltene
Mar 06 2016 05:01
And because the smallest number of decimal points is 0, and for that largestValueWitjSingleUnitResution will be 2, we don't run into the edge you worried about
Marshall Pierce
@marshallpierce
Mar 06 2016 05:01
Ah, OK.
Gil Tene
@giltene
Mar 06 2016 05:01
Yes. That would be s good description
Marshall Pierce
@marshallpierce
Mar 06 2016 05:02
OK, I think I've taken enough of your time for one evening; thanks for the help. I'm sure I'll have other questions later, but I can proceed further through the record path now and actually have some confidence in what I'm blindly porting.
Gil Tene
@giltene
Mar 06 2016 05:03
Always good to have someone scrutinize the math and edge conditions....
I'll check here again after I land in London...
Marshall Pierce
@marshallpierce
Mar 06 2016 05:04
OK, have fun in London!
Gil Tene
@giltene
Mar 06 2016 05:05
Doing a talk on Hardware Transactionsl Memory (thinking up talk flow now, slides tomorrow).
Marshall Pierce
@marshallpierce
Mar 06 2016 05:05
Ah. QCon London?
Gil Tene
@giltene
Mar 06 2016 05:06
Yup.
Marshall Pierce
@marshallpierce
Mar 06 2016 05:29
largestValueWithSingleUnitResolution can be 2 * 10^0 = 2 at the smallest, and subBucketCountMagnitude = log_2(largestValueWithSingleUnitResolution) = 1, so I think the ternary here is unnecessary since sBCM is never 0.
subBucketHalfCountMagnitude = ((subBucketCountMagnitude > 1) ? subBucketCountMagnitude : 1) - 1;
Also, I think that's just Math.max(subBucketCountMagnitude, 1) - 1 even if the ternary is necessary, and max can be implemented with sufficient bit twiddling to avoid a branch, which I assume/hope has been done
Anyway, I'm off to sleep; I'll be interested to see what you have to say on TSX and such things. Cheers