Dash slow pattern-matching performance on many elements

[Spriteware]

Hello,
First, thank you for your amazing work on Dash.

Describe your context

dash                      2.17.1
dash_ag_grid              31.2.0
dash-bootstrap-components 1.4.1
dash-core-components      2.0.0
dash-html-components      2.0.0
dash-table                5.0.0
jupyter-dash              0.4.2

Browser: Firefox / Chrome (not related) on MacOS 14 (not related either).

Describe the bug

I recently came across a performance limitation of Dash that really made my app slow, and at some point, unusable.
The idea is that I needed to have N checkboxes that my user can check or uncheck. N can sometimes be 20, but it could actually go up to 500 or 1000. That’s where I hit some performance issue with Dash.

Expected behavior

I expect to have N > 1.000 checkboxes rendered in my webpage with no struggle. A similar Vanilla JavaScript code can handle more than 100.000 checkboxes before the page starts to get slow. I imagine that using React comes with some performance downgrade, but it seems to be optimizable.

Screenshots

Here is a visual example for the problem (for 500) ; you can see a lag between my clicks and checkboxes actually being checked:

Reproducible code

We create 500 checkboxes and get their value with one callback.

import uuid
import random 
import dash
from dash import dcc, html
from dash.dependencies import Input, Output, ALL

app = dash.Dash(__name__)

# We create 500 checkboxes 
checkboxes = [
    dcc.Checklist(
        options=[{"label": f"Checkbox {i+1}", "value": "checked"}],
        id={"type": "checkbox", "group": random.choice(["a", "b", "c"]), "index": str(uuid.uuid4())},
        inline=True
    ) for i in range(500)
]

app.layout = html.Div([
    html.Div(id="output", style={"position": "fixed", "top": 0, "left": "200px"}),
    html.Div(checkboxes)
])

# Client-side callback to illustrate that network is not the bottleneck here
app.clientside_callback(
    """
    function(checkbox_values, checkbox_ids) {
        const groupCounts = { a: 0, b: 0, c: 0 };

        checkbox_values.forEach((value, i) => {
            if (value && value.includes('checked')) {
                const group = checkbox_ids[i].group;
                groupCounts[group]++;
            }
        });

        const totalChecked = groupCounts.a + groupCounts.b + groupCounts.c;
        return `${totalChecked} checkboxes checked (Group A: ${groupCounts.a}, Group B: ${groupCounts.b}, Group C: ${groupCounts.c})`;
    }
    """,
    Output("output", "children"),
    Input({"type": "checkbox", "group": ALL, "index": ALL}, "value"),
    Input({"type": "checkbox", "group": ALL, "index": ALL}, "id"),
)


# Run the app
if __name__ == "__main__":
    app.run_server(debug=True, port=8060)

The issue is not with the callback itself, but occurs prior to the callback. It just takes some time to gather all the checkboxes, and then fires the callback (which runs fast).

Here are some things I noticed:

• performance drops after 100s of elements.
• it’s still slow even if I get rid of the groups and replace string indexes with integers
• CPU is between 90-100% and at some point the browser may ask to stop the script
• the problem is not related to the browser. I tested on Chrome and Firefox, recent versions.
• a similar vanilla JavaScript page (with pattern-matching-like IDs being parsed to JSON) can handle more than 100,000 checkboxes without any performance drop…

Here is the performance report (Firefox). I clicked 4 times, the CPU was around 90% all the time, making the page unresponsive:

One of the bottlenecks seems to be getReadyCallbacks from dash_renderer.

I hope this can be solved!

[Spriteware]

I decided to further investigate this, and see if I can suggest something.

Important note: I am not a TypeScript developer.

Here is the profiler that I used :

https://profiler.firefox.com/from-browser/calltree/?globalTrackOrder=g0wf&hiddenGlobalTracks=1we&hiddenLocalTracksByPid=2634-0w8~36260-0~2638-0~36259-0~36333-0~35465-01~36332-0&implementation=js&thread=u&v=10

