search

HdrHistogram / hdrhistogram-go

A pure Go implementation of Gil Tene's HDR Histogram.
MIT License
429 stars 64 forks source link

[perf] optimize ValueAtPercentile(s): introduce nextCountAtIdx() and reduce by 25.6% the on-cpu usage #46

Closed filipecosta90 closed 2 years ago

filipecosta90 commented 2 years ago

This PR optimizes ValueAtPercentile(s) by introducing nextCountAtIdx() and only updating the iterator highestEquivalentValue when required in order to reduce wasteful cpu usage. If we look at ValueAtPercentile numbers, It reduced by 25.6% the on-cpu usage.

master branch benchmark percentiles calculation:

% go test -bench="BenchmarkHistogramValueAtPercentile" -benchtime=10s -cpuprofile profile.out
goos: darwin
goarch: arm64
pkg: github.com/HdrHistogram/hdrhistogram-go
BenchmarkHistogramValueAtPercentile-8                             264561         42905 ns/op           0 B/op          0 allocs/op
BenchmarkHistogramValueAtPercentileGivenPercentileSlice-8          58002        214438 ns/op           0 B/op          0 allocs/op
BenchmarkHistogramValueAtPercentilesGivenPercentileSlice-8        173206         69352 ns/op         248 B/op          4 allocs/op

cpu.optimize.nextCountAtIdx branch benchmark percentiles calculation:

% go test -bench="BenchmarkHistogramValueAtPercentile" -benchtime=10s -cpuprofile profile.out
goos: darwin
goarch: arm64
pkg: github.com/HdrHistogram/hdrhistogram-go
BenchmarkHistogramValueAtPercentile-8                             369895         31900 ns/op           0 B/op          0 allocs/op
BenchmarkHistogramValueAtPercentileGivenPercentileSlice-8          83106        147954 ns/op           0 B/op          0 allocs/op
BenchmarkHistogramValueAtPercentilesGivenPercentileSlice-8        232894         52160 ns/op         248 B/op          4 allocs/op
codecov-commenter commented 2 years ago

Codecov Report

Merging #46 (164c49c) into master (35c7773) will increase coverage by 0.10%. The diff coverage is 100.00%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master      #46      +/-   ##
==========================================
+ Coverage   76.81%   76.91%   +0.10%     
==========================================
  Files           6        6              
  Lines         690      693       +3     
==========================================
+ Hits          530      533       +3     
  Misses         95       95              
  Partials       65       65
Impacted Files Coverage Δ
hdr.go 89.93% <100.00%> (+0.10%) :arrow_up:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 35c7773...164c49c. Read the comment docs.