[webkit-dev] Parallel JavaScript: Why a separate ParallelArray types

Fri Apr 12 22:26:04 PDT 2013

On Apr 12, 2013, at 6:35 PM, Maciej Stachowiak <mjs at apple.com> wrote:

> 
> On Apr 12, 2013, at 2:13 PM, Filip Pizlo <fpizlo at apple.com> wrote:
> 
>> 
>> On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa <rniwa at webkit.org> wrote:
>> 
>>> On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo <fpizlo at apple.com> wrote:
>>> 
>>> On Apr 12, 2013, at 1:39 PM, Jarred Nicholls <jarred.nicholls at gmail.com> wrote:
>>> 
>>>> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo <fpizlo at apple.com> wrote:
>>>> 
>>>> For as little worth as it is, I agree with you Filip that providing low-level primitives would be best in terms of a foundation for many parallel programming models.  In terms of actually supporting shared mutable memory and locks, it would be a challenge for the engines to become thread-safe (internally) across contexts that share memory cells.  I'd envision the sharing of mutable memory being an opt-in semantic, marking a piece of memory as being shared/mutable from multiple contexts.
>>> 
>>> Fixing the engines is a matter of typing. ;-)
>>> 
>>> I don't think we need to add language features for opt-in, though this is an intriguing idea.
>>> 
>>> Without opt-in, the one biggish challenge would be DOM accesses from threads other than the main thread; I suspect for those the initial implementation would have to throw an exception from non-main-threads if you try to access a DOM node.  This is akin to what some UI toolkits do: they let you have threads but prohibit access UI things from anything but the thread on which the runloop sits.  Of course, they don't do the thread-check; we would have to do it to preserve integrity and security.
>>> 
>>> We already have Web workers for this kind of stuff, no?  Is your proposal significantly different from what Web worker offers?
>> 
>> Web workers don't have shared memory.  They instead have a really expensive message passing model.
>> 
>> Yes, my proposal is significantly different from Web workers.
> 
> A message passing model a la Web Workers has some advantages compared to threads with shared mutable state and locks:

You have all of the same problems as with threads and locks.  The two are logically equivalent.  You can imagine a lock as being a message queue that always has a token in it when the lock is unlocked, and the token is read out to "lock" the lock.  You can imagine a shared memory location as being a task that controls that location, and you send messages to it to read and write the location.

> - No possibility of deadlock

There is a possibility of deadlock.  You can have one task waiting for a message from another, and that other waiting for a message from the first.

But I think that deadlocks are a red herring.  For a locked program to experience deadlock, you need an inversion of lock nesting.  But not only can this be detected dynamically - you can throw an exception as soon as it happens - it also seems to happen infrequently.  I've seen people scare each other over them at programming language conferences, but I think that deadlocks are sufficiently rare in practice that it's not worth worrying too much about.

I do think that deadlock is more common in the message passing world, though - it's easy to think that you're at a point in the code where a message ought to be available to you, not realizing that nobody would have sent the message because they're still waiting on you to do something else.  More interestingly, in the message passing world a deadlock is almost impossible to detect by the runtime: you know what queues people are reading from, but you don't know who was supposed to have written into those queues, and when.  The lock abstraction is strictly more sensible to reason about: you know who holds the lock and who wants to acquire it, and so the runtime can always observe the whole program's "dependence graph" and thus you can rapidly detect when things have gone wrong.

So I think that not is message passing just as prone to deadlock as locks, I suspect that locks actually make it less likely and easier to deal with when it does occur.

In threaded programs, I think that races are more dangerous, which brings me to:

> - No possibility of corrupting data structures due to races

There is a possibility of corrupted data structures.  Just as with thread+lock programs where you might have so many data structures and so many locks that you forget which lock to hold where, you can end up with so many tasks and so many message queues that you forget which one has which semantics.  I recall seeing a presentation by a formal methods fellow at Utah about a tool for debugging large MPI programs.  Aside from the ugliness of MPI, what was striking to me was just how subtle the message passing bugs become when you have even a modest amount of concurrency and even a slightly interesting parallel program - deadlocks were a particularly common bug that people got - more so than what I've seen in lock-based code - but also you'd have mismatched send/receive pairs where someone thought they were receiving a particular message but actually got a different one.  There is no silver bullet here - you can decompose your program into more discrete message queues but then the same bug manifests as a deadlock, or you can combine message queues together but then get into a corrupt state where you received the wrong thing.  This is akin to adding more locks to protect races: if you add too many you might deadlock (or run slower), but if you add too few you might race.

