Show HN: Sorting 50K Array, HTML5 Web Worker Demo

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

by afshinmeh • 10 years ago

88 59 10 years ago

afshinm.github.io

keyle• 10 years ago

I must be silly but I expected the web worker version to run faster. I must have understood "many threads". It ran nearly 200ms slower :)

That said, not locking the UI thread and showing user feedback is totally worth 200ms extra for most tasks.

Touche2• 10 years ago

There's serialization costs for going back and forth.

In some contexts launching multiple workers is possible if you can split up work, in which case it would be faster. Sorting a single array is not such a context though.

laxd• 10 years ago

Merge sort?

SigmundA2• 10 years ago

The demo doesn't seem to serialize anything, it doesn't transfer the array.

I would guess the extra time is just worker initialization including fetching/parsing worker.js.

cjdell• 10 years ago

You can bypass the serialisation cost by using the transferList for ArrayBuffer instances, which is used by typed arrays i.e. Int32Array, Float64Array etc.

i.e. self.postMessage(myTypedArray, [myTypedArray.buffer])

I used this approach to generated geometry within a web worker for a WebGL project. Only downside is the web worker that initialised the array will lose ownership of the buffer and will have to create a new one to pass more information.

https://developer.mozilla.org/en/docs/Web/API/Worker/postMes...

OskarS• 10 years ago

You can totally split sorting across different threads/cores, just divide the list up and do a final merge pass. Basically the idea behind external sorting, where the amount of data is not big enough to fit into main memory, so you have to sort chunk-by-chunk and then merge the chunks.

BatFastard• 10 years ago

3 more years and maybe HTML 5 will catch up to where Flash was 3 years ago! Here's to hoping!

jsingleton• 10 years ago

Not silly at all. It can't run faster, as there is a maximum speed your machine could do this. Doing it in the background can't change this but it is non-blocking. Many threads won't always help speed it up, but it does get it off of the UI thread. For example, the browser process may be single threaded or already using all the available cores it can.

Asynchronous behaviours, including synchronising with the UI aren't free and all add overhead. Of course the benefit is that the app stays responsive to user input.

Some problems can be performed in parallel, but even if they can then it may slow them down. Orchestration isn't free and unless you can use more cores it probably won't help. I wrote a simple demo of this in .NET Core [0] for a book [1] (where I've written more on these topics, from a C# perspective).

It may not be intuitive to web developers, as the server is naturally blocking and async has a different effect on HTTP request/responses. Yet if you've done any desktop/mobile app work then you'll know it's very important to not do anything intensive on the UI thread. It's a pretty common mistake to make.

[0] https://github.com/PacktPublishing/ASP.NET-Core-1.0-High-Per...

[1] https://unop.uk/book

sgift• 10 years ago

A quote from Brian Goetz which reminds us of the reasons not all code benefits from being run in parallel:

"A parallel execution always does more work than a sequential one, since — in addition to solving the problem — it also must decompose the problem, create and manage tasks to describe the subproblems, dispatch and wait for those tasks, and merge their results. So the parallel execution always starts out "behind" the sequential one and hopes to make up for the initial deficit through economy of scale."

https://www.ibm.com/developerworks/library/j-java-streams-4-...

But even then, your point stands that being able to work while the web worker version is running makes it better even if it is slower.

wigster• 10 years ago

for me the web worker IS consistently faster. Chrome 54. 3100ms vs 3400ms.

spdionis• 10 years ago

Same here. 7000ms vs 5500ms. Chrome 54.

dspillett2• 10 years 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/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.

chadscira7• 10 years ago

If 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.

caleblloyd2• 10 years ago

Cool demo! Web Workers are nice, and well supported by the evergreen browswers. Lots of apps do CPU intensive stuff on the server though and don't actually need them.

I am more interested in "Shared Web Workers", since it would allow for synchronization between tabs. It's got pretty poor support though, only Firefox, Chrome desktop, and Opera :(

nol13• 10 years ago

But why have a server do it when you can use the client!

(Use them to read in semi-large xlsx files and unzip and resize folders of images client side before uploading, really because processing them one by one on the client makes it simpler to show progress (feels like we're doing this wrong, but it works), but also saves resources for us.)

pkstn• 10 years ago

Check out localStorage: it's change event is shared instantaneously between tabs

caleblloyd2• 10 years ago

That's what I'll have to do. It just seems hacky when all I want to do is pass events and not persist the data. Plus I think localstorage is turned off in some private browsing modes, maybe Safari?

didip• 10 years ago

Is this demo supposed to highlight the strength of web worker? It runs 300-400ms slower on web worker.

spiderfarmer• 10 years ago

Yes. And it succeeds. The browser is responsive during the web worker method and is beachballing without.

sumnulu• 10 years ago

"As you can see, without Web Worker, your browser maybe able to sort the 50K Array but you can't work with your browser while sorting and also your browser won't render anything until sorting ends, that's why you can't see the animated progress bar in the page."

Jtsummers6• 10 years ago

Web workers offer several benefits:

1) UI isn't locked up by long running tasks;

2) Potential performance improvement by running multiple processes at once (parallelization);

3) Potential design improvements by decomposing the problem into a CSP-like design (which may or may not relate back to (2)).

