Improve bucketing of native histograms with positive schema

[wyfo]

Following #1915, I've also started thinking about implementing native histograms in the Rust client. Looking at the current Go implementation:

client_golang/prometheus/histogram.go

Lines 661 to 698 in c316de0

	var (
	key int
	schema = atomic.LoadInt32(&hc.nativeHistogramSchema)
	zeroThreshold = math.Float64frombits(atomic.LoadUint64(&hc.nativeHistogramZeroThresholdBits))
	bucketCreated, isInf bool
	)
	if math.IsInf(v, 0) {
	// Pretend v is MaxFloat64 but later increment key by one.
	if math.IsInf(v, +1) {
	v = math.MaxFloat64
	} else {
	v = -math.MaxFloat64
	}
	isInf = true
	}
	frac, exp := math.Frexp(math.Abs(v))
	if schema > 0 {
	bounds := nativeHistogramBounds[schema]
	key = sort.SearchFloat64s(bounds, frac) + (exp-1)*len(bounds)
	} else {
	key = exp
	if frac == 0.5 {
	key--
	}
	offset := (1 << -schema) - 1
	key = (key + offset) >> -schema
	}
	if isInf {
	key++
	}
	switch {
	case v > zeroThreshold:
	bucketCreated = addToBucket(&hc.nativeHistogramBucketsPositive, key, 1)
	case v < -zeroThreshold:
	bucketCreated = addToBucket(&hc.nativeHistogramBucketsNegative, key, 1)
	default:
	atomic.AddUint64(&hc.nativeHistogramZeroBucket, 1)
	}

I've spotted several things to improve:

• Inf bucket can be computed directly, avoiding an extra if isInf
• bucket for positive schema can be computed with:
  _, exp2 := math.Frexp(math.Pow(frac, float64(int(1)<<schema))); exp2 + (exp << schema)
• if frac == 0.5 can be avoided by using math.Frexp(math.Nextafter(math.Abs(v), math.Inf(-1))) (zero threshold must be checked first)
• a single math.Abs(v) > zeroThreshold can replace the two tests (since math.Abs(v) is already computed); then nativeHistogramBucketsPositive, nativeHistogramBucketsNegative could become [2]sync.Map, indexed by math.Signbit(v)
• math.Frexp, as well as math.Nextafter can be replaced by a simplified version that skips special cases (NaN, Inf, etc.), since they’re already filtered out

The most important optimization is bucket computation — avoiding binary search, which gets slow as arrays grow (especially schema 8).
I’ve done experiments in Rust: https://github.com/wyfo/native-histogram (benchmark results can be found here)

I will try to submit a PR — hopefully next week.

[wyfo]

I forgot to add that math.Pow(frac, float64(int(1)<<schema)) can be replaced by simpler function that gives the same result with much better performance. For example

func pow(f float64, schema int) float64 {
    result := f
    for i := 0; i < schema; i++ {
        result *= result
    }
    return result
}

In my experiments, I tested various implementations of pow. However, Rust compiler is very different from Go, so I can't expect the same optimizations. But here is the Go version that should give:

func pow(f float64, schema int) float64 {
    result := f
    switch schema {
    case 8:
        result *= result
        fallthrough
    case 7:
        result *= result
        fallthrough
    case 6:
        result *= result
        fallthrough
    case 5:
        result *= result
        fallthrough
    case 4:
        result *= result
        fallthrough
    case 3:
        result *= result
        fallthrough
    case 2:
        result *= result
        fallthrough
    case 1:
        result *= result
    }
    return result
}