577995 - Sorting using nsXULSortService is slow

Status: RESOLVED INCOMPLETE

(Core :: XUL, defect)

Description

[Ben Parr [:bparr]]

Steps to reproduce:
1) Open the Add-ons Manager with many (20 or more) extensions installed
2) Open the "Extensions" category
3) Click a sorter (e.g. "Size")

This is a problem in the other categories, not just the "Extensions" category. Each add-on is represented as a richlistitem, which the sort service is sorting. With 20 items, sortService.sort(...) took about 500 milliseconds to run. With 35 items, it took about 850 milliseconds to run.

Comment 1

[Neil Deakin (away until Sept 6)]

Attachment: simple testcase

This testcase with very simple richlistitems shows the following:

- sorting with 25 items: 8ms
- sorting with 200 items: 62ms

I would assume that it isn't the sorting itself which takes a long time, but the complexity of what is being inserted.

Comment 2

[Boris Zbarsky [:bzbarsky]]

> 1) Open the Add-ons Manager with many (20 or more) extensions installed

I tried creating such a profile by installing some extensions from AMO but the result crashes on launch.

Any chance of attaching a profile that shows the problem?

Comment 3

[Boris Zbarsky [:bzbarsky]]

> I would assume that it isn't the sorting itself which takes a long time, but
> the complexity of what is being inserted.

Looking at a profile of the testcase in comment 1, that assumption seems to be correct.  1.5% of the time is spent under NS_QuickSort.  66.6% of the time is spent under nsXULElement::RemoveChildAt and 66.6% of the time is spent under nsGenericElement::InsertChildAt.

The details are XUL stuff in all its glory: XBL bindings (20% of the total time right there!), XUL ordinals, etc, etc.  Might be worth doing an actual profile of the extension manager case to get an idea of what the pain points are there...

Would it make any sense to use box-ordinal for the reordering instead of DOM removal and reinsertion?

Comment 4

[Dave Townsend [:mossop]]

How many DOM mutations are going on here. Is the sort mutating the DOM directly or some internal map and then only mutating the DOM once the sort is complete. Presumably the former is worse on memory for large cases but with complex XBL bindings would likely be faster.

Comment 5

[Boris Zbarsky [:bzbarsky]]

> How many DOM mutations are going on here.

One remove/insert per element being sorted, if I read the sort code correctly.

> Is the sort mutating the DOM directly or some internal map and then only
> mutating the DOM once the sort is complete.

Yes.  See XULSortServiceImpl::SortContainer.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Er.. "Yes" == "the latter".

Comment 7

[Jens Stutte [:jstutte]]

Since bug 1489690 this is called nsXULSortService.

And FWIW, since bug 1839051 it uses std::sort through nsTArray::Sort. According to comment 3 that is not really relevant here (but the reason I am looking at it).

nsXULElement::RemoveChildAt and nsGenericElement::InsertChildAt seem to be gone from our tree, not sure if they have been just somehow renamed or if that means this bug can be closed.

Asking :mccr8 as you were involved in bug 1563066 time ago...

Comment 8

[Andrew McCreight [:mccr8]]

I don't know what those methods are called now, but they just sound like standard DOM methods for inserting and removing children of an element. That being said, I think various parts of the infrastructure here have been rewritten, multiple times (in particular, I'm thinking of the new DOM bindings and I think there's some newer representation of child nodes), in the 14 years since this was filed, so let's just close this and people can raise performance issues if they are encountering them again.