Closed Bug 463598 Opened 16 years ago Closed 15 years ago

Value-hiding javascript code performs poorly when there are hundreds or thousands of controlled values

Categories

(Bugzilla :: Bugzilla-General, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
Bugzilla 3.4

People

(Reporter: mkanat, Assigned: mkanat)

References

Details

Attachments

(1 file, 7 obsolete files)

If I have a value-controlled field with hundreds of controlled values, the browser pretty much locks up when I try to change the controller field. I need to improve the performance of the JS code here (and I have a pretty good idea how to do it).
Summary: Value-hiding code performs poorly when there are hundreds or thousands of controlled values → Value-hiding javascript code performs poorly when there are hundreds or thousands of controlled values
Attached patch v1 (obsolete) — Splinter Review
This seems to fix the problem totally! The slowness seems to have come from bz_optionIndex, which was looping through the <select> over and over and over. We handle it by creating a cache for that <select> the first time we access it, and then we use the cache from then on.
Attachment #346872 - Flags: review?(bbaetz)
Comment on attachment 346872 [details] [diff] [review]
v1

Why don't these all have ids on them that we can just use getElementById on?
(In reply to comment #2)
> (From update of attachment 346872 [details] [diff] [review])
> Why don't these all have ids on them that we can just use getElementById on?

  Because values can have characters in them that are not valid ids.
Status: NEW → ASSIGNED
Can't those be escaped? It just seems like we're reinventing the wheel here.
(In reply to comment #4)
> Can't those be escaped? It just seems like we're reinventing the wheel here.

  I'm not sure, I don't think they can be. I suppose I could go look up the spec.
Alternately, the js call can be to showValueWhen('bz_field_<x>', 'bz_field_<y>') and you can allocate the ids as you go, with no reference to the 'real' name/id. May not be possible to manage without a two-pass approach, though.
No, I suppose that'd be possible. Each legal value has a unique integer id.

Note that in older versions of Firefox document.getElementById actually is probably slower than what I'm doing in the patch, but in newer versions it should be fine.
Comment on attachment 346872 [details] [diff] [review]
v1

r- as above
Attachment #346872 - Flags: review?(bbaetz) → review-
Attached patch v2 (obsolete) — Splinter Review
bbaetz: You were right! It's much faster with ids, and actually it greatly simplifies the code, as well.
Attachment #346872 - Attachment is obsolete: true
Attachment #363042 - Flags: review?(guy.pyrzak)
Attachment #363042 - Flags: review?(bbaetz)
It's still slow in IE and WebKit, but it's faster than it used to be. For IE7, I'm not surprised--it has a relatively slow JS engine. For WebKit, it's most likely because of the code in getPossiblyHiddenOption, which is going to be something like O(n^2) without any way that I see around it.
Comment on attachment 363042 [details] [diff] [review]
v2

This looks right, but I need to play around with it on multiple browsers.

Is there a test instance on landfill that shows this, to save me setting up the slow case manually?

The O(n^2) is a bit ugly, and I had to think through several times why that was the case with this patch.

The issue is that we have to iterate through all options to find out if they're hidden and fix them up if needed.

The O(n^2) behaviour is because for each option on the list we have to grovel through the select to look for it and check its attributes.

I guess we can't pass in the dom node to the callback rather than the ids because its being replaced. Can we instead pass in what child it is? So getPossiblyHiddenOption does:

 item = aSelect.childNodes[aPos];

directly. (Its possible that that line would be O(n) but if it is then the algorithm in the patch is O(n^3) because you're iterating through childNodes and accessing them by position anyway. Mozilla appears to have child elements as arrays but I don't think that the DOM specs require children to be implemented that way)

(Note that there may be text nodes between the <option> elements, so I don't think that you can just count them off, but I'm not 100% sure)

Why the css change for .bz_hidden_option?
(In reply to comment #11)
> Is there a test instance on landfill that shows this, to save me setting up the
> slow case manually?

  
> The O(n^2) is a bit ugly, and I had to think through several times why that was
> the case with this patch.

  Oh, I'm sorry, I thought that was apparent from my comment.

> I guess we can't pass in the dom node to the callback rather than the ids
> because its being replaced. Can we instead pass in what child it is?

  Hmm, something like that, yeah. During initHideOptionsForIE we could cache the position of each option and then see if it can be accessed that way. Or we could just put the comment objects themselves into an array (possibly along with the options) and just access them that way. I think that sounds reasonable.

> Why the css change for .bz_hidden_option?

  Oh, visibility: hidden was unnecessary, I was just removing it. I had accidentally left that in after my testing on the original patch.
Attached patch v3 (obsolete) — Splinter Review
Okay, this uses the store-in-array method and is much much faster on WebKit than the old version was.

IE 7 performance is still pretty weak, but I think that's just because IE has a really slow JS engine. (Thankfully there's no perf problem ever for small numbers of field values--you really have to have thousands before it becomes an issue.) As far as I know, there's no JS profiler for IE, so I have no idea how to find out where it's spending its time, and I don't really care (as IE8 will hopefully be faster...).
Attachment #363042 - Attachment is obsolete: true
Attachment #363792 - Flags: review?(bbaetz)
Attachment #363042 - Flags: review?(guy.pyrzak)
Attachment #363042 - Flags: review?(bbaetz)
And here's a test installation:

  http://landfill.bugzilla.org/mkanat-ui/show_bug.cgi?id=2323

The "Drop Down" <select> controls the values of the "Controlled" select, which has something like 3000 or 5000 total values.
Attached patch v3.1 (obsolete) — Splinter Review
Just fixed some bitrot caused by a checkin from a few minutes ago.
Attachment #363792 - Attachment is obsolete: true
Attachment #363828 - Flags: review?(bbaetz)
Attachment #363792 - Flags: review?(bbaetz)
Comment on attachment 363828 [details] [diff] [review]
v3.1

Way too many assignments has got in the way of this; I'll be able to take a look at it tomorrow or Tuesday.
Flags: blocking3.4+
Attachment #363828 - Flags: review?(guy.pyrzak)
Attached file Profiler output on IE8 (obsolete) —
(In reply to comment #13)
> issue.) As far as I know, there's no JS profiler for IE, so I have no idea how
> to find out where it's spending its time, and I don't really care (as IE8 will
> hopefully be faster...).

In IE8 there's Profiler in the Developer Tools (F12 to run it) that's included by default. I think that might also be available in IE7 as a separate download but I'm not sure. Anyway, I did a simple profiles run in IE8 using your test install and bug. I simply loaded the test bug mentioned on comment #14 and then selected Option 1 on the Drop Down box (both actions profiled). Performance was awfully slow. :(

Here's the result CSV, which shows that 50% of time was spent in hideOptionInIE, 30% in showOptionInIE and 14% in getPossiblyHiddenOption function. Hope this helps.
Attached patch v4 (obsolete) — Splinter Review
Hey wicked, thanks for the profile! I did some investigation, and this version is 20x faster on IE than it was before. It's still not *fast*, but it at least doesn't seem like the browser's locked up, now.

The problem on IE was that calling parent.replaceChild() on a <select> with lots of options was really slow. Using IE's "replaceNode" function is much faster, when it's available.

It's still MUCH faster on all the other browsers (virtually instantaneous on Safari and Firefox) than the old code was.
Attachment #363828 - Attachment is obsolete: true
Attachment #373570 - Attachment is obsolete: true
Attachment #375242 - Flags: review?(wicked)
Attachment #375242 - Flags: review?(bbaetz)
Attachment #363828 - Flags: review?(guy.pyrzak)
Attachment #363828 - Flags: review?(bbaetz)
Attachment #375242 - Flags: review?(bbaetz) → review-
Comment on attachment 375242 [details] [diff] [review]
v4

Wrong patch - this is the same as the last one
Attached patch Actual v4 (obsolete) — Splinter Review
Ah, thanks for catching that. :-)
Attachment #375242 - Attachment is obsolete: true
Attachment #375246 - Flags: review?(wicked)
Attachment #375246 - Flags: review?(bbaetz)
Attachment #375242 - Flags: review?(wicked)
Hey bbaetz, any chance of getting a review on this?
wicked, could you put this review in your top priority list?
Attachment #375246 - Flags: review?(wicked)
Attachment #375246 - Flags: review?(bbaetz)
Attachment #375246 - Flags: review-
Comment on attachment 375246 [details] [diff] [review]
Actual v4

I tested JS to work (iow, does what it's supposed to do and no script errors) on the following browsers (on XP unless otherwise noted):
 1) IE v8.0.6001.18762 (Vista) - Annoying 5 to 25 second delay. Even locks Taskbar! Drop down remains topmost window which looks funky. Easily becomes unresponsive.
 2) IE v7.00.6000.16827 - Annoyingly slow, takes about 60 to 100 seconds to respond. Luckily doesn't lock Taskbar like on Vista. Drop down remains topmost window which looks funky. Easily becomes unresponsive.
 3) Google Chrome v2.0.172.28 - Slooooow... Takes ~75 seconds to respond. Luckily locks up only the affected tab. Can easily trigger unresponsive tab dialog.
 4) Opera v9.64 build 10487 and Opera v9.64 build 2480 (CentOS x86_64) - Seems blazing! Evidently runs JS on background since control length is adjusted few times. There's also funky dynamic effects if one happens to open the drop down before JS has finished it's run. :)
 5) Safari v3.2.3 (525.29) - Noticeable delay but easily tolerable since it's only few seconds.
 6) Firefox v3.0.10 (Gecko/2009042316, Vista): Annoying 5 to 10 second delay. Opening the drop down is also slow.
 7) Firefox v3.0.10 (Gecko/2009042316): Annoying 10 to 15 second delay.
 8) Firefox v3.0.10-1.el5.centos (Gecko/2009042718, CentOS x86_64): Has to wait for a response since it takes about 5 to 20 seconds. Sometimes triggers the slow script dialog that stops script execution until dialog is answered.

