I've actually got a bunch of sort algorithms written as async javascript:
Writing a Non-Blocking JavaScript Quicksort
31–40 of 43 posts
Re: Writing a Non-Blocking JavaScript Quicksort
#32[deleted]
Re: Writing a Non-Blocking JavaScript Quicksort
#33> 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);
}
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.
Re: Writing a Non-Blocking JavaScript Quicksort
#34Earlier quoted context omitted.
Not with transferable objects.
From [1]: > 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...
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.
Re: Writing a Non-Blocking JavaScript Quicksort
#35Is 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.
"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.
Re: Writing a Non-Blocking JavaScript Quicksort
#36Earlier quoted context omitted.
From [1]: > 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...
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.
The way I understand it is that they usually just move the pointer to the ArrayBuffer's underlying data store. No block copy occurs.
Re: Writing a Non-Blocking JavaScript Quicksort
#37The obvious solution is to use a Web Worker, 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); }); Prints, "[1, 2, 3]"
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.
It's massively unfortunate that a tradeoff like this has to be made (speed vs responsiveness).
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.
Re: Writing a Non-Blocking JavaScript Quicksort
#38Earlier quoted context omitted.
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.
Yes, I am aware of that. 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 "comp…
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.
Re: Writing a Non-Blocking JavaScript Quicksort
#39The obvious solution is to use a Web Worker, 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); }); Prints, "[1, 2, 3]"
It is not efficient to use a webworker when transferring the data into it and out of it takes O(N) time.
The new SharedArrayBuffer should solve that particular problem. Once videos are online, you should check out @naveedi's talk from JSConf 2 weeks ago.
Re: Writing a Non-Blocking JavaScript Quicksort
#40> 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 (th…
I was also curious about the lack of promises