Javascript, how to write a Array.sort method so that it is called through a timeout strategy?

Question

I am having a bottleneck with my sort() functions, something like:

list.sort(function (a,b) {return (a.value - b.value);});

that freezes the browser for a couple of seconds.

For the same situation with a loop it is recommended to use a "timeout" strategy, such as the one described here:

How to stop intense Javascript loop from freezing the browser

Then, the question is, can this be implemented with the sort methods?

*EDITED following the comment discussion

// main_div is a div defined before
for (let i=0; i<list.length; i++) {
    main_div.appendChild(document.getElementById(list[i].id));
}

How many elements in the array? Is there a possibility to use a [web worker](https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers) — Jaromanda X, Aug 28 '16 at 10:28
@JaromandaX I am looking into it now, discovered few minutes ago so I have no idea. The elements are like +500 now, but they could/will be more — GWorking, Aug 28 '16 at 10:32
500 elements is freezing the browser for 2 seconds? are you running on a 80386? — Jaromanda X, Aug 28 '16 at 10:33
@JaromandaX Now that you say it like this, probably what is freezing the browser is re-colocating the DOM nodes rather than the sorting. But still, the question remains relevant since as you suggested it involves using a webworker. I am looking at http://www.html5rocks.com/en/tutorials/workers/basics/ and trying to get a js_file from a function like in here http://stackoverflow.com/questions/3379875/can-javascript-get-a-function-as-text but with no success so far — GWorking, Aug 28 '16 at 10:36
@JaromandaX but I am also running a Chromebook, and the full system is loosing responsivity from time to time so the sort could also be a bottleneck — GWorking, Aug 28 '16 at 10:37
ahh, so this is an array of DOM nodes. Can you show the code that manipulates the DOM with the sorted array - it may be that the best way to deal with it is using a documentFragment - but without seeing that code, I'm only speculating — Jaromanda X, Aug 28 '16 at 10:38
The code is nothing strange, I have a bunch of nodes in div1, I move them to div2, and I move them again to div1 following a sorted array that has something like array.id and array.value, this is sorted by value, and I use the id to pick up the nodes from div2 to div1 — GWorking, Aug 28 '16 at 10:47
so, you're moving 500+ nodes, sorting an array, and moving 500+ nodes again? — Jaromanda X, Aug 28 '16 at 10:48
yes, I have 500 nodes in div1 (with a complex structure) and then I want to sort them by x, then I get an array of 500 objects with only 2 values, the x value, and the id of the node. Then to sort the original nodes I move the 500 nodes to div2 and then I move them again to div1 in the correct order by using this array. So I am not sorting the nodes but a simplified array — GWorking, Aug 28 '16 at 10:51
Again, without seeing anything, I can only speculate, but I'm sure you're overcomplicating how you display the sorted nodelist - the sorting **is not the bottleneck** so it doesn't matter if you're sorting on a simplified array or a nodelist — Jaromanda X, Aug 28 '16 at 10:53
@JaromandaX I've added how I add the divs in the question, I can tell you that when I move the 500 nodes to main_div it is not the problem, and I'd say moving them back is neither the problem. In any case I will look into it, but still I am very interested in being able to run parts of javascript in a non-blocking thread-like way, being that this sort or any other code — GWorking, Aug 28 '16 at 11:00
I've just tested with 10000 elements, and even doing it "the slow way" takes 1/10th of a second! — Jaromanda X, Aug 28 '16 at 11:17
@JaromandaX, I have now tested to change the DOM loop for a function-based loop to add the divs and you're right that the sorting doesn't take any significant time, so point taken. But still, I will try to get this done with a webworker as a way to understand them — GWorking, Aug 28 '16 at 11:27
I meant that the sorting in the display (not just the sort, but changing the DOM as well) takes 1/10th of a second for 10,000 elements - of course I don't know how complex each of your elements is — Jaromanda X, Aug 28 '16 at 11:30

trincot · Accepted Answer · 2016-08-28T12:26:48.267

