Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
> From: webkit-dev-boun...@lists.webkit.org > [webkit-dev-boun...@lists.webkit.org] on behalf of Maciej Stachowiak > [m...@apple.com] > Sent: Monday, April 15, 2013 10:05 PM > To: Filip Pizlo > Cc: Benjamin Poulain; webkit-dev@lists.webkit.org; dpra...@chromium.org > Subject: Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray > types > > These languages are popular, but I believe most complex projects using them > with threading a long tail of nasty > but hard-to-diagnose threadsafety bugs. Indeed, my assumption was always that languages with special-purpose concurrency constructs were not popular for the same reason all special-purpose languages are not popular compared to C++: they're not C++. It's hard to get over the hump of competing with C++, and a new concurrency paradigm isn't enough to do it even if that paradigm is better than shared memory+mutexes. The lack of success isn't evidence that the concurrency construct is worthless, just that lacks whatever spark (which is often marketing and not technical superiority) that causes some languages to succeed and others to fail. Joe - This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful. ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 10:26 PM, Filip Pizlo wrote:
>
> 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.
The key difference in practice seems to be that message passing can be made
nonblocking and asynchronous, whereas locking typically is not.
>
>> - 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.
Yes, you can have pseudo-deadlocks like this, but unlike actually blocking on a
mutex in serial code on the main thread, this will not cause the web page as a
whole to outright hang. This is the only distinction I meant to draw. If my
webpage was blocked on a hypothetical JS mutex on the main thread, then I (as
the user) can't click on a link or select text or what have you. If it's
waiting for a message reply that never comes, then I almost certainly can.
>
> 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 had the (perhaps incorrect) impression that there was no reliable way to
avoid lock inversion other than globally ensuring that the program as a whole
always grabs locks in the same order. If there is a better solution, then fine.
But even a good solution would entail the potential of blocking the WebProcess
main thread for a long time, and message passing doesn't have that effect.
>
>
>> - 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.
There's no penalty to single-threaded code from message passing, though. With
shared state however: If every JS array had to safely handle concurrent access
from multiple threads (at the very least preventing memory corruption), that
would be a huge performance penalty for single-threaded code. Or if you only
turn on the checks when a second thread is created, then you have a performance
cliff, and the checks would likely still harm code that doesn't actually access
data structures concurrently.
Message passing (at least in the Workers style) is really only suitable for
course-grained concurrency, and indeed, it does impose a significant
communication overhead.
>>
>> 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.
I clarified above what I meant here.
>
> 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.
Indeed, there is no synchronous message receive on any thread in Web Workers.
> 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 …
> });
Can a lock-based model with only asynchronous locking be made efficient enough
for real use? (If you offer the synchronous version at all, then the worst
programmers will use it, once again leading to blocking). I would guess it ends
up only good enough for course-grained concurrency, at which point it does not
have much advantage compared to message passing.
>
> 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.
If a mistake of type X with consequence Y is possible in Model A but not in
Model B, that's an advantage for Model B. The Web has set higher expectations
of protecting the user from the consequences of badly written webpages.
> 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 … });
>
> An
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
> From: webkit-dev-boun...@lists.webkit.org > [webkit-dev-boun...@lists.webkit.org] on behalf of Filip Pizlo > [fpi...@apple.com] > Sent: Saturday, April 13, 2013 12:17 PM > To: Ian Hickson > Cc: dpra...@chromium.org; Benjamin Poulain; webkit-dev@lists.webkit.org > Subject: Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray > types > > Same difference. I think this is overly harsh. Nobody will hold a gun to your > head and force you to use threads. The bumbling fools will probably ignore it. Experience from desktop development tells me that bumbling fools absolutely love threads, and will probably start sticking things that are more appropriately done in other ways into threads as soon as threads are available. Ok, let's use the less-loaded term of "unprepared novice": the primary characteristic of this type of developer is that they have a task they want to complete, they Google to find a tool for the job, and then they hack something together with the first tool they find without taking time to study it and learn its intricacies, or evaluate alternatives. Often they follow sample programs without understanding what the samples are doing. Threads are complicated, and really should not be used without a thorough grounding in what can go wrong. Unfortunately there are lots of primers out there that give a very sketchy overview of how to use threads, and novice programmers are exactly the type to take a sketchy overview and think that's all they need to know to start coding. Other approaches are also complicated, yes - we should evaluate each approach to see how complicated each is and how much guidance the structure of the API gives in how to use it correctly, on the assumption that novice programmers WILL be trying to write complex things using nothing more than a random one page blog post about the API for documentation. We can't assume that just because the API is complicated, novices will not find out about it - novices love to play with the new shiny things as much as anybody. > The situation we have now is far worse actually: to get your scripts to do > useful thing you need to turn them inside-out using continuation passing > style. Much of it is because every interesting API is asynchronous. Are you > suggesting that continuation passing style with fully asynchronous APIa is > easier to understand than threads and synchronous APIs? I suspect that they > can both be classified as hard, and both lead to people making terrible > mistakes. I also suspect that threads are the easier of the two - at least > that is my thinking based on memories of how hard it was for a professor to > explain CPS to people. My experience is that threads and locks are roughly equivalent to goto: easy to explain how they work, but because they can be used in so many ways, harder to explain how to use them safely. While continuation passing, or message passing, or event driven styles are more like standard procedural flow control: more restrictive in how you structure your programs (which is the point!) but less conducive to creating spaghetti code. I definitely think that asynchronous API's are much easier to reason about than traditional threads & locks, once you grok how asynchronous API's work. With threads & locks, even an advanced user has to do a lot of work to prove their design correct every time use of a lock is altered. They're extremely fragile compared to higher-level abstractions. The higher-level abstractions MAY be as difficult to learn (although my anecdotal experience is the opposite) but more of the work is up front in setting up to use them in the first place. Joe - This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful. ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
Things are not that bad. (See Shadow DOM for instance where people begged for it to become a standard) You should definitely write something up and have a working prototype that demonstrates how your solution improves performance, cleaner implementations, etc. You will also have to prove that this won't introduce security issues. Any new feature will face a lot of scrutiny since it impacts everything that runs a web browser so be prepared for negative feedback. You will spend much more time replying on mailing list than actually implementing it. :-) Even if your proposal fails, it will still be used as a reference for a future solution. On Sat, Apr 13, 2013 at 12:35 PM, Dirk Pranke wrote: > > On Fri, Apr 12, 2013 at 10:44 PM, Filip Pizlo wrote: > >> >> On Apr 12, 2013, at 10:43 PM, Ryosuke Niwa wrote: >> >> Perhaps we can come up with some JS API for shared memory & lock and >> propose it in TC39 or WebApps WG? >> >> >> I think that would be wonderful. Anyone else interested? >> >> > Feel free to write something up, but as I said before, I suspect any such > proposal is DOA in either group. If you wanted to get something adopted > here, I think you would have to build something, ship it, and then have it > become so successful that the standards groups would be forced to > reconsider their positions. > > -- Dirk > > > ___ > webkit-dev mailing list > webkit-dev@lists.webkit.org > https://lists.webkit.org/mailman/listinfo/webkit-dev > > ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 13, 2013, at 12:35 PM, Dirk Pranke wrote: > > On Fri, Apr 12, 2013 at 10:44 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 10:43 PM, Ryosuke Niwa wrote: >> Perhaps we can come up with some JS API for shared memory & lock and propose >> it in TC39 or WebApps WG? > > I think that would be wonderful. Anyone else interested? > > > Feel free to write something up, but as I said before, I suspect any such > proposal is DOA in either group. Sad. > If you wanted to get something adopted here, I think you would have to build > something, ship it, and then have it become so successful that the standards > groups would be forced to reconsider their positions. Even sadder. -Filip > > -- Dirk > ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, Apr 12, 2013 at 10:44 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 10:43 PM, Ryosuke Niwa wrote: > > Perhaps we can come up with some JS API for shared memory & lock and > propose it in TC39 or WebApps WG? > > > I think that would be wonderful. Anyone else interested? > > Feel free to write something up, but as I said before, I suspect any such proposal is DOA in either group. If you wanted to get something adopted here, I think you would have to build something, ship it, and then have it become so successful that the standards groups would be forced to reconsider their positions. -- Dirk ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 13, 2013, at 10:01 AM, Ian Hickson wrote: > On Sat, 13 Apr 2013, Filip Pizlo wrote: >>> >>> It doesn't imply you can't have locks, it implies you can't have >>> unprotected shared state. >> >> Same difference. I think this is overly harsh. Nobody will hold a gun to >> your head and force you to use threads. The bumbling fools will probably >> ignore it. > > You vastly underestimate the scale of the problem. You vastly overestimate it. It's a subjective statement. I think this discussion would work better if we focused on the particulars of why, or why not, various approaches to concurrency, or lack thereof, work, or don't work. I don't think general statements about scales of problems and under or overestimations will get us anywhere. > > >> And even if the fool did use shared mutable state, the worst case >> outcome is a flaky webpage. It's not the end of the world. > > Users don't blame the page. They blame the browser. The browser that > implements the API that lets authors get data corruption and deadlocks > ends up being "broken" relative to the browsers where authors can't do > those things. Users then migrate to the other browsers. > > When it comes to the Web, this basically _is_ the end of the world. I think this is a big leap. Shared mutable state is not an "API that lets authors get data corruption and deadlocks". You already conceded that it does not lead to deadlocks any more than message passing. Any API lets authors get data corruption - this is just a natural outcome of there being no such thing as proven-correct software. > > >> I don't think that shared mutable state is that bad for bumbling fools, >> particularly when compared to the status quo. >> >> But on a higher level, I think that the bumbling fool argument ignores >> the level of sophistication that web developers are already capable of >> achieving. The stuff people build with web technology never ceases to >> amaze me. The web platform already has its warts, and people already >> find ways around them; they do so because on the whole, these are smart >> people. Giving them a useful too that is already available and >> well-understood in other languages can only be a good thing. >> >> I personally do not like thinking of the people who use the stuff I >> build as fools; I don't think it's constructive. > > I didn't say authors were all fools, any more than I said they're all > genius hostile attackers. > > However, that doesn't mean we can pretend that all Web authors are Jeff > Dean. There's a wide range of authors, from the nation-state-resourced > attacker literally trying to explode nuclear centrifuges or break into > e-mail accounts of political dissidents in order to kill them, to the > amateur programmers who make really elementary mistakes with a frightening > regularity yet manage to exercise all kinds of APIs in the Web platform. > > What you are suggesting is a change to the entire design philosophy of the > platform, a philosophy that has made it one of the, if not the single, > most successful platform(s) in the history of computing. This isn't > something to be done lightly. I appreciate the philosophy. But are you suggesting that the true virtue of the web is the fact that it doesn't support concurrency, and that adding concurrency would annihilate all of the hard work that people have done? Seems extreme. > > (As a general note, by the way, I would recommend making proposals for new > features in a vendor-neutral forum like one of the WHATWG or W3C lists, > rather than in webkit-dev.) I hear you loud and clear. This thread emerged somewhat organically from a tangentially related proposal to add ParallelArrays. I do have a preference for this to be discussed with a wider audience sooner rather than later, though I do appreciate the feedback on webkit-dev, and it's good to see such lively discussion coming even from non-WebKittens. -Filip > > -- > Ian Hickson U+1047E)\._.,--,'``.fL > http://ln.hixie.ch/ U+263A/, _.. \ _\ ;`._ ,. > Things that are impossible just take longer. `._.-(,_..'--(,_..'`-.;.' ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Sat, 13 Apr 2013, Filip Pizlo wrote: > > > > It doesn't imply you can't have locks, it implies you can't have > > unprotected shared state. > > Same difference. I think this is overly harsh. Nobody will hold a gun to > your head and force you to use threads. The bumbling fools will probably > ignore it. You vastly underestimate the scale of the problem. > And even if the fool did use shared mutable state, the worst case > outcome is a flaky webpage. It's not the end of the world. Users don't blame the page. They blame the browser. The browser that implements the API that lets authors get data corruption and deadlocks ends up being "broken" relative to the browsers where authors can't do those things. Users then migrate to the other browsers. When it comes to the Web, this basically _is_ the end of the world. > I don't think that shared mutable state is that bad for bumbling fools, > particularly when compared to the status quo. > > But on a higher level, I think that the bumbling fool argument ignores > the level of sophistication that web developers are already capable of > achieving. The stuff people build with web technology never ceases to > amaze me. The web platform already has its warts, and people already > find ways around them; they do so because on the whole, these are smart > people. Giving them a useful too that is already available and > well-understood in other languages can only be a good thing. > > I personally do not like thinking of the people who use the stuff I > build as fools; I don't think it's constructive. I didn't say authors were all fools, any more than I said they're all genius hostile attackers. However, that doesn't mean we can pretend that all Web authors are Jeff Dean. There's a wide range of authors, from the nation-state-resourced attacker literally trying to explode nuclear centrifuges or break into e-mail accounts of political dissidents in order to kill them, to the amateur programmers who make really elementary mistakes with a frightening regularity yet manage to exercise all kinds of APIs in the Web platform. What you are suggesting is a change to the entire design philosophy of the platform, a philosophy that has made it one of the, if not the single, most successful platform(s) in the history of computing. This isn't something to be done lightly. (As a general note, by the way, I would recommend making proposals for new features in a vendor-neutral forum like one of the WHATWG or W3C lists, rather than in webkit-dev.) -- Ian Hickson U+1047E)\._.,--,'``.fL http://ln.hixie.ch/ U+263A/, _.. \ _\ ;`._ ,. Things that are impossible just take longer. `._.-(,_..'--(,_..'`-.;.' ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 13, 2013, at 8:37 AM, Ian Hickson wrote: > On Sat, 13 Apr 2013, Filip Pizlo wrote: >>> >>> Actually, you can't. We very specifically designed workers (and even >>> more importantly the API on the main thread) so that you cannot block >>> on waiting for a message. >> >> You can also design lock APIs this way: > > Sure. Lots of APIs do it this way. > > >> Anyway, apologies for getting into semantics, but web workers don't >> eliminate "deadlock" - they just ensure that the main thread doesn't >> block if it happens. > > They do eliminate deadlock in the sense of two threads that cannot receive > any messages because they are blocked on each other. They don't eliminate > "soft" deadlock in the sense of an application that no longer progresses > because it's waiting for a message that'll never come, but that's no worse > than many kinds of logic errors where code stops progressing. > > >>> Certainly you can have a logic error that causes the application to >>> stop progressing, but you cannot have a deadlock that blocks the event >>> loop of the main thread. >> >> You can already block the main thread by having a runaway script, so >> this could be viewed as an overly harsh goal when picking concurrency >> models. > > Actually you can't have runaway scripts on the main thread on the Web. > Browsers will just abort the scripts after a brief timeout. It's even easier to abort a program that is waiting for a lock, than it is to abort a program that is stuck in a loop. Again, this is not a great argument against locks. > > >>> Web APIs have different constraints than non-Web platforms that may >>> help explain why the Web sometimes seems dumb from the perspective of >>> professional programers or computer scientists. Specifically, the Web >>> platform's design assumes the following: >>> >>> 1. Every Web author is potentially hostile and very clever, >> >> Threads do not make the Web author any more hostile, but I appreciate >> that this should be a serious goal. > > Right, this aspect is not especially relevant to Web workers. I included > it just for completeness because these two reasons really do underlie most > of the decisions that people coming from other platforms find weird. > > >>> 2. Every Web author is potentially a bumbling fool. >> >> I don't disagree with this, but I'm not sure that I'm convinced that the >> application of this ethos implies that we cannot have locks > > It doesn't imply you can't have locks, it implies you can't have > unprotected shared state. Same difference. I think this is overly harsh. Nobody will hold a gun to your head and force you to use threads. The bumbling fools will probably ignore it. The situation we have now is far worse actually: to get your scripts to do useful thing you need to turn them inside-out using continuation passing style. Much of it is because every interesting API is asynchronous. Are you suggesting that continuation passing style with fully asynchronous APIa is easier to understand than threads and synchronous APIs? I suspect that they can both be classified as hard, and both lead to people making terrible mistakes. I also suspect that threads are the easier of the two - at least that is my thinking based on memories of how hard it was for a professor to explain CPS to people. And even if the fool did use shared mutable state, the worst case outcome is a flaky webpage. It's not the end of the world. > > We _can_ have shared state that can only be accessed in a safe way. > IndexDB, for instance, allows shared state accessed from workers, because > you can only get to the state via a transaction-like deadlock-free API. > > >> Responsive UI is a good argument for having concurrency, and making it >> easier to use. > > So long as it doesn't sacrifice the two higher priorities of making the > API safe against attackers, and being simple enough to be used by bumbling > fools, sure. I don't think that shared mutable state is that bad for bumbling fools, particularly when compared to the status quo. But on a higher level, I think that the bumbling fool argument ignores the level of sophistication that web developers are already capable of achieving. The stuff people build with web technology never ceases to amaze me. The web platform already has its warts, and people already find ways around them; they do so because on the whole, these are smart people. Giving them a useful too that is already available and well-understood in other languages can only be a good thing. I personally do not like thinking of the people who use the stuff I build as fools; I don't think it's constructive. -Filip > > -- > Ian Hickson U+1047E)\._.,--,'``.fL > http://ln.hixie.ch/ U+263A/, _.. \ _\ ;`._ ,. > Things that are impossible just take longer. `._.-(,_..'--(,_..'`-.;.' ___
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Sat, 13 Apr 2013, Filip Pizlo wrote: > > > > Actually, you can't. We very specifically designed workers (and even > > more importantly the API on the main thread) so that you cannot block > > on waiting for a message. > > You can also design lock APIs this way: Sure. Lots of APIs do it this way. > Anyway, apologies for getting into semantics, but web workers don't > eliminate "deadlock" - they just ensure that the main thread doesn't > block if it happens. They do eliminate deadlock in the sense of two threads that cannot receive any messages because they are blocked on each other. They don't eliminate "soft" deadlock in the sense of an application that no longer progresses because it's waiting for a message that'll never come, but that's no worse than many kinds of logic errors where code stops progressing. > > Certainly you can have a logic error that causes the application to > > stop progressing, but you cannot have a deadlock that blocks the event > > loop of the main thread. > > You can already block the main thread by having a runaway script, so > this could be viewed as an overly harsh goal when picking concurrency > models. Actually you can't have runaway scripts on the main thread on the Web. Browsers will just abort the scripts after a brief timeout. > > Web APIs have different constraints than non-Web platforms that may > > help explain why the Web sometimes seems dumb from the perspective of > > professional programers or computer scientists. Specifically, the Web > > platform's design assumes the following: > > > > 1. Every Web author is potentially hostile and very clever, > > Threads do not make the Web author any more hostile, but I appreciate > that this should be a serious goal. Right, this aspect is not especially relevant to Web workers. I included it just for completeness because these two reasons really do underlie most of the decisions that people coming from other platforms find weird. > > 2. Every Web author is potentially a bumbling fool. > > I don't disagree with this, but I'm not sure that I'm convinced that the > application of this ethos implies that we cannot have locks It doesn't imply you can't have locks, it implies you can't have unprotected shared state. We _can_ have shared state that can only be accessed in a safe way. IndexDB, for instance, allows shared state accessed from workers, because you can only get to the state via a transaction-like deadlock-free API. > Responsive UI is a good argument for having concurrency, and making it > easier to use. So long as it doesn't sacrifice the two higher priorities of making the API safe against attackers, and being simple enough to be used by bumbling fools, sure. -- Ian Hickson U+1047E)\._.,--,'``.fL http://ln.hixie.ch/ U+263A/, _.. \ _\ ;`._ ,. Things that are impossible just take longer. `._.-(,_..'--(,_..'`-.;.' ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Sat, Apr 13, 2013 at 8:26 AM, Filip Pizlo wrote: > > 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 always thought libdispatch style concurrency would be a great fit for the web. It is slightly higher level and probably easier to use than locks and threads, without being particularly limiting. You also get thread management and platform event integration (timers etc) in the same package. The programming style (with blocks C extension) even looks like Javascript style. antti > -Filip > > > Regards, > Maciej > > > > ___ > webkit-dev mailing list > webkit-dev@lists.webkit.org > https://lists.webkit.org/mailman/listinfo/webkit-dev > > ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Sat, Apr 13, 2013 at 12:25 AM, Filip Pizlo wrote:
> You can also design lock APIs this way:
>
> lock.acquireAsynchronously(function() { … do things … });
>
> It's less attractive to me, but I think that this is similar to other
> programming models already out there.
>
Maybe a stupid question but: is there any other way to do a lock in this
case? (assuming you can never block the main event loop). I was only
considering models like the one above.
Benjamin
___
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, Apr 12, 2013 at 11:07 PM, Ryosuke Niwa wrote: > Do you think it's possible to come up with an API/semantics that would > allow us to seamlessly switch between single-threaded, SIMD/GPU > accelerated, and GPU accelerations? Or would be too cumbersome / too hard > to implement? > > It would be really neat if we could dynamically detect cases where we can > use lightweight alternatives such as OpenCL instead of creating a real > thread. > I think we can keep the GPU problems out of the equation to have a better focus. If only because their programming model is quite different. WebGL already offer GPU computation. Long before Cuda and OpenCL, engineers have just been abusing OpenGL shaders to perform general computation. (e.g. of publication from 2005: https://developer.nvidia.com/content/gpu-gems-2-chapter-31-mapping-computational-concepts-gpus ). WebGL definitely offers a less convenient model than OpenCL or Cuda, but it is not like OpenCL is a silver bullet. On the other hand, efficient concurrent programming is simply not possible with JavaScript. I think that is worth looking into. Benjamin ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 11:56 PM, Ian Hickson wrote:
> On Fri, 12 Apr 2013, Filip Pizlo wrote:
>>
>> 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.
>
> Actually, you can't. We very specifically designed workers (and even more
> importantly the API on the main thread) so that you cannot block on
> waiting for a message.
You can also design lock APIs this way:
lock.acquireAsynchronously(function() { … do things … });
It's less attractive to me, but I think that this is similar to other
programming models already out there.
Anyway, apologies for getting into semantics, but web workers don't eliminate
"deadlock" - they just ensure that the main thread doesn't block if it happens.
It's still possible for the web app itself to get into a deadlocked state even
if the UI thread is still receptive to events. There is a difference here.
Both locks and message queues can be designed around asynchrony. With
asynchrony, the "deadlock" of locks becomes no more dangerous than the
"deadlock" of your message handler never firing even though you expected it to.
This is what I meant by deadlock being a feature of both locks and
message-passing: both are equally predisposed to someone stalling, and in both
cases you can avert the stall in the programming model by using asynchrony
instead of blocking operations.
>
> Certainly you can have a logic error that causes the application to stop
> progressing, but you cannot have a deadlock that blocks the event loop of
> the main thread.
You can already block the main thread by having a runaway script, so this could
be viewed as an overly harsh goal when picking concurrency models.
>
>
> Web APIs have different constraints than non-Web platforms that may help
> explain why the Web sometimes seems dumb from the perspective of
> professional programers or computer scientists. Specifically, the Web
> platform's design assumes the following:
>
> 1. Every Web author is potentially hostile and very clever,
Threads do not make the Web author any more hostile, but I appreciate that this
should be a serious goal.
> 2. Every Web author is potentially a bumbling fool.
I don't disagree with this, but I'm not sure that I'm convinced that the
application of this ethos implies that we cannot have locks, particularly since
their acquisition on the main thread can be asynchronous just like the message
passing of workers is.
>
> Most platforms instead assume that their programmers are mostly benign and
> that their programmers are mostly competent.
>
> These two assumptions are the main reason for almost every "weird"
> decision the Web platform has.
>
> If you want to do highly efficient computation, the Web is probably not
> going to be the best platform to use to do it, because computational
> performance has never been near the top of the priority list. Responsive
> UI is a high priority, security (resilience to hostile author code) is a
> high priority, fault tolerance has been a high priority (gracefully
> handling author mistakes), the ability to have code work uniformly across
> a wide variety of devices and platforms has been a high priority (most of
> the time, though we stumbled a bit with mobile input models).
Responsive UI is a good argument for having concurrency, and making it easier
to use.
>
> If you want to do intensive computation, the answer has traditionally been
> "do it on the server".
>
> --
> Ian Hickson U+1047E)\._.,--,'``.fL
> http://ln.hixie.ch/ U+263A/, _.. \ _\ ;`._ ,.
> Things that are impossible just take longer. `._.-(,_..'--(,_..'`-.;.'
___
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
>> Perhaps we can come up with some JS API for shared memory & lock and >> propose it in TC39 or WebApps WG? > > I think that would be wonderful. Anyone else interested? We proposed a shared memory concept a long time ago: https://bugs.webkit.org/show_bug.cgi?id=53485 Although it helps to reduce the message passing (decoding/encoding) costs of large buffers, it still involves JS on the other side. We are definitely interested to improve JS with multicore support. Now even phones have 2-4 cores, and would be great to use them for computing. Regards, Zoltan ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
I think the start point here would be the use case, we are talking about a web browser, normally the user wants to parallelize some data and visualize it. This visualization can be done through html/svg/canvas/webgl. Thinking about WebGL and canvas(accelerated canvas), threads can be nocive because context switch is expensive(specially in mobile devices). Now looking on OpenCL, it provides an extension that shares data between opencl and opengl driver, so we do not need to readback from gpu. Other interesting point discussed already: we should be able to create a low level API where the user can create a high level abstraction, about this statement WebCL has a big advantage because someone[1] already proved it can be done. [1] http://www.eecs.berkeley.edu/~lmeyerov/projects/pbrowser/pubfiles/lashc2012.pdf On Fri, Apr 12, 2013 at 11:25 PM, Rik Cabanier wrote: > > > On Fri, Apr 12, 2013 at 10:34 PM, Filip Pizlo wrote: > >> >> On Apr 12, 2013, at 9:46 PM, Rik Cabanier wrote: >> >> >> >> On Fri, Apr 12, 2013 at 9:39 PM, Zoltan Herczeg >> wrote: >> >>> > A message passing model a la Web Workers has some advantages compared >>> to >>> > threads with shared mutable state and locks: >>> > - No possibility of deadlock >>> > - No possibility of corrupting data structures due to races >>> > - No performance penalty from correctly supporting fine-grained >>> concurrent >>> > access to arbitrary mutable objects >>> > >>> > 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. >>> > >>> > I believe message passing as a concurrent programming model is much >>> less >>> > prone to severe errors than shared mutable state + locking. I think you >>> > have to be super smart to even have a chance of using shared mutable >>> state >>> > correctly. That being said, I am not sure Web Workers as they exist >>> today >>> > are the best possible form of message passing. >>> >>> We tried to use WebWorkers for parallel computation, but in their current >>> form, they are useless. We also searched for other Worker demos on the >>> net, and all of them were slower with workers. I suspect ParallelArray >>> will not help either. >>> >> >> Have you tried pdf.js? That uses workers for various operations. >> There's an option to turn off workers and it makes pages display slower. >> >> >> Pdf.js is really cool. But I agree with Zoltan's general assessment of >> workers: they are not easy to use. Just because pdf.js uses them doesn't >> mean we can't do better. >> > > I completely agree. Not only are they hard; apparently it's unspecified > what API's are available to them. [1] > I was just replying to his point that all uses of workers make things > slower. > > > 1: > http://lists.w3.org/Archives/Public/public-whatwg-archive/2013Apr/0054.html > >> >>> The problem is not producing messages, but receiving and processing them >>> on the other side. Why? Because that involves JS. Noone will use JS to >>> search prime numbers, they want to control the UI (animations, image >>> generation, physics, etc.). >>> >>> Imho Workers need an API, which can be used to set (and perhaps get) >>> properties without calling JS. Especially timed set (the change should be >>> happen in a given time in the future). Very important for smooth >>> animations. These properties must be constants: numbers, strings, RGBA >>> arrays, etc. When we set dozens of properties, the extra cost on the UI >>> side should be minimal. >> >> >> What do you mean here? Maybe some pseudocode will make it clear for me. >> >> ___ >> webkit-dev mailing list >> webkit-dev@lists.webkit.org >> https://lists.webkit.org/mailman/listinfo/webkit-dev >> >> >> > > ___ > webkit-dev mailing list > webkit-dev@lists.webkit.org > https://lists.webkit.org/mailman/listinfo/webkit-dev > > ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, 12 Apr 2013, Filip Pizlo wrote: > > 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. Actually, you can't. We very specifically designed workers (and even more importantly the API on the main thread) so that you cannot block on waiting for a message. Certainly you can have a logic error that causes the application to stop progressing, but you cannot have a deadlock that blocks the event loop of the main thread. Web APIs have different constraints than non-Web platforms that may help explain why the Web sometimes seems dumb from the perspective of professional programers or computer scientists. Specifically, the Web platform's design assumes the following: 1. Every Web author is potentially hostile and very clever, 2. Every Web author is potentially a bumbling fool. Most platforms instead assume that their programmers are mostly benign and that their programmers are mostly competent. These two assumptions are the main reason for almost every "weird" decision the Web platform has. If you want to do highly efficient computation, the Web is probably not going to be the best platform to use to do it, because computational performance has never been near the top of the priority list. Responsive UI is a high priority, security (resilience to hostile author code) is a high priority, fault tolerance has been a high priority (gracefully handling author mistakes), the ability to have code work uniformly across a wide variety of devices and platforms has been a high priority (most of the time, though we stumbled a bit with mobile input models). If you want to do intensive computation, the answer has traditionally been "do it on the server". -- Ian Hickson U+1047E)\._.,--,'``.fL http://ln.hixie.ch/ U+263A/, _.. \ _\ ;`._ ,. Things that are impossible just take longer. `._.-(,_..'--(,_..'`-.;.' ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, Apr 12, 2013 at 10:34 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 9:46 PM, Rik Cabanier wrote: > > > > On Fri, Apr 12, 2013 at 9:39 PM, Zoltan Herczeg > wrote: > >> > A message passing model a la Web Workers has some advantages compared to >> > threads with shared mutable state and locks: >> > - No possibility of deadlock >> > - No possibility of corrupting data structures due to races >> > - No performance penalty from correctly supporting fine-grained >> concurrent >> > access to arbitrary mutable objects >> > >> > 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. >> > >> > I believe message passing as a concurrent programming model is much less >> > prone to severe errors than shared mutable state + locking. I think you >> > have to be super smart to even have a chance of using shared mutable >> state >> > correctly. That being said, I am not sure Web Workers as they exist >> today >> > are the best possible form of message passing. >> >> We tried to use WebWorkers for parallel computation, but in their current >> form, they are useless. We also searched for other Worker demos on the >> net, and all of them were slower with workers. I suspect ParallelArray >> will not help either. >> > > Have you tried pdf.js? That uses workers for various operations. > There's an option to turn off workers and it makes pages display slower. > > > Pdf.js is really cool. But I agree with Zoltan's general assessment of > workers: they are not easy to use. Just because pdf.js uses them doesn't > mean we can't do better. > I completely agree. Not only are they hard; apparently it's unspecified what API's are available to them. [1] I was just replying to his point that all uses of workers make things slower. 1: http://lists.w3.org/Archives/Public/public-whatwg-archive/2013Apr/0054.html > >> The problem is not producing messages, but receiving and processing them >> on the other side. Why? Because that involves JS. Noone will use JS to >> search prime numbers, they want to control the UI (animations, image >> generation, physics, etc.). >> >> Imho Workers need an API, which can be used to set (and perhaps get) >> properties without calling JS. Especially timed set (the change should be >> happen in a given time in the future). Very important for smooth >> animations. These properties must be constants: numbers, strings, RGBA >> arrays, etc. When we set dozens of properties, the extra cost on the UI >> side should be minimal. > > > What do you mean here? Maybe some pseudocode will make it clear for me. > > ___ > webkit-dev mailing list > webkit-dev@lists.webkit.org > https://lists.webkit.org/mailman/listinfo/webkit-dev > > > ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 11:07 PM, Ryosuke Niwa wrote: > On Fri, Apr 12, 2013 at 10:44 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 10:43 PM, Ryosuke Niwa wrote: > >> On Fri, Apr 12, 2013 at 2:13 PM, Filip Pizlo wrote: >> >> On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa wrote: >> >>> On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: >>> >>> On Apr 12, 2013, at 1:39 PM, Jarred Nicholls >>> wrote: >>> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo 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. >> >> I never thought Web workers was tied to a message passing model but you've >> convinced me of this point in our earlier in-person discussion. >>> This is just a thought but is it possible to infer semantics of what Web >>> workers and use GPU or SIMD instructions instead of starting a new thread >>> as appropriate? >> >> Probably that would be hard, because the Web Worker semantics are so >> bizarre: they require copying things all over the place. It's probably an >> even worse match for SIMD/GPU/multicore than just Array.prototype.forEach(). >> >> Yeah, I was thinking that this is possible once we've added a shared memory >> model. You've also convinced me in the same in-person discussion and in a >> reply to Maciej's response that memory corruption isn't an issue in JS. I'm >> totally with you and Zoltan that the current message passing model makes Web >> workers pretty much useless. >> >> Perhaps we can come up with some JS API for shared memory & lock and propose >> it in TC39 or WebApps WG? > > I think that would be wonderful. Anyone else interested? > > Do you think it's possible to come up with an API/semantics that would allow > us to seamlessly switch between single-threaded, SIMD/GPU accelerated, and > GPU accelerations? Or would be too cumbersome / too hard to implement? That's hard. > > It would be really neat if we could dynamically detect cases where we can use > lightweight alternatives such as OpenCL instead of creating a real thread. To their credit, ParallelArrays try to do this, but do so at the cost of other constraints. Right now the web doesn't have a general concurrency mechanism. I think we should start simple. Just having the ability to use threads would be a huge improvement over what is available now! > > - R. Niwa > > ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, Apr 12, 2013 at 10:44 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 10:43 PM, Ryosuke Niwa wrote: > > On Fri, Apr 12, 2013 at 2:13 PM, Filip Pizlo wrote: > >> >> On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa wrote: >> >> On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: >> >>> >>> On Apr 12, 2013, at 1:39 PM, Jarred Nicholls >>> wrote: >>> >>> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo 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. >> > > I never thought Web workers was tied to a message passing model but you've > convinced me of this point in our earlier in-person discussion. > >> This is just a thought but is it possible to infer semantics of what Web >> workers and use GPU or SIMD instructions instead of starting a new thread >> as appropriate? >> >> >> Probably that would be hard, because the Web Worker semantics are so >> bizarre: they require copying things all over the place. It's probably an >> even worse match for SIMD/GPU/multicore than just Array.prototype.forEach(). >> > > Yeah, I was thinking that this is possible once we've added a shared > memory model. You've also convinced me in the same in-person discussion > and in a reply to Maciej's response that memory corruption isn't an issue > in JS. I'm totally with you and Zoltan that the current message passing > model makes Web workers pretty much useless. > > Perhaps we can come up with some JS API for shared memory & lock and > propose it in TC39 or WebApps WG? > > I think that would be wonderful. Anyone else interested? > Do you think it's possible to come up with an API/semantics that would allow us to seamlessly switch between single-threaded, SIMD/GPU accelerated, and GPU accelerations? Or would be too cumbersome / too hard to implement? It would be really neat if we could dynamically detect cases where we can use lightweight alternatives such as OpenCL instead of creating a real thread. - R. Niwa ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 7:03 PM, Dirk Pranke wrote: > On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: > I'm curious: would you want to use ParallelArray, if you had the flexibility > of building a different abstraction? > > I find ParallelArray to be an awkward abstraction to begin with. I like work > queues and such. The whole idea that the only parallelism you get is from > arrays feels narrow-minded. > > I think the needs of the HPC / GPU-accelerating crowd are quite different > from the people looking for general concurrency solutions to the multi-core > problem. Mandatory snarky remark: I don't think that HPC is what people will be doing in JavaScript, in a browser! But in all seriousness, I'm all for considering the HPC and GPU-acceleration workloads along with all of the other use cases of concurrency. I believe that the best programming models are the ones that cover even more usage scenarios than their designer intended. :-) > > For what it's worth, NRWT is (IMO) an interesting example of a > highly-parallel program. I know, it's pretty cool! > In a sense, the problem is perfectly suited to map/reduce, and the > performance of NRWT scales linearly well up to (at least) 48-core machines; > the necessarily-serial part of the program is quite small. However, in order > to turn it into a usable program (where you can actually tell what's going on > and manage it well), you do need to actually monitor tasks and queues and > provide problem-specific feedback to the user. I'm not sure what the message > of that is, exactly … To me it's just that: concurrency is hard and there is no silver bullet. In the absence of silver bullets the best you can do, as a programming language/programming model designer is to give people a general tool, and do the best you can to guard them on the security and isolation front. We can do this in JavaScript: it's a memory-safe language already. -Filip > > -- Dirk ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 10:43 PM, Ryosuke Niwa wrote: > On Fri, Apr 12, 2013 at 2:13 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa wrote: > >> On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: >> >> On Apr 12, 2013, at 1:39 PM, Jarred Nicholls >> wrote: >> >>> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo 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. > > I never thought Web workers was tied to a message passing model but you've > convinced me of this point in our earlier in-person discussion. >> This is just a thought but is it possible to infer semantics of what Web >> workers and use GPU or SIMD instructions instead of starting a new thread as >> appropriate? > > Probably that would be hard, because the Web Worker semantics are so bizarre: > they require copying things all over the place. It's probably an even worse > match for SIMD/GPU/multicore than just Array.prototype.forEach(). > > Yeah, I was thinking that this is possible once we've added a shared memory > model. You've also convinced me in the same in-person discussion and in a > reply to Maciej's response that memory corruption isn't an issue in JS. I'm > totally with you and Zoltan that the current message passing model makes Web > workers pretty much useless. > > Perhaps we can come up with some JS API for shared memory & lock and propose > it in TC39 or WebApps WG? I think that would be wonderful. Anyone else interested? > > - R. Niwa > > ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, Apr 12, 2013 at 2:13 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa wrote: > > On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: > >> >> On Apr 12, 2013, at 1:39 PM, Jarred Nicholls >> wrote: >> >> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo 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. > I never thought Web workers was tied to a message passing model but you've convinced me of this point in our earlier in-person discussion. > This is just a thought but is it possible to infer semantics of what Web > workers and use GPU or SIMD instructions instead of starting a new thread > as appropriate? > > > Probably that would be hard, because the Web Worker semantics are so > bizarre: they require copying things all over the place. It's probably an > even worse match for SIMD/GPU/multicore than just Array.prototype.forEach(). > Yeah, I was thinking that this is possible once we've added a shared memory model. You've also convinced me in the same in-person discussion and in a reply to Maciej's response that memory corruption isn't an issue in JS. I'm totally with you and Zoltan that the current message passing model makes Web workers pretty much useless. Perhaps we can come up with some JS API for shared memory & lock and propose it in TC39 or WebApps WG? - R. Niwa ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 9:46 PM, Rik Cabanier wrote: > > > On Fri, Apr 12, 2013 at 9:39 PM, Zoltan Herczeg wrote: > > A message passing model a la Web Workers has some advantages compared to > > threads with shared mutable state and locks: > > - No possibility of deadlock > > - No possibility of corrupting data structures due to races > > - No performance penalty from correctly supporting fine-grained concurrent > > access to arbitrary mutable objects > > > > 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. > > > > I believe message passing as a concurrent programming model is much less > > prone to severe errors than shared mutable state + locking. I think you > > have to be super smart to even have a chance of using shared mutable state > > correctly. That being said, I am not sure Web Workers as they exist today > > are the best possible form of message passing. > > We tried to use WebWorkers for parallel computation, but in their current > form, they are useless. We also searched for other Worker demos on the > net, and all of them were slower with workers. I suspect ParallelArray > will not help either. > > Have you tried pdf.js? That uses workers for various operations. > There's an option to turn off workers and it makes pages display slower. Pdf.js is really cool. But I agree with Zoltan's general assessment of workers: they are not easy to use. Just because pdf.js uses them doesn't mean we can't do better. > > > The problem is not producing messages, but receiving and processing them > on the other side. Why? Because that involves JS. Noone will use JS to > search prime numbers, they want to control the UI (animations, image > generation, physics, etc.). > > Imho Workers need an API, which can be used to set (and perhaps get) > properties without calling JS. Especially timed set (the change should be > happen in a given time in the future). Very important for smooth > animations. These properties must be constants: numbers, strings, RGBA > arrays, etc. When we set dozens of properties, the extra cost on the UI > side should be minimal. > > What do you mean here? Maybe some pseudocode will make it clear for me. > > ___ > webkit-dev mailing list > webkit-dev@lists.webkit.org > https://lists.webkit.org/mailman/listinfo/webkit-dev ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 6:35 PM, Maciej Stachowiak wrote: > > On Apr 12, 2013, at 2:13 PM, Filip Pizlo wrote: > >> >> On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa wrote: >> >>> On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: >>> >>> On Apr 12, 2013, at 1:39 PM, Jarred Nicholls >>> wrote: >>> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo 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 pair
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, Apr 12, 2013 at 9:39 PM, Zoltan Herczeg wrote: > > A message passing model a la Web Workers has some advantages compared to > > threads with shared mutable state and locks: > > - No possibility of deadlock > > - No possibility of corrupting data structures due to races > > - No performance penalty from correctly supporting fine-grained > concurrent > > access to arbitrary mutable objects > > > > 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. > > > > I believe message passing as a concurrent programming model is much less > > prone to severe errors than shared mutable state + locking. I think you > > have to be super smart to even have a chance of using shared mutable > state > > correctly. That being said, I am not sure Web Workers as they exist today > > are the best possible form of message passing. > > We tried to use WebWorkers for parallel computation, but in their current > form, they are useless. We also searched for other Worker demos on the > net, and all of them were slower with workers. I suspect ParallelArray > will not help either. > Have you tried pdf.js? That uses workers for various operations. There's an option to turn off workers and it makes pages display slower. > > The problem is not producing messages, but receiving and processing them > on the other side. Why? Because that involves JS. Noone will use JS to > search prime numbers, they want to control the UI (animations, image > generation, physics, etc.). > > Imho Workers need an API, which can be used to set (and perhaps get) > properties without calling JS. Especially timed set (the change should be > happen in a given time in the future). Very important for smooth > animations. These properties must be constants: numbers, strings, RGBA > arrays, etc. When we set dozens of properties, the extra cost on the UI > side should be minimal. What do you mean here? Maybe some pseudocode will make it clear for me. ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
> A message passing model a la Web Workers has some advantages compared to > threads with shared mutable state and locks: > - No possibility of deadlock > - No possibility of corrupting data structures due to races > - No performance penalty from correctly supporting fine-grained concurrent > access to arbitrary mutable objects > > 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. > > I believe message passing as a concurrent programming model is much less > prone to severe errors than shared mutable state + locking. I think you > have to be super smart to even have a chance of using shared mutable state > correctly. That being said, I am not sure Web Workers as they exist today > are the best possible form of message passing. We tried to use WebWorkers for parallel computation, but in their current form, they are useless. We also searched for other Worker demos on the net, and all of them were slower with workers. I suspect ParallelArray will not help either. The problem is not producing messages, but receiving and processing them on the other side. Why? Because that involves JS. Noone will use JS to search prime numbers, they want to control the UI (animations, image generation, physics, etc.). Imho Workers need an API, which can be used to set (and perhaps get) properties without calling JS. Especially timed set (the change should be happen in a given time in the future). Very important for smooth animations. These properties must be constants: numbers, strings, RGBA arrays, etc. When we set dozens of properties, the extra cost on the UI side should be minimal. Regards, Zoltan ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: > I'm curious: would you want to use ParallelArray, if you had the > flexibility of building a different abstraction? > > I find ParallelArray to be an awkward abstraction to begin with. I like > work queues and such. The whole idea that the only parallelism you get is > from arrays feels narrow-minded. > I think the needs of the HPC / GPU-accelerating crowd are quite different from the people looking for general concurrency solutions to the multi-core problem. For what it's worth, NRWT is (IMO) an interesting example of a highly-parallel program. In a sense, the problem is perfectly suited to map/reduce, and the performance of NRWT scales linearly well up to (at least) 48-core machines; the necessarily-serial part of the program is quite small. However, in order to turn it into a usable program (where you can actually tell what's going on and manage it well), you do need to actually monitor tasks and queues and provide problem-specific feedback to the user. I'm not sure what the message of that is, exactly ... -- Dirk ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 2:13 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa wrote: > >> On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: >> >> On Apr 12, 2013, at 1:39 PM, Jarred Nicholls >> wrote: >> >>> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo 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: - No possibility of deadlock - No possibility of corrupting data structures due to races - No performance penalty from correctly supporting fine-grained concurrent access to arbitrary mutable objects 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. I believe message passing as a concurrent programming model is much less prone to severe errors than shared mutable state + locking. I think you have to be super smart to even have a chance of using shared mutable state correctly. That being said, I am not sure Web Workers as they exist today are the best possible form of message passing. Regards, Maciej ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 1:59 PM, Ryosuke Niwa wrote: > On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 1:39 PM, Jarred Nicholls > wrote: > >> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo 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. > > This is just a thought but is it possible to infer semantics of what Web > workers and use GPU or SIMD instructions instead of starting a new thread as > appropriate? Probably that would be hard, because the Web Worker semantics are so bizarre: they require copying things all over the place. It's probably an even worse match for SIMD/GPU/multicore than just Array.prototype.forEach(). -Filip > > - R. Niwa ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Fri, Apr 12, 2013 at 1:50 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 1:39 PM, Jarred Nicholls > wrote: > > On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo 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? This is just a thought but is it possible to infer semantics of what Web workers and use GPU or SIMD instructions instead of starting a new thread as appropriate? - R. Niwa ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 1:39 PM, Jarred Nicholls wrote: > On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo wrote: > > On Apr 12, 2013, at 8:36 AM, "Hudson, Rick" wrote: > > > I'm assuming that we agree that JavaScript must evolve to leverage the > > hardware's power stingy parallelism. > > True, but there is also the question of how high of a priority we should give > to this relative to other project goals, and also what opportunity costs are > introduced from any particular implementation of parallelism that we choose. > What you are proposing will only work for code that performs non-effectful > operations. This is a limited form of parallelism, and I'm not sure that > it's a general enough programming model to warrant adding new things to the > platform. > > > For completeness there seems to be the following approaches. > > > > 1)Add nothing to the language and rely on increasingly sophisticated > > compilers to detect opportunities to safely parallelize computations within > > the current semantics. > > 2)Add methods to Array that provide parallel semantics. > > 3)Add syntax and keywords such as parallelFor to introduce parallelism. > > 4)Add a parallel type (ParallelArray) and associated methods that > > provide parallel semantics. > > You forgot the obvious ones: > > 5) Message passing > 6) Shared mutable memory with either threads and locks, or something along > those lines. > > We sort of already have (5) but it is half baked; I think there is > opportunity to improve it. > > We don't have (6). (6) subsumes all of (1), (2), (3), (4), and (5) as it > would allow the programmer to roll all of those primitives in JS. > > We should not reject shared mutable memory out of hand. It is the prevailing > technique for implementing concurrency and parallelism in the other languages > that people use. > > > > > The _nothing_ approach would have to deal with array methods, such as map > > and reduce, that have sequential semantics. For example reduce is really > > reduce right (or fold right) and these semantics defeat parallelization. > > For example the EIC signature for the function/closure passed to reduce > > assumes E === C[I] but the value E could be the result of previous > > invocation of the function. This approach seems to be strictly worse than > > the methods approach. A similar nothing approach is to analyze loops to > > mechanically discover opportunities for parallelization. While there exists > > decades of literature that have been full of optimism the reality is that > > this approach has not achieved wide spread success. > > Part of that lack of success stems from the fact that most code that does > things to arrays has subtle loop-carried side-effects. The closures passed > to ParallelArray methods could have those, also; and if they did then you > wouldn't be able to soundly parallelize. > > You haven't convinced me that ParallelArray will be any more successful than > the full autoparallelization approach. You also haven't convinced me that it > will be any more successful than other eclectic ideas, like OpenMP, for > example. I don't think that such annotation-based approaches have been > particularly successful in other languages. The languages that have seen the > most success in parallel development are precisely those that give *complete* > control to the programmer, such as Java, which gives you threads and locks > combined with a sensible memory model - and allows you to craft your > algorithm in the way that best suits your problem domain. Why is this > approach being rejected? > > > > > The _methods_ approach side steps the semantics issue raised in the nothing > > approach but does not compose well with the original methods. For example > > Array has several inherently sequential methods, such as push and pop, > > that do not have a reasonable parallel semantics since they force mutation. > > That said this approach has its proponents. Nico > > http://smallcultfollowing.com/babysteps/blog/2013/02/26/splitting-the-pjs-api/ > > suggested that we add unorderedMap and unorderedReduce to indicate that > > the scheduling of the computation be unordered. While the idea is > > compelling on the surface it is likely to lead to the development of > > algorithms that are at first sequential and then hacked to make them > > parallel. This approach will impede the goal of having programmers develop > > parallel algorithms and the appropriate parallel data structures. The > > methods approach would miss a real opportunity here to move programmers > > away from the sequential models and on to parallel models. > > ParallelArray also misses this opportunity. The only thing that > ParallelArray does is adds methods that could have been added to Array, and > requires you to say, when you write your code, if you want parallelization or > not. The only problem this solves is inferring the "is it profitable t
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
Argh, sending from the right address this time. On Fri, Apr 12, 2013 at 4:39 PM, Jarred Nicholls wrote: > On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo wrote: > >> >> On Apr 12, 2013, at 8:36 AM, "Hudson, Rick" >> wrote: >> >> > I'm assuming that we agree that JavaScript must evolve to leverage the >> hardware's power stingy parallelism. >> >> True, but there is also the question of how high of a priority we should >> give to this relative to other project goals, and also what opportunity >> costs are introduced from any particular implementation of parallelism that >> we choose. What you are proposing will only work for code that performs >> non-effectful operations. This is a limited form of parallelism, and I'm >> not sure that it's a general enough programming model to warrant adding new >> things to the platform. >> >> > For completeness there seems to be the following approaches. >> > >> > 1)Add nothing to the language and rely on increasingly >> sophisticated compilers to detect opportunities to safely parallelize >> computations within the current semantics. >> > 2)Add methods to Array that provide parallel semantics. >> > 3)Add syntax and keywords such as parallelFor to introduce >> parallelism. >> > 4)Add a parallel type (ParallelArray) and associated methods that >> provide parallel semantics. >> >> You forgot the obvious ones: >> >> 5) Message passing >> 6) Shared mutable memory with either threads and locks, or something >> along those lines. >> >> We sort of already have (5) but it is half baked; I think there is >> opportunity to improve it. >> >> We don't have (6). (6) subsumes all of (1), (2), (3), (4), and (5) as it >> would allow the programmer to roll all of those primitives in JS. >> >> We should not reject shared mutable memory out of hand. It is the >> prevailing technique for implementing concurrency and parallelism in the >> other languages that people use. >> >> > >> > The _nothing_ approach would have to deal with array methods, such as >> map and reduce, that have sequential semantics. For example reduce is >> really reduce right (or fold right) and these semantics defeat >> parallelization. For example the EIC signature for the function/closure >> passed to reduce assumes E === C[I] but the value E could be the result of >> previous invocation of the function. This approach seems to be strictly >> worse than the methods approach. A similar nothing approach is to analyze >> loops to mechanically discover opportunities for parallelization. While >> there exists decades of literature that have been full of optimism the >> reality is that this approach has not achieved wide spread success. >> >> Part of that lack of success stems from the fact that most code that does >> things to arrays has subtle loop-carried side-effects. The closures passed >> to ParallelArray methods could have those, also; and if they did then you >> wouldn't be able to soundly parallelize. >> >> You haven't convinced me that ParallelArray will be any more successful >> than the full autoparallelization approach. You also haven't convinced me >> that it will be any more successful than other eclectic ideas, like OpenMP, >> for example. I don't think that such annotation-based approaches have been >> particularly successful in other languages. The languages that have seen >> the most success in parallel development are precisely those that give >> *complete* control to the programmer, such as Java, which gives you threads >> and locks combined with a sensible memory model - and allows you to craft >> your algorithm in the way that best suits your problem domain. Why is this >> approach being rejected? >> >> > >> > The _methods_ approach side steps the semantics issue raised in the >> nothing approach but does not compose well with the original methods. For >> example Array has several inherently sequential methods, such as push and >> pop, that do not have a reasonable parallel semantics since they force >> mutation. >> > That said this approach has its proponents. Nico >> http://smallcultfollowing.com/babysteps/blog/2013/02/26/splitting-the-pjs-api/suggested >> that we add unorderedMap and unorderedReduce to indicate that the >> scheduling of the computation be unordered. While the idea is compelling on >> the surface it is likely to lead to the development of algorithms that are >> at first sequential and then hacked to make them parallel. This approach >> will impede the goal of having programmers develop parallel algorithms and >> the appropriate parallel data structures. The methods approach would miss a >> real opportunity here to move programmers away from the sequential models >> and on to parallel models. >> >> ParallelArray also misses this opportunity. The only thing that >> ParallelArray does is adds methods that could have been added to Array, and >> requires you to say, when you write your code, if you want parallelization >> or not. The only problem this solves
Re: [webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
On Apr 12, 2013, at 8:36 AM, "Hudson, Rick" wrote: > I'm assuming that we agree that JavaScript must evolve to leverage the > hardware's power stingy parallelism. True, but there is also the question of how high of a priority we should give to this relative to other project goals, and also what opportunity costs are introduced from any particular implementation of parallelism that we choose. What you are proposing will only work for code that performs non-effectful operations. This is a limited form of parallelism, and I'm not sure that it's a general enough programming model to warrant adding new things to the platform. > For completeness there seems to be the following approaches. > > 1)Add nothing to the language and rely on increasingly sophisticated > compilers to detect opportunities to safely parallelize computations within > the current semantics. > 2)Add methods to Array that provide parallel semantics. > 3)Add syntax and keywords such as parallelFor to introduce parallelism. > 4)Add a parallel type (ParallelArray) and associated methods that provide > parallel semantics. You forgot the obvious ones: 5) Message passing 6) Shared mutable memory with either threads and locks, or something along those lines. We sort of already have (5) but it is half baked; I think there is opportunity to improve it. We don't have (6). (6) subsumes all of (1), (2), (3), (4), and (5) as it would allow the programmer to roll all of those primitives in JS. We should not reject shared mutable memory out of hand. It is the prevailing technique for implementing concurrency and parallelism in the other languages that people use. > > The _nothing_ approach would have to deal with array methods, such as map and > reduce, that have sequential semantics. For example reduce is really reduce > right (or fold right) and these semantics defeat parallelization. For example > the EIC signature for the function/closure passed to reduce assumes E === > C[I] but the value E could be the result of previous invocation of the > function. This approach seems to be strictly worse than the methods > approach. A similar nothing approach is to analyze loops to mechanically > discover opportunities for parallelization. While there exists decades of > literature that have been full of optimism the reality is that this approach > has not achieved wide spread success. Part of that lack of success stems from the fact that most code that does things to arrays has subtle loop-carried side-effects. The closures passed to ParallelArray methods could have those, also; and if they did then you wouldn't be able to soundly parallelize. You haven't convinced me that ParallelArray will be any more successful than the full autoparallelization approach. You also haven't convinced me that it will be any more successful than other eclectic ideas, like OpenMP, for example. I don't think that such annotation-based approaches have been particularly successful in other languages. The languages that have seen the most success in parallel development are precisely those that give *complete* control to the programmer, such as Java, which gives you threads and locks combined with a sensible memory model - and allows you to craft your algorithm in the way that best suits your problem domain. Why is this approach being rejected? > > The _methods_ approach side steps the semantics issue raised in the nothing > approach but does not compose well with the original methods. For example > Array has several inherently sequential methods, such as push and pop, that > do not have a reasonable parallel semantics since they force mutation. > That said this approach has its proponents. Nico > http://smallcultfollowing.com/babysteps/blog/2013/02/26/splitting-the-pjs-api/ > suggested that we add unorderedMap and unorderedReduce to indicate that the > scheduling of the computation be unordered. While the idea is compelling on > the surface it is likely to lead to the development of algorithms that are at > first sequential and then hacked to make them parallel. This approach will > impede the goal of having programmers develop parallel algorithms and the > appropriate parallel data structures. The methods approach would miss a real > opportunity here to move programmers away from the sequential models and on > to parallel models. ParallelArray also misses this opportunity. The only thing that ParallelArray does is adds methods that could have been added to Array, and requires you to say, when you write your code, if you want parallelization or not. The only problem this solves is inferring the "is it profitable to parallelize" question. I'm not sure that inferring the answer to this question is hard enough to warrant a new type. > > The _syntax_ approach suggests that we follow the lead of Amp and add > parallelFor and siblings to JavaScript. This approach seems to suffer from >
[webkit-dev] Parallel JavaScript: Why a separate ParallelArray types
I'm assuming that we agree that JavaScript must evolve to leverage the hardware's power stingy parallelism. For completeness there seems to be the following approaches. 1) Add nothing to the language and rely on increasingly sophisticated compilers to detect opportunities to safely parallelize computations within the current semantics. 2) Add methods to Array that provide parallel semantics. 3) Add syntax and keywords such as parallelFor to introduce parallelism. 4) Add a parallel type (ParallelArray) and associated methods that provide parallel semantics. The _nothing_ approach would have to deal with array methods, such as map and reduce, that have sequential semantics. For example reduce is really reduce right (or fold right) and these semantics defeat parallelization. For example the EIC signature for the function/closure passed to reduce assumes E === C[I] but the value E could be the result of previous invocation of the function. This approach seems to be strictly worse than the methods approach. A similar nothing approach is to analyze loops to mechanically discover opportunities for parallelization. While there exists decades of literature that have been full of optimism the reality is that this approach has not achieved wide spread success. The _methods_ approach side steps the semantics issue raised in the nothing approach but does not compose well with the original methods. For example Array has several inherently sequential methods, such as push and pop, that do not have a reasonable parallel semantics since they force mutation. That said this approach has its proponents. Nico http://smallcultfollowing.com/babysteps/blog/2013/02/26/splitting-the-pjs-api/ suggested that we add unorderedMap and unorderedReduce to indicate that the scheduling of the computation be unordered. While the idea is compelling on the surface it is likely to lead to the development of algorithms that are at first sequential and then hacked to make them parallel. This approach will impede the goal of having programmers develop parallel algorithms and the appropriate parallel data structures. The methods approach would miss a real opportunity here to move programmers away from the sequential models and on to parallel models. The _syntax_ approach suggests that we follow the lead of Amp and add parallelFor and siblings to JavaScript. This approach seems to suffer from not being backwardly compatible and like the methods approach misses an opportunity to move programmers away from their sequential mindset. The _parallel type_ approach provides a clear separation from the semantics of Array and in doing so does a much better job of encouraging programmers to build parallel algorithms and data structures instead of attempting to parallelize sequential algorithms. The contract between the programmer and the system can be better defined if ParallelArray exists independently of Array and the two prototypes could develop independently. That is not to say that we shouldn't follow the principle of least surprise and leverage the programmer's familiarity with the Array methods signatures. For example the kernel/callback function should follow the same conventions found in the Array.map signature such as the call back (kernel) function formals being element, index, array. Furthermore the parallel type approach is a clear indication to the SDE and JIT implementers that the programmer wishes to execute this code in parallel. The SDE will be able to assist the programmer when they don't follow the contract, for example by throwing when it encounters a kernel with side effects. While the parallel type approach could be implemented on top of the methods or even the syntax approach information about the intent of the programmer would be lost to the JIT and the SDE. In summary the real value in adding ParallelArray as its own type is that it helps move the developer structure his programs and choose his algorithms with parallelism in mind and convey that intent clearly. - Rick ___ webkit-dev mailing list webkit-dev@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-dev
