[Autocomplete] renderOption is extremely slow

totszwai commented 2 years ago

Duplicates

[X] I have searched the existing issues

Latest version

[X] I have tested the latest version

Steps to reproduce 🕹

Go to this sandbox: https://stackblitz.com/edit/react-nv8116-okqafc?file=demo.tsx

Steps:

Have more than 500+ entries as Autocomplete options
Expand the dropdown or start typing anything
Observe the extreme lag on expand or when typing/deleting the first letter

Current behavior 😯

Extreme lag when Autocomplete is using renderOption with somewhat "large" entries.

Expected behavior 🤔

Expect it to not lag... or at least for things as little as under 1-2000 entries, it shouldn't be that bad.

Context 🔦

There is another ticket trying to resolve this issue but it looks like the changes to the virtualization never got merged into any release?

https://github.com/mui/material-ui/issues/25417

The merged fix seems to be only address the documentation (based on the title).

I don't think renderOption should be re-rendering everything from scratch on every operations (expand, keypress)?

Your environment 🌎

See sandbox.

michaldudak commented 2 years ago

Thanks for reporting this issue. It is noticeably slow, even on a powerful machine.

Would you be interested in trying to improve the implementation

trizotti commented 1 year ago

@michaldudak , do you have any other approach in mind on how to improve the Autocomplete performance without using virtualization?

mukultayal135 commented 5 months ago

@michaldudak , do you have any other approach in mind on how to improve the Autocomplete performance without using virtualization?

So now what has been the solution to slow renderOption problem, I see your solution wasn't merged. Also I tried using the ListBox virtualization the problem still persists as renderOption runs independently of VirtualisedListboxComponent

michaldudak commented 5 months ago

The unstyled Autocomplete component will be getting an overhaul in Base UI later this year. We look to address the long-standing issues with it. We are planning to use the new implementation to power the Material UI Autocomplete in the future.

mukultayal135 commented 5 months ago

So basically now the delay will stay in checkbox unselection right?

The thing is though I used virtualisation in ListBoxComponent but still in renderOption I consoled and saw that it was rendering all options, do you know this

On Mon, 27 May 2024 at 12:37 PM, Michał Dudak @.***> wrote:

The unstyled Autocomplete component will be getting an overhaul in Base UI later this year. We look to address the long-standing issues with it. We are planning to use the new implementation to power the Material UI Autocomplete in the future.

— Reply to this email directly, view it on GitHub https://github.com/mui/material-ui/issues/34712#issuecomment-2132788213, or unsubscribe https://github.com/notifications/unsubscribe-auth/AVJBNCCFB4OEPU2TQC6ECRLZELLTFAVCNFSM6AAAAAARCJ7OTSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCMZSG44DQMRRGM . You are receiving this because you commented.Message ID: @.***>

michaldudak commented 5 months ago

If it's something that can be fixed in Material UI, perhaps it can land in the code sooner (cc @DiegoAndai). In Base UI we don't currently have the capacity to work on issues of components pending overhaul.

DiegoAndai commented 5 months ago

We don't have the bandwidth to investigate this issue deeply right now, especially with the Base UI refactor coming later this year. Anyway, I'll add the ready to take label if someone wants to investigate whether it's possible to fix this on the Material UI side. I'll be more than happy to provide guidance.

I'm also adding it to the Base UI refactor milestone in case it's not fixed by then so we can review it while refactoring.

mukultayal135 commented 5 months ago

Thanks Diego for the update

On Thu, 6 Jun 2024 at 2:12 AM, Diego Andai @.***> wrote:

We don't have the bandwidth to investigate this issue deeply right now, especially with the Base UI refactor coming later this year. Anyway, I'll add the ready to take label if someone wants to investigate whether it's possible to fix this on the Material UI side. I'll be more than happy to provide guidance.

I'm also adding it to the Base UI refactor milestone in case it's not fixed by then so we can review it while refactoring.

— Reply to this email directly, view it on GitHub https://github.com/mui/material-ui/issues/34712#issuecomment-2150929663, or unsubscribe https://github.com/notifications/unsubscribe-auth/AVJBNCCV4DDNDMRSMVS3TTLZF5Z4HAVCNFSM6AAAAAARCJ7OTSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCNJQHEZDSNRWGM . You are receiving this because you commented.Message ID: @.***>

m4theushw commented 4 months ago

I was having the same problem with an Autocomplete with 2k options and no virtualization. After a quick investigation I realized this problem is the same we had in the DataGrid when we tried to reduce the styles specificity by moving the styles from the main component to the child components. Each time a styled component is instantiated, Emotion has to serialize the styles and this may take some time when the component is used very often and has complex styling (e.g. Checkbox). In the case of the Autocomplete, for every option and every styled component inside renderOption a serialization must be done. I think this bug can only be properly fixed with the zero-runtime CSS engine. Meanwhile, to fix it in my project I removed all MUI components from renderOption and replaced with HTML primitives. The styles I moved to a custom Popper component passed to the Autocomplete via PopperComponent prop. This is the recommended approach in https://emotion.sh/docs/performance.

