96534 - query.cgi is slow to reflow when you change the product field

Status: RESOLVED FIXED

(Bugzilla :: Query/Bug List, enhancement, P1)

Description

[Binh Tran]

The javascript is really slow when selecting a product
on the query page using Internet Explorer 5+.

Note: reason for being slow is that there are many
products, components, and versions for the javascript
to work with. Query Page works fine on Internet Explorer
when the number of components,versions,products is low.

However the javascript works fine on Netscape even with
a large list of products, components, and versions.

Is there a way to modify the javascript so that Internet Explorer
will perform as well as Netscape? (with a large list of products,components
and versions)

Comment 1

[Dave Miller [:justdave]]

I think this was fixed in 2.14 though I'm not positive (andreas?).  As I recall,
there was a bug in IE's javascript that caused it to get a lot of undefined
variable errors if you had show errors enabled, and I'd imagine you'd get the
behavior you mention if you had errors disabled.  This was worked around I
think.  I'll wait for Andreas to confirm though, he knows more about the
javascript stuff than I do :)

Comment 2

[Matthew Tuck [:CodeMachine]]

The reason it works OK in N4 is that N4 doesn't reflow the page like it should.
 This is also a problem with N6 and Mozilla.

I'm not sure that there's anything that can be done about this in Bugzilla,
they're browser performance bugs.

Comment 3

[David Lawrence [:dkl]]

If anyone cares, it does this also using Konqueror. 

Comment 4

[Luis Villa]

cc'ing; also, if it is a performance problem in all browsers except NS 4.x, then
the problem is bugzilla's and not the browser's. Some way should be found to
make the javascript more efficient (or alternately, provide a js free version,
like bugzilla.redhat.com does).

Comment 5

[David Lawrence [:dkl]]

Adding a user preference for javascript or no javascript would be a possible
workaround for the 2.16 time frame if a better solution has not been discovered
by then.

Comment 6

[Christian Reis]

Hashing this out on #mozwebtools, I see the following solutions:

a) Removing the JS completely, no layout changes
+ familiar, low-impact, 100% perf solution
-  allows incorrect selection, bad UI

b) Alter layout of query.cgi
+ much needed anyway, perf a plus
- high-impact on UI, hamper QA temporarily

c) Inspect JS code and improve it speedwise
* dkl has suggested the code might suffer from a design problem, and said he was
gonna look into it. dkl, comments?

d) Provide placebo fix by adding a checkbutton to page or user pref:
"x Don't use (very slow) javascript on product/component selection boxes in
query.cgi"
+ low impact, low UI change
- not a real fix

e) Ignore problem, and mark WONTFIX

I personally don't think e) is an alternative at all. Comments?

Comment 7

[Luis Villa]

So... I mentioned this problem to one of the many code gods we have stashed away
here at work. Being the type he is, he immediately seized upon this as a
challenge and despite not having ever written any javascript before he produced
the following patch in about 15 minutes. In my test installations (see
http://bugzilla-test.ximian.com/query.cgi, which is unpatched, and
bugzilla-test.ximian.com/query2.cgi, which is patched) this makes for a very
noticeable difference in performance. It is most noticeable when clicking on one
 component and then quickly clicking on another; note that this is very smooth
in query2.cgi and jumpy in query.cgi. 

In a nutshell, the main change of the patch is to create a new array listing
only the changed components and then iterate over that instead of over all
components in a couple places.

Hrm. I'm having a real headache of a time getting the patch to behave correctly
against the query.cgi in bugzilla cvs; I'll post it as soon as I can, though.

Comment 8

[Luis Villa]

Attachment: a patch, I think

Comment 9

[Luis Villa]

OK, so... I've attached the patch. There was a /slight/ change to the structure
of the javascript in query.cgi between our fork and the main tree. So, while
this patch will apply cleanly to bugzilla from CVS, and it /should/ work, it is
not the exact patch I've applied to my tree, so it isn't tested. 

