[BUG] dash-renderer 4.0: O(n²) dependency graph resolution causes 8-9 second freeze in Firefox with ~400 callbacks

[mbworth]

---

Describe your context

dash                      4.0.0
dash_ag_grid              32.3.2
dash-bootstrap-components 2.0.4
dash-bootstrap-templates  2.1.0
dash_daq                  0.6.0
dash-extensions           2.0.4
dash-iconify              0.1.2
dash-leaflet              1.1.3
dash-loading-spinners     1.0.3
dash_mantine_components   2.3.0
dash-svg                  0.0.12

• OS: Windows 11
• Browser: Firefox (latest stable), also tested in Chrome
• Chrome handles the same app without noticeable delay

Describe the bug

Our production app registers ~400 callbacks (~150 using pattern-matching with ALL/MATCH). On page load, the _dash-dependencies response is 332kB. All network requests complete within 1.3 seconds, but there's an 8-9 second freeze before the first _dash-update-component POST fires. The entire delay is client-side JavaScript execution in the dash-renderer.

A Firefox profiler capture shows the content thread burning 36.68 seconds of CPU during this window. The hot functions are all in the dependency graph builder:

Samples	Function
2071 (27.8%)	forEach
1857 (24.9%)	Tn
1826 (24.5%)	Ln/<
1799 (24.2%)	some
1788 (24.0%)	Tn/<
1768 (23.8%)	map
79 (1.1%)	addDependency

The forEach/some/map nesting pattern and the presence of addDependency suggest O(n²) behavior in the callback dependency graph resolution — for each callback, it appears to check against all others.

Chrome's V8 engine handles the same workload fine, which suggests Firefox's SpiderMonkey doesn't optimize these particular loop patterns as aggressively. That said, 400 callbacks shouldn't require 37 seconds of CPU in any browser.

Expected behavior

The dependency graph for ~400 callbacks should resolve in under 1 second. The current implementation appears to scale quadratically — this will become a bigger problem as apps grow.

Steps to reproduce

Any Dash 4 app with ~400+ callbacks, especially with heavy use of pattern-matching IDs (ALL/MATCH), loaded in Firefox. Chrome masks the issue due to engine-level optimizations, but the underlying algorithmic complexity is the same.

Additional context

HAR file confirms the timeline: all assets and _dash-dependencies load by 1.3s, then nothing happens until 9.3s when the first callback POST fires. The gap is pure JS execution. Happy to share the Firefox profiler capture and HAR if helpful.

[mbworth]

Update: root cause identified and verified fix

We dug into this further with dev bundles enabled (enable_dev_tools(dev_tools_serve_dev_bundles=True)) so the Firefox profiler would show real function names instead of minified ones. Here's what we found.

The entire 8-9 second freeze is spent inside computeGraphs in dependencies.js, specifically building the multiGraph used for client-side circular dependency detection. The runtime callback lookup structures (inputMap, outputMap, inputPatterns, outputPatterns) are cheap to build — the expensive part is exclusively the multiGraph construction.

Here's the profiler output with dev bundles (35.76s total CPU on the content thread):

Samples	Function	What it's doing
4869 (67.9%)	forEach	Built-in array iteration
2222 (31.0%)	addOutputToMulti/</<	Inner loop: iterating expanded input IDs
2167 (30.3%)	addOutputToMulti/<	Middle loop: iterating inputs per output
2119 (29.6%)	stringifyId	Serializing pattern-matching IDs to strings
2087 (29.1%)	combineIdAndProp	Building "{id}.{prop}" strings for graph edges
1973 (27.5%)	map	Built-in array mapping
1854 (25.9%)	stringifyVal	JSON.stringify for each wildcard value
1800 (25.1%)	some	Built-in array some
340 (4.7%)	addOutputToMulti	Outer function
198 (2.8%)	addInputToMulti	Pushes edges into multiGraph
124 (1.7%)	addDependency	DepGraph edge insertion (uses indexOf for dedup)

The cost comes from how multiGraph handles pattern-matching callbacks. For each callback output, makeAllIds expands wildcard patterns (ALL/MATCH) into a cartesian product of all concrete ID values seen across the app. Then for each expanded output, addOutputToMulti iterates every input and calls makeAllIds again to expand input wildcards. Each of those calls combineIdAndProp → stringifyId, which runs Object.keys().sort().map().join() fresh every time with no caching. Then addDependency checks for duplicate edges using Array.indexOf instead of a Set. On top of all that, a second pass iterates duplicateOutputs scanning all callbacks' input/output arrays with nested .some() loops.

With ~150 pattern-matching callbacks, the wildcard expansion creates thousands of concrete IDs, and the nested iteration over all of them is O(n²) or worse.

The fix we tested

We patched dash_renderer.dev.js to skip the multiGraph construction while keeping everything else intact. Three changes:

1. Replaced the addOutputToMulti function body with return;
2. Simplified the outputs.forEach loop inside computeGraphs to only call addPattern/addMap — removing the makeAllIds expansion, combineIdAndProp calls, and checkInOutOverlap logic that only fed multiGraph
3. Removed the duplicateOutputs.forEach second pass

The multiGraph object still gets created (empty) and triggerDefaultState still calls graphs.MultiGraph.overallOrder() without error — it just returns an empty array.

