Demonstrating Web Worker: Sorting a 50K array in your browser | Hacker News Reader

Demonstrating Web Worker: Sorting a 50K array in your browser

afshinm.github.io

47 pointsafshinmeh40 comments

I don't know much about web workers. According to my understanding, they can only communicate by message passing. This means that, if I have a 50K array and wish to sort it via a web worker, I must copy it twice: once incoming and again outgoing. This copying is likely to be as expensive as sorting it (well, maybe not if you use bubble sort). How do you mitigate this?

Fortunately, Transferable Objects (which didn't arrive until a bit after Web Workers) solves this :)

http://updates.html5rocks.com/2011/12/Transferable-Objects-L...

Looks like the OP's linked example does not use this, since the sort reported that it took longer when using web workers than when it didn't use web workers, at least a full second longer.

I wonder how much performance would improve if the example did use Transferable Objects.

Note that IE can have some issues with transferable objects.

Also note that the messages cannot encapsulate, say, closures or anything else that you can't JSON.stringify()/JSON.parse().

If one wants to share data with two different web-workers (doing different computations on the same immutable data), there is still a problem. Or so I suppose (?)

Yeah, you'd have to clone the data.

I didn't know this, awesome.

You vastly overestimate the cost of copying 50k elements. On low end mobile you'll get at least 1GB/sec and on desktop you can get easily 10GB/sec. Now sorting at these speeds is a whole other story.

The real thing to consider is if the latency of the round trip messaging is less than just doing the work in place. With something like web workers you're going to have to hit the event loops when messaging back and forth which aren't always empty.

Well, its just a demonstration to show that a huge cpu-bound task can be done inside the web browser. To be honest, I'm not sure if it worth to use it in production.

I would say not having that UI lag while doing a huge cpu-bound task would be worth it in production.

It is still a huge win since copying is both O(N) and cache coherent, while sorting is of course O(N log(N))

Deeply misleading title. It's basically pointing out that if you use "Web Worker" then you can do stuff in the browser in background. It's really nothing to do with sorting the array - it's just using that as a task for the background work.

Yeah, its even a bit slower since it doesn't appear to be using multiple workers.

Slightly OT, but I found that you can detect the number of available cores with "navigator.hardwareConcurrency", but unfortunately that includes HT threads, at least in Chrome on OSX, so it says 8 instead of 4 on my machine. Is there a workaround?

Thank you. I just updated the title.

You need to update the title on this submission as well:

  Demonstrating Web Worker: Background
      sorting a 50K array in your browser

Or something similar.

Cool, Updated.

I strongly recommend you update your web page title to say the same thing, otherwise the mods here may adjust this title to match that one.

Web workers would have been a must have for a project I worked in a few years ago. I had to write a real-time video allocation algorithm that had dynamic hardware with extreme combination constraints, and varying encoding rules for audio and video (think HD, SD, Dolby, stereo). It also had to allow for changes without moving existing allocations (otherwise viewers TV programmes would glitch).

The back-end was an embedded device that only accepted XML and could not do the calculation.

I had to have this do the allocation in IE8! So I wrote a timer based allocation routine that would release the UI thread enough to not lock up the browser. It worked (sort of), but was ugly and took way too long!

I think it should be more clear that it's using bubble sort to purposely take a longer time than necessary.

I'd expect sorting an array of 50k elements to be instantaneous on a modern machine, even in Javascript.

My first thought was, "WTF? Sorting 50k elements is a big deal?"

It seems that there are significant differences in browsers as well.

  Windows 8
  --------------------
  Firefox v38 | 2629ms
  Chrome v40  | 4281ms 
  IE v11      | 7899ms

I found this thread from about 3 years ago interesting:

https://news.ycombinator.com/item?id=2566365

Basically if web workers could access the GPU as well via WebGL.

...with bubble sort.

Might want to mention that in the title.

I did all the tests faster without webworkers than with them.

They're not faster. They take roughly the same amount of time, but with an extra bit of overhead for instantiating the worker and an event to say it's finished, so they're actually slower. But.. they don't block the browser doing things so the page still responses to input while they're working. If you need to do something that's doing to take 8s (e.g. this demo on my Mac Air), having the user still able to interact with the page while a progress bar updates is a huge advantage.

Nice explanation.

It's trivial to periodically pass control back to the UI with setTimeout or setInterval.

So doing something that takes 8s doesn't have to block the UI at all. The "without webworkers" version should be renamed to "Naively programmed version" or something.

It gets ugly fast. Most tasks are not a simple sort. There's a reason that cooperative multitasking is not widely used in operating systems anymore.

Javascript is not an operating system.

There aren't many operations in javascript which will block. The only real issue is that your javascript code executes in the same thread as UI. Which just means you need to think a bit harder about keeping it responsive.

"Start threads!" in programming is usually a lazy hack.

Lazy hack, or using OS/browser/whatever features instead of reinventing them poorly?

What's the benefit you get from programming like that?

Because once you introduce threads, your program complexity increases massively. You're now throwing a few groups of instructions at the CPU and saying "Hay! Execute these instructions in any order you like". Then you're adding code to deal with the issues of that random execution entails.

Also, it's not faster, so what's the actual point?

The browser should use all CPU cores efficiently to make javascript fast. Exposing WebWorkers to javascript programmers IMHO is totally the wrong way to do that.

In the case of something as simple as a bubble sort, you probably could code something to periodically hand control back to the browser to pick up input events, but I imagine that would slow it down considerably as you'd need to check every few milliseconds otherwise the user will see some lag. Also, in something more complex inserting breaks would be a lot harder. Why bother when web workers are a good, working solution?

I'd bet using setTimeout with a 0ms delay every loop wouldn't slow the example down significantly, and would have the desired effect of making the UI responsive.

You might be surprised. There are conditions under which browsers will impose a 4ms minimum delay when you ask for less. I believe it's when you set a timeout within a timeout.

Edit: close. https://html.spec.whatwg.org/multipage/webappapis.html#timer...

"Timers can be nested; after five such nested timers, however, the interval is forced to be at least four milliseconds."

Does that work?

Yes it does. I'm not convinced multithreading is something that should be encouraged within javascript personally.

I think the purpose was just to show that you can perform the computation without stalling the rendering thread, not that it is faster.

Exactly. It's not necessarily faster. The point is, I wanted to show that a cpu-bound task like sorting can be done in web browser without experiencing interrupts or hiccups.

> Your browser sorted 50K Array without any crash or lagging, because your browser supports Web Worker. When you do a job with Web Worker, it's just like when you run a program in another thread. Also you can see the animated progress bar while sorting. The text clearly explains that it's about not lagging or crashing, not about being faster.

Is co-operative multitasking really as far as it's got, after two decades of web progress? Sheesh.

Mozilla is working on SharedArrayBuffer (https://blog.mozilla.org/javascript/2015/02/26/the-path-to-p...) which brings something like pthreads to the browser.

Reply on news.ycombinator.com