Bug 8177 – Javascript search incredibly slow

• Status: CLOSED
• Resolution: FIXED
• Component: DOM

[Andrew]

Hi,

This JavaScript function:

                        function selectd() {
                           for(var i=0;i<document.fmain.user.options.length;i++) {
                              if (document.fmain.domain.options[i].value ==
                              document.fmain.user.options[document.fmain.user.selectedIndex].value) {
                                 document.fmain.domain.selectedIndex=i;
                              }
                           }
                        }
                        function selectu() {
                           for(var i=0;i<document.fmain.domain.options.length;i++) {
                              if (document.fmain.user.options[i].value ==
                              document.fmain.domain.options[document.fmain.domain.selectedIndex].value) {
                                 document.fmain.user.selectedIndex=i;
                              }
                           }
                        }

Causes Safari to beachball for around 15 seconds before selecting the correct domain/username on a 1.5Ghz PowerBook, with 1.25GB or RAM runing Tiger. 

I can't give you a test case as this function is taken from WHM a script that requires root authentication on a server which naturally I can't put in a bug report. Basically there is a list of around 600 domains and a list of about 600 usernames, if the user clicks on the username it will search through the list of domains for the matching domain and vice-versa.

On the latest nightly the beachball spins for around 5-7 seconds, so there has been some improvement. However both FireFox and Opera select instantly, no noticable delay what-so-ever.

Andrew

[Alexey Proskuryakov]

Created attachment 8095 [details]
test case

[Alexey Proskuryakov]

I can confirm that this test case runs slower in Safari/WebKit than in Firefox, but not nearly as much (about 1 second in the latest nightly, about 5 seconds in 10.4.6, and that's a G4/867DP).

Reporter, do you see any important difference between my test case and yours? Also, could you please capture a sample of what happens during the freeze? Spin Control from Developer Tools would do it automatically, or you can use Activity Monitor if you don't have Developer Tools installed.

[Andrew]

Your test case does cause a beachball but for no where near as long as the original code. The format of the original code is:

 <select size="7" name="domain" onChange="selectu();">

			<option value="lnj23jkn6">1q1fhewsdax.com</option>
			<option value="wadsa266">1tasda2122.co.uk</option>

But there are 600+ option values, each of which is different and 9 characters long.

The other part of the script is like this:

<select size="7" name="user" onChange="selectd();">

			<option value="lnj23jkn6">lnj23jkn6</option>
			<option value="wadsa266">wadsa266</option>

But there are 600+ option values.

When selecting a value from the list with the code on the original page as described here Activity Monitor went from single figures for CPU usage up to 85% until the beach ball stopped.

I apologise for not having the skill to write a test case.

[Alexey Proskuryakov]

As a workaround, you can take most DOM accesses out of the loop - this makes the code run really fast. In my example, this suggestion corresponds to:

function selectd() {
   user = document.fmain.user;
   domain = document.fmain.domain;
   useroptions = document.fmain.user.options;
   domainoptions = document.fmain.domain.options;
   for (var i=0; i < useroptions.length; i++) {
	  if (domainoptions[i].value == useroptions[user.selectedIndex].value) {
		 domain.selectedIndex=i;
	  }
   }
}

Speaking about a possible fix in WebCore, looks like the lengths of HTMLCollections need to be cached better.

[Andrew]

Alexey, thanks for your reply. Unfortunately this is not my code, it is code from a piece of software (WHM) that I am forced to use in my daily job. Therefore I can't change it. It would however seem to be a WebCore bug as the code as is runs instantly in Presto/Gecko!

Looking forward to your solution.

[Alexey Proskuryakov]

Created attachment 8882 [details]
proposed patch

Use shared CollectionInfos for HTMLOptionsCollection and HTMLNameCollection, too.

The test runs perfectly fast now. A test with 2000 options also runs fast (no visible delay, a nice change from tens of seconds), but it still takes several seconds to open, because the DOM version keeps changing, which defeats caching:
   for (var i=0; i < 2000; i++)
	document.fmain.user.options[i] = new Option("User " + i, i);

I couldn't understand why the other collections (images, applets, all etc.) were returned from Document, but were only shared for HTMLDocuments. I just did the same.

[Darin Adler]

(In reply to comment #6)
> I couldn't understand why the other collections (images, applets, all etc.)
> were returned from Document, but were only shared for HTMLDocuments. I just did
> the same.

That's just a bug. We should fix that. In general, an XML document with XHTML elements in it should do almost everything the same as an HTML document.

[Darin Adler]

Comment on attachment 8882 [details]
proposed patch

m_CollectionInfo should be m_collectionInfo (both of them) and m_NameCollectionInfo should be m_nameCollectionInfo.

NUM_CACHEABLE_TYPES no longer seems to be a good name since now it's just the dividing line between ones that have no name and ones that have a name. Also no need for it to be all capitals -- macros are supposed to have all capital names, but that's not appropriate for enums or constants (I know, preexisting issue, not something you did).

+    HashMap<String, HTMLCollection::CollectionInfo>::iterator iter = map.find(name);
+    if (iter != map.end())
+        return &iter->second;
+    
+    return &map.add(name, HTMLCollection::CollectionInfo()).first->second;

I think it would be cool to just say:

    if (iter == map.end())
        iter = map.add(name, ...);

to collapse the two cases into one.

Is there goint to be trouble having lots of cached collections under different names, with no limit on the number? Could this lead to memory bloat?

Otherwise looks great.

review- just for the nitpicks above.

[Alexey Proskuryakov]

Created attachment 8951 [details]
proposed patch

Addressed the comments. Also changed the HashMap to use AtomicStringImpl*.

Of course, one can create an example for which this patch increases memory requirements significantly, but this is not much different from the existing m_elementsById or m_selectedRadioButtons caches... It's hard for me to estimate whether this is a practical issue.

[Alexey Proskuryakov]

Created attachment 8952 [details]
proposed patch

Oops, broke the build with a last-minute change. Should be better now.

[Darin Adler]

Comment on attachment 8952 [details]
proposed patch

Really unfortunate to introduce HTMLCollection.h into Document.h, but I suppose unavoidable.

+    HTMLCollection::CollectionInfo* nameCollectionInfo(int type, const String& name);

Can the above be an enum instead of int?

Nice patch, r=me.

[Alexey Proskuryakov]

(In reply to comment #11)
> Can the above be an enum instead of int?
Fixed.

Committed revision 15006.

Reporter, could you please use a nightly build to verify that this fixes the original issue?

[Andrew]

I cannot test the proposed fix as the latest nightly (Jun 24) fails to launch for me. I will try again soon.

Thanks.

[Alexey Proskuryakov]

Anyway, the latest nightly is r15004 at the moment, so the fix is not there yet :-)

[Andrew]

I was too quick hehe! :p

[Alexey Proskuryakov]

(In reply to comment #13)
> the latest nightly (Jun 24) fails to launch for me. I will try again soon.

  BTW: many Safari enhancers, such as PithHelmet, make WebKit crash on launch now. This is extremely unfortunate, but there isn't much that we can do about it.

[Andrew]

Thanks for the tip, I removed all the extras and WebKit launched. I'm pleased to report this bug is resolved! Now all I have to do is wait for Safari to be released with this version of WebKit (how many months is that going to be, sigh!).

I appreciate your help and fix.