Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#9707 closed task (fixed)

[patch/cla] dijit.findWidgets simplification

Reported by: Les Owned by: bill
Priority: high Milestone: 1.4
Component: Dijit Version: 1.3.2
Keywords: findWidgets Cc:
Blocked By: Blocking:

Description

I simplified the dijit.findWidgets function (lightly tested).

dijit.findWidgets = function(/*DomNode*/ root){
	// summary:
   	//		Search subtree under root returning widgets found.
	//		Doesn't search for nested widgets (ie, widgets inside other widgets).
	
	var outAry = [];

	function getChildrenHelper(root){
		dojo.query(">", root).forEach(function(node) {
			var widgetId = node.getAttribute("widgetId");
			if(widgetId){
				var widget = dijit.byId(widgetId);
				outAry.push(widget);
			}else{
				getChildrenHelper(node);	
			}
		});
	}

	getChildrenHelper(root);
	return outAry;
};

Change History (19)

comment:1 Changed 10 years ago by bill

Do you mean by using dojo.query()? IIRC I specifically didn't use dojo.query() because it was faster to do it the way the current code works (or at least for IE6, where the performance was the biggest issue).

comment:2 Changed 10 years ago by Les

Yes, I just added dojo.query to get the children. The code is now more compact, but not as fast. Feel free to ignore this suggestion since performance is an issue.

comment:3 Changed 10 years ago by bill

Resolution: wontfix
Status: newclosed

OK, I'm going to close it then, this is one of those functions that gets called a lot so I wanted to optimize it for performance.

comment:4 Changed 10 years ago by Les

just FYI: I tried to convert dijit.findWidgets to use a non-recursive approach, but the code became longer, harder to understand and it didn't perform as I expected.

http://www.jslab.dk/articles/non.recursive.preorder.traversal.part4

comment:5 Changed 10 years ago by Les

Resolution: wontfix
Status: closedreopened

I'm going the reopen this ticket since the new code is now simpler and faster (2x as fast on some browsers).

dijit.findWidgets = function (/*DomNode*/ root) {

    // summary:
    //        Search subtree under root returning widgets found.
    //        Doesn't search for nested widgets (ie, widgets inside other widgets).
    var outAry = [];

    function getChildrenHelper(root) {
        var node = root.firstChild;
        while(node) {
            if (node.nodeType == 1) {
                var widgetId = node.getAttribute("widgetId");
                if (widgetId) {
                    var widget = dijit.byId(widgetId);
                    outAry.push(widget);
                } else {
                    getChildrenHelper(node);
                }
            }
            node = node.nextSibling;
        }
    }

    getChildrenHelper(root);
    return outAry;
};

comment:6 Changed 10 years ago by bill

Cool, I'll check it out. Thanks for looking into this. What were your performance results for each browser? I'm more interested in speeding up the slow and large-market-share browsers/versions.

Some dojo folks did performance tests on live collections before, see http://bugs.dojotoolkit.org/browser/trunk/bench/live_collections.html, and I thought I followed that pattern, although I guess this is a different ball of wax since it's just traversing a children list rather than a return from some function call like getElementsByTagName().

comment:7 Changed 10 years ago by Les

I tested the new findWidgets on IE 6, IE7, IE 8, Chrome 4, Safari 4 (Win), FF 3.0 and FF 3.5. Each platform showed speed improvement. Chrome 4 and Safari 4 both were 2x faster, FF 3.5 was 50% faster. IE was 10% faster.

Interestingly, performance numbers dropped a little when I changed getChildrenHelper() to an anonymous recursively called function.

Also, I tried to unroll the recursion, but the results were not good.

comment:8 Changed 10 years ago by Les

I'm more interested in speeding up the slow and large-market-share browsers

You mean IE?

comment:9 Changed 10 years ago by bill

Milestone: tbd1.4
Owner: set to bill
Status: reopenednew

Yah IE is definitely the biggest market share and usually the slowest.

I tried your patch and these are my results, running 1000 times on themeTester.html:

IE6 (before/after): 1813/1766 IE7: 1687/1687 IE8 (before/after): 750/765 (then again, 719/781) safari 4 (before/after): 117/71 FF3.5/win (before/after): 226/203

Looks good except that IE8 got marginally slower for me. But still an overall win I guess.

BTW, all the spacing changes you made are invalid, they go against our coding spec (the way it is originally is correct).

comment:10 Changed 10 years ago by bill

Oh, I just realized my test was strange since themeTester.html starts with a widget as the very root node. But running on test_Dialog.html shows all IE's getting slower:

FF3.5/mac:   882 --> 531
Safari4/mac:  316 --> 129
IE6:  3219 --> 3422
IE7:  2500 --> 3719
IE8:   1360 --> 1594

What was your test?

comment:11 Changed 10 years ago by Les

My test:

  1. http://archive.dojotoolkit.org/nightly/dojotoolkit/dijit/tests/test_Menu.html
  1. Run findWidgets 1000 times, each findWidgets returns 23 widgets:
var findWidgets = function (/*DomNode*/ root) {

    // summary:
    //        Search subtree under root returning widgets found.
    //        Doesn't search for nested widgets (ie, widgets inside other widgets).
    var outAry = [];

    function getChildrenHelper(root) {
        var node = root.firstChild;
        while(node) {
            if (node.nodeType == 1) {
                var widgetId = node.getAttribute("widgetId");
                if (widgetId) {
                    var widget = dijit.byId(widgetId);
                    outAry.push(widget);
                } else {
                    getChildrenHelper(node);
                }
            }
            node = node.nextSibling;
        }
    }

    getChildrenHelper(root);
    return outAry;
};

console.time('new');
for(var i=0; i<1000; i++) {
findWidgets(dojo.body());
}
console.timeEnd('new')

console.time('old');
for(var i=0; i<1000; i++) {
dijit.findWidgets(dojo.body());
}
console.timeEnd('old')

Results in ms:

Chrome 4: 1491 --> 483
FF 3.4: 1088 --> 662
IE8 5125 --> 4797
Safari 4 (Win)  1502 --> 464

I don't have IE6 or IE7 on my home computer, but as you can see the speed improvement is huge on newer browsers, remarkably Chrome 4 and Safari 4 is 3x faster.

I piped the JavaScript? code through this pretty printer:http://jsbeautifier.org/

Is there a dedicated Dojo pretty printer? :)

comment:12 Changed 10 years ago by Les

fixed typo: FF 3.5, not FF 3.4

comment:13 Changed 10 years ago by Les

My themeTester results: http://archive.dojotoolkit.org/nightly/dojotoolkit/dijit/themes/themeTester.html

Chrome 4:  951 --> 278
FF 3.5: 175 --> 198
IE 8: 3641 --> 3328
Safari 4 (Win): 717 --> 232

Again, big improvement except FF 3.5, but FF 3.5 was fastest overall at only 198 ms :)

comment:14 Changed 10 years ago by Les

My test_Dialog results:
http://archive.dojotoolkit.org/nightly/dojotoolkit/dijit/tests/test_Dialog.html

Chrome 4: 1170ms --> 346ms
FF 3.5: 650ms --> 473ms
IE8: 3906ms --> 3750ms
Safari 4 (Win) 1001ms --> 333ms

My tests show remarkable improvement.

comment:17 Changed 10 years ago by bill

Dojo doesn't have a pretty printer although there is a coding-conventions checker in util/checkStyle.

OK, I'll check this in along w/the others. Thanks for the patches.

comment:18 Changed 10 years ago by bill

Resolution: fixed
Status: newclosed

(In [20101]) findWidgets() performance boost from Les (CLA on file), thanks! Fixes #9707 !strict.

comment:19 Changed 10 years ago by bill

Type: enhancementtask

seems like these aren't really enhancements from the users' point of view, labeling as tasks instead

Note: See TracTickets for help on using tickets.