Interestingly, a data race in JavaScript would be much less harmful than one in C++ or even Java.  In C++ a data race quickly leads to unbounded heap corruption.  Clearly not cool.  In Java it typically manifests as an exception - null pointer most commonly, sometimes array out-of-bounds or others.  It never results in unbounded heap corruption.  But JavaScript is that language that wants to just keep going.  Not only are we protected from unbounded heap corruption like in Java, but the failure-oblivious nature of the language implies that even if your JS code is sloppy with threads, you can defend yourself from the worst of it by simply ignoring the inevitable 'undefined' values you'll get.  I wouldn't recommend that as an architecture strategy, but I think that this is kind of neat.  Moreover, this obliviousness to errors, and the fact that they do occur, is not something that threads bring to the table: JS code already deals with it.  I don't think that the JS code in the wild is semantically and formally perfect; it's not intended to be.  I don't think a few races will derail it.

But on a more serious note, I prefer to give web developers some credit: they do really cool things with this imperfect language already, and they have already come up with super sophisticated continuation-passing styles to work around the lack of concurrency.  I think if you're smart enough to write a UI using continuation passing style, then you're probably smart enough to know how to grab some locks here and there.

To the extent that the message passing community doesn't talk about races, or claims that they don't have them, I think it's a combination of clever semantics (the mismatched send-receive pair is claimed by them to be a different problem entirely) and the fact that hardly anybody uses message passing.  We're all aware of the alleged horrors of locking precisely because so many people use it.  It's like the way we always hear of the alleged horrors of C++ and never of the alleged horrors of Haskell.  It's because nobody uses Haskell.

> - No performance penalty from correctly supporting fine-grained concurrent access to arbitrary mutable objects

There is a huge performance penalty.  Message queues involve the same underlying synchronization primitives as locks.  To my knowledge, locks tend to be better tuned, and the literature on how to make them fast is more extensive.  In fact the only really well thought-through high-throughput fine-grained message passing system I've seen was in one of the latest MPI libraries, and the literature on it was thin.  It seemed like a bunch of black magic and they didn't test it on a lot of benchmarks - mostly because they didn't have a lot of benchmarks since nobody uses message passing, lol.  Locks, on the other hand, have numerous well-known super-cheap implementations - you can build a high-throughput, low-latency lock with a fast path that doesn't even require atomic instructions, that scales to arbitrary contention, in about 1000 lines of code, and there are plenty of papers that tell you how to do it (Pizlo et al PPPJ'11 is my favorite one, of course; that one cites a bunch of the other work).

Message queues also have the same risk of "stall" as threads: you can have someone waiting for a message that hasn't been sent yet, just as you can have someone attempting to acquire a lock that is still held.

> 
> The first is particularly important as you really do not want the web page's UI thread to lock up, even if the page itself is not making progress.

But message passing also leads to lock-up.  You could have someone waiting for a message that hasn't been sent yet.

Of course you could try to side-step this by mandating that there is no synchronous message receive operation on the main thread, and instead all messages arrive back asynchronously.  But there is no reason why you couldn't do that with locks: you could have an async lock operation:

lock.acquireAsynchronously(function() { … do things once lock is available … });

But I'm not sure that this would even be necessary.  If the web page's UI gets stuck because of an error made by the programmer, then that's not necessarily the programming language designer's problem to solve.  I don't believe that a deadlock is any more likely than a long-running computation or a run-away memory leak.  In fact in my experience it is less likely, particularly if you provide people with a sensible API for good locking discipline like:

lock.acquire(function() { … do things … });

And specifically disallow manual lock acquire/release except using this block-scoped idiom.  The only way to deadlock in that world is to have inverted lock nesting, which can be detected by the runtime, and you can throw an exception in all offending threads.

Also, you could do a libdispatch style, where there is no "lock" per se but instead you just have queues that you put tasks on.  I like that, too.  It's also formally equivalent to both locks and message queues, but much more similar to threads and locks in practice.

> 
> I believe message passing as a concurrent programming model is much less prone to severe errors than shared mutable state + locking.

I don't think there is evidence to support this claim.  In fact there is evidence to support the opposite: hardly anybody uses languages that only have message passing (Erlang was I think the only "popular" one ever, for a very loose definition of "popular"), but languages that have shared mutable state are used widely (C++, Java, and many others).

> I think you have to be super smart to even have a chance of using shared mutable state correctly.

It's true that concurrency is hard.  My point is that there is no silver bullet.  You can shoot yourself just as badly with message passing as with shared mutable state.

> That being said, I am not sure Web Workers as they exist today are the best possible form of message passing.

Yup!

Anyways, I would support a well-implemented message passing model over either Web Workers or these ParallelArrays, any day.  But I think that threads are the prevailing technique that people use today.  While they are really scary in languages that lack memory safety, they end up being quite benign in memory-safe languages like Java.  I see no reason to fear them in JavaScript, which is just as memory-safe as Java.

-Filip

> 
> Regards,
> Maciej

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20130412/36239255/attachment.html>