Note that I tested using the same set of values as in comment #14. It had 4005 total values with 2 always visible, 1622 visible for value "Option 1", 1721 visible for value "Option 2" and 660 visible for value "---".

>Index: Bugzilla/Field/Choice.pm
>===================================================================
>+    $self->{controlled_values} = \%controlled_values;

You forgot to update admin/fieldvalues/confirm-delete.html.tmpl to use this correctly. Please, check also that _check_if_controller sub in this module handles the new return type.

>+=item C<controlled_values>

Really nice of you to also add documentation for this item. :)

>Index: js/field.js
>===================================================================
>+    for (var i = 0; i < controlled_value_ids.length; i++) {
...
>+        var controller_item = document.getElementById(
>+            _value_id(controller_field.id, controller_value_id));

Unless I'm reading this wrong, this always fetches the same item for each loop. If so, shouldn't this be outside of the for loop?

> function showOptionInIE(aNode, aSelect) {
>-    if (browserCanHideOptions(aSelect)) return;
>+    if (browserCanHideOptions(aSelect)) return aNode;
>     // If aNode is an Option
>     if (typeof(aNode.value) != 'undefined') return;

Shouldn't this return something too? Otherwise it generates a strict warning (function showOptionInIE does not always return a value) and might create problems at call site. When does this happen, anyway?

>Index: template/en/default/bug/field-events.js.tmpl
>===================================================================
>+                  [[% cont_ids.join(',') %]],

It seems somebody forgot to run tests.. :)

#   Failed test '(en/default) template/en/default/bug/field-events.js.tmpl has unfiltered directives:
#   36: cont_ids.join(',')
# --ERROR'
#   in t/008filter.t at line 131.
I just tried my test case on all the mentioned browsers without this patch. And the results are... simply put staggeringly mind blowing!

Opera is still best since it doesn't lock neither itself nor the system up but it still takes about 40 to 120 seconds to update the drop down. And all that time there's stale data visible, which is confusing.

Firefox locks itself up for about 70 to 165 seconds. Safari also locked itself up and took about 80 to 160 seconds to complete. Chrome locked only one tab but took well over 5 minutes and I ended up killing the tab before it even completed first step (select Option 1).

IE7 locks itself up and doesn't even complete first step for over 20 minutes. IE8 locks itself as well as Vista UI up and completes at about 3 to 4 minutes. I didn't run full tests on either of them since no one is going to wait that long for IE to respond before killing it and cursing at Gates.

So all in all, this patch is vast improvement in any case!
Thank you for your excellent review and attention to detail, wicked! :-) I'm thinking I'll get you a new patch with the issues fixed fairly soon--within the next few days, hopefully today (Monday).
Attached patch v5Splinter Review
Thanks for catching all that stuff, wicked! :-) I've fixed it all.