Comment 10

[Luis Villa]

Just some perf numbers: when testing this on bugzilla.redhat, I found that
clicking on one product and then ctl+clicking on a second product took 15
seconds to render when unpatched and 4 seconds when patched. Similar tests on
ximian gave similar 50-60% performance increases for the use of multiple
products. Still not ideal but much, much better. 

Comment 11

[Luis Villa]

If you are running an older bugzilla (or one of the RH children),
http://tieguy.org/query.patch should apply cleanly against those. [also adding
patch keyword, and I'd like to nominate it for 2.16 but I'm not sure what the
procedure is for that anymore.]

Comment 12

[Luis Villa]

Also adding review and perf as per suggestion in IRC.

Comment 13

[Jacob Steenhagen]

I agree, if this helps with speed at http://bugzilla.mozilla.org/query.cgi it'd
be a huge plus.

Comment 14

[Christian Reis]

Changing platform/os/severity. Let me see if i can hack this JS for the current cvs.

Comment 15

[Christopher Aillon (sabbatical, not receiving bugmail)]

Moving to new product Bugzilla...

Comment 16

[Zach Lipton [:zach]]

This is a query issue

Comment 17

[Luis Villa]

Christian: it should apply cleanly to bugzilla cvs. It may have one extra
parens; that's all.

Comment 18

[Christian Reis]

Okay, I'll produce a clean patch. However, I've noticed we could also
change the way in which the arrays are declared at the beginning of the
page so I'm looking into that as well (though it may be out of the scope
of this bug).

Comment 19

[Christian Reis]

Attachment: Patch against current cvs

Comment 20

[Luis Villa]

The arrangement of data in the array is sub-optimal, and could be tuned to allow
more efficient looping over the data. I wouldn't say it is out of the scope of
this bug, but it definitely would replace my patch (as opposed to complementing it.)

Comment 21

[Christian Reis]

okay, i've made a patch that applies against current cvs. I've setup two mockups
of b.m.o with patch applied and not applied. it's scary. :)

http://www.async.com.br/~kiko/query-patched.html takes about 2seconds to redraw
when clicking on a program. http://www.async.com.br/~kiko/query-original.html
takes about 9s to do the same. it's awesome. :) clahey, louie, congrats.

I would think this is so harmless it could be nominated for 2.14, but that's
just my opinion.

Comment 22

[Christian Reis]

I've added a test install to landfill, which can be seen at
http://landfill.tequilarista.org/bz96534 and I actually wrote a small script
using curl to add hundreds of components so we could see the performance problem
more closely. 

Interestingly, however, this plan has backfired somewhat and I've come to notice
that the performance problems aren't directly related to the sheer amount of
components registere but more to the amount of products _and_ components. What
I'm trying to imply is that a wider "product tree" is what makes query.cgi
slower and not just having a deeper one.

On landfill, i'd recommend testing URLs
http://landfill.tequilarista.org/bz96534/query-fast.cgi versusnd I've come to
notice that the performance problems aren't directly related to the sheer amount
of components registere but more to the amount of products _and_ components.
What I'm trying to imply is that a wider "product tree" is what makes query.cgi
slower and not just having a deeper one.

On landfill, i'd recommend testing URLs
http://landfill.tequilarista.org/bz96534/query-fast.cgi versus 
http://landfill.tequilarista.org/bz96534/query.cgi and clicking on FooBar and
MyOwnBadSelf (grin) repeatedly. On my local K6 400 it takes 3 seconds on
query.cgi and about 1 on query-fast.cgi. The other options have a lot of
components and the speedup isn't really spectacular for them, though they are
faster.

YMMV of course. :)
   

Comment 23

[Christian Reis]

Attachment: for educational purposes, the script I used to create hundreds of products on landfill

Comment 24

[Luis Villa]

