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

http://afshinm.github.io/50k/

by afshinmeh • 11 years ago

47 40 11 years ago

afshinm.github.io

ColinWright3• 11 years ago

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.

afshinmeh6• 11 years ago

Thank you. I just updated the title.

ColinWright3• 11 years ago

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.

MrBuddyCasino• 11 years ago

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?

millstone• 11 years ago

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?

afshinmeh6• 11 years ago

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.

rrss11222• 11 years ago

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

Drakim2• 11 years ago

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

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

afshinmeh6• 11 years ago

I didn't know this, awesome.

amelius• 11 years ago

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 (?)

angersock• 11 years ago

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

rrss11222• 11 years ago

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.

CyberDildonics• 11 years ago

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

bgirard• 11 years ago

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.

meerita• 11 years ago

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

theCricketer• 11 years ago

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

afshinmeh6• 11 years ago

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.

onion2k2• 11 years ago

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.

afshinmeh6• 11 years ago

Nice explanation.

eueueu5• 11 years ago

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.

Ravengenocide• 11 years ago

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.

martin-adams• 11 years ago

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!

jtchang• 11 years ago

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.

TheLoneWolfling• 11 years ago

...with bubble sort.

Might want to mention that in the title.

moonbug• 11 years ago

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

tantalor• 11 years ago

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.

jlarocco• 11 years ago

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?"

qw• 11 years ago

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

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

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

Related Stories