Page MenuHomePhabricator

AutoWikiBrowser performance issues using large lists
Closed, ResolvedPublicBUG REPORT

Description

Steps to replicate the issue (include links if applicable):
This is the same scenario as in T428372.

  • Create a large article list (e.g. ~20,000 articles in category Year of birth missing)
  • Remove a single item
  • Start processing with a pre-parse setting and continued skips.

Another scenario:

  • Paste a list of 37 Rules into the ReplaceSpecial dialog.

What happens?:
Visibly slow processing of remove an item. Visibly slow processing of redraw in the article list, especially when scrolling. Visibly slow processing, with flashing of the details box, in the ReplaceSpecial case.

What should have happened instead?:
Snappier response.

Software version
AWB 6.5.0.0 and 6.4.0.0.

Other information (browser name/version, screenshots, etc.):

Some profiling shows two major choke points; there may be others. The ListBox2.RemoveSelected method uses in-memory manipulation and a complete reload when operating on lists >= 500 long. This was introduced in SVN 12716. But most of the cases in practice only have one item selected, and the ListBox.RemoveAt method is very efficient. To be fair, the ListBox code may have been rewritten since Framework 4.5.2. A quick fix would be to just use RemoveAt for the one-item path; on a set of tests that results in a 26x speedup. The other cases would require considerable profiling to see where the tradeoff with in-memory technique happens. By the way, the LINQ operations can be optimized a little.

The other is the code that finds the longest article name in order to size the horizontal scrollbar, which is run every time a single item is drawn, even though the longest name rarely changes. To check the longest name when an article is added or removed from the list sounds attractive, but that would require subclassing ListBox.ObjectCollection, which is surprisingly difficult, or maybe use a DataSource (which fires change events). Just simplifying the LINQ code in the redraw results in a more than 6x speedup for the whole redraw method.

In ReplaceSpecial, the slow population of the tree redraw is slightly mitigated by using BeginUpdate/EndUpdate for the paste.

So I propose checking in the simple fixes and putting more fundamental logic changes on the backlog.

Event Timeline

SVN 13025: use the ListBox's RemoveAt implementation if <= 100 items are selected. Testing shows that is quicker for long (>500) lists. Further profiling could show the breakeven point for other scenarios, but this must cover the commonest ones.

SVN 13026: replace slow LINQ functions with a simple loop to calculate the longest article name. Still to do: keep a running updated in a subclass of ListBox's ObjectCollection. Improvements between 4x and 6x on very long lists.

SVN 13027: use BeginUpdate to easily prevent flashing when a large number of ReplaceSpecial rules are pasted into the tree. Still to do: prevent the rule detail page flashing too.

Further info on rev 13026 / lbArticles_DrawItem change: my benchmarks (20k items):

existing lbArticles.Items.Cast<Article>().Select(ar => ar.Name).ToList().OrderByDescending(s => s.Length).First(); takes about 18 ms total for one 20k article paste.
The new foreach takes about 2 ms for same. So I agree clearly faster.

Probably the OrderByDescending is the slow bit. An alternative lbArticles.Items.Cast<Article>().Aggregate((max, cur) => max.Name.Length > cur.Name.Length ? max : cur).Name; also takes about 2 ms for same. At the level of ms no different to foreach. Maybe a more detailed profiler can confirm if foreach better than Aggregate?

Agreed the Aggregate method probably uses basically the same logic as the loop but with additional object creation. Having done a lot with LINQ I'm always suspicious these days and want to know what goes in inside, so I'm more inclined to use the C style.

I did try wrapping or subclassing the Listbox.ItemsCollection class, and comparing the name length on every Add, Remove etc. But that turns out to be famously intricate (the Items property has to do double duty) and I gave up. 2 ms is nothing to sneeze at.

Oddly on my benchmarks my ARM Surface is faster than my ancient PC at 20K items, but slower at 100K. Maybe because object references are twice as big.

Observation: every time (almost) that the lbArticles DrawItem method is called when the item count is the same as last time, the identity of the longest article hasn't changed. The exception, deleting that article and adding a shorter one without an intervening draw of the list, is hard to imagine.

Every time the visible part of the list changes and the list is redrawn, the DrawItem method is called 16 times in succession, once for each visible line. Testing a "list is same length" shortcut, DrawItem runs between 2x and 3x faster on average; it only re-scans the list one time in 16. On my (slow) PC with a 20K item list that's a change from 2.2 ms to 0.8 ms per item, times 16 per re-display. 22.4 ms is not really noticeable but not hard to code either, and it's between 6x and 7x faster on a 100K list.

Furthermore, skipping the horizontal bar resize when the longest article is unchanged adds a smidge to the speed.

Finally, there's a bug introduced in 6.4; if you clear the entire list the scrollbar isn't removed (oddly, it gets longer) because the DrawItem code isn't called. I'll enter another bug.

DavidBrooks claimed this task.

SVN 13039. Only recompute the lbArticles horizontal scrollbar when the number of items in the list has changed. This only needs to be done once per paint of the window, which calls Draw_Item between 16 and 22 times. It may be tempting to put it in UpdateNumberOfArticles, but that is called on every list change, while Draw_Item isn't called while the window is minimized.

Comparing text string length is only a proxy for display width. As it happens, in my 20K test, the second-longest item name has the longest display width (due to the font being proportional spaced) but computing all the widths on each change takes nearly a second.

I think this is done with the perf fixes. Display in ReplaceSpecial could be improved but it isn't called repeatedly.