Allocation tracker: fix the live heap tracking by r1viollet · Pull Request #453 · DataDog/ddprof

r1viollet · 2025-10-21T14:27:14Z

What does this PR do?

Replace the bitset data structure with something that will not suffer from collisions.
Please refer to the allocation_tracker.md file for up to date notes.

Motivation

Ensure that allocation tracking is correct.

Additional Notes

NA

How to test the change?

There are benchmarks in this PR. They are mostly generated through AI. I do have some doubts on some of the results.
I did some manual testing to check that overhead seems reasonable.
Next step is end to end testing on real workloads.

Adjust the bench including absl examples The absl implementation seems to crash on concurrent access

This was causing memory contention for no reason

Use a single hash step for both chunk & slot

pr-commenter · 2025-10-21T14:27:58Z

Benchmark results for collatz

Parameters

	Baseline	Candidate
config	baseline	candidate
profiler-version	ddprof 0.20.0+e7d474bb.79617775	ddprof 0.20.0+f67c50e1.79973302

Summary

Found 0 performance improvements and 0 performance regressions! Performance is the same for 1 metrics, 0 unstable metrics.

See unchanged results

scenario	Δ mean execution_time
scenario:ddprof -S bench-collatz --preset cpu_only collatz_runner.sh	same

pr-commenter · 2025-10-21T14:28:03Z

Benchmark results for BadBoggleSolver_run

Parameters

	Baseline	Candidate
config	baseline	candidate
profiler-version	ddprof 0.20.0+e7d474bb.79617775	ddprof 0.20.0+f67c50e1.79973302

Summary

Found 0 performance improvements and 0 performance regressions! Performance is the same for 1 metrics, 0 unstable metrics.

See unchanged results

scenario	Δ mean execution_time
scenario:ddprof -S bench-bad-boggle-solver BadBoggleSolver_run work 1000	unsure [-14.501ms; -2.665ms] or [-0.734%; -0.135%]

KowalskiThomas

Haven't reviewed tests yet, will do later!

KowalskiThomas · 2025-10-22T07:55:26Z