Christian: the reason for your observations about the product listing being
central to the performance improvements is that (given the current data
structure) to determine whether or not a component should be shown, all
components are iterated over. What clahey's patch does is, for each component,
do [selected products] actions instead of [all products]. Hence, if you only
have a small number of products to start with, you won't see much performance gain. 

To get better performance, that scales wrt the number of components, new data
structures have to be created. Specifically, there would have to be an array
which maps products to components, so that when one selects a product, you'd
iterate over only the components _in_that_product_. At the moment, there is no
way to do that- you have to iterate over /all/ the components to figure out what
component they are in (which is where RH gets screwed.)

Comment 25

[Christian Reis]

Patch almost ready that implements the reversed product list. Just a
little bit of patience and all the ultraproduct/component bugzilla
setups will be a lot better. I'll have it in about 2h.

Comment 26

[Luis Villa]

Looks like we were thinking along the same tracks; I hadn't checked my email and
was about to post that it looked trivial to create such a product array. Having
never written any javascript, I'll leave the job to you, Christian. 

Comment 27

[Christian Reis]

Attachment: patch against query.cgi rewriting javascript

Comment 28

[Christian Reis]

Who said I wrote any Javascript before? *sigh*

Okay, the latest v1 patch attached implements the JS in a completely different
way, changing the arrays that exist. I'm not sure it's faster yet, but I'm
betting it and and will be testing on landfill next thing.

Caveats:
a) The current (cvs) implementation of query.cgi actually sorts products and
versions when multiple selections for products are done. I haven't implemented
that; it seems to have worked before because of the way the code and data
structures were organized. This structure is much clearer IMHO, but others may
differ.  So this is a regression of sorts if you like. It will be much faster
without sorting though.

b) Multiple selection doesn't work on Opera (seems opera only sets
"option[i].selected  == true" for the last selection clicked); dkl however
states it never worked. Any JS ninjas want to fix this? 

Reviewers?

Comment 29

[Luis Villa]

I for one don't think I can use any patch that doesn't sort across multiple
packages; that'll make it very difficult to do some of the multiple-component
selection I use regularly. I see how that is much easier to implement, though.
Compromise I'd prefer not to have to make, though. Maybe a JS god can implement
one of the simpler sorting algorithms to post-process the list?  

Comment 30

[Christian Reis]

I'd like to point out (specially for redhat folks) that my patch cuts the page
size by 50% on http://landfill.tequilarista.org/bz96534/query-fast2.cgi and
that's a good thing.

Louie, I'd like you to _positively confirm to me_ that bugzilla query.cgi today
sorts the versions, components and milestones for multiple product selections,
or if it merely has them group-sorted? Christopher says he's going to do a
merge-sort for us...

BTW: The sort need only kick in for multiple selections; for a single-selection
we can count on the database shipping items sorted, which is great. 

Comment 31

[Luis Villa]

Yeah, it is currently sorted, even for multiple product selections, which 95% of
the time doesn't matter but for that 5% of the time is very, very nice. That 50%
in page size will make the RH people very excited, I'm sure.:)

Comment 32

[David Lawrence [:dkl]]

Attachment: js/perl changes based on kiko's last patch

Comment 33

[Christian Reis]

David, against what version was that patch issued? I can't get that to apply
anywhere! My current implementation totally rewrites that section of code into
make_js_array unfortunately. I'll try and use the concept in mine but I have the
following problem:

            foreach $c (@{$data{$p}}) {
                if ( $in ) {
                    $ret .= ", ";
                }
                $ret .= "'$c'";
                $in = 1;
            }

See, I need to check and add the "," there if I'm doing any iteration after the
first (so we get the [ "Foo", "Bar", ... ] effect ). How could this be solved in
a better way?

Comment 34

[Christian Reis]

I have thought of a possible extra optimization. We could check _if_ the user
control or shift-clicked on the list, meaning: user altered one or more items in
the Program list. In this case, we don't have to re-insert all the items back
into our list; just insert/remove the items relevant and sort the items again.

