Rails spinoffs - Jun 2006 - getElementsByClassName

How should I expect the performance of this function to be?

I wrote this code:

function CreateTOC(){
			
	var $aTOC = document.getElementsByClassName(''tocitem'');

	if(isArray($aTOC)){
	
		$temp = ''<INPUT TYPE="SUBMIT"
NAME="cmdSave_Update"
VALUE="Close" CLASS="menubuttons"> '';
		$temp += ''<INPUT TYPE="SUBMIT"
NAME="cmdSave_Update"
VALUE="Save_Update" CLASS="menubuttons"> '';
		$temp += ''<SELECT NAME="cboTOC"
onChange="location=this.options[this.selectedIndex].value">
'';
		$temp += ''<OPTION VALUE="">Table of
Contents</OPTION>'';

		for($i = 0; $i < $aTOC.length; $i ++){
			
			$sValue 	= $aTOC[$i].name;
			$sName 	= $aTOC[$i].innerHTML;
			$temp 	+= ''<OPTION VALUE="'' + $sValue +
''">'' +
$sName+ ''</OPTION>'';
			alert($sValue);
			}
		
		$temp += ''</SELECT> '';
		$temp += ''<INPUT TYPE="SUBMIT"
NAME="cmdOpenReport"
VALUE="Open Report" CLASS="menubuttons"> '';
		<?php if($_SESSION[''PrintOptions''] == 0) $sPrintOptions
= ''Off''; else $sPrintOptions = ''On'';?>
		$temp += ''<INPUT TYPE="SUBMIT"
NAME="cmdPrintOptions"
VALUE="Print Options <?=$sPrintOptions?>" '';
		$temp += ''STYLE="font-size: 9px; width: 90px"
CLASS="menubuttons"> '';
		$(''menu'').innerHTML = $temp;
			
		}

	}

In a small page (258 lines of code), it''s quick, in another page (7500
lines of code), it takes 10-15 seconds to load. I''ve checked and most
of
the delay is getElementsByClassName. 

Is that right?

_____________________
Thanks,   

Keith Davis - MCSA, A+, N+
P.R.I.D.E. - Director of Computer Services
www.pridedallas.com
Work (214) 351-6600 ext. 119
Mobile (214) 906-5183




_______________________________________________
Rails-spinoffs mailing list
Rails-spinoffs-1W37MKcQCpIf0INCOvqR/iCwEArCW2h5@public.gmane.org
http://lists.rubyonrails.org/mailman/listinfo/rails-spinoffs

Keith Davis wrote:
> How should I expect the performance of this function to be?
[...snipped code suspected problem area...]
>        * var $aTOC =
document.getElementsByClassName(''tocitem'');*
Unfortunately the only way to find objects with a given class name can 
be slow. This is because the library much search each element in 
consideration and see if it contains the given class name. Since an 
element can have more than one class name this is not a simple comparison.

document.getElementsByClassName() uses a regular expression to find 
matching classes which is fairly fast but if you have a lot of elements 
it can be slow. The best way to make it faster is to reduce the number 
of element to check. For example if you know that the elements you are 
looking for is contained by an element with a known id you can do:

$$(''#section .tocitem'');

Or if you know the element tag name you can increase performance by 
searching elements with the known tag. So:

$$(''li.tocitem'');

One more problem to consider. If you use the $$() instead of 
document.getElementsByClassName() it will use Element.hasClassName() 
which is much slower than using a regular expression. So prior to using 
the $$() function you might want to do:

Element.hasClassName = function(element, className) {
	return element.className.match(new RegExp("(^|\\s)" +
		className + "(\\s|$)"));
};

This will cause Element.hasClassName() to use the same implementation 
that document.getElementsByClassName() uses which in my tests produces 
much better performance because it is a simple regex (builtin to 
Javascript and therefore fast) instead of splitting each classname, 
constructing an object and then iterating over each item in the 
collection to determine if the class exists.

Eric

Given the results of your testing, do you intend to propose a patch  
for Prototype?

May I suggest that adding non-capturing groups to the RegExp may be  
the tiniest bit faster? This is untested supposition, and I''d be  
quite interested to see your results if you chose to test it.

      new RegExp("(?:^|\\s)" + className + "(?:\\s|$)")


TAG

On Jun 21, 2006, at 1:10 PM, Eric Anderson wrote:
>
> One more problem to consider. If you use the $$() instead of  
> document.getElementsByClassName() it will use Element.hasClassName 
> () which is much slower than using a regular expression. So prior  
> to using the $$() function you might want to do:
>
> Element.hasClassName = function(element, className) {
> 	return element.className.match(new RegExp("(^|\\s)" +
> 		className + "(\\s|$)"));
> };
>
> This will cause Element.hasClassName() to use the same  
> implementation that document.getElementsByClassName() uses which in  
> my tests produces much better performance because it is a simple  
> regex (builtin to Javascript and therefore fast) instead of  
> splitting each classname, constructing an object and then iterating  
> over each item in the collection to determine if the class exists.
>
> Eric
>

Tom Gregory wrote:
> Given the results of your testing, do you intend to propose a patch for 
> Prototype?
I was planning on it but I have only tested my problem domain. I am not 
sure how it would compare in a variety of environments. As the number of 
elements increases libraries like Event:Selector and behavior.js get 
really slow because of searching for class names.

Narrowing down the search provides the most benefit (via an id or tag 
name) but in my tests reimplementing Element.hasClassName() as a regular 
expression also provides a small benefit because each comparison is 
faster (for my web pages).

But I haven''t tested to see under what situations it is faster. Is it 
faster only when the elements have many class names or even when an 
element has one class name? Could hasClassName do a stupid comparison 
and only if that fails do a RegExp to achieve faster results (since most 
elements either do not have a class or only have one). Something like:

element.className == className ||
	element.className.match(new RegExp("(^|\\s)" +
	className + "(\\s|$)"))

There should be a performance gain of caching the RegExp object (so we 
don''t have to recreate the RegExp every time we do a comparison) but
how
much of a gain and how much would that increase the code complexity?

Also perhaps the optimization really needs to happen in libraries like 
behaviour.js and Event:Selectors. If your rules look something like this:

var Rules {
	''.foo'': function(e) {},
	''.bar'': function(e) {},
	''.baz'': function(e) {},
}

You are doing three full document traversals when you only need to do 
one. It gets worse as you continue to add more rules. Perhaps those 
libraries should do one document traversal and index all the info. This 
increases memory usage but should speed up cases like this. But then if 
my rules are lighter:

var Rules {
	''#section p.foo'': function(e) {},
	''#another-section li.bar'': function(e) {},
	''#yet_another a.baz'': function(e) {},
}

In this case we only traverse parts of the document so a pre-traversal 
that indexes all the info would be overkill.

Optimization is obviously needed but I think comprehensive benchmarks 
should be done before developing patches to determine what provides the 
most benefit under the most situations with the least complexity added 
to the code. Without that we are only partially guessing and we may be 
making Prototype more complex than it needs to be.

Even once optimization is done there are a few other things to consider:

* There will still probably be special cases that will be slow. This 
information needs to be published so people who fall into those special 
cases know how to make their way out.

* Most of this optimization is needed because we are doing so much work 
in Javascript. Is there a better way? XPath has the same goal of CSS 
Selectors. Is there native browser support for that? Perhaps it would be 
a better technology. Also the browsers have to do this same work when 
applying CSS styles. Is there anyway they could expose that 
functionality so we could have native code doing the searching instead 
of slow interpreted code? I think a element selector library is 
extremely useful but implementing it at the Javascript level seems to be 
the wrong implementation.

Eric