Writing a Non-Blocking JavaScript Quicksort • Hacker News Board

Re: Writing a Non-Blocking JavaScript Quicksort

#41

Post by mikekchar » Wed, Jun 10, 2015, 4:18 PM UTC

gpvos wrote: post #27

mikekchar wrote: post #14

Earlier quoted context omitted.

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 bro…

One of the comments in the Gecko bug links to a post by Chromium developer James Robinson, which explains a lot of the technical details quite clearly: https://groups.google.com/a/chromium.org/d/msg/blink-dev/Hn3...

Thanks for this. The rest of the thread is also very illuminating. I finally understand what they are opposed to. It makes sense.

Re: Writing a Non-Blocking JavaScript Quicksort

#42

Post by drostie » Wed, Jun 10, 2015, 4:20 PM UTC

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.

That's going to be tricky to do with quicksort... you could definitely do it with mergesort, though, but you'd have to abandon the in-place guarantee.

The basic problem is that Array.prototype.sort() does not accept indexes for a slice of the array to sort between.

Re: Writing a Non-Blocking JavaScript Quicksort

#43

Post by KayEss » Thu, Jun 11, 2015, 3:06 AM UTC

drostie wrote: post #42

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.

That's going to be tricky to do with quicksort... you could definitely do it with mergesort, though, but you'd have to abandon the in-place guarantee. The basic problem is that Array.prototype.sort() does not accept indexes for a slice of the array to sort between.

It's simple enough if you split the list at the partition point, but hard if you do it in place.