the first 50% of bottle neck

52% comes from difference, inside the last filter of getReadyCallbacks. 46% comes from redux middleware. I first investigated getReadyCallbacks in dash/dash-renderer/src/actions/dependancies_ts.ts. Here is the concerned code:

// Find `requested` callbacks that do not depend on a outstanding output (as either input or state)
// Outputs which overlap an input do not count as an outstanding output
return filter(
    cb =>
        all<ILayoutCallbackProperty>(
            cbp => !outputsMap[combineIdAndProp(cbp)],
            **difference**(
                flatten(cb.getInputs(paths)),
                flatten(cb.getOutputs(paths))
            )
        ),
    candidates
);

difference is a Ramda.JS function, that works by comparing the full values of objects. I could see that it is really slow compared to a full JS equivalent that only tests strings, for example.

I created a function named differenceBasedOnIdthat uses vanilla JS and compares just strings using combineIdAndProp.

    const differenceBasedOnId = function(inputs, outputs) {
        return inputs.filter(input => {
            return !outputs.some(output => {
                return combineIdAndProp(input) === combineIdAndProp(output);
            });
        });
    };

The function is way faster, and can easily compute difference for 2000 inputs in 11ms - which takes 22 SECONDS for Ramda object based difference. Note that using R.difference on strings would also be faster.

So the final TypeScript updated code would be :

    const differenceBasedOnId = (inputs: any[], outputs: any[]): any[] => 
        inputs.filter(input => 
            !outputs.some(output => 
                combineIdAndProp(input) === combineIdAndProp(output)
            )
        );

    // Find `requested` callbacks that do not depend on a outstanding output (as either input or state)
    // Outputs which overlap an input do not count as an outstanding output
    return filter(
        cb =>
            all<ILayoutCallbackProperty>(
                cbp => !outputsMap[combineIdAndProp(cbp)],
                differenceBasedOnId(
                    flatten(cb.getInputs(paths)),
                    flatten(cb.getOutputs(paths))
                )
            ),
        candidates
    );

second 50% of bottleneck

The second part of the bottleneck. This one require to go deeper. The 46% splits in two calls that are making 15% and 14%.

At the end, we see that 63% of this slow part ((14+15)/46) is because of a function named getIds. The function is pretty simple and relies on Ramda 👀.

const getIds = (cb: ICallback, paths: any) =>
    uniq(
        pluck('id', [
            ...flatten(cb.getInputs(paths)),
            ...flatten(cb.getState(paths))
        ])
    );

Going even deeper, we can see that uniq will actually use propEq from ramda, that itself relies on equals from ramda. I then noticed that the remaining 37% from above will actually call the same equals function from ramda. So the root problem seem to be that equals from ramda is not fast enough.

As before, I decided to replace Ramda and not use uniq nor pluck . I compute the ids as string, and use a Map to be sure that ids are unique.

Here are the timings, on a simplified code that just use inputs:

It takes 12 seconds for Ramda to get the unique list of 2000 inputs. The vanilla JS code is 500x faster.

The updated getIds function would be :

const getIds = (cb: ICallback, paths: any) => {

    const items = [
        ...flatten(cb.getInputs(paths)),
        ...flatten(cb.getState(paths))
    ];

    const uniqueIds = new Map(items.map(item => [stringifyId(item.id), item]));
    const uniqueItems = Array.from(uniqueIds.values());
    return uniqueItems;
}
    

Conclusion

I compiled the source code again locally, and I now obtain a fully responsive app.
Here is an example with 2000 checkboxes (previous had 500...):

I'll see if I can succeed to do a PR (never did before) !

[RenaudLN]

Amazing debugging, I had encountered this issue before but never went to the bottom of it. Thanks for doing that!

[Spriteware]

Amazing debugging, I had encountered this issue before but never went to the bottom of it. Thanks for doing that!

Thank you! I'm glad to know that I did not investigate something that only impacts myself.