Result: page load went from 8-9 seconds to near-instant. All callbacks (that we tested) fire correctly. The only loss we can think of is client-side circular dependency detection, which the server already handles in Python.

For anyone who wants to test this themselves, the relevant code is in dash-renderer/build/dash_renderer.dev.js inside the computeGraphs function. Search for addOutputToMulti — that's the function to gut. You'll also need enable_dev_tools(dev_tools_serve_dev_bundles=True, dev_tools_hot_reload=False, dev_tools_ui=False, dev_tools_props_check=False) to serve the dev bundle.

We think the right long-term fix is either making the client-side circularity check opt-in (since the server already does it), or reworking it to operate at the pattern level rather than expanding every concrete ID combination. The current approach defeats the purpose of pattern-matching by enumerating all possibilities up front.

[AnnMarieW]

Thanks for reporting.
Can you please include a minimal example that replicates the issue?

[mbworth]

Here's a self-contained MWE that reproduces the issue. Set NUM_GROUPS higher for a longer freeze — at 500 we see ~4 seconds in Firefox vs ~2 seconds in Chrome.

"""
MWE: Dash 4 Firefox performance regression with pattern-matching callbacks.

Run: python dash_firefox_mwe.py
Open in Firefox vs Chrome and compare load times.

See: https://github.com/plotly/dash/issues/3661
"""

from dash import Dash, html, dcc, Input, Output, State, ALL, callback

app = Dash(__name__, suppress_callback_exceptions=True)

NUM_GROUPS = 500
ITEMS_PER_GROUP = 5

children = []
for g in range(NUM_GROUPS):
    group_children = []
    for i in range(ITEMS_PER_GROUP):
        group_children.append(
            html.Div([
                dcc.Input(
                    id={'type': 'input', 'group': g, 'index': i},
                    value=f'g{g}-i{i}',
                ),
                html.Div(
                    id={'type': 'output', 'group': g, 'index': i},
                ),
            ])
        )
    children.append(html.Details([
        html.Summary(f'Group {g}'),
        html.Div(group_children),
    ]))

app.layout = html.Div([
    html.H3('Dash 4 Firefox Performance MWE'),
    html.P(f'{NUM_GROUPS} groups x {ITEMS_PER_GROUP} items'),
    html.Div(children),
])

for g in range(NUM_GROUPS):
    @callback(
        Output({'type': 'output', 'group': g, 'index': ALL}, 'children'),
        Input({'type': 'input', 'group': g, 'index': ALL}, 'value'),
        prevent_initial_call=True,
    )
    def update(values, _g=g):
        return [f'Updated: {v}' for v in values]

for g in range(NUM_GROUPS - 1):
    @callback(
        Output({'type': 'output', 'group': g + 1, 'index': ALL}, 'style'),
        Input({'type': 'input', 'group': g, 'index': ALL}, 'value'),
        prevent_initial_call=True,
    )
    def cross_update(values, _g=g):
        return [{'color': 'blue'} for _ in values]

for g in range(0, NUM_GROUPS, 3):
    @callback(
        Output({'type': 'output', 'group': g, 'index': ALL}, 'title'),
        Input({'type': 'input', 'group': g, 'index': ALL}, 'value'),
        State({'type': 'output', 'group': g, 'index': ALL}, 'children'),
        prevent_initial_call=True,
    )
    def tooltip_update(values, current, _g=g):
        return [f'{v} ({c})' for v, c in zip(values, current or [''] * len(values))]

if __name__ == '__main__':
    app.run(debug=False, port=8050)

[AnnMarieW]

Thanks for the example. When I run it in Chrome and Firefox I don't see any difference in performance.

[mbworth]

Ok, how long is it taking to load? The MWE at 500 groups takes ~4s on our end — you may need to bump NUM_GROUPS higher depending on your hardware. The core issue isn't Firefox vs Chrome specifically, it's the O(n²) scaling in computeGraphs due to the multiGraph wildcard expansion. On our production app (~400 callbacks, ~150 pattern-matching) it burns 35+ seconds of CPU. The Firefox/Chrome comparison was just to illustrate that the same algorithmic cost hits differently across JS engines. Our root cause analysis and verified fix are in the follow-up comment above.

[AnnMarieW]

For 500 groups x 5 items Largest Contentful Paint (LCP) = 1.68 s

For 1000 groups x 5 items Largest Contentful Paint (LCP) = 4.57 s

Note for maintainers: I also checked dash 2.4.0 and the results are the same, so this is not a regression,

[AnnMarieW]

This looks like this was also discussed (but not resloved) in this issue: #3008 (comment) @RenaudLN ?

This comment is from @T4rk1n :

I think the computeGraph is not very optimized and could probably be refactored, complexity should be like o(layout_components * (inputs+outputs)) at most. But we can see a couple nested .some and .forEach that increase that further.

[mbworth]

That lines up with what we're seeing. The computeGraphs function is doing a lot of heavy lifting at startup to build a dependency graph that's only used for circular dependency detection on the client side — something the server already handles. On our app with ~400 callbacks, that work alone accounts for the entire 8-9 second freeze.

We tested a patch that skips that graph construction entirely and everything still works correctly, loads near-instantly. The details and profiler data are in the comments above.

Sounds like #3008 is hitting the same kind of thing but in a different part of the code. Would love to see the refactor T4rk1n described — it would address both issues.