This is hard, though, and I'm not sure it's worth it. Christopher of course
disagrees. :)

Comment 35

[Andreas Franke (gone)]

Dave: This bug has nothing to do with QuickSearch, sorry.

Comment 36

[Luis Villa]

Christian: I assume dave's patch applies against the older, RH based bugzilla's
like my own... 

Comment 37

[David Lawrence [:dkl]]

Louis: No, the patch I submitted 08/25/01 15:21 is a patch against the standard
mozilla code. I have a version of the last changes working with production RH
code that I could generate a patch for if needed.

Comment 38

[Christian Reis]

Attachment: patched in merge_arrays and changed updateselect a bit

Comment 39

[Christian Reis]

Attachment: v5 patch (%s/hash/array/g, fixed comments)

Comment 40

[Christian Reis]

Attachment: v6 (full array merging, optimized for adding components)

Comment 41

[Christian Reis]

The latest patch incorporates the merge/sort fixes suggested. It also implements
something like dkl suggested in the perl code, reducing the patch a bit.

This _also_ incorporated christopher's suggestion that we optimize for selecting
additional components, avoiding sorting those components individually again.

I'm half-javascript-insane, so somebody that still hasn't got dain bramage might
want to look at it and see if it works for them. I think we've got a good speed
increase, nice page size reduction, and no regression in features. So let me
know what you think about it. I daresay it's good enough. :)

Comment 42

[Christian Reis]

Attachment: now doesn't trigger on first page load

Comment 43

[Christian Reis]

I thought up an extra optimization, which is avoiding refilling the whole list
on the initial page load . This is implemented in the last patch, and I think it
will buy us some startup time savings - which will probably be noticeable for
large installs like bmo, redhat and ximian. David, Myk, Louie, if you want to
try these changes out, I think they look very nice indeed. And review is still
wanted.

Comment 44

[Myk Melez [:myk] [@mykmelez]]

>I thought up an extra optimization, which is avoiding refilling the whole list
>on the initial page load.

Does this take pre-selected items in the products list into account?

Comment 45

[Christian Reis]

Attachment: fixed bug in comment and optim

Comment 46

[Christian Reis]

There was a teensy bug that wasn't triggering the optim. It's in now. A bad
comment, too.

Myk: yes, sir. I check to see if selectedIndex == -1 before short-cutting out of
the function. I think this will do heaps of good to page load!

Comment 47

[Christian Reis]

Okay, I've done some preliminary testing using mozilla win32 on a P100 (slowest
box I could find) comparing result times for page loads and selections on
http://landfill.tequilarista.org/bz96534/query4.cgi
Warning: it's not pretty for the current situation ;) (keep in mind query4.cgi
is the current status)

a) Page load time
- Default query.cgi: 45s
- My JS query3.cgi: 35s 
- My JS + loadpage opt query4.cgi: 15s

b) Select one item
- Default query.cgi: 58s
- My old JS query-fast2.cgi: 9s 
- My JS + loadpage opt query4.cgi: 8s

c) [Select one] + Select three items (counting only time for second selection)
- Default query.cgi: 20s
- My old JS query-fast2.cgi: 12s 
- My JS + loadpage opt query4.cgi: 4s
b is particularly 3vil. Now all we need is somebody to verify if the results
output are correct :) IMHO these results are pretty impressive. Of course,
somebody might notice that landfill now has over 1000 dummy components lying
around, but hey, justdave said OK. 

Comment 48

[Christian Reis]

Attachment: v9 patch (every optimization has a bug, this one fixed)

Comment 49

[Christian Reis]

Okay, after serious regression testing, I've identified one last bug (*grin*) in
the code, which bit us when product selections came preloaded with _one
selection_. It's fixed. I want more people to bang on this; this bug is becoming
a boring monologue.

(details of the bug are in comment for first load that starts "turn first_load
off. [...]")

Comment 50

[Luis Villa]

I'll be trying this out on my test box this afternoon, probably; don't despair,
kiko :)