DiegoAndai commented 4 months ago

Thanks @m4theushw, for providing a possible way of improving the issue 🙌🏼

I think this bug can only be properly fixed with the zero-runtime CSS engine

The good news is that the Material UI v6 components, including Autocomplete, will support zero-runtime. The beta will be available in the following weeks, and the stable release will be available soon as well.

2598Nitz commented 4 months ago

Anyway, I'll add the ready to take label if someone wants to investigate whether it's possible to fix this on the Material UI side. I'll be more than happy to provide guidance.

Hi @DiegoAndai , I also have this requirement of not calling renderListOption for every option when I am using virtualization.

In my case, the bottleneck is the getOptionProps being called for all the options.

My requirement:

I plan to use Autocomplete with 50k options.
I also plan to provide option to 'Select All' options.

Bottleneck: Considering the worst case of 50k options being in selected state, the time complexity of getOptionProps will be O(N) for each option leading to an O(N^2) complexity where N is the number of options.

My proposed solution:

I think when virtualization is enabled, we can prevent calling getOptionProps and renderOption.
Instead we can wrap this logic in a callback and send that as a child of the ListBoxComponent.
However, we'll have to introduce an additional prop to Autocomplete component, a Boolean prop 'isVirtualized' would be required to indicate virtualization is used and user wants to defer the option rendering logic.

Code changes required:

Updated renderListOption function:

  const renderListOption = (option, index) => {
    const renderOptionWithProps = (props = {}) => {
      const optionProps = getOptionProps({ option, index });
      const allProps = { ...optionProps, className: classes.option, ...props };
      return renderOption(
        allProps,
        option,
        { selected: allProps['aria-selected'], index, inputValue },
        ownerState
      );
    };

    if (!isVirtualized) {
      return renderOptionWithProps();
    } else {
      return [renderOptionWithProps];
    }
  };

Changes required for the virtualization example:

renderOption prop now can accept a list item equivalent element instead of returning props and state as output of renderOption.
The renderRow function will have to be modified to include the style or any other prop to be passed to our callback function.

