Bug 105483

Summary:

Slow performance with <select> with many options and size >= 2

Product:

WebKit

Reporter:

Mihai Parparita <mihaip>

Component:

Layout and Rendering

Assignee:

Mihai Parparita <mihaip>

Status:

RESOLVED FIXED

Severity:

Normal

CC:

ap, dglazkov, eric, esprehn, ian, inferno, tabatkins

Priority:

Version:

528+ (Nightly build)

Hardware:

Unspecified

OS:

Unspecified

Attachments:

Description	Flags
Test case	none
Test case with no newlines	none
Patch	none
Patch for landing	none

Mihai Parparita

Reported 2012-12-19 17:06:12 PST

Created attachment 180250 [details] Test case The attached test case (should be done from a local filesystem to remove any networking overhead) contains a <select> with 20,000 <options>. There's some simple timing code that measures initial parse and rendering time. It takes 2709ms on 25.0.1365.1 on a Mac Pro running 10.8.2. WebKit nightly build at r138184 takes 4226ms. Firefox 17.0.1 takes 70ms. Here's some more detailed timings: <option>s Chrome time Firefox time 100 1ms 1ms 1000 18ms 3ms 2000 57ms 5ms 3000 103ms 9ms 4000 163ms 11ms 5000 226ms 16ms 10000 798ms 34ms 15000 1702ms 51ms 20000 2709ms 70ms WebKit appears to have some greater-than-linear behavior here. This only happens when using <select size="2"> or higher; when rendered as a popup the test case only takes 150ms.

Attachments
Test case (410.56 KB, text/html) 2012-12-19 17:06 PST, Mihai Parparita	no flags	Details
Test case with no newlines (391.02 KB, text/html) 2012-12-20 14:45 PST, Mihai Parparita	no flags	Details
Patch (4.61 KB, patch) 2012-12-20 16:42 PST, Mihai Parparita	no flags	Details Formatted Diff Diff
Patch for landing (4.53 KB, patch) 2012-12-21 07:13 PST, Mihai Parparita	no flags	Details Formatted Diff Diff
Show Obsolete (1) View All Add attachment proposed patch, testcase, etc.

Mihai Parparita

Comment 1 2012-12-20 14:45:53 PST

Created attachment 180413 [details] Test case with no newlines

Mihai Parparita

Comment 2 2012-12-20 14:50:49 PST

Some quick profiling shows that we spend most of the time in NodeRenderingContext::previousRenderer. That has this comment: // FIXME: We should have the same O(N^2) avoidance as nextRenderer does // however, when I tried adding it, several tests failed. It looks like Eric added that in http://trac.webkit.org/changeset/80330/trunk/Source/WebCore/dom/Node.cpp. I wonder if tests would still fail. Also interesting is that the previousRenderer calls are caused by text nodes being inserted, but not the "bar" text nodes inside <option>, instead by the newline ones between the <option> tags. I attached a modified test case that has 20,000 <options> with no newlines between them, and it takes 217ms, almost 10x faster than the one with newlines. Since those text nodes are not displayable when in a <select>, maybe we can short-circuit Text::textRendererIsNeeded for them.

Elliott Sprehn

Comment 3 2012-12-20 15:23:31 PST

HTMLSelectElement::childShouldCreateRenderer should just return false for Text nodes. There's no reason we should ever put text renderers as descendants of a <select>, specifically this check is wrong. if (!usesMenuList()) return true; it should be: if (!usesMenuList()) return !childContext.node()->isTextNode(); we could probably be even more aggressive and check for hasTagName(HTMLNames::optionTag) || hasTagName(HTMLNames::optgroupTag) but looking at the code I think that might break validation messages... it's not clear how those work with the shadow tree here.

Mihai Parparita

Comment 4 2012-12-20 15:41:02 PST