Comment 51

[David Lawrence [:dkl]]

v9 patch seems to work very well for us.

https://bugzilla.redhat.com/bugzilla/query2.cgi?jscript=1

Comment 52

[Christian Reis]

Oh, goodie, users.

There is a twin optimization to the multiple-select one: unselecting one or more
items. In that case, it theoretically would be faster to remove elements from
the list instead of unsorting them. 

There are some cruel reflections of that mod. The biggest one is that we uniq as
we merge many components/vers/tms, and in that we defeat simply removing duped
elements. We _could_ mark the arrays as having been dupified; using a persistent
array this could be done perhaps efficiently. Another is that we can't remove
from the options themselves, I need to remove from an array and flat load it out
into the options.

I don't want to do this. If enough people complain, I might. The reason is, I
believe that the performance problems we have now happen because loading the
arrays into the SELECT boxes is too slow, and that might be where we can gain
some extra speed. I would like some input on that and Fabian has offered to help.

If anybody can see something dumb in the JS (there were quite a couple in the
older versions of the patch) I'd really like to hear it. Sorry for
over-commenting. JS is 3vil.

Comment 53

[Luis Villa]

Just for the record, in case casual users stumble over this: there are still
some bugs in the last version of the patch; christian is looking at them and
should have a patch out. But... it is /damn/ fast :) Looking forward to a
version that works...

Comment 54

[Christian Reis]

Hmm, bugs in my code, you suggest? :)

Okay, I've found it. I'll paste it in against the latest version and also attach
the new version (yeah, more comments):

