Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing a Non-Blocking JavaScript Quicksort

breck-mckye.com

Post reply on HN
Print view View original

11–20 of 43 posts

Re: Writing a Non-Blocking JavaScript Quicksort

#11

Post by lancefisher »

tantalor wrote: post #2

The 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.

Re: Writing a Non-Blocking JavaScript Quicksort

#12

Post by chejazi »

chejazi wrote: post #9

The main takeaway for me was lesson #4: "setTimeout and browser timing are deceptive and shouldn’t be wholly trusted"... and as a result, use the setImmediate API.

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)."

https://developer.mozilla.org/en-US/docs/Web/API/Window/setI...

Re: Writing a Non-Blocking JavaScript Quicksort

#13

Post by scotty79 »

Wouldn't it be faster to run built-in sort on each 1/8 of array, than each 1/4, 1/2 and the whole array in the end?

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.

Re: Writing a Non-Blocking JavaScript Quicksort

#14

Post by mikekchar »

chejazi wrote: post #12
chejazi wrote: post #9

The main takeaway for me was lesson #4: "setTimeout and browser timing are deceptive and shouldn’t be wholly trusted"... and as a result, use the setImmediate API.

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)." https://developer.mozilla.org/en-US/docs/Web/API/Window/setI...

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).

Re: Writing a Non-Blocking JavaScript Quicksort

#15

Post by thomasfoster96 »

exogen wrote: post #7
Kiro wrote: post #6

Earlier quoted context omitted.

setImmediate is not supported in IE8 either.

The polyfill implements setImmediate using postMessage in IE8, though. AFAIK it's not really possible to polyfill WebWorkers.

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.

Re: Writing a Non-Blocking JavaScript Quicksort

#16

Post by amelius »

tantalor wrote: post #2

The 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.

Re: Writing a Non-Blocking JavaScript Quicksort

#18

Post by AgentME »

thomasfoster96 wrote: post #15
exogen wrote: post #7

Earlier quoted context omitted.

The polyfill implements setImmediate using postMessage in IE8, though. AFAIK it's not really possible to polyfill WebWorkers.

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…

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.

Re: Writing a Non-Blocking JavaScript Quicksort

#20

Post by gpvos »

girvo wrote: post #10
KayEss wrote: post #5

The 'long tail' really oughtn't be that long if they switched to the native sort when a partition becomes small enough.

> switched to the native sort when a partition becomes small enough 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.

I understood that they chose between the two versions at the top level, not at lower levels.
Post reply on HN