3 ms·
> I must be silly but I expected the web worker version to run faster. I must have understood "many threads". They are only using a single worker thread, not m
by dspillett 10y ago
> I must be silly but I expected the web worker version to run faster. I must have understood "many threads".
They are only using a single worker thread, not multiple, so it will take pretty much the same time for the actual as the same engine is interpreting and/or JIT-compiling the code.The extra time you see is that needed to bring up the worker, manage synchronisation, tear it down when complete, and any other such overheads.
A quick look at the source says bubble sort is being used which on its own is not as obviously paralisable as, for example, Shell's sort, but multiple threads could be used here generally.
But most parallel sort algorithms assume efficient shared memory so the thread can all access the data immediately without having their own copy, or other fast IPC methods, which is not possible with webworkers which can only communicate via message passing currently which is unlikely to be efficient enough for large scale sorting in many (most?) cases. There are experimental shared memory options in some JS engines, https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/SharedArrayBuffer https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... for example) so this may change in the not too distant future.
In this case choosing a better single threaded sort would far outperform this done over multiple threads - they presumably picked a slow algorithm to properly illustrate their point.
Edit: Additionally, as well as building the worker you need to pass it the initial data to work on (or new data if reusing a worker in a more advanced algorithm) which will consume time. In this simple example the data to be sorted is created in the worker rather than being passed in (and back out sorted), so you'd need to factor that in too. Though transferables would help here if what you are doing naturally works with the object types that support that.
- chadscira 10y agoIf you wanted to go crazy you can use transferables to get around the memory copy cost. It would be a fun experiment to figure out at what point does it make sense to use multiple workers considering the initial cost of worker distribution.
- dspillett 10y agoHaving had a quick read (I'd somehow missed nontransferables and thought less efficient message passing was the only way, thanks for the pointer) that could help but because the objects are moved to the new context and lost in the original you do need to create and populate fresh ones for each worker (so extra copy operations that wouldn't be needed if true shared memory were possible). Still, that might work well for some algorithms over certain data types. For example a divide and conquer based sort like merge or quick might benefit as you can send the first few partitions to different workers and let the first worker to the final merging. It wouldn't work for Shell's sort though as splitting the data into transferable chunks for that algorithm is not going to be efficient as it touches from the beginning of the array to the end in each iteration. And you'd need to be analyse if the gaining time splitting the actual sort between threads is enough to not be negated (or worse, dwarfed) by the time needed for all the extra data copying. Outside sorting, number crunching tasks where the operations have a high locality of reference and so are easily partitioned would work well without hitting too much sharing trouble. Fractals for instance: computing one pixel of a Mandelbrot display does not rely on knowing anything about the neighbouring ones (or any others) so partitioning the work is going to be trivial. Compression too, if you don't mind losing a small amount of compression efficiency (due to dictionary resets at the partition boundaries) in exchange for the bump in potential parallelism.