+  // Linear probing to find an empty/deleted slot or the address
+  for (unsigned probe = 0; probe < AddressTable::kMaxProbeDistance; ++probe) {


I remember yesterday Cursor said it would be smart to do quadratic probing and you seemed to agree, did you eventually decide against it?

Yes, this was a pretty good suggestion. I will get back to testing this. Though I did want to secure a first fix.

KowalskiThomas · 2025-10-22T08:01:37Z

+    // Check if slot already contains our address
+    if (current == addr) {
+      return false; // Already tracked
+    }


If I understand correctly, we get here if either the current value is not empty/deleted or if CAS failed (and we reloaded the "actual" current value into current after the failed CAS).

What I don't understand is in what case current == addr may be true. From what I gather, it would mean either (1) the memory was previously added into the table before we even tried to insert it (but I don't understand when this would happen) (2) another thread tried to insert the same address we wanted to insert into the table at the same time as we did (but again, I would expect malloc to return each address only to one caller, so I don't understand when this would happen)

I'm definitely not saying this is wrong, I'm just curious to understand why we need it 😅

I can kind of see a world where we mess up instrumenting a free, so malloc already freed this (but did not remove), then we try to re-add it on subsequent alloc.
I do not really see this as expected though.
So your point might be that we should be watching these more carefully, which is correct.

Makes sense to me, it probably doesn't hurt (much) to account for this case anyway! Thanks for the explanation.

- Clean unused sampling strategy - Align on naming convention

… of addresses

r1viollet · 2025-10-22T12:04:53Z

-        // Check if we reached max number of elements
-        // Clear elements if we reach too many
-        // todo: should we just stop new live tracking (like java) ?
-        if (IsDDResOK(push_clear_live_allocation(tl_state))) {


We would need to work on the clear strategy.
For now I have to remove this.

r1viollet · 2025-10-22T12:14:39Z

Is this acceptable with prod workloads ?

The fixed sizes might be too small. I expect some tables will be created with almost nothing, whereas other tables will quickly be filled.
Example: could we have a separate tracking for mappings ? I could use a hint on the code path we are using (example: mmap & munmap get a single table).

- Introduce a table for large allocations - Avoid creating tables on the free code path

r1viollet · 2025-10-22T14:05:17Z

Is this acceptable with prod workloads ?

The fixed sizes might be too small. I expect some tables will be created with almost nothing, whereas other tables will quickly be filled. Example: could we have a separate tracking for mappings ? I could use a hint on the code path we are using (example: mmap & munmap get a single table).

I added a separate hashmap for mmap allocations.
Looking forwards to dogfooding this to figure out if it works well!

- cleanup notes with more accurate numbers on overhead. - cleanup duplicate variable

KowalskiThomas

What I'm seeing makes sense to me with my limited knowledge of ddprof

Approving (but maybe take it with a grain of salt) 🙈

KowalskiThomas · 2025-10-22T15:11:33Z

+    // Check if slot already contains our address
+    if (current == addr) {
+      return false; // Already tracked
+    }


Makes sense to me, it probably doesn't hurt (much) to account for this case anyway! Thanks for the explanation.

r1viollet · 2025-10-22T15:28:03Z

@nsavoire fyi, when you have some spare time to review 🙇

r1viollet added 9 commits October 20, 2025 12:15

Live heap - prototype alternatives to the bitset data structure

44014a8

Live heap - refactoring of bitset structure

fa80693

allocation_tracker_fix - local bench tooling

57eaace

Address tracking - update sharding to 128MB shards

33ec7d0

address bitset benchmark

640a116

Adjust the bench including absl examples The absl implementation seems to crash on concurrent access

Address tracking - simplify table sizes

3f699e1

allocation tracker - remove the global counter

7e37bcd

This was causing memory contention for no reason

Address tracking - Add a lsan suppression for leaked tables

594ee4f

Allocation tracking - Hash to find the chunk

6bfad54

Use a single hash step for both chunk & slot

r1viollet requested a review from nsavoire as a code owner October 21, 2025 14:27

Allocation tracking fix - minor doc clean up

623cd99

r1viollet force-pushed the r1viollet/fix_dealloc_events branch from b2b2c94 to 623cd99 Compare October 21, 2025 15:18

r1viollet commented Oct 21, 2025

View reviewed changes

Comment thread benchmark_overhead.sh Outdated

KowalskiThomas reviewed Oct 22, 2025

View reviewed changes

r1viollet commented Oct 22, 2025

View reviewed changes

Comment thread include/lib/address_sampler.hpp Outdated

r1viollet added 3 commits October 22, 2025 11:33

Address tracking - Clean up & address comments

31e5db9

- Clean unused sampling strategy - Align on naming convention

Address tracking - clean up & unify types of structures

c29b6f2

Address tracking - adjust the benchmark to deal with different ranges…

2196cc3

… of addresses

r1viollet commented Oct 22, 2025

View reviewed changes

Address tracking - reduce number of shards

6bc597d

- Introduce a table for large allocations - Avoid creating tables on the free code path

r1viollet commented Oct 22, 2025

View reviewed changes

Comment thread include/lib/address_bitset.hpp Outdated

Address tracking - Minor cleanup

f67c50e

- cleanup notes with more accurate numbers on overhead. - cleanup duplicate variable

KowalskiThomas approved these changes Oct 22, 2025

View reviewed changes

r1viollet merged commit 5031ff7 into main Oct 22, 2025
2 checks passed

r1viollet deleted the r1viollet/fix_dealloc_events branch October 22, 2025 15:26

		// Linear probing to find an empty/deleted slot or the address
		for (unsigned probe = 0; probe < AddressTable::kMaxProbeDistance; ++probe) {

Uh oh!

Conversation

r1viollet commented Oct 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

What does this PR do?

Motivation

Additional Notes

How to test the change?

Uh oh!

pr-commenter Bot commented Oct 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Benchmark results for collatz

Parameters

Summary

Uh oh!

pr-commenter Bot commented Oct 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Benchmark results for BadBoggleSolver_run

Parameters

Summary

Uh oh!

Uh oh!

KowalskiThomas left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

KowalskiThomas Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

r1viollet Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

KowalskiThomas Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

r1viollet Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

KowalskiThomas Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

r1viollet Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

r1viollet commented Oct 22, 2025

Uh oh!

r1viollet commented Oct 22, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

KowalskiThomas left a comment

Choose a reason for hiding this comment

Uh oh!

KowalskiThomas Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

r1viollet commented Oct 22, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

r1viollet commented Oct 21, 2025 •

edited

Loading

pr-commenter Bot commented Oct 21, 2025 •

edited

Loading

pr-commenter Bot commented Oct 21, 2025 •

edited

Loading

r1viollet commented Oct 22, 2025 •

edited

Loading