Skip to content

Commit b4f2349

Browse files
committed
pythongh-156545: Fix flamegraph export RecursionError on deeply recursive programs
Convert the recursive convert_children() function in _convert_to_flamegraph_format() to an iterative post-order traversal using an explicit stack. This prevents RecursionError when profiling programs with deep call stacks.
1 parent 9d45fc5 commit b4f2349

1 file changed

Lines changed: 28 additions & 14 deletions

File tree

‎Lib/profiling/sampling/stack_collector.py‎

Lines changed: 28 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -238,8 +238,13 @@ def _convert_to_flamegraph_format(self, *, min_samples=None):
238238
}
239239

240240
def convert_children(children, min_samples, path_info):
241-
out = []
242-
for func, node in children.items():
241+
# Iterative post-order traversal to avoid RecursionError
242+
# on deeply recursive call stacks.
243+
node_map = {}
244+
topo_order = []
245+
stack = list(children.items())
246+
while stack:
247+
func, node = stack.pop()
243248
samples = node["samples"]
244249
significant_for_thread = any(
245250
thread_samples >= max(
@@ -255,7 +260,6 @@ def convert_children(children, min_samples, path_info):
255260
if samples < min_samples and not significant_for_thread:
256261
continue
257262

258-
# Intern all string components for maximum efficiency
259263
filename_idx = self._string_table.intern(func[0])
260264
funcname_idx = self._string_table.intern(func[2])
261265
module_name = self._get_module_name(func[0], path_info)
@@ -288,11 +292,9 @@ def convert_children(children, min_samples, path_info):
288292

289293
source = self._get_source_lines(func)
290294
if source:
291-
# Intern source lines for memory efficiency
292295
source_indices = [self._string_table.intern(line) for line in source]
293296
child_entry["source"] = source_indices
294297

295-
# Include opcode data if available
296298
opcodes = node.get("opcodes", {})
297299
if opcodes:
298300
child_entry["opcodes"] = dict(opcodes)
@@ -305,15 +307,27 @@ def convert_children(children, min_samples, path_info):
305307
)
306308
}
307309

308-
# Recurse
309-
child_entry["children"] = convert_children(
310-
node["children"], min_samples, path_info
311-
)
312-
out.append(child_entry)
313-
314-
# Sort by value (descending) then by name index for consistent ordering
315-
out.sort(key=lambda x: (-x["value"], x["name"]))
316-
return out
310+
node_map[id(node)] = child_entry
311+
topo_order.append((func, node))
312+
for child_func, child_node in node["children"].items():
313+
stack.append((child_func, child_node))
314+
315+
# Build children lists bottom-up (reverse topological order)
316+
for func, node in reversed(topo_order):
317+
entry = node_map[id(node)]
318+
for child_func, child_node in node["children"].items():
319+
child_entry = node_map.get(id(child_node))
320+
if child_entry is not None:
321+
entry["children"].append(child_entry)
322+
entry["children"].sort(key=lambda x: (-x["value"], x["name"]))
323+
324+
root_entries = []
325+
for child_func, child_node in children.items():
326+
e = node_map.get(id(child_node))
327+
if e is not None:
328+
root_entries.append(e)
329+
root_entries.sort(key=lambda x: (-x["value"], x["name"]))
330+
return root_entries
317331

318332
# Filter out very small functions (less than 0.1% of total samples)
319333
total_samples = self._total_samples

0 commit comments

Comments
 (0)