Writing a Non-Blocking JavaScript Quicksort
breck-mckye.com
breck-mckye.com
var code = "onmessage = function (evt) {evt.data.sort(); postMessage(evt.data)}";
function asyncSort(data, cb) {
var worker = new Worker(URL.createObjectURL(new Blob([code])));
worker.onmessage = function (evt) { cb(evt.data); };
worker.postMessage(data);
}
asyncSort([3, 2, 1], function (res) { console.log(res); });
"[1, 2, 3]"However it looked like he needed to support IE8, so this might be an ok solution (although I would argue a terrible one for anyone who doesn't need to support IE8/9).
Edit: I assume I'm being downvoted because you're still running the script in the main thread, and therefore lose the concurrency. Obviously this is an issue with a polyfill, but the point of polyfilling web workers would be to keep the one codebase rather than writing your your web app with and then without web workers.
Depending on what you're doing, you may want to yield after x operations rather than on every recursive invocation like the example shown. There is a performance cost to using setImmediate.
But FWIW, you can do canvas pixel operations with a web worker, which you then blit to the canvas, which is acceptable in some cases.
> when transferring an ArrayBuffer from your main app to Worker, the original ArrayBuffer is cleared and no longer usable
This is really too restrictive in many situations.
[1] https://developers.google.com/web/updates/2011/12/Transferab...
Isn't that exactly what they are doing?
>> Our approach was simply to prefer the native implementation unless working in IE8 or with arrays over a thousand items.
The basic problem is that Array.prototype.sort() does not accept indexes for a slice of the array to sort between.
I remember seeing this in an event-driven server framework (computation as the special case), this usage of "non-blocking" suggests it might be a trend.
It used to be "blocked" meant "process is waiting for an external event, usually I/O". Doing computation was typically referred to as "busy". "Non-blocking" meant "without putting the process to sleep".
There seems to be a shift in the meaning of this particular piece of terminology that I find interesting, because it seems to reflect the reality that "computers" actually do very little "computing". Instead computers mainly communicate, and even the CPUs themselves probably spend most of their time waiting on main memory (60ns) rather than doing actual arithmetic (sub ns in most cases).
Of course, "human" in the above isn't strictly correct, since we know that computers talk to each other all the time, too. Indeed, when that happens the main engine of computation isn't really one or the other of the computers, but the link between them (i.e., the protocol).
So now "blocking" means requiring the main engine of computation to "sleep" and wait for "external input". For a human UI this means the classic sense of waiting on the wetware end, but it can just as easily mean waiting on the hardware end.
We strive to build responsive systems, so we wish for them to be "non-blocking" in every case. This means, if the human wants to communicate to the computer, it shouldn't be prevented to because the computer is currently working on a solitary operation. Ultimately it's the same principle we've already accepted from the reverse direction.
Other ecosystems also have problems with computations on the UI thread but running most of the application logic on different threads comes far more natural there and standard libraries offer a much richer support for multi-threading/fine-grained task execution (be it mutable or immutable shared state).
Apparently "non-blocking" is used here to mean roughly the opposite of what it normally means (that your computation doesn't slow down the I/O). Oddly enough, this seems kind of reasonable for interactive programs: the I/O is the more important part, so it's the thing you want to not interfere with.
It's still a little confusing.
No, it's been one for a long time. We call this situation "cooperative multithreading". (If you object to the "threading" term, bear in mind we called it this long before everything was multi-core.) We have learned to prefer pre-emptive multithreading on the grounds that while cooperative multithreading may occasionally have small advantages, it frequently has massive disadvantages, and the balance isn't even close.
Unfortunately, the browser has had all kinds of work done on it over the years that deeply assumed cooperative multithreading was the order of the day, and it's very difficult to change that out now. I do not mean that as a sarcastic statement or something, I mean, seriously, changing a codebase or specification base the size of the browser from cooperative to pre-emptive is an incredible and very difficult change. Computation blocks are a huge and ongoing problem if you want really low-latence javascript, and while there's not "nothing" you can do about it, the tools are pretty crude and limited.
"setTimeout and browser timing are deceptive and shouldn’t be wholly trusted"... and as a result, use the setImmediate API.
https://developer.mozilla.org/en-US/docs/Web/API/Window/setI...
It's a bit of a mess. I think there is some misunderstanding here of what the requirements are. I should be able to queue callbacks and have them execute using 100% of the CPU, but still yield to browser and IO events so that the broswer (or IO processing) is responsive.
A lot of the talk is about minimum waits. For example setTimeout(0) apparently has a minimum timeout according to the spec. It's not that I want the minumum wait to be any particular value. It's that I want it to be as small as it can be while still yielding to browser and IO events. While I have callbacks queued and executing, I want the CPU to be pegged at 100%. While it is pegged at 100%, the browser should still be responsive if my callbacks yield often.
So reading the thread it seems that on Gecko setTimeout(0) does not max the CPU (because it is waiting -- I'm going to give this a try next time I get a chance). Also using .then() on a native Promise does not seem to yield to the browser (apparently this is what the spec asks for).
Edit: ok I read some background, assume you mean it should be unclamped?
My background is in embedded telephony. I've worked on many systems that are single threaded because you have real time constraints. You have to make sure that your bit of work finishes in a certain amount of time and then you yield to the next bit of work. You could imagine that it would be very strange if a telephone switch handled connecting one call, but before it could connect another call it would have to "rest" for 15 ms.
The Javascript event loop is really just the reactor pattern: http://en.wikipedia.org/wiki/Reactor_pattern
There are many, many useful ways to use the reactor pattern. In fact, I have often used it in preference of threads in GUI applications because it gives you very fine grained control over how much responsiveness you want in the UI. As long as you yield every X ms, it means that the user only has to wait X ms for a response to their actions. You can also prioritise work easily. With threads, you are at the mercy of the task scheduler and so you might have very uneven response times.
In the same way, I want to be able to program things that run continuously in JS but not have to give up the responsiveness in the browser (or other IO events). Like the original author, imagine that you are sorting thousands of records and it will take 3 seconds. You don't want to hang the browser for 3 seconds because maybe they want to click the "cancel" button. So you yield every 50 ms. But if you have something like a 15 ms wait time every time you yield, your 3 second task is going to take 4 seconds... for no reason at all.
So what I want is to be able to yield, have the system check for events and if there aren't any, resume as quickly as possible. Obviously there will be some overhead. But sticking a timer on it and saying, "I'm just going to take a brief nap" really sucks.
The problem I'm noticing is that some people think that there should be no delay at all. As soon as schedule a callback, it should run. This is not desirable at all. Again, the whole point is to yield to events and then come back. I just don't want to wait longer that it is necessary to do that.
To sum up, it's not that I want to use 100% CPU all the time, but if it is impossible to do, then it is broken. Similarly, if I am using 100% of the CPU and yielding every X ms, then then events should be handled every X ms (modulus the amount of time the event handler takes).
The most obvious thing is just to call out to a (semi-) global:
function quicksort(arr, cb) {
var thread_balance = 1;
function thread(start, end) {
if (not trivially solved) {
partition_stuff;
thread_balance += 1;
setImmediate(...);
setImmediate(...);
} else {
thread_balance -= 1; // this thread is done.
if (thread_balance === 0) {
cb(arr);
}
}
}
thread(0, arr.length);
}
Taking this a little further, we can wrap setInterval in a Promises library which gives you back a promise for the sorted halves of the array; the thread(start, end) promise resolves with the [start..end-1] indices being sorted, and in the nontrivial case returns Promise.all([thread(start, pivot - 1), thread(pivot, end)]) (the promise-library's merge of the two promises to complete the work). Same idea really.
Does Array.sort run much faster when the array already has some order?
EDIT: It doesn't. Sorting even totally sorted array takes as much as sorting shuffled array.