On Apr 12, 2013, at 6:35 PM, Maciej Stachowiak <m...@apple.com> wrote:
>
> On Apr 12, 2013, at 2:13 PM, Filip Pizlo <fpi...@apple.com> wrote:
>
>>
>> On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa <rn...@webkit.org> wrote:
>>
>>> On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo <fpi...@apple.com> wrote:
>>>
>>> On Apr 12, 2013, at 1:39 PM, Jarred Nicholls <jarred.nicho...@gmail.com>
>>> wrote:
>>>
>>>> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo <fpi...@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
_______________________________________________
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev
