gh-154085: Avoid duplicating diff line values

Project: python/cpython | Language: Python | Concepts: refactoring, testing-strategy, algorithmic-optimization | Difficulty: mid
Link: https://github.com/python/cpython/pull/154099

The problem

The sampling profiler's differential flamegraph output could incorrectly duplicate "self time" (time spent directly in a line/function) across multiple line nodes when a function's code was split across several lines. This led to inflated or incorrect self-time totals in the visualization, making performance analysis inaccurate.

Why it's non-trivial

A naive fix—simply summing or copying self-time values for each line—would not account for cases where the same function appears on multiple lines or where line-level changes split a function's execution across several nodes. Without careful proportional allocation, it's easy to over-count self time, especially when mapping between baseline and current profiles that have changed line numbers or structure.

The approach

The PR introduces a more careful allocation of self and non-self (descendant) samples to avoid duplicating values:

-        current_self = current_data["self"]
-        baseline_self = baseline_data["self"] * scale
-        baseline_total = baseline_data["total"] * scale
+        current_self = node.get("self", 0)
+        current_total = node.get("value", 0)
+
+        current_nonself = current_total - current_self
+        aggregate_nonself = current_data["total"] - current_data["self"]
+
+        # Allocate self and descendant samples separately.  Line-number
+        # changes can split one function path into several rendered nodes,
+        # and using independent weights for self and inclusive totals could
+        # otherwise assign a node more self samples than total samples.
+        self_weight = self._sample_weight(
+            current_self,
+            current_data["self"],
+            current_total,
+            current_data["total"],
+        )
+        nonself_weight = self._sample_weight(
+            current_nonself,
+            aggregate_nonself,
+            current_total,
+            current_data["total"],
+        )
+        baseline_self = baseline_data["self"] * scale * self_weight
+        baseline_nonself = (
+            baseline_data["total"] - baseline_data["self"]
+        ) * scale * nonself_weight
+        baseline_total = baseline_self + baseline_nonself

What it does:

• Instead of directly copying self/total values, it computes proportional weights (self_weight and nonself_weight) based on the current node's share of the aggregate function's samples.
• It then scales the baseline's self and non-self time by these weights, ensuring that the sum across all line nodes for a function matches the function's total, and no line node gets more self time than its inclusive time.

A new static helper method is introduced for this weighting:

+    @staticmethod
+    def _sample_weight(value, aggregate, fallback_value, fallback_aggregate):
+        if aggregate > 0:
+            return value / aggregate
+        if fallback_aggregate > 0:
+            return fallback_value / fallback_aggregate
+        return 0

What it does:

• Calculates the proportion of samples to assign to a node, with sensible fallbacks if the aggregate is zero.

Other changes ensure that elided nodes (nodes collapsed due to changes in the code) do not incorrectly retain or duplicate self-time:

+                node["self"] = 0
+                node.pop("opcodes", None)
+                node.pop("thread_opcodes", None)

What it does:

• Resets self-time and removes opcode metadata from elided nodes, so only visible (non-elided) nodes retain sample data.

The test suite is expanded with several new tests to verify:

• Self time is not duplicated across line nodes.
• Baseline self time does not exceed inclusive time.
• Elided nodes' metadata is correct and does not double-count samples.

From the review thread

No notable review discussion on this PR.

Takeaways

• When aggregating or diffing hierarchical data, always ensure that per-node values are proportionally allocated to avoid double-counting, especially when the structure may change between versions.
• Testing for edge cases (like line splits, elided nodes, and ancestor/descendant relationships) is crucial to prevent subtle data duplication or loss in tree-like algorithms.
• Helper functions that encapsulate allocation logic (such as proportional weighting) can clarify intent and reduce the risk of logic errors in complex data transformations.