Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

perf(approx_topk): Reduce memory usage of HyperLogLog in approx_topk. #15559

Merged
merged 9 commits into from
Jan 9, 2025

Conversation

jeschkies
Copy link
Contributor

@jeschkies jeschkies commented Dec 30, 2024

What this PR does / why we need it:

The count min sketch data structure backing the new approx_topk aggregation uses HyperLogLog (HLL) to track the actual cardinality of the aggregated vector.

We were using the sparse version of the HLL. However, that would result in a memory and allocation overhead.

                               │ before.log  │              after.log              │
                               │   sec/op    │   sec/op     vs base                │
HeapCountMinSketchVectorAdd-16   425.4m ± 2%   357.7m ± 3%  -15.91% (p=0.000 n=10)

                               │  before.log   │              after.log               │
                               │     B/op      │     B/op      vs base                │
HeapCountMinSketchVectorAdd-16   12.098Mi ± 0%   2.627Mi ± 0%  -78.29% (p=0.000 n=10)

                               │ before.log  │             after.log              │
                               │  allocs/op  │  allocs/op   vs base               │
HeapCountMinSketchVectorAdd-16   116.9k ± 0%   108.8k ± 0%  -6.92% (p=0.000 n=10)

Special notes for your reviewer:

Checklist

  • Reviewed the CONTRIBUTING.md guide (required)
  • Documentation added
  • Tests updated
  • Title matches the required conventional commits format, see here
    • Note that Promtail is considered to be feature complete, and future development for logs collection will be in Grafana Alloy. As such, feat PRs are unlikely to be accepted unless a case can be made for the feature actually being a bug fix to existing behavior.
  • Changes that require user attention or interaction to upgrade are documented in docs/sources/setup/upgrade/_index.md
  • If the change is deprecating or removing a configuration option, update the deprecated-config.yaml and deleted-config.yaml files respectively in the tools/deprecated-config-checker directory. Example PR

@jeschkies jeschkies requested a review from a team as a code owner December 30, 2024 09:47
@jeschkies jeschkies mentioned this pull request Dec 30, 2024
6 tasks
@jeschkies jeschkies requested review from chaudum and cstyan December 30, 2024 09:48
@jeschkies jeschkies changed the title (perf) Reduce memory usage of HyperLogLog in approx_topk. (perf): Reduce memory usage of HyperLogLog in approx_topk. Dec 30, 2024
@jeschkies jeschkies changed the title (perf): Reduce memory usage of HyperLogLog in approx_topk. perf(approx_topk): Reduce memory usage of HyperLogLog in approx_topk. Dec 30, 2024
@pull-request-size pull-request-size bot added size/S and removed size/M labels Dec 30, 2024
@jeschkies
Copy link
Contributor Author

Copy link
Contributor

@chaudum chaudum left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@@ -585,7 +587,8 @@ func (b *LabelsBuilder) LabelsResult() LabelsResult {

// Get all labels at once and sort them
b.buf = b.UnsortedLabels(b.buf)
sort.Sort(b.buf)
// sort.Sort(b.buf)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Line can be removed

@@ -19,7 +19,7 @@ func NewCountMinSketch(w, d uint32) (*CountMinSketch, error) {
Depth: d,
Width: w,
Counters: make2dslice(w, d),
HyperLogLog: hyperloglog.New16(),
HyperLogLog: hyperloglog.New16NoSparse(),
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think we should leave a comment.

// Sparse HLL sketches should result in less memory usage for cardinalities of 100k or less but the automatic transition from sparse
// to non-sparse sketches above that cardinality range results in significantly more memory allocs/bytes. 
// Until we have a reliable way of estimating the cardinality set in advance, always use non-sparse for faster performance.

Copy link
Contributor

@cstyan cstyan left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

good to know that the auto transition in the HLL library is this expensive 👍

@chaudum chaudum merged commit bef2043 into main Jan 9, 2025
60 checks passed
@chaudum chaudum deleted the karsten/benchmark-engine branch January 9, 2025 10:27
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants