* The library implements a sparse storage approach where only populated buckets consume memory and count towards the bucket limit. * This differs from the OpenTelemetry implementation, which uses dense storage. While dense storage allows for O(1) time insertion of * individual values, our sparse representation requires O(log m) time where m is the bucket capacity. However, the sparse * representation enables more efficient storage and provides a simple merging algorithm with runtime linear in the number of * populated buckets. Additionally, this library also provides an array-backed sparse storage, ensuring cache efficiency. *
* The sparse storage approach offers significant advantages for distributions with fewer distinct values than the bucket count, * allowing the library to achieve representation of such distributions with an error so small that it won't be noticed in practice. * This makes it suitable not only for exponential histograms but also as a universal solution for handling explicit bucket * histograms. * *
* Before we merge the buckets, we need to take care of the special zero-bucket and bring both histograms to the same scale. *
* For the zero-bucket, we merge the zero threshold from both histograms and collapse any overlapping buckets into the resulting new * zero bucket. *
* In order to bring both histograms to the same scale, we can make adjustments in both directions: we can increase or decrease the * scale of histograms as needed. *
* See the upscaling section for details on how the upscaling works. Upscaling helps prevent the precision of * the result histogram merged from many histograms from being dragged down to the lowest scale of a potentially misconfigured input * histogram. For example, if a histogram is recorded with a too low zero threshold, this can result in a degraded scale when using * dense histogram storage, even if the histogram only contains two points. * *
* (x - l) / l = (u - x) / u ** * where {@code l} is the lower bucket boundary and {@code u} is the upper bucket boundary. *
* This assumption allows us to increase the scale of histograms without increasing the bucket count. Buckets are simply mapped to * the ones in the new scale containing the point of least relative error of the original buckets. *
* This can introduce a small error, as the original center might be moved slightly. Therefore, we ensure that the upscaling happens * at most once to prevent errors from adding up. The higher the amount of upscaling, the less the error (higher scale means smaller * buckets, which in turn means we get a better fit around the original point of least relative error). * *
* This offers significant benefits for distributions with fewer distinct values: * If we have at least as many buckets as we have distinct values to store in the histogram, we can represent this distribution with * a much smaller error than the dense representation. * This can be achieved by maintaining the scale at the maximum supported value (so the buckets become the smallest). * At the time of writing, the maximum scale is 38, so the relative distance between the lower and upper bucket boundaries is * {@code (2^2^(-38))}. *
* The impact of the error is best shown with a concrete example: * If we store, for example, a duration value of {@code 10^15} nanoseconds (= roughly 11.5 days), this value will be stored in a * bucket that guarantees a relative error of at most {@code 2^2^(-38)}, so roughly 2.5 microseconds in this case. * As long as the number of values we insert is lower than the bucket count, we are guaranteed that no down-scaling happens: * In contrast to dense storage, the scale does not depend on the spread between the smallest and largest bucket index. *
* To clarify the difference between dense and sparse storage, let's assume that we have an empty histogram and the maximum scale is * zero while the maximum bucket count is four. * The same logic applies to higher scales and bucket counts, but we use these values to get easier numbers for this example. * The scale of zero means that our bucket boundaries are {@code 1, 2, 4, 8, 16, 32, 64, 128, 256, ...}. * We now want to insert the value {@code 6} into the histogram. The dense storage works by storing an array for the bucket counts * plus an initial offset. * This means that the first slot in the bucket counts array corresponds to the bucket with index {@code offset} and the last one to * {@code offset + bucketCounts.length - 1}. * So if we add the value {@code 6} to the histogram, it falls into the {@code (4,8]} bucket, which has the index {@code 2}. *
* So our dense histogram looks like this: * *
* offset = 2 * bucketCounts = [1, 0, 0, 0] // represent bucket counts for bucket index 2 to 5 ** * If we now insert the value {@code 20} ({@code (16,32]}, bucket index 4), everything is still fine: * *
* offset = 2 * bucketCounts = [1, 0, 1, 0] // represent bucket counts for bucket index 2 to 5 ** * However, we run into trouble if we insert the value {@code 100}, which corresponds to index 6: That index is outside of the bounds * of our array. * We can't just increase the {@code offset}, because the first bucket in our array is populated too. * We have no other option other than decreasing the scale of the histogram, to make sure that our values {@code 6} and {@code 100} * fall in the range of four consecutive buckets due to the bucket count limit of the dense storage. *
* In contrast, a sparse histogram has no trouble storing this data while keeping the scale of zero: * *
* bucketIndiciesToCounts: {
* "2" : 1,
* "4" : 1,
* "6" : 1
* }
*
*
* Downscaling on the sparse representation only happens if either:
*