You could execute the sort with the native sort method, but in a separate thread, using a web worker. The web worker will notify when it has completed its job. I have wrapped this in an ES6 promise, so you can use the then method (see further down for non-promise version):

function asyncSort(data) {
    // Return a promise
    return new Promise(function (resolve) {
        // function to be called by web worker:
        function onmessage(e) {
            e.data.sort();
            postMessage(e.data);
        }
        // Create the worker, passing it the above code (as blob URL)
        var worker = new Worker(URL.createObjectURL(
            new Blob(['onmessage = ' + onmessage.toString()])));
        // Capture the event when worker has finished
        worker.onmessage = function (e) { 
            resolve(e.data); // resolve the promise
        };
        // Let worker execute the sort (async)
        worker.postMessage(data);
    });
}

// Sample call
asyncSort([2, 3, 1]).then(function (result) {
    console.log(result); // [1, 2, 3]
});

The non-promise version looks like this:

function asyncSort(data, callback) {
    function onmessage(e) {
        e.data.sort();
        postMessage(e.data);
    }
    var worker = new Worker(URL.createObjectURL(
        new Blob(['onmessage = ' + onmessage.toString()])));
    worker.onmessage = function (e) { 
        callback(e.data);
    };
    worker.postMessage(data);
}

asyncSort([2, 3, 1], function (result) {
    console.log(result);
});

Note that IE (at least up to version 11) raises a security error on the Blob URL. As a work-around you would have to create a separate JS script file with just this content:

onmessage = function (e) {
    e.data.sort();
    postMessage(e.data);
}

...and then reference that script as the URL to the Worker in the original script:

new Worker('script.js')

Yes! that's what I was looking for, and thanks to let me see how to define a new worker with a simple function. A pity the webworkers cannot have access to the document or the DOM though :) — GWorking, Aug 28 '16 at 15:20
You're welcome. Just an additional idea for the DOM manipulation: create an array with pairs of sort data and related DOM HTML (fragment). Sort that by the "sort data" (whatever you sort by), and then join all the HTML together and insert it back. Downside is that you need to reassign event handlers. — trincot, Aug 28 '16 at 15:48
What I do is to generate an array with the id of my node and the data I want to sort, so the sort() only sorts this array, then with the sorted array I can access to my node through the id. I think this is what you're saying in some sense (?) — GWorking, Aug 29 '16 at 07:42
That is a good solution, yes: you would look up each element again by its id after the sort returns, and then move it to its correct position. I was actually hinting for providing the complete HTML of the node (instead of its id), thinking you could just destroy all elements in one go and recreate them by injecting the sorted HTML. In some situations this might be faster, but with the event handling downside. — trincot, Aug 29 '16 at 07:46

score 2 · Answer 2 · answered Aug 28 '16 at 11:00

2

You can implement your own sorting function, for example, here a simple selection sort:

function asort(a, compare, done) {
    var i = 0, j = 0, len = a.length;

    function step() {
        if(j >= len)
            [i, j] = [i + 1, i + 1];
        if(i >= len)
            return done();
        if(compare(a[j], a[i]) < 0)
            [a[i], a[j]] = [a[j], a[i]]
        j++;
        setTimeout(step, 0);
    };

    step();
}

This is far slower than the stock sort, but doesn't block the main thread.

answered Aug 28 '16 at 11:00

georg

211,518
52
313
390

perhaps you should add a note regarding your use of ES2015+ methods that wont work in IE11 for example - nor will it work in Edge unless you have the anniversary update (Edge 14) – Jaromanda X Aug 28 '16 at 11:23
Thanks for the heads up… but honestly I don't see a point in comments like this. If you feel something should be added to the post - just edit it, this is how SO works. – georg Aug 28 '16 at 20:16
I've only been on SO for a year and I've had such advice given every effing time i post an answer that wine work on ie7 or something. So I thought THAT was how it worked around here. I.e. find anything to criticize a good answer – Jaromanda X Aug 28 '16 at 21:18

Javascript, how to write a Array.sort method so that it is called through a timeout strategy?

2 Answers2