(In reply to comment #3) > HTMLSelectElement::childShouldCreateRenderer should just return false for Text nodes. There's no reason we should ever put text renderers as descendants of a <select>, specifically this check is wrong. That seems fine to me. This would change the rendered appearance of http://persistent.info/webkit/test-cases/text-in-select.html, but given that neither IE, nor Firefox or Opera do anything with the text nodes outside of the <option> tags, I think that should be fine. I'll put up a patch.

Elliott Sprehn

Comment 5 2012-12-20 15:57:36 PST

(In reply to comment #4) > (In reply to comment #3) > > HTMLSelectElement::childShouldCreateRenderer should just return false for Text nodes. There's no reason we should ever put text renderers as descendants of a <select>, specifically this check is wrong. > > That seems fine to me. This would change the rendered appearance of http://persistent.info/webkit/test-cases/text-in-select.html, but given that neither IE, nor Firefox or Opera do anything with the text nodes outside of the <option> tags, I think that should be fine. > > I'll put up a patch. Hmm yeah, our behavior seems decidedly busted: <!DOCTYPE html> <select size="2"></select> <script> d = document.querySelector('select').appendChild(document.createElement('div')); d.textContent = 'DIV'; d.style.backgroundColor = 'red'; </script> we render that div, but we probably shouldn't as no other browser does. I'd say lets add a test for that and make this check: if (!usesMenuList()) return childContext.node()->hasTagName(HTMLNames::optionTag) || childContext.node()->hasTagName(HTMLNames::optgroupTag) || validationMessageShadowTreeContains(childContext.node());

Mihai Parparita

Comment 6 2012-12-20 16:13:03 PST

(In reply to comment #5) > we render that div, but we probably shouldn't as no other browser does. Crazy. FWIW, the HTML parser would throw out <div> when in a <select>: https://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/WebCore/html/parser/HTMLTreeBuilder.cpp&exact_package=chromium&q=sInSelectMode&l=1372

Elliott Sprehn

Comment 7 2012-12-20 16:15:44 PST

(In reply to comment #6) > (In reply to comment #5) > > we render that div, but we probably shouldn't as no other browser does. > > Crazy. FWIW, the HTML parser would throw out <div> when in a <select>: > > https://code.google.com/searchframe#OAMlx_jo-ck/src/third_party/WebKit/Source/WebCore/html/parser/HTMLTreeBuilder.cpp&exact_package=chromium&q=sInSelectMode&l=1372 Yeah I noticed that trying to create that test case...

Mihai Parparita

Comment 8 2012-12-20 16:42:20 PST

Created attachment 180442 [details] Patch

Eric Seidel (no email)

Comment 9 2012-12-20 20:18:02 PST

Comment on attachment 180442 [details] Patch Looks reasonable. I'll CC Tab/Hixie just to make sure.

Eric Seidel (no email)

Comment 10 2012-12-20 20:19:51 PST

The only question for the HTML/CSS experts: Is it OK to ignore all non-option/optgroup content inside <select> elements?

Eric Seidel (no email)

Comment 11 2012-12-20 20:20:08 PST

By "ignore" I mean "do not create renderers for".

Elliott Sprehn

Comment 12 2012-12-20 20:23:30 PST

Comment on attachment 180442 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=180442&action=review I talked with Tab about this earlier today and he said as far as CSS is concerned that the inside of a <select> is a magical black hole into the browser where the standards for rendering don't apply. > LayoutTests/fast/forms/menulist-no-renderer-for-unexpected-children.html:7 > +<p id="description"></p> You don't need this <p> here. description creates it for you. > LayoutTests/fast/forms/menulist-no-renderer-for-unexpected-children.html:11 > +<div id="console"></div> You don't need the id="console" div, and we usually omit the <html>, <head> and <body> element since they're all unnecessary boilerplate.

Mihai Parparita

Comment 13 2012-12-21 07:13:21 PST

Created attachment 180517 [details] Patch for landing

Mihai Parparita

Comment 14 2012-12-21 07:13:47 PST

Comment on attachment 180442 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=180442&action=review >> LayoutTests/fast/forms/menulist-no-renderer-for-unexpected-children.html:7 >> +<p id="description"></p> > > You don't need this <p> here. description creates it for you. Done >> LayoutTests/fast/forms/menulist-no-renderer-for-unexpected-children.html:11 >> +<div id="console"></div> > > You don't need the id="console" div, and we usually omit the <html>, <head> and <body> element since they're all unnecessary boilerplate. Done

WebKit Review Bot

Comment 15 2012-12-21 07:31:31 PST

Comment on attachment 180517 [details] Patch for landing Clearing flags on attachment: 180517 Committed r138374: <http://trac.webkit.org/changeset/138374>

Note You need to log in before you can comment on or make changes to this bug.