--- query-v9.cgi        Tue Aug 28 14:26:19 2001
+++ query.cgi   Tue Aug 28 14:26:54 2001
@@ -394,14 +394,20 @@
 
 function updateSelect(array, sel, target, sel_is_diff, single) {
 
-    // array merging/sorting in the case of multiple selections
+    // if single, even if it's a diff (happens when you have nothing
+    // selected and select one item alone), skip this.
     if ( ! single ) {
 
+        // array merging/sorting in the case of multiple selections
+
         if ( sel_is_diff ) {
-            // if the sel array we received was a diff, just merge the
-            // additionals.
-            for ( i in sel ) {
-                comp = merge_arrays(array[sel[i]], target.options, 1);
+        
+            // merge in the current options with the first selection
+            comp = merge_arrays(array[sel[0]], target.options, 1);
+
+            // merge the rest of the selection with the results
+            for ( i=1 ; i < sel.length ; i++ ) {
+                comp = merge_arrays(array[sel[i]], comp, 0);
             }
         } else {
             // here we micro-optimize for two arrays to avoid merging with a


As of now there are NO known problems with this patch. I would like to see
speedups, but unless Fabian or some other JS/DOM ninja pulls a rabbit out of his
hat, I think there's not much more to do.

In case people are wondering about the amount of comments, I'll defend myself by
saying JS is tricky code at times, and that some of these changes and opts I've
done are not too clear in the code. Perhaps to the regular algorithm ninja, it
is, but to me it's not.

Please, bang hard on this. I think we're close to the end.

Comment 55

[Christian Reis]

Attachment: v10 patch (some optimizations have two bugs, both fixed now)

Comment 56

[Christian Reis]

I thought up a new optimization. We could, instead of zeroing out the SELECT
before reinserting everybody, change the options in-place. This could be done in
two ways:

a) By setting value and text to the values we want. I've tested this, and it's
VERY slow. It seems to repaint in a wierd way, leaving a trail of dragged data
behind. No good.

b) By attributing a new Option() to the current position. This _would_ work,
though I'm not sure how fast it would be. However, the ns4 behaviour (quirks, in
mozilla) is to not allow the SELECT control to grow if you don't clear it out
first, says shaver. So I can't really see how this could be compatibly implemented.

So we're back to fixing bugs and waiting for input from reviewers and testers.
(Thanks, Louie.)

Comment 57

[Christian Reis]

Fabian has suggested changing the loop in updateSelect where we insert to the
SELECT something like:

    var newOption;
    for( i = 0; i < comp.length; i++) {
        newOption = new Option(comp[i], comp[i]);
        target.add(newOption, null);
    }

which would use the DOM1 add() method. However, it's not supported in NS4. If it
gets us significant boosts, we can sniff for it.

Comment 58

[Christian Reis]

Attachment: Added case-insensitive sorting to avoid dain bramage in merge_sort()

Comment 59

[Luis Villa]

Short the DOM-based stuff, the latest version of Christian's patch is now in
production at bugzilla.ximian.com and is very snappy. Thanks a bunch, Christian.

Comment 60

[Myk Melez [:myk] [@mykmelez]]

Attachment: HTML source of query.cgi with patch applied on test b.m.o.

Comment 61

[Myk Melez [:myk] [@mykmelez]]

Applied the patch on my own b.m.o. testing installation and did preliminary
testing.  It worksforme and is faster than the previous version.

Comment 62

[Myk Melez [:myk] [@mykmelez]]

Attachment: IGNORE PREVIOUS - HTML source of query.cgi with patch applied on test b.m.o.

Comment 63

[Christian Reis]

Attachment: v12 (fixed spacing, added perl sorting of js arrays. considering r= approval)

Comment 64

[Christopher Aillon (sabbatical, not receiving bugmail)]

r=caillon for javascript.  someone else should r= the perl stuff.

Comment 65

[Christian Reis]

Me and Fabian went over a couple of possibilities, and we've decided that this
can  rest. Randell is working on optimization of Option inserts (see bug 97345),
which is our major bottleneck here AFAICS. I've attached the current patch,
which does pre-sorting of the components and versions so if your database output
isn't sorted, it now gets done so it's consistent with our merge_array() method
and doesn't provide for irregularly sorted component lists.

Basically, this is hopefully the pre-review patch that we've been waiting for.
Thanks for everybody who endured the spam, and provided input on this.

Comment 66

[Dave Miller [:justdave]]

The existing query.cgi javascript has never worked in iCab on Mac OS X.  It
always completely trashed the component, version, and milestone lists if you had
Javascript enabled.  You guys will be happy to know that the new Javascript code
works perfectly in iCab 2.5.3.

in Omniweb 4.0.1, It also never worked before.  Omniweb would not trash them,
but would only display the first element in each list.  However, with the new JS
code,  it does not work at all in Omniweb.  Omniweb behaves as if there were no
javascript running.  Omniweb 4.0.4 was just released today.  I'm in the process
of downloading it now.  I'll let you know if it does any different (Omniweb's
javascript support is still young)

Comment 67

[Christian Reis]

Attachment: v13 (perl cleanups)

Comment 68

[Jacob Steenhagen]

The perl looks good to me... r=jake on that.

I don't know enough about Javascript other than to say "Yes, it works" :)

Comment 69

[Dave Miller [:justdave]]

r= justdave on the perl.

already have the r= caillon for the javascript, waiting for an r= from dkl on
the javascript (which he said he'd provide later today after seeing how it ran
on his server)

Comment 70

[Luis Villa]

If I can, I'll r=louie the javascript- I've had it in place at bugzilla.ximian
(both internal and external) for several days without issue, and it seems solid
from a code perspective.

Comment 71

[Dave Miller [:justdave]]

checked in.

Comment 72

[Fabian Guisset]

Sorry for the spam, but I wanted to take advantage of the fact that most
bugzilla gurus are CC'ed here to say that I am very grateful of the work you
guys are doing on Bugzilla. Without you I dare not think of what my life would
be when it comes to find a bug! You seem to have a very good team and I wish you
the best of luck for the next releases. I of course am always at your
disposition if you need advice on DOM stuff (wink kiko ;-)
-Fabian, a happy bugzilla user.