I wish I could find an even faster solution, but I think that for now this is a reasonable balance between various options. I may still give this entire method of doing things up for some sort of select.options-populating method. But for 3.4 this will work, I think. People will just have to accept some slowness if they put a lot of options in there.
Attachment #375246 - Attachment is obsolete: true
Attachment #381000 - Flags: review?(bbaetz)
Attachment #381000 - Flags: review?(wicked)
Can I get a review on this bug? It's a blocker and it's been sitting here unreviewed for 16 days.
Comment on attachment 381000 [details] [diff] [review]
v5

Sure, here you go.

Tested that option hiding seems to still work on trunk with all the previously mentioned browsers. Also tested that attempting to delete a controller field value gives correct confirm and error messages.

I agree with mkanat that this already brings so major performance improvement that this should go in before attempting optimize this further.
Attachment #381000 - Flags: review?(wicked)
Attachment #381000 - Flags: review?(bbaetz)
Attachment #381000 - Flags: review+
Flags: approval?
Flags: approval3.4?
Flags: approval?
Flags: approval3.4?
Flags: approval3.4+
Flags: approval+
Thanks, wicked!! :-)

tip:

Checking in Bugzilla/Field/Choice.pm;
/cvsroot/mozilla/webtools/bugzilla/Bugzilla/Field/Choice.pm,v  <--  Choice.pm
new revision: 1.11; previous revision: 1.10
done
Checking in js/field.js;
/cvsroot/mozilla/webtools/bugzilla/js/field.js,v  <--  field.js
new revision: 1.16; previous revision: 1.15
done
Checking in skins/standard/global.css;
/cvsroot/mozilla/webtools/bugzilla/skins/standard/global.css,v  <--  global.css
new revision: 1.66; previous revision: 1.65
done
Checking in template/en/default/admin/fieldvalues/confirm-delete.html.tmpl;
/cvsroot/mozilla/webtools/bugzilla/template/en/default/admin/fieldvalues/confirm-delete.html.tmpl,v  <--  confirm-delete.html.tmpl
new revision: 1.14; previous revision: 1.13
done
Checking in template/en/default/bug/field-events.js.tmpl;
/cvsroot/mozilla/webtools/bugzilla/template/en/default/bug/field-events.js.tmpl,v  <--  field-events.js.tmpl
new revision: 1.2; previous revision: 1.1
done
Checking in template/en/default/bug/field.html.tmpl;
/cvsroot/mozilla/webtools/bugzilla/template/en/default/bug/field.html.tmpl,v  <--  field.html.tmpl
new revision: 1.28; previous revision: 1.27
done
Checking in template/en/default/global/user-error.html.tmpl;
/cvsroot/mozilla/webtools/bugzilla/template/en/default/global/user-error.html.tmpl,v  <--  user-error.html.tmpl
new revision: 1.281; previous revision: 1.280
done


