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);
}
Example,
asyncSort([3, 2, 1], function (res) { console.log(res); });
I thought that as well, if you are going to use setImmediate, it would probably make the most sense to just a web worker which is actually standardized and supported in all browsers (and won't turn your quick sort fn into a mess).
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).
You can sort of polyfill web workers by providing the same API but running the web worker in the main thread.
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.
Which misses the point entirely. The problem the author had was doing sorting of many items in IE8 without a warning. Using a real web worker would be a solution, but using a web worker polyfill that ran in the main thread would put him right back where he started, with IE8 triggering a warning.
I wasn't clear enough: I'd be polyfilling web workers not for this specific problem, but for other cases where I could use web workers and not lose IE8 support.
This is a good approach for the times you can't use web workers. It's not just old browsers either. You can't draw to the canvas with a web worker.
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.
That may be what the API requires, but is it actually implemented as a physical move/copy of memory? It sounds like they can just make the array _appear_ to be cleared, while keeping it in place in memory.
You need to add a test at the start of your quicksort function - when the number of elements for this invocation is < 500, invoke native sort on the current subset.
Eek... "[setImmediate] is not expected to become standard, and is only implemented by recent builds of Internet Explorer and Node.js 0.10+. It meets resistance both from Gecko (Firefox) and Webkit (Google/Apple)."
Wah! I just skimmed through the Gecko bug that is linked from the above link. I recommend reading reading it through if you are interested in using these techniques on multiple browsers.
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).
To be honest, I don't really understand what "unclamped" means in this context.
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.
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).
Is computation becoming a special case of being blocked (on I/O)?
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.
In the browser, Javascript (outside of webworkers) is single-threaded, and while running it blocks the browser run-loop (for the given webpage.) This means the page can't accept or respond to any incoming events. It's "blocked" from interaction.
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).
Just to get a little more specific with this: the shift is in the accepted "main engine of computation" (to make up a mediocre term). We used to have something of an engineer's viewpoint, that the physical location of the electrical operation of the mathematics (i.e., the CPU) was this main engine. It's been a long road, but the new viewpoint is a bit more philosophical: the main engine is the human-computer nexus.
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.
Javascript is a special problem child there because a large part of it's raison d'être is DOM manipulation and yet that's the thing that cannot be parallelized, even with web workers because the DOM has not been designed with any kind of parallelism in mind.
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).
This confused me quite a bit as well. "Wait, what? There's such a thing as a blocking quicksort? Maybe with mutexes or something, but this is JavaScript..."
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.
"Is computation becoming a special case of being blocked (on I/O)?"
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.
> There’s just one problem – now we’ve made the function asynchronous, how do we know when it has finished?
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);
}
This is why concurrent datatypes are often interested in simple registers that you can only increment/decrement, they are still super-helpful for coordinating when a workload is complete.
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.
42 comments
[ 3.0 ms ] story [ 90.3 ms ] threadHowever 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.
"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).
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.
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.
http://stestagg.github.io/sort/
The most obvious thing is just to call out to a (semi-) global:
This is why concurrent datatypes are often interested in simple registers that you can only increment/decrement, they are still super-helpful for coordinating when a workload is complete.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.