(2) is really not the purpose though, it's just a potential benefit. golang, for instance, doesn't give us inherently better performance by use of goroutines. What it gives us is better design and separation of execution blocks so that they can run concurrently. Better performance is just a perk when things can run in parallel.

sz4kerto• 10 years ago

3.5 seconds on Chrome.

Native code does this around 10000% faster.

reitzensteinm• 10 years ago

Sorted with bubble sort. It's just an artificial load to facilitate the demo.

mattmanser2• 10 years ago

Web Workers are such a disaster of a terrible API. I can't believe actual programmers came up with that syntax.

Passing strings and filenames around, what were they thinking?

SigmundA2• 10 years ago

It basically like a process rather than a thread, and you can share buffers zero copy.

VeejayRampay• 10 years ago

This reads like the gratuitous/lazy critique of someone who didn't bother to read the actual API documentation for Web Workers. You can pass more complex data structures to Web Workers than mere strings. ArrayBuffers instances for example.

mattmanser2• 10 years ago

Oooooo, ArrayBuffers! Really?

I've actually used Web Workers and they're horrible to use. Just even a glance at the syntax will send any sane programmer into a pit of despair.

The 2nd comment at the moment is library to use Web Workers without having to use the default sucky API.

That says it all.

Why would I make a huge comment explaining the obviously bad the API is when even the laziest programmer can open the link and see how bad it is?

lai• 10 years ago

On Android Chrome the web worker took 18 seconds while the non web worker took 11 seconds but was utterly unresponsive. Having a responsive ui using the web worker with later results than a non responsive ui with faster results is a trade off I'll take any day.

mibbiting3• 10 years ago

You don't need web workers to be "responsive". You just need to cut the job up into bits, and yield to the UI thread every so often.

It's utterly unresponsive because it's not programmed very well. Not because it's not using web workers.

The demo is a great example of why Threads are inefficient for most cases. Better programming is what's needed.

Jtsummers6• 10 years ago

That requires decomposing problems in more unnatural ways and introducing greater overhead.

Using a trivial sort example, you're suggesting something like:

  sort (Array):
    i := 0;
    while(not-sorted):
      sort-step
      i := i + 1
      if i % 100 = 0:
        yield

This requires tuning, and all sorts of fun things. And a redesign of your algorithms.

With something like webworkers, you don't have to alter your algorithms in any fundamental way. They're left alone and the change is how they're plugged into each other. You allow the scheduler to handle yielding and other details.

tylercubell• 10 years ago

Show us, won't you?

fizzbatter• 10 years ago

For anyone familiar with the landscape:

Are webworkers likely to improve dramatically as time goes on? For example, the cost of using web workers appears[1] to be far greater than just spinning up another thread in, say, Go[2]. I assume this is mainly due to how the browser is sandboxing JS. So, is there room for improvement here? Or have most things js related been so drastically optimized that we are without much hope here?

[1]: Purely speculative on my part. [2]: Yes i know Go has green threads, it's purely an example. I was going to say Rust, but that seems like an unfair comparison.

fenomas2• 10 years ago

In my experience web workers aren't noticeably slower than regular JS (apart from the cost of copying any shared memory back and forth).

They're slower in this demo (for some people but not others), but microbenchmarks in JS are very hard to to do right, and I don't think the author here was trying to make an accurate ubenchmark.

nicolasd• 10 years ago

The difference on my machine is not even 50ms - good tradeoff for more responsiveness

tychuz• 10 years ago

300-400 ms on mine.

Ofcourse, not hanging the website beats 400 ms.

chadscira7• 10 years ago