3.4:

Checking in Bugzilla/Field/Choice.pm;
/cvsroot/mozilla/webtools/bugzilla/Bugzilla/Field/Choice.pm,v  <--  Choice.pm
new revision: 1.10.2.1; previous revision: 1.10
done
Checking in js/field.js;
/cvsroot/mozilla/webtools/bugzilla/js/field.js,v  <--  field.js
new revision: 1.15.2.1; previous revision: 1.15
done
Checking in skins/standard/global.css;
/cvsroot/mozilla/webtools/bugzilla/skins/standard/global.css,v  <--  global.css
new revision: 1.64.2.2; previous revision: 1.64.2.1
done
Checking in template/en/default/admin/fieldvalues/confirm-delete.html.tmpl;
/cvsroot/mozilla/webtools/bugzilla/template/en/default/admin/fieldvalues/confirm-delete.html.tmpl,v  <--  confirm-delete.html.tmpl
new revision: 1.13.2.1; previous revision: 1.13
done
Checking in template/en/default/bug/field-events.js.tmpl;
/cvsroot/mozilla/webtools/bugzilla/template/en/default/bug/field-events.js.tmpl,v  <--  field-events.js.tmpl
new revision: 1.1.2.1; previous revision: 1.1
done
Checking in template/en/default/bug/field.html.tmpl;
/cvsroot/mozilla/webtools/bugzilla/template/en/default/bug/field.html.tmpl,v  <--  field.html.tmpl
new revision: 1.24.2.3; previous revision: 1.24.2.2
done
Checking in template/en/default/global/user-error.html.tmpl;
/cvsroot/mozilla/webtools/bugzilla/template/en/default/global/user-error.html.tmpl,v  <--  user-error.html.tmpl
new revision: 1.276.2.1; previous revision: 1.276
done
Status: ASSIGNED → RESOLVED
Closed: 15 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: