Bug Tracker

Opened 13 years ago

Closed 13 years ago

#908 closed enhancement (fixed)

merge speed improvments

Reported by: sebastian Owned by:
Priority: major Milestone: 1.1.3
Component: core Version: 1.1.2
Keywords: Cc:
Blocked by: Blocking:

Description

I commented on the blog post regarding the performance comparison of various frameworks and said I would test a bit.

So I did. Here are the results.

The test page is very simple. It starts like this:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN"
  "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript">
function echo(m)
{
   var msg = document.getElementById("msg");
   msg.appendChild(document.createTextNode(m + "
"));
}

$(document).ready(function() {
   var start, end;
   start = new Date();
   var byname = document.getElementsByTagName("div");
   end = new Date();
   echo("Byname count: " + byname.length);
   echo("Byname time: " + (end - start));
   start = new Date();
   var directsel = $("div");
   end = new Date();
   echo("Direct selector count: " + directsel.length);
   echo("Direct selector time: " + (end - start));
   start = new Date();
   var doublesel = $("div div");
   end = new Date();
   echo("Double selector count: " + doublesel.length);
   echo("Double selector time: " + (end - start));
   start = new Date();
   var murdersel = $("div, div div");
   end = new Date();
   echo("Murder selector count: " + murdersel.length);
   echo("Murder selector time: " + (end - start));
});
</script>
</head>
<body>
<pre id="msg"></pre>

This is followed by 285 repetitions of this HTML snippet, which forms
the search base for the expressions above:
<div>
</div>
<div>
   <div>
   </div>
</div>
<div>
   <div>
   </div>
   <div>
       <div>
       </div>
   </div>
</div>

(A total of 1995 divs.)

I ran the tests on a Athlon64 3000+ (clocked at 2.2 GHz), single core, 1 GB RAM, running Gentoo Linux in 64-bit mode. I used three browsers: Firefox 1.5.0.9 Opera 9.02 Konqueror 3.5.5

I tested each of them several times; the results varied within 5%.

OK, that's all very boring, really. Here's the important thing: I tested both jQuery 1.1.1 and a version patched with the attached file. The patched version uses the object identity issue I pointed out in the blog comment to speed up the duplicate check of merge() and map().

Here are my results:

Firefox:
Without speed patch:

Byname count: 1995
Byname time: 1
Direct selector count: 1995
Direct selector time: 2535
Double selector count: 1140
Double selector time: 4019
Murder selector count: 1995
Murder selector time: 6588

With speed patch:

Byname count: 1995
Byname time: 1
Direct selector count: 1995
Direct selector time: 139
Double selector count: 1140
Double selector time: 2621
Murder selector count: 1995
Murder selector time: 2588


Opera:
Without speed patch:

Byname count: 1995
Byname time: 0
Direct selector count: 1995
Direct selector time: 2579
Double selector count: 1140
Double selector time: 2113
Murder selector count: 1995
Murder selector time: 4945

With speed patch:

Byname count: 1995
Byname time: 0
Direct selector count: 1995
Direct selector time: 45
Double selector count: 1140
Double selector time: 2108
Murder selector count: 1995
Murder selector time: 2105


Konqueror:
Without speed patch:

Byname count: 1995
Byname time: 0
Direct selector count: 1995
Direct selector time: 5043
Double selector count: 1140
Double selector time: 3699
Murder selector count: 1995
Murder selector time: 9540

With speed patch:

Byname count: 1995
Byname time: 0
Direct selector count: 1995
Direct selector time: 128
Double selector count: 1140
Double selector time: 8415
Murder selector count: 1995
Murder selector time: 8490

Only an extensive test suite can verify that everything still works correctly after applying the patch, but the dramatic performance improvements especially on the simple selector should make it worth the while. The strange slowdown of Konqueror on the second selector also needs investigating. Another issue is of course the rather unsophisticated timing method I used. This was a quick hack, a work of a few hours, and I have no previous experience with JS profiling.

Thank you for this interesting library.

Sebastian Redl

--- jquery.js   2007-01-22 23:20:57.000000000 +0100
+++ jquery-smartmerge.js        2007-01-23 00:36:54.000000000 +0100
@@ -182,12 +182,12 @@
               return this.prevObject || jQuery([]);
       },
       find: function(t) {
-               return this.pushStack( jQuery.map( this, function(a){
+               return this.pushStack( jQuery.nodemap( this, function(a){
                       return jQuery.find(t,a);
               }) );
       },
       clone: function(deep) {
-               return this.pushStack( jQuery.map( this, function(a){
+               return this.pushStack( jQuery.nodemap( this, function(a){
                       return a.cloneNode( deep != undefined ? deep : true );
               }) );
       },
@@ -216,7 +216,7 @@
       },

       add: function(t) {
-               return this.pushStack( jQuery.merge(
+               return this.pushStack( jQuery.nodemerge(
                       this.get(),
                       t.constructor == String ?
                               jQuery(t).get() :
@@ -498,7 +498,7 @@
                       if ( arg[0] == undefined )
                               r.push( arg );
                       else
-                               r = jQuery.merge( r, arg );
+                               r = jQuery.nodemerge( r, arg );

               });

@@ -592,6 +592,20 @@

               return first;
       },
+       nodemerge: function(first, second) {
+               for(var i = 0, fl = first.length; i < fl; ++i) {
+                       first[i].jQnmarked = true;
+               }
+               for(var i = 0, sl = second.length; i < sl; ++i) {
+                       if(!second[i].jQnmarked) {
+                               second[i].jQnmarked = true;
+                               first.push(second[i]);
+                       }
+               }
+               for(var i = 0, fl = first.length; i < fl; ++i) {
+                       first[i].jQnmarked = false;
+               }
+       },
       grep: function(elems, fn, inv) {
               // If a string is passed in for the function, make a function
               // for it (a handy shortcut)
@@ -638,6 +652,41 @@
               }

               return r;
+       },
+       nodemap: function(elems, fn) {
+               // This version is specialized for arrays consisting entirely of
+               // objects, in particular DOM nodes.
+               // If a string is passed in for the function, make a function
+               // for it (a handy shortcut)
+               if ( typeof fn == "string" )
+                       fn = new Function("a","return " + fn);
+
+               var result = [], r = [];
+
+               // Go through the array, translating each of the items to their
+               // new value (or values).
+               for ( var i = 0, el = elems.length; i < el; i++ ) {
+                       var val = fn(elems[i],i);
+
+                       if ( val !== null && val != undefined ) {
+                               if ( val.constructor != Array ) val = [val];
+                               result = result.concat( val );
+                       }
+               }
+
+               var r = result.length ? [ result[0] ] : [];
+
+               for ( var i = 1, rl = result.length; i < rl; i++ ) {
+                       if(!result[i].jQmmarked) {
+                               result[i].jQmmarked = true;
+                               r.push(result[i]);
+                       }
+               }
+               for ( var i = 1, rl = r.length; i < rl; i++ ) {
+                       r[i].jQmmarked = false;
+               }
+
+               return r;
       }
 });

@@ -834,7 +883,7 @@
                       old = expr;
                       var f = jQuery.filter( expr, elems, not );
                       expr = f.t.replace(/^s*,s*/, "" );
-                       cur = not ? elems = f.r : jQuery.merge( cur, f.r );
+                       cur = not ? elems = f.r : jQuery.nodemerge( cur, f.r );
               }

               return cur;
@@ -905,7 +954,7 @@
                                       // If the token match was found
                                       if ( m ) {
                                               // Map it against the token's handler
-                                               r = ret = jQuery.map( ret, jQuery.isFunction( jQuery.token[i+1] ) ?
+                                               r = ret = jQuery.nodemap( ret, jQuery.isFunction( jQuery.token[i+1] ) ?
                                                       jQuery.token[i+1] :
                                                       function(a){ return eval(jQuery.token[i+1]); });

@@ -926,7 +975,7 @@
                                       if ( ret[0] == context ) ret.shift();

                                       // Merge the result sets
-                                       jQuery.merge( done, ret );
+                                       jQuery.nodemerge( done, ret );

                                       // Reset the context
                                       r = ret = [context];
@@ -976,7 +1025,7 @@
                                                       if ( jQuery.nodeName(this, "object") && tag == "*" )
                                                               tag = "param";

-                                                       jQuery.merge( r,
+                                                       jQuery.nodemerge( r,
                                                               m[1] != "" && ret.length != 1 ?
                                                                       jQuery.getAll( this, [], m[1], m[2], rec ) :
                                                                       this.getElementsByTagName( tag )
@@ -1025,7 +1074,7 @@
               if ( ret && ret[0] == context ) ret.shift();

               // And combine the results
-               jQuery.merge( done, ret );
+               jQuery.nodemerge( done, ret );

               return done;
       },

Change History (1)

comment:1 Changed 13 years ago by john

Milestone: 1.1.3
need: Review
Resolution: fixed
Status: newclosed
Version: 1.1.2

I borrowed your 'marked' idea for checking uniqueness and merged some new improvements in (rev [1576]), that are actually very very fast. Thanks for your help!

Note: See TracTickets for help on using tickets.