Binary search for large bucket count histograms

[mic-max]

Fixes #3248

Changes

• When using Metric.DefaultHistogramCountForBinarySearch or more buckets for a histogram, it will use binary search instead of linear search.
  • 1.0x faster for ~50 buckets
  • 3.7x faster for 1000 buckets no labels

Histogram Benchmark results from main with same the same parameters.

Method	BoundCount	Mean	Error	StdDev
HistogramHotPath	10	49.47 ns	1.016 ns	1.725 ns
HistogramHotPath	49	60.95 ns	1.217 ns	1.016 ns
HistogramHotPath	50	69.81 ns	2.435 ns	7.180 ns
HistogramHotPath	1000	358.74 ns	6.944 ns	14.340 ns

from mic-max:hist-binary - shows slightly slower performance for small bound count and great speedup for large bound counts.

Method	BoundCount	Mean	Error	StdDev
HistogramHotPath	10	57.19 ns	1.139 ns	1.481 ns
HistogramHotPath	49	70.11 ns	1.103 ns	0.978 ns
HistogramHotPath	50	71.75 ns	1.450 ns	1.286 ns
HistogramHotPath	1000	95.72 ns	1.932 ns	2.644 ns

For significant contributions please make sure you have completed the following items:

• [x] Appropriate CHANGELOG.md updated for non-trivial changes
• [x] Design discussion issue #
• [x] Changes in public API reviewed

Additional Notes

To find the point at which binary search would be faster I performed only the HistogramHotPath benchmark with 2 similar BoundCount values, one above and one below the threshold value. I continued until the time taken matched for both linear and binary search which happened to be at an array size of ~50 in this scenario.

Method	BoundCount	Mean	Error	StdDev
HistogramHotPath	49	68.81 ns	1.356 ns	1.268 ns
HistogramHotPath	50	68.46 ns	0.973 ns	0.910 ns

[codecov[bot]]

Codecov Report

Merging #3252 (2bb1212) into main (db0918e) will decrease coverage by 0.00%. The diff coverage is 100.00%.

Additional details and impacted files

@@            Coverage Diff             @@
##             main    #3252      +/-   ##
==========================================
- Coverage   87.10%   87.10%   -0.01%     
==========================================
  Files         280      280              
  Lines       10081    10112      +31     
==========================================
+ Hits         8781     8808      +27     
- Misses       1300     1304       +4     

Impacted Files	Coverage Δ
src/OpenTelemetry/Metrics/HistogramBuckets.cs	100.00% <100.00%> (ø)
src/OpenTelemetry/Metrics/MetricPoint.cs	82.99% <100.00%> (-0.12%)	:arrow_down:
src/OpenTelemetry/ProviderExtensions.cs	81.81% <0.00%> (-9.10%)	:arrow_down:
...Telemetry/Metrics/PeriodicExportingMetricReader.cs	72.72% <0.00%> (-5.46%)	:arrow_down:
src/OpenTelemetry/Logs/Pool/LogRecordSharedPool.cs	97.36% <0.00%> (-2.64%)	:arrow_down:
src/OpenTelemetry/Logs/OpenTelemetryLogger.cs	86.66% <0.00%> (-2.23%)	:arrow_down:
....Prometheus.HttpListener/PrometheusHttpListener.cs	81.33% <0.00%> (-1.34%)	:arrow_down:
...tation/OpenTelemetryProtocolExporterEventSource.cs	85.00% <0.00%> (+10.00%)	:arrow_up:
...Propagators/OpenTelemetryPropagatorsEventSource.cs	100.00% <0.00%> (+12.50%)	:arrow_up:

[github-actions[bot]]

This PR was marked stale due to lack of activity and will be closed in 7 days. Commenting or Pushing will instruct the bot to automatically remove the label. This bot runs once per day.

[github-actions[bot]]

Closed as inactive. Feel free to reopen if this PR is still being worked on.

[mic-max]

Please reopen

[github-actions[bot]]

This PR was marked stale due to lack of activity and will be closed in 7 days. Commenting or Pushing will instruct the bot to automatically remove the label. This bot runs once per day.

[github-actions[bot]]

Closed as inactive. Feel free to reopen if this PR is still being worked on.

[mic-max]

Please reopen - ready for review.

If someone can also perform the benchmarks on their PC that would be great to see how it compares. Instructions:

1. git checkout upstream/main
2. cd tests/Benchmarks/
3. notepad Metrics/HistogramBenchmarks.cs and modify the lines to [Params(10, 49, 50, 1000)] and private const int MaxValue = 10000;
4. dotnet run -c Release -f net6.0 -- -f *HistogramHotPath*
5. Copy table to a notepad document
6. Download my branch: zip file link
7. cd tests/Benchmarks/
8. dotnet run -c Release -f net6.0 -- -f *HistogramHotPath*
9. Copy table to the notepad document.
10. Share the document here as a comment :)

[utpilla]

Add unit tests to ensure that we update the correct buckets when using binary search.

[github-actions[bot]]

This PR was marked stale due to lack of activity and will be closed in 7 days. Commenting or Pushing will instruct the bot to automatically remove the label. This bot runs once per day.

[xiang17]

I also had a question on how to evaluate whether it's worth the preprocessing time. There needs to be a balance. If we preprocess O(n) just for optimizing a couple of queries which has an O(log(n)) complexity for 10% improvement, it might not be worth it. So I think it's crucial to have an idea on (1) how often the query happens and (2) how long the preprocessing takes.

The issue #3248 mentioned that some customers like to have faster search, which makes sense. But is it worth to add the O(n) memory and CPU burden from the preprocessing in construction of all the MetricPoint instances to all customers?

[github-actions[bot]]

This PR was marked stale due to lack of activity and will be closed in 7 days. Commenting or Pushing will instruct the bot to automatically remove the label. This bot runs once per day.

[github-actions[bot]]

Closed as inactive. Feel free to reopen if this PR is still being worked on.