Last Comment Bug 463598 - Value-hiding javascript code performs poorly when there are hundreds or thousands of controlled values
: Value-hiding javascript code performs poorly when there are hundreds or thous...
Status: RESOLVED FIXED
:
Product: Bugzilla
Classification: Server Software
Component: Bugzilla-General (show other bugs)
: 3.3
: All All
: -- normal (vote)
: Bugzilla 3.4
Assigned To: Max Kanat-Alexander
: default-qa
Mentors:
Depends on: 308253
Blocks:
  Show dependency treegraph
 
Reported: 2008-11-07 03:09 PST by Max Kanat-Alexander
Modified: 2009-06-21 12:35 PDT (History)
5 users (show)
mkanat: approval+
mkanat: approval3.4+
mkanat: blocking3.4+
See Also:
QA Whiteboard:
Iteration: ---
Points: ---


Attachments
v1 (6.23 KB, patch)
2008-11-07 04:47 PST, Max Kanat-Alexander
bbaetz: review-
Details | Diff | Review
v2 (10.20 KB, patch)
2009-02-18 18:49 PST, Max Kanat-Alexander
no flags Details | Diff | Review
v3 (10.75 KB, patch)
2009-02-23 16:29 PST, Max Kanat-Alexander
no flags Details | Diff | Review
v3.1 (10.93 KB, patch)
2009-02-23 20:20 PST, Max Kanat-Alexander
no flags Details | Diff | Review
Profiler output on IE8 (12.99 KB, application/vnd.ms-excel)
2009-04-19 09:17 PDT, Teemu Mannermaa (:wicked)
no flags Details
v4 (10.93 KB, patch)
2009-04-30 15:41 PDT, Max Kanat-Alexander
bbaetz: review-
Details | Diff | Review
Actual v4 (11.42 KB, patch)
2009-04-30 15:50 PDT, Max Kanat-Alexander
wicked: review-
Details | Diff | Review
v5 (14.77 KB, patch)
2009-06-01 22:20 PDT, Max Kanat-Alexander
wicked: review+
Details | Diff | Review

Description Max Kanat-Alexander 2008-11-07 03:09:35 PST
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).
Comment 1 Max Kanat-Alexander 2008-11-07 04:47:36 PST
Created attachment 346872 [details] [diff] [review]
v1

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.
Comment 2 Bradley Baetz (:bbaetz) 2008-11-07 05:04:13 PST
Comment on attachment 346872 [details] [diff] [review]
v1

Why don't these all have ids on them that we can just use getElementById on?
Comment 3 Max Kanat-Alexander 2008-11-07 05:06:58 PST
(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.
Comment 4 Bradley Baetz (:bbaetz) 2008-11-07 05:39:16 PST
Can't those be escaped? It just seems like we're reinventing the wheel here.
Comment 5 Max Kanat-Alexander 2008-11-07 17:54:20 PST
(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.
Comment 6 Bradley Baetz (:bbaetz) 2008-11-07 18:39:56 PST
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.
Comment 7 Max Kanat-Alexander 2008-11-08 10:47:52 PST
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 8 Bradley Baetz (:bbaetz) 2009-01-25 11:05:24 PST
Comment on attachment 346872 [details] [diff] [review]
v1

r- as above
Comment 9 Max Kanat-Alexander 2009-02-18 18:49:15 PST
Created attachment 363042 [details] [diff] [review]
v2

bbaetz: You were right! It's much faster with ids, and actually it greatly simplifies the code, as well.
Comment 10 Max Kanat-Alexander 2009-02-18 19:00:49 PST
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 11 Bradley Baetz (:bbaetz) 2009-02-23 15:37:08 PST
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?
Comment 12 Max Kanat-Alexander 2009-02-23 16:00:55 PST
(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.
Comment 13 Max Kanat-Alexander 2009-02-23 16:29:02 PST
Created attachment 363792 [details] [diff] [review]
v3

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...).
Comment 14 Max Kanat-Alexander 2009-02-23 16:32:49 PST
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.
Comment 15 Max Kanat-Alexander 2009-02-23 20:20:02 PST
Created attachment 363828 [details] [diff] [review]
v3.1

Just fixed some bitrot caused by a checkin from a few minutes ago.
Comment 16 Bradley Baetz (:bbaetz) 2009-03-01 11:44:33 PST
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.
Comment 17 Teemu Mannermaa (:wicked) 2009-04-19 09:17:23 PDT
Created attachment 373570 [details]
Profiler output on IE8

(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.
Comment 18 Max Kanat-Alexander 2009-04-30 15:41:30 PDT
Created attachment 375242 [details] [diff] [review]
v4

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.
Comment 19 Bradley Baetz (:bbaetz) 2009-04-30 15:49:00 PDT
Comment on attachment 375242 [details] [diff] [review]
v4

Wrong patch - this is the same as the last one
Comment 20 Max Kanat-Alexander 2009-04-30 15:50:23 PDT
Created attachment 375246 [details] [diff] [review]
Actual v4

Ah, thanks for catching that. :-)
Comment 21 Max Kanat-Alexander 2009-05-14 16:57:54 PDT
Hey bbaetz, any chance of getting a review on this?
Comment 22 Frédéric Buclin 2009-05-18 14:42:36 PDT
wicked, could you put this review in your top priority list?
Comment 23 Teemu Mannermaa (:wicked) 2009-05-24 03:48:07 PDT
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.
Comment 24 Teemu Mannermaa (:wicked) 2009-05-25 00:28:13 PDT
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!
Comment 25 Max Kanat-Alexander 2009-05-25 00:41:28 PDT
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).
Comment 26 Max Kanat-Alexander 2009-06-01 22:20:53 PDT
Created attachment 381000 [details] [diff] [review]
v5

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.
Comment 27 Max Kanat-Alexander 2009-06-17 17:22:45 PDT
Can I get a review on this bug? It's a blocker and it's been sitting here unreviewed for 16 days.
Comment 28 Teemu Mannermaa (:wicked) 2009-06-19 11:20:46 PDT
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.
Comment 29 Max Kanat-Alexander 2009-06-21 12:35:05 PDT
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

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