For anyone that is interested in easily using WebWorkers for this sort of work please check out task.js (https://github.com/icodeforlove/task.js).

It allows you to send a pure function with provided arguments to a autoscaling WebWorker pool.

Heres a similar demo (http://s.codepen.io/icodeforlove/debug/ZOjBBB , you can bring all cores to 100% usage)

But for this specific scenario it could have been coded like this using task.js (vs http://afshinm.github.io/50k/worker.js which is not reusable)

    // mentioned sort function (close to exact code from site)
    function bubbleSort(a) {
        var swapped;
        
        do {
            swapped = false;
            for (var i=0; i < a.length-1; i++) {
                if (a[i] > a[i+1]) {
                    var temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                    swapped = true;
                }
            }
        } while (swapped);

        return a;
    }

    // turn the function into a worker task
    const bubbleSortAsync = task.wrap(bubbleSort);

    // this now runs in a autoscaling worker pool (first run includes worker initialization time)
    console.time('BubbleSort Worker');
    bubbleSortAsync([9,1,2,3]).then(sortedArray => {
        console.timeEnd('BubbleSort Worker');
    }, error => { /* this is extra credit, yes we can handle worker errors */ });

Also when dealing with large messages you can use transferables (https://developer.mozilla.org/en-US/docs/Web/API/Transferabl...).

The web has really came a long way, this kind of stuff is extremely useful, for instance you could use it when processing pixel data for a 10MP image with a RGBA array of 40M. In that scenario the work can be spread across all cores, and blows away the alternate approach of just locking the UI. In that case if you were using task.js you would just chunk the work, and use a async control flow library like bluebird.

   // in this situation all cores would be at 100% without locking the UI
   let processedPixels = await Promise.map(chunks, processPixelChunkAsync);

thinkMOAR3• 10 years ago

2.8 seconds without 3.3 seconds with webworker

Imho not acceptable trade-off, did not hear the term web workers yet, and now i'm not even upset i did not and probably will never....

chadscira7• 10 years ago

2.8 seconds is locking the browser

3.3 seconds is not locking browser

When dealing with web it is unacceptable to lock the browser. Also with core / worker distribution you may be able to make the worker approach faster :).

thinkMOAR3• 10 years ago

That's something we disagree on then, in my humble opinion, on the web it is unacceptable to make users wait longer then necessary. And it's not a small, 1 or 2 percent difference. And certainly not longer then 1 second.

And why is the example then not setup with core/worker distribution so it actually does as you write 'potentially' work faster?

Nice i can still use my browser while i wait longer for the stuff i _want_ to see. But what is the use? I want to see that data/page i click the link or button for, nothing else.

Or please elaborate why it is in _your opinion_ unacceptable to lock a browser but get the data on screen faster?

teaearlgraycold• 10 years ago

That's not how you should think about this.

It's 2.8 seconds of unresponsiveness vs. 0 seconds of unresponsiveness.

globuous• 10 years ago

Although the web worker version is slower, the fact that it doesn't block UI is a huge gain.

I tried to see if I could make the bubble sort function async as to not block the browser UI using callbacks as opposed to workers. Here's a (messy) fiddle for those that want to check it out: https://jsfiddle.net/tbinetruy/8q1de9jk/ (watch out, this fiddle runs the blocking bubble sort on a 50k array on page load, so it'll freeze your UI for 5 seconds. Then the non-blocking sort kicks in and your UI becomes usable again).

For a 50k array, the blocking code ran in 6.682s and the non-blocking code in 9.297s (when I ran it locally just now anyway). I added a clickable button and update the DOM every 25ms with a random number to show the user what the non blocking code allows for.

The same type of non blocking code without relying on web workers should also be possible with async functions and promises. I'll have to look into it.

methyl• 10 years ago

To me, it's not slower, performance almost exactly matches the blocking version. I'm on i7 Macbook Pro and Chrome.

chadscira7• 10 years ago

In response to your last comment, you should check out https://github.com/icodeforlove/task.js. It will do that and much more.

fenomas2• 10 years ago

I don't get why everyone is focused on the worker version being slower. Microbenchmarks in JS are hard to get right, and I don't think this demo attempts to make an accurate comparison. It's just showing what workers do and why they're useful.

I use workers heavily in a game I'm making, and in my experience they perform equivalently to regular JS, modulo any time you spend copying memory back and forth.

edit: It seems this demo dynamically creates the worker from scratch every time it's used, and destroys it afterwards. That's probably the cause of any performance difference people are seeing.

chadscira7• 10 years ago

Good catch.

From my experience though there is a small overhead in terms of workers, also the message cost. But still even if it was 300% slower it's justified because it is unacceptable to lock the browser.

Too many commenters here are coming from the backend, or desktop software where they already have a UI thread. I ask these commenters a simple question, when is the last time you saw your browser freeze? If that doesn't happen often then the devs are doing many things like this to keep that experience enjoyable. Web is it own kind of beast in terms of development, the biggest concern is perceived responsiveness. We get to write off async delays when using webworkers (and similar methods) because users are already used to network requests taking time.

martin-adams2• 10 years ago

Oh my, I was given the impossible task of writing a hardware resource allocation algorithm to produce encoding XML config from the UI in JavaScript. Think of a hardware device needing to efficiently transcode 80 SD or 12 HD (mix and match) video streams (plus audio - stereo/dolby) on varying encode cards (6 max), all from a drag and drop interface and without disrupting existing encoding allocations to prevent glitches while it reconfigures.

Long story short, this had to work in IE8 and not block the UI to get it done and no plugins. I wrote some crazy way of doing the work in chunks using a setTimeout to get it complete. The project was a success but I stated very firmly that this was a job for the device, not the UI in future versions. Hard when the device in question only had a 300MHz CPU.

Those were the days.

chadscira7• 10 years ago

Life before WebWorkers was fun :). Another way was to create multiple iframes, and use a form of hacky message passing to use more cores, but i think this may have depended on the browser implementation.

martin-adams2• 10 years ago

Haha, would never of thought to use iframes!

psadri• 10 years ago

Btw, webpack's worker-loaders make using web workers incredibly easy.

Show HN: Sorting 50K Array, HTML5 Web Worker Demo

Related Stories