In Node.JS, is there any way to make Array.prototype.sort () for other processes?

Question

FYI: I already do this with web workers, and it works great, but I just studied what might and cannot be done with process.nextTick.

So, I have an array of a million elements, which I sort in Node.JS. I want Node to respond to other requests while he does this.

Is there a way to make Array.prototype.sort () not block other processes? Since this is the main function, I cannot insert any process.nextTick ().

I could do quicksort manually, but I don’t see how you do it efficiently, in the continuation-pass style that seems to be required for process.nextTick (). I can change the for loop to do this, but sort () seems impossible.

Answer 1

While it is not possible to make Array.prototype.sort somehow itself asynchronously, asynchronous sorting is certainly possible, as this sorting demo shows, demonstrate the advantage of speed setImmediate (padding) over setTimeout.

Unfortunately, the source code does not seem to come with any license. The Github repo for a demonstration at https://github.com/jphpsf/setImmediate-shim-demo calls Jason Weber the author. You can ask him if you want to use (parts) of the code.

I think that if you use setImmediate (available with Node 0.10), the individual sort operations will effectively alternate with the I / O callbacks. For such a large amount of work, I would not recommend process.nextTick (if it works at all, because there is a limit of 1000 maxTickDepth). See setImmediate vs. nextTick for some backgroud.

Using setImmediate instead of simple “synchronous” processing will certainly be slower overall, so you can choose to process individual sort operations on a “tick” to speed up the process, due to Node not responding during that time. I think that the right balance between speed and responsiveness with I / O can only be found with experimentation.

A simpler alternative would be to do this more as web workers: create a child process and do the sorting there. The biggest problem you are facing is moving the sorted data back into your main process (to generate some kind of output, presumably). AFAIK there is nothing like portable objects for Node.js. After buffering the sorted array, you can pass the results to the stdout child process and analyze the data in the main process, or perhaps simpler; use child processes .

You may not have a free processor core, so the child process will invade another processor time. To avoid the sorting process from damaging other processes, you may need to give it a low priority. This seems to be impossible to do with Node, but you can try using nice as described here: https://groups.google.com/forum/#!topic/nodejs/9O-2gLJzmcQ . I have no experience in this matter.

Answer 2

Well, initially I thought you could use async.sortBy , but upon closer inspection it seems that it will not behave the way you need. See Array.sort and Node.js for a similar question, although there is currently no accepted answer.

Answer 3

I know this is a pretty old question, but I came across a similar situation where there was still no easy solution that I could find.

I modified the existing quicksort and published a package that periodically terminates the EventLop: https://www.npmjs.com/package/qsort-async

If you are familiar with traditional quicksort, my only modification was the original function that performs the splitting. Basically, the function still modifies the array in place, but now returns a promise. It stops execution for other things in Eventloop if it tries to process too many elements in one iteration. (I believe that the default size that I specified was 10,000).

Note: it is important to use setImmedate here, not process.nextTick or setTimeout here. nextTick will actually put your execution in front of the IO of the process, and you will still have problems responding to other requests related to IO. setTimeout is too slow (I assume one of the other answers is related to the demo).

Note 2: If something like merge sort is more suitable for your style, you can do the same logic in this type of 'merge' function.

 const immediate = require('util').promisify(setImmediate); async function quickSort(items, compare, left, right, size) { let index; if (items.length > 1) { index = partition(items, compare, left, right); if (Math.abs(left - right) > size) { await immediate(); } if (left < index - 1) { await quickSort(items, compare, left, index - 1, size); } if (index < right) { await quickSort(items, compare, index, right, size); } } return items; } 

Full code here: https://github.com/Mudrekh/qsort-async/blob/master/lib/quicksort.js