Why does it take more time to sort jQuery set than array in Safari?

Question

Let's say I have the following JS on my page (compare is a simple comparator function not relevant to the question):

    function sortArray(a) {
        a.sort(compare);
    }

    function sortJQuerySet(b) {
        b.sort(compare);
    }

    $(document).ready(function(){
        var a = [], b = [], i = 0, n = 1000;

        for(i=0; i<n; ++i) {
            a.push($('<div>' + i.toString() + '</div>'));
            b.push($('<div>' + i.toString() + '</div>'));
        }

        b = $(b);

        $('#runner').click(function(){
            sortArray(a);
            sortJQuerySet(b);
        });
    });

As you can see, a and b are essentially the same array, the only difference is that b is turned into jQuery set. I'm trying to sort both of those arrays and to profile the sorting. Please note that the number of elements in both arrays is 1000.

Here is the result of profiling of sorting for both containers in Safari: enter image description here

Safari makes about half a million comparisons on jQuery set with 1000 elements. This looks much more like quadratic sort than like O(n log n) sort. In a meantime, sorting the native array is just fine.

Sorting in Chrome browser works in about equal time for both container types.

P.S. I used Safari 6.0.4, jQuery 1.7.1 and jQuery 1.10.1. Code: https://gist.github.com/ikostia/5925715

Your sorting function returns either `-1` or `0` for each element. The second line isn't right. — Blender, Jul 04 '13 at 07:56
Also, `.text` returns the `text` function, not the element's text. — Blender, Jul 04 '13 at 08:01
@Blender Oh, I see. Sorry for that (Already changed). Anyway, that does not change the fact that the function itself is called a quadratic number of times. — ikostia, Jul 04 '13 at 08:02
@dystroy My question does not relate to the speed of each container itself. The difference in performance is caused by the sorting algorithm as well (at least I suspect so). The number of ``compare`` calls has nothing to do with the speed of container. — ikostia, Jul 04 '13 at 08:06
@Blender What do you mean by 'any other browser'? I can't reproduce it in anything except for Safari either. — ikostia, Jul 04 '13 at 08:15

score 1 · Accepted Answer · edited May 23 '17 at 11:49

Perhaps this discussion regarding WebKit engine could shed some light.

It appears to me from the line: 631 if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->inSparseMode()) { that only non-arrays, or arrays in some kind of "sparse" mode are sorted inefficiently. I'm not sure what sparse mode is, but let's try my Raymond Chen inspired psychic powers: if you assign a[0]=1 and a[1000000]=2, you don't want a 1 to 999999 to be stored, so an array like that will end up in a sparse mode which functions more like a hash table keyed by integers. The same applies to non-arrays...

(the source code discussed in the aforementioned citation is here)

So let's now take a look at the jQuery source code. Calling $(someArrayOrSelectorString) results in invoking the init method (Line 43). The init method returns jQuery.makeArray( selector, this ), where this is an instance of jQuery (please, correct me if I'm wrong). And, finally, inside makeArray method the jQuery.merge (line 600) is invoked, which will populate the jQuery instance with the passed array elements.

So it looks like wrapping an array results in an array-like object (jQuery instance), but not a real array. And Safari treats this object like a sparse one.

(You might be interested in this answer and comments. That's where I've borrowed the idea for my answer)

Why does it take more time to sort jQuery set than array in Safari?

1 Answers1