Performance issue in sortable widget with long lists

[stollr]

There is a huge performance issue in the sortable widget which started in version (1.12.1) and is still existing in current version 1.13.1, when used with large lists.

There's already a ticket for this issue in the old tracker: https://bugs.jqueryui.com/ticket/15097 and a corresponding stackoverflow question.

Today I have created some new fiddles to show the issue. Please compare the console output in the fiddle:

jquery-ui version	fiddle url	output	time of initialization in seconds
1.11.4	https://jsfiddle.net/m0j61Lnw/0/	"#1", "Mon Mar 28 2022 12:24:40 GMT+0200 (Mitteleuropäische Sommerzeit)"	0
		"#2", "Mon Mar 28 2022 12:24:40 GMT+0200 (Mitteleuropäische Sommerzeit)"
1.12.0	https://jsfiddle.net/m0j61Lnw/2/	"#1", "Mon Mar 28 2022 12:15:08 GMT+0200 (Mitteleuropäische Sommerzeit)"	2
		"#2", "Mon Mar 28 2022 12:15:10 GMT+0200 (Mitteleuropäische Sommerzeit)"
1.12.1	https://jsfiddle.net/m0j61Lnw/3/	"#1", "Mon Mar 28 2022 12:15:46 GMT+0200 (Mitteleuropäische Sommerzeit)"	16
		"#2", "Mon Mar 28 2022 12:16:02 GMT+0200 (Mitteleuropäische Sommerzeit)"
1.13.1	https://jsfiddle.net/m0j61Lnw/1/	"#1", "Mon Mar 28 2022 12:23:11 GMT+0200 (Mitteleuropäische Sommerzeit)"	16
		"#2", "Mon Mar 28 2022 12:23:27 GMT+0200 (Mitteleuropäische Sommerzeit)"

There are some solutions suggested in the stackoverflow answeres and in the old ticket.

It would be great if you could fix the issue. Otherwise we are stuck on version 1.11.4 :-(

[stollr]

Update:
I can approve that this workaround significantly reduces the performance issue:

$.ui.sortable.prototype._setHandleClassName = function() {
    this._removeClass( this.element.find( ".ui-sortable-handle" ), "ui-sortable-handle" );
    $.each( this.items, function() {
        (this.instance.options.handle
         ? this.item.find( this.instance.options.handle )
         : this.item
        ).addClass('ui-sortable-handle');
    });
};

If set before the initialization of the sortable.

[mgol]

Thanks for the report. Since the issue is already in 1.12, given limited team resources it's not likely to be fixed by the UI team; see the project status at https://blog.jqueryui.com/2021/10/jquery-maintainers-update-and-transition-jquery-ui-as-part-of-overall-modernization-efforts/. I'd review a PR if you'd like to submit one, though.

[stollr]

@mgol I've submitted a PR ;-)

[melloware]

I can confirm for the last 5 years in Primefaces we have used this same patch.

Here is the original report ticket: primefaces/primefaces#3675

// GitHub PrimeFaces #3675 performance
$.widget( "ui.sortable", $.ui.sortable, {
    _setHandleClassName: function() {
        this._removeClass( this.element.find( ".ui-sortable-handle" ), "ui-sortable-handle" );
        $.each( this.items, function() {
                        (this.instance.options.handle 
                        ? this.item.find( this.instance.options.handle ) 
                        : this.item
                        ).addClass('ui-sortable-handle');
        } );
    }
});

[dahopem]

@mgol, @fnagel, the cause for the excessive time complexity is an O(n*n*log(n)) algorithm.

Analysis

Consider this call stack:

. _setHandleClassName (loops over all items)
. _addClass
. _toggleClass
. _classes
. processClassString
. bindRemoveEvent
. _on
. add
. jQuery.uniqueSort (loops over all items)

Given that the jQuery.uniqueSort will have a time complexity in O(n*log(n)), _setHandleClassName will have a time complexity in O(n*n*log(n)). This more than quadratic time complexity makes _setHandleClassName inacceptably slow for large inputs (e.g. 5000 items which shall be sortable).

[mgol]

I don't see an easy fix for this. We'd probably have to stop keeping this.bindings as a jQuery object to avoid the repeated uniqueSort invocations, and only wrap it with a jQuery object when needed. But that would break code that relies on the current bindings shape.

[mgol]

BTW, the bindings.add line:

jquery-ui/ui/widget.js

Line 600 in a9e8520

this.bindings = this.bindings.add( element );

is not the only issue. A lot of the slowdown also comes from recomputing classElementsLookup modifications, in particular:

jquery-ui/ui/widget.js

Line 528 in a9e8520

current = $( $.uniqueSort( current.get().concat( options.element.get() ) ) );

classElementsLookup is an object with values being jQuery objects, so adding elements by one to it has the same computational complexity issues.

Ideally, bindings should be a Set & classElementsLookup a map to Sets instead of jQuery objects. That does carry a new kind of risk, though, especially for classElementsLookup - whenever a jQuery object is actually needed from them, the Set needs to be converted to a jQuery object which may trigger a slowdown in a different place.

I submitted a draft PR with these changes; it passes tests and the initialization time reported for the test case reported here is at ~50 ms on my machine. I am not sure it won't introduce other issues, though, plus it changes the shape of some objects, so landing it would be risky. Feel free to have a look at the code & test these changes locally, though.

PR: #2313

[patrickteng]

why is the PR not accepted? I just updated to 1.14.1 today and hit the issue, because I forgot that i had to manually change the code in my previous version to make it load faster.

[mgol]

why is the PR not accepted?

I've explained it above:

"I am not sure it won't introduce other issues, though, plus it changes the shape of some objects, so landing it would be risky. Feel free to have a look at the code & test these changes locally, though."

[mgol]

@patrickteng testing PR #2313 on your project and confirming whether it works fine would help with potentially eventually merging the PR. So far, no one did that, so complaints are unwarranted.

[patrickteng]

@mgol it worked 2 years back on 1.12.1, and it still is working fine now on 1.14.1 in my project after my change 2 hours ago. But i had to directly modify the js file as it's being used in multiple places.

[mgol]

@patrickteng PR #2313 was opened a few months ago, not 2 years ago. It's physically impossible for you to have applied it on 1.12.1 2 years ago...

[patrickteng]

@mgol because the issue has existed since forever. This is the same solution that i applied to the latest version.

https://stackoverflow.com/questions/20398400/jquery-ui-sortable-call-is-slow-when-applies-to-thousands-of-elements

[mgol]

I was not asking for the Stack Overflow patch - I was asking about my PR #2313; those are different. The patch may be working for you, but it's using a hack that skips some internal logic which may result in some APIs not working properly - therefore, it's not possible to include it in jQuery UI.

I need people to test my PR on their projects. If no one does that, the likelihood of it being merged diminishes.