Example renderRow function (NOTE: Haven't checked the implementation for grouping yet):

function renderRow(props) {
  const { data, index, style } = props;
  const [renderOption] = data[index];
  const inlineStyle = {
    ...style,
    top: style.top + LISTBOX_PADDING,
  };

  return (
    renderOption({style: inlineStyle})
  );
}

With these changes, I don't see any visible drop in performance for 'Select All' operation with 100k options. NOTE: The performance improvement won't be visible in a non-prod env due to this additional validation being done. The validation done here also results in a O(N^2) complexity as mentioned before. It would have been good if validations like these are kept optional irrespective of the env.

Kindly let me know if the proposed solution above is an acceptable solution. I can start working on it with a PR.

mukultayal135 commented 4 months ago

That sounds good I really appreciate your efforts Nitesh I hope your fix gets pushed as soon as possible

On Thu, 11 Jul 2024 at 11:30 PM, Nitesh Gowda @.***> wrote:

Anyway, I'll add the ready to take label if someone wants to investigate whether it's possible to fix this on the Material UI side. I'll be more than happy to provide guidance.

Hi @DiegoAndai https://github.com/DiegoAndai , I also have this requirement of not calling renderListOption https://github.com/mui/material-ui/blob/431af6a2fd9bf6cd0422c61e36c937d1ea5e5015/packages/mui-material/src/Autocomplete/Autocomplete.js#L600 for every option when I am using virtualization.

In my case, the bottleneck is the getOptionProps https://github.com/mui/material-ui/blob/431af6a2fd9bf6cd0422c61e36c937d1ea5e5015/packages/mui-material/src/Autocomplete/Autocomplete.js#L601 being called for all the options.

My requirement:

I plan to use Autocomplete with 50k options.

I also plan to provide option to 'Select All' options.

Bottleneck: Considering the worst case of 50k options being in selected state, the time complexity of getOptionProps will be O(N) for each option leading to an O(N^2) complexity where N is the number of options.

My proposed solution:

I think when virtualization is enabled, we can prevent calling getOptionProps and renderOption.

Instead we can wrap this logic in a callback and send that as a child of the ListBoxComponent.

However, we'll have to introduce an additional prop to Autocomplete component, a Boolean prop 'isVirtualized' would be required to indicate virtualization is used and user wants to defer the option rendering logic.

Code changes required:

Updated renderListOption function:

const renderListOption = (option, index) => { const renderOptionWithProps = (props = {}) => { const optionProps = getOptionProps({ option, index }); const allProps = { ...optionProps, className: classes.option, ...props }; return renderOption( allProps, option, { selected: allProps['aria-selected'], index, inputValue }, ownerState ); };
if (!isVirtualized) {
  return renderOptionWithProps();
} else {
  return [renderOptionWithProps];
}
};

Changes required for the virtualization example https://mui.com/material-ui/react-autocomplete/#virtualization:

renderOption prop now can accept a list item equivalent element instead of returning props and state as output of renderOption.

The renderRow function will have to be modified to include the style or any other prop to be passed to our callback function.

Example renderRow function (NOTE: Haven't checked the implementation for grouping yet):

function renderRow(props) { const { data, index, style } = props; const [renderOption] = data[index]; const inlineStyle = { ...style, top: style.top + LISTBOX_PADDING, };

return ( renderOption({style: inlineStyle}) ); }

With these changes, I don't see any visible drop in performance for 'Select All' operation with 100k options. NOTE: The performance improvement won't be visible in a non-prod env due to this https://github.com/mui/material-ui/blob/431af6a2fd9bf6cd0422c61e36c937d1ea5e5015/packages/mui-base/src/useAutocomplete/useAutocomplete.js#L259 additional validation being done. The validation done here also results in a O(N^2) complexity as mentioned before. It would have been good if validations like these are kept optional irrespective of the env.

Kindly let me know if the proposed solution above is an acceptable solution. I can start working on it with a PR.

— Reply to this email directly, view it on GitHub https://github.com/mui/material-ui/issues/34712#issuecomment-2223552254, or unsubscribe https://github.com/notifications/unsubscribe-auth/AVJBNCB2VY5JRQR7GAXPJYTZL3B4BAVCNFSM6AAAAAARCJ7OTSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMRTGU2TEMRVGQ . You are receiving this because you commented.Message ID: @.***>

2598Nitz commented 4 months ago

Hi @michaldudak @DiegoAndai , any thoughts on the callback solution for renderListOption mentioned above ?

DiegoAndai commented 2 months ago

@michaldudak is this problem something you're looking to fix in Base UI? If so, what would be your approach?

@2598Nitz I understand the general idea of the proposal but not in detail. What do you mean with "Instead we can wrap this logic in a callback and send that as a child of the ListBoxComponent."? What ListBoxComponent? How/when will the callback be called?

2598Nitz commented 2 months ago

Instead we can wrap this logic in a callback and send that as a child of the ListBoxComponent

You can check the updated renderListOption function shared in https://github.com/mui/material-ui/issues/34712#issuecomment-2223552254

In updated renderListOption function, I am calling renderOption function to create the ReactElement for rendering an option if virtualization is not enabled. If virtualization is enabled, I am returning a function which calls renderOption.

The return value of renderListOption is the child of AutocompleteListBox

What ListBoxComponent?

AutocompleteListBox is the ListBoxComponent I was referring to in my previous update. Seems like ListBoxComponent is renamed to ListBoxSlot on current master branch.

How/when will the callback be called?

Considering the virtualization enabled scenario, it will be called by renderRow function: Below, renderOption is the callback function.

function renderRow(props) {
  const { data, index, style } = props;
  const [renderOption] = data[index];
  const inlineStyle = {
    ...style,
    top: style.top + LISTBOX_PADDING,
  };

  return (
    renderOption({style: inlineStyle})
  );
}

For knowing where renderRow function is coming from, you can check the virtualization example shared here: https://mui.com/material-ui/react-autocomplete/#virtualization

michaldudak commented 2 months ago

Is this problem something you're looking to fix in Base UI?

We are going to completely overhaul the Autocomplete component, but this will likely occur after the first stable release.

vinroger commented 1 month ago

Hi @michaldudak, is this issue still relevant to be solved? (After the release for the new UI)

I am interested to take this and improve the time complexity for searching the options. Thank you

michaldudak commented 1 month ago

Hi, we haven't worked on the Autocomplete in the new package just yet. We don't have it specced out. We are going to release the first stable version of @base_ui/react without it and work on it shortly after the release. It's great to see that you'd like to help, but we plan to rewrite this component within the team.

vinroger commented 1 month ago

I see - thank you so much for the kind answer Michal. @michaldudak

To clarify - even if I managed to reduce the time complexity for the options matching (and speed up the overall autocomplete performance), this contribution will be rendered "deprecated" in the future, and therefore it is not recommended to proceed, is this correct?

If it is not recommended to proceed, I am interested to take part on MUI library and contribute to performance optimisation. Is there any specific component that you suggest exploring?

Thank you in advance

michaldudak commented 1 month ago

Yes, that is correct. We are going to redesing the Autocomplete from the ground up, so there is no point in optimizing it today.

As for other improvement areas, I'll leave it to @aarongarciah and @DiegoAndai to decide as they are closer to Material UI.

aarongarciah commented 1 month ago

Making improvements to the Autocomplete component is not one of our priorities for the reasons Michał mentioned above. That said, we'd happily accept improvements from the community.

mui / material-ui