You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
This repository was archived by the owner on Jan 25, 2022. It is now read-only.
Repository navigation
This repository was archived by the owner on Jan 25, 2022. It is now read-only.
C++ is considering a new primitive called synchronic which is similar to futex but has a few different tradeoffs, would work better on some hardware, and would be portable. There's a sample implementation with data, and @ogiroux is working on a new paper with an updated API.
It would be good to understand why synchronic isn't used JavaScript's shared memory:
Maybe synchronic itself would benefit from corrections.
Maybe it is a good fit, but is misunderstood (see demonstration below).
Will synchronic usage in C++17 (or whenever it's standardized) be mappable to JavaScript's primitives?
There are some notes in the DISCUSSION.md document regarding "why futex and not synchronic", but more are in the original proposal. I'll move of those over to DISCUSSION.md and try to make sure everything is there, and then we can discuss that.
(@jfbastien, There appear to be no "demonstration below", only a png.)
I second Jeffrey's recommendation. Especially since futexes don't seem to be universally supported everywhere?
Lars Hansen / 7:30 PM Mar 3:
Futexes supply the API but not even on Linux were we planning to use the native futexes directly.
(I like the "synchronic" API much better than futexes and will investigate it as a replacement.)
JF Bastien / 5:43 PM Mar 4:
+1 on synchronic. On feasability: PNaCl exposes a restricted futex on Linux/Windows/OSX, and it works, but I agree that it should be an implementation detail of synchronic.
Synchronic works poorly with asm.js and has not been included in the new spec. There's a section on synchronic below that addresses this in more detail.
Olivier Giroux / 4:14 AM Aug 22:
The exact API for synchronic has been in flux lately. What I'd like to focus on, if you guys are interested in a discussion about it, are the semantics. I would like to make a case for weaker semantics than futex guarantees, primarily for performance reasons.
The only essential difference between a synchronic and a futex is that the former is allowed to just poll for a while and skip the OS involvement if the condition was met during polling. This difference means that a synchronic can sometimes be satisfied in <100ns, when the minimum cost for futex is more like ~50us. A good-QOI implementation of synchronic will rapidly fallback to a lower-energy mechanism to avoid wasting resources, which could involve both yielding and eventually the OS queue as a last-resort.
When you code against futex directly then you're on the hook to mix polling, yielding and futex to cover the range of temporal response. This is a sort of dark art. I'm sure if you apply yourself then you can all master it, but do all your users need to?
I've been developing the synchronic library to try to prevent that. The API isn't the most essential thing about it, it's the idea of putting a gasket on the complexity that most users don't need. Secondarily, I'm putting a gasket on the portability problems too - Mac OS X and iOS aren't so well equipped as Linux and Windows in this department.
I really like synchronic (the spec and the code I've seen so far, anyway - Olivier's original paper and the code that was on Google Code). For programming in plain JS, in contrast with asm.js, I would want to stay away from futexes and use synchronic cells as the primitives in most cases.
So far, though, futexes have seemed like the better common primitive API for asm.js and plain JS. There are a couple of reasons.
Futexes are simple - no cross-worker storage management is needed beyond agreeing on an address, and no procedural initialization is needed either, so the protocols invoved are simple. In contrast, a synchronic requires at least a couple of cells - arguably the size depends on the type of datum held in the synchronic and is variable - and may require some initialization, so the protocol is a bit more complicated. One of the uses for futexes and synchronic will be to implement pthreads for translated C/C++, with a potentially unbounded number of locks, so the complexity of these protocols is not beside the point, though I don't want to overstate my case here, I'm not saying it wouldn't work.
Also, I think we'll need plain atomics regardless of whether we have synchronic or not, so synchronic does not have secondary benefits in API size reduction or whatever.
Finally, when programming in plain JS we probably want synchronics to be objects, while in asm.js they can't be (no GC, for starters). This isn't a huge consideration, but having "two kinds of synchronics" isn't appealing, at least not yet.
At the same time, futexes are hard to use; I've implemented a synchronic API for JS on top of futexes and I've been experimenting with spin loops for performance, and of course the performance improves when I guess right, but the guessing is hard. It would be lovely to abstract that away. So I've been wondering whether it would be possible and desirable to keep the futex API with its simplicity of one location of known size and no initialization protocol, but to incorporate the fast-wait idea from synchronic into it. This probably would be similar to Olivier's expectUpdate primitive, I'm not sure yet.
Synchronic was pretty heavily revised by @ogiroux in P0126R0, and it looks like it's going forward with a few wording changes. I think the new interfaces will address some of @lars-t-hansen's concerns.
The new API in that document is very compact compared with the old one (I'm surprised at some of the omissions actually) but I don't understand how it addresses any of my concerns, exactly (see my Aug 31 remark above).
Anyway I just want to note that I'd like to look into a synchronic API for JS in earnest after the January TC39 meeting, to see if we can find something that's workable for JS and asm.js. I've been using synchronics (implemented on top of futexes) in various sample and demo programs and in addition to the promise of better performance they are a lot less error-prone and cumbersome than futexes.
A good goal would be to hammer out a strawman API and a rough implementation by the end of February.
@ogiroux / @jfbastien, I have some questions about the revised synchronic proposal referenced above.
The proposal states, "Invocations of the expect functions that are unblocked by the invocation of a notify function may re-evaluate the user-provided predicate and block again." Am I to take that literally -- the proviso only applies to the predicate form -- or is it an oversight in the proposal, and it applies also to the value form?
Is there an updated document for synchronic or is the 2015-09-24 version the latest?
Is there a prototype implementation of this proposal somewhere?
OK, so putting the current code and the current proposal together with Olivier's last comment above, I now understand better. The current synchronic proposal really is "only" a better (more performant) futex, it is not the flexible atomic cell with reliable signaling from the older proposal.
Since expect_update / expect_update_for are a drop-in replacement for futexWait and notify with the special case of a do-nothing user function is a drop-in replacement for futexWake, it's probably the case that these synchronics could replace the futexes in the current JS proposal without much risk. Given the promise of better performance they probably should, if we can get the API worked out.
We'd lose the direct ability to wake some number 1 < k < all of waiting threads, and futexWakeOrRequeue is probably lost too. I expect neither is critical.
I'm fine with SHM being delayed in movement to production if it means continued API changes for performance and efficiency reasons. My own concern is ports to JS from C++, and I'm interested in the level of care for porting these API changes will bring about.
Comments and feedback on the proposal would be most welcome (notably see the Discussion section, where there are some items that are really questions and open issues), this bug is a good place for feedback. If all I hear is crickets I will contact some of you directly next week.
The proposal text is in this repo on the branch "synchronic", in tc39/synchronic.html.
I like the proposal. Have you explored porting the emscripten pthread support using synchronics instead of futexes? I'm not too concerned about code that uses futexes currently; it sounds like you didn't find much.
OTOH, I am curious if there are many examples of implementations of various synchronization primitives using synchronics. There are many with futexes. Though maybe this is a good thing, as it will discourage people from implementing their own primitives. :)
I like the proposal. Have you explored porting the emscripten pthread support using synchronics instead of futexes?
I have looked at that some. It's a mixed bag (this is from looking at the MUSL implementation that we use for Emscripten): Some places the library uses futex-in-a-loop to implement a synchronic, sometimes even with a preceding spin-wait. Other places it's more complicated.
I'm starting to believe that synchronics are complementary to futexes, or that futexWait is a variation on expectUpdate that checks its condition going in but not after that, but I'm not quite there yet.
OTOH, I am curious if there are many examples of implementations of various synchronization primitives using synchronics. There are many with futexes. Though maybe this is a good thing, as it will discourage people from implementing their own primitives. :)
I spent some time today building a lock and condition variable implementation on top of synchronics. Effectively - to get the desirable semantics - I ended up reimplementing in JS some of the logic from the futex implementation, notably in order to be able to wake just one waiter. That's not necessarily a problem, since synchronics got the job done, the code may well be faster than the futex-based implementation, and synchronics can be used for much faster custom synchronization. It just adds to the burden for the application programmer, if that's all we provide.
In my github there are example implementations of various locks and barriers. Easing the emulation of condition variables was not really a goal and I agree that you end up rolling your own futex in order to do that.
Just having support for the wake-one semantic carries a cost to performance even if you never use it. I don’t have a good sense of how often that is really necessary in practice. My sense is that most people will not write that code you wrote to emulate it, because they don’t actually need it - for example, you should not feel like you need it for locks and barriers.
Then, if I had a choice of two features to have, then I’d prefer {synchronic + condition variable} over {synchronic + futex}.
On the strawman nature of std::mutex : I think I'm fine with that because during this work I have already caused some shame to one vendor, who happened to improve their std::mutex tremendously in the next release. Everyone got a win out of that. Would be nice if that happened on OS X too. :^)
On the allocation idea : I didn't mean to say that the synchronic object needed to live in the shared array, but I wanted to point out that the user's one special ability was the ability to use words in that memory. It might make for an ugly API but as a thought experiment, imagine if calls of synchronic member functions were provided with locations in that memory to use for acceleration. Then the overarching goals could still be met within the envelope -- but until someone has a clever idea the API would be ugly.
IIUC @pizlonator your main objection is that the spec currently limits 1 synchronic per SAB?
Even if this objection is addressed, we still have the issue that synchronics lead to slower mutexes than futexes do.
A developer can of course create multiple SABs, but that's silly. What about SAB+int?
How is that better or different than futexes?
Are you proposing that every client will preallocate a pool of synchronics and then hash mutex addresses to select some synchronic? That sounds like what futexes do for you already, except than futexes do it a lot better.
If you have N synchronics then you have to choose between some ugly solutions:
every call to lock/unlock hashes the lock address to compute a synchronic index. This slows down uncontended critical sections, probably by a lot more than we want.
use synchronics like you use futexes: only access the synchronic on the slow path of your own locking algorithm. This eliminates any advantages of synchronic since now the client must write their own wait loop.
Both approaches require the client to manage their own concurrent hashing of synchronics, which is something that futexes do for you. The first approach is hella slow and the second approach requires the client to implement their own futex-style concurrent hashing.
I still believe that this is the wrong approach. We should stick with futexes.
—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
I join in doubt that the approach strawman just outlined is a good one.
One would probably either allocate exactly as many instances of synchronic state as needed (however that is done with the api) or would treat it the same as Futex by e.g. considering notify() to be expensive. It follows that if you can only have one copy of synchronic state and that is not the exact number you need, then you would treat it as being expensive.
There is a way to tell synchronic that you think it's expensive already in the C++ paper p0126r2 (note: this is the one part that is handled slightly differently in the implementation, which I think is further to the benefit of this type of use actually). When you use this option, it basically becomes a pass-through to Futex on platforms that have it. On platforms that don't have Futex, it has the freedom to desugar into something that is still less than Futex polyfill at least in part because "notify one" is always only a hint for synchronic. On your platform it could literally use your parking lot.
Still, it's better if you can have enough state so that you can leave it on full-automatic. It's too bad that is difficult to do with the TC39 proposal.
What I think the underlying issue here is that Synchronics is only one tool, and is not always the best tool to use. That being said, there are numerous cases where it is the best tool, but the older, more familiar futex and mutex tools have their own use cases as well.
The question should be then, what is there against having more than one "tool" available? I see the primary way to avoid misuse is by presenting properly made tutorials on these APIs, rather than by limiting the amount of tools in the tool shed you can use.
The issue that the SharedArrayBuffer is the only shared object type was known from the start, see my earliest remarks on this bug and the reason why I was resistant to synchronics at the time. Futexes were chosen at the outset of the SAB project explicitly because there is no object management to worry about other than picking a word in memory. (The performance issues described above were not a consideration - or at least not to my knowledge - only the fit to the problem.) Futexes were also an obvious good fit for implementing pthreads, as Filip also points out.
The JS proposal for synchronics was developed to stay within the constraint of being able to share only SharedArrayBuffer objects, and not allowing the internal state of the synchronic to be visible in the SharedArrayBuffer. As Filip noted above, this forces an internal representation where data are managed behind the program's back by the implementation of synchronics. For the small thread counts that we're currently seeing this might not have been a terrible problem but it's clearly true that it would not scale well.
I think it's time to put synchronics aside for now and move forward with the futexes we have - they are probably the better fit for the constraints we have.
And I apologize for not making this excursion properly data-driven. One data point is hardly sufficient.
(The discussion opens up a couple of issues around the TC39 futexes too, eg whether the fairness baked into them will get in the way of parallelism and whether it will now be useful, as very early versions of the spec had it, to expose relax/yield/pause type primitives to aid fast locks. But I will open separate issues for those.)
Aww, the API was flawed on a low level? No possibility of providing their benefit over futexes in another proposal, or will that be rolled into futexes as well? I'm still looking forward to platform specific spins being hidden behind an API.
Edit: I agree about leaving futexes in, but I'm wondering what's blocking attempts to cover all optimal threading cases in further API additions if synchronics in the current proposal is unfit.
I don't disagree with the outcome here given the context. I would like to end on a summary of why the outcome is right.
For efficient waiting, the combination of user + platform code needs to use some byte(s) of shared memory to decide if the slow path or the fast path should be taken. Also, the association between that state and the synchronization variable has to be O(1), which usually means they are side-by-side. As things stand with SAB only the user can use SAB, and in particular emplace "objects" there.
The consequence is that only the user can implement waiting prior to the slow-path-taken decision. A user could write synchronic on his own, with state in the SAB, but one can't be provided for him.
@taisel: if my conclusion is correct, then it casts a shadow over any prospective encapsulation of waiting that helps programmers use futex well.
@lars-t-hansen: I don't see how you could avoid relax/yield/sleep. You are set on a path where you'll need them. Wouldn't you say?
Right, synchronic would need to be an actual JS object, not magically tied to a SAB, to be efficient.
@lars-t-hansen IIUC that wasn't considered because of asm.js? If we ignore asm.js and look at SAB from a pure JS perspective, would it make sense to have synchronic then?
@jfairbank@lars-t-hansen I think it comes down to what is easier to reduce to what. You can implement synchronic on top of futex, or you can implement futex on top of synchronic. But if you implement futex on top of synchronic (or, rather, a bunch of synchronics) then unless you do some tricks you will have bad performance. Probably you'll have to implement your own concurrent hash map. On the other hand implementing synchronic on top of futex is less difficult.
From that standpoint, even if asm.js wasn't the primary use case, we would still want futex over synchronic. Futex is the better "kernel" feature, since it's easier to reduce other primitives to it. Synchronic is something you add when you already have other stuff.
(Thinking bigger, I think that in future languages any memory location that is shared should support the following primitives in addition to read/write:
CAS
Fenced load/store
Futex wait
Futex wake
This would mirror the way it works in C if you have a futex library lying around.)
I'm somewhat loath to let web developers figure out the right balance between spin, yield and sleep. Sure it'll be done by toolchains, but what I like about synchronic is that the VM figures it out for you instead. We can change it as the platforms evolve and we can also prioritize things based on factors the web cares about more than typical native platforms.
It's still possible for developers to silly-spin, but something like synchronic gives them the tool to do the Right Thing. I feel like in most cases futex gives them that tool a bit too late, and it's somewhat blunt.
Assuming the storage issue (which leads to a fast-path slowdown) is solved, do you have other concerns @pizlonator?
@jfbastien in a perfect world where doing the side-table lookup is free, I would have no objections.
I object to the suggestion that a side table lookup can be made to be free. Note that the fastest possible unlock path is a CAS, which is much cheaper than a side-table lookup. A side-table lookup will either have to acquire and release some other lock or it will have to use high-overhead lock-free hash map things. Either way that's super expensive. I believe that we are talking about a fundamental trade-off here and the futex API is the way that it is because that's how you ensure that fast paths are fast.
I don't see how you could avoid relax/yield/sleep. You are set on a path where you'll need them. Wouldn't you say?
That's what I fear. As I wrote above, a very early version of this spec had an Atomics.pause() operation that was simply meant to have the effect of the PAUSE instruction of the x86. I am older and wiser now, and see that that may not be sufficient. I've opened Issue #87, let's take the discussion there.
Activity
lars-t-hansen commentedon Aug 24, 2015
There are some notes in the DISCUSSION.md document regarding "why futex and not synchronic", but more are in the original proposal. I'll move of those over to DISCUSSION.md and try to make sure everything is there, and then we can discuss that.
(@jfbastien, There appear to be no "demonstration below", only a png.)
lars-t-hansen commentedon Aug 24, 2015
[This is the discussion thread on the original spec that gave rise to the present bug.]
jyasskin / 4:35 PM Mar 2:
+ogiroux@gmail.com has another API at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4195.pdf that's based on Futex-y primitives but may be easier to work with. It can be implemented as a library on top of what your proposal already has, so it's not essential, just something to be aware of.
Lars Hansen / 4:54 PM Mar 2:
Thanks, very helpful.
* Hans Boehm / 9:00 PM Mar 2:*
I second Jeffrey's recommendation. Especially since futexes don't seem to be universally supported everywhere?
Lars Hansen / 7:30 PM Mar 3:
Futexes supply the API but not even on Linux were we planning to use the native futexes directly.
(I like the "synchronic" API much better than futexes and will investigate it as a replacement.)
JF Bastien / 5:43 PM Mar 4:
+1 on synchronic. On feasability: PNaCl exposes a restricted futex on Linux/Windows/OSX, and it works, but I agree that it should be an implementation detail of synchronic.
JF Bastien / 11:19 PM Mar 4:
For details on NaCl's futex, see:
https://chromium.googlesource.com/native_client/src/native_client/+/master/src/untrusted/irt/irt.h
Lars Hansen / 10:50 AM Aug 21:
Synchronic works poorly with asm.js and has not been included in the new spec. There's a section on synchronic below that addresses this in more detail.
Olivier Giroux / 4:14 AM Aug 22:
The exact API for synchronic has been in flux lately. What I'd like to focus on, if you guys are interested in a discussion about it, are the semantics. I would like to make a case for weaker semantics than futex guarantees, primarily for performance reasons.
The only essential difference between a synchronic and a futex is that the former is allowed to just poll for a while and skip the OS involvement if the condition was met during polling. This difference means that a synchronic can sometimes be satisfied in <100ns, when the minimum cost for futex is more like ~50us. A good-QOI implementation of synchronic will rapidly fallback to a lower-energy mechanism to avoid wasting resources, which could involve both yielding and eventually the OS queue as a last-resort.
When you code against futex directly then you're on the hook to mix polling, yielding and futex to cover the range of temporal response. This is a sort of dark art. I'm sure if you apply yourself then you can all master it, but do all your users need to?
I've been developing the synchronic library to try to prevent that. The API isn't the most essential thing about it, it's the idea of putting a gasket on the complexity that most users don't need. Secondarily, I'm putting a gasket on the portability problems too - Mac OS X and iOS aren't so well equipped as Linux and Windows in this department.
I would love more feedback.
Cheers,
Olivier
lars-t-hansen commentedon Aug 31, 2015
(Visibility: @ogiroux @jfbastien)
I really like synchronic (the spec and the code I've seen so far, anyway - Olivier's original paper and the code that was on Google Code). For programming in plain JS, in contrast with asm.js, I would want to stay away from futexes and use synchronic cells as the primitives in most cases.
So far, though, futexes have seemed like the better common primitive API for asm.js and plain JS. There are a couple of reasons.
Futexes are simple - no cross-worker storage management is needed beyond agreeing on an address, and no procedural initialization is needed either, so the protocols invoved are simple. In contrast, a synchronic requires at least a couple of cells - arguably the size depends on the type of datum held in the synchronic and is variable - and may require some initialization, so the protocol is a bit more complicated. One of the uses for futexes and synchronic will be to implement pthreads for translated C/C++, with a potentially unbounded number of locks, so the complexity of these protocols is not beside the point, though I don't want to overstate my case here, I'm not saying it wouldn't work.
Also, I think we'll need plain atomics regardless of whether we have synchronic or not, so synchronic does not have secondary benefits in API size reduction or whatever.
Finally, when programming in plain JS we probably want synchronics to be objects, while in asm.js they can't be (no GC, for starters). This isn't a huge consideration, but having "two kinds of synchronics" isn't appealing, at least not yet.
At the same time, futexes are hard to use; I've implemented a synchronic API for JS on top of futexes and I've been experimenting with spin loops for performance, and of course the performance improves when I guess right, but the guessing is hard. It would be lovely to abstract that away. So I've been wondering whether it would be possible and desirable to keep the futex API with its simplicity of one location of known size and no initialization protocol, but to incorporate the fast-wait idea from synchronic into it. This probably would be similar to Olivier's expectUpdate primitive, I'm not sure yet.
jfbastien commentedon Oct 23, 2015
Synchronic was pretty heavily revised by @ogiroux in P0126R0, and it looks like it's going forward with a few wording changes. I think the new interfaces will address some of @lars-t-hansen's concerns.
lars-t-hansen commentedon Jan 15, 2016
The new API in that document is very compact compared with the old one (I'm surprised at some of the omissions actually) but I don't understand how it addresses any of my concerns, exactly (see my Aug 31 remark above).
Anyway I just want to note that I'd like to look into a synchronic API for JS in earnest after the January TC39 meeting, to see if we can find something that's workable for JS and asm.js. I've been using synchronics (implemented on top of futexes) in various sample and demo programs and in addition to the promise of better performance they are a lot less error-prone and cumbersome than futexes.
A good goal would be to hammer out a strawman API and a rough implementation by the end of February.
lars-t-hansen commentedon Feb 18, 2016
@ogiroux / @jfbastien, I have some questions about the revised synchronic proposal referenced above.
The proposal states, "Invocations of the expect functions that are unblocked by the invocation of a notify function may re-evaluate the user-provided predicate and block again." Am I to take that literally -- the proviso only applies to the predicate form -- or is it an oversight in the proposal, and it applies also to the value form?
Is there an updated document for synchronic or is the 2015-09-24 version the latest?
Is there a prototype implementation of this proposal somewhere?
lars-t-hansen commentedon Feb 18, 2016
Ah, looks like @ogiroux's github repo has current code.
lars-t-hansen commentedon Feb 18, 2016
OK, so putting the current code and the current proposal together with Olivier's last comment above, I now understand better. The current synchronic proposal really is "only" a better (more performant) futex, it is not the flexible atomic cell with reliable signaling from the older proposal.
Since expect_update / expect_update_for are a drop-in replacement for futexWait and notify with the special case of a do-nothing user function is a drop-in replacement for futexWake, it's probably the case that these synchronics could replace the futexes in the current JS proposal without much risk. Given the promise of better performance they probably should, if we can get the API worked out.
We'd lose the direct ability to wake some number 1 < k < all of waiting threads, and futexWakeOrRequeue is probably lost too. I expect neither is critical.
jfbastien commentedon Feb 18, 2016
Latest paper: http://open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0126r1.pdf
taisel commentedon Feb 19, 2016
I'm fine with SHM being delayed in movement to production if it means continued API changes for performance and efficiency reasons. My own concern is ports to JS from C++, and I'm interested in the level of care for porting these API changes will bring about.
lars-t-hansen commentedon Feb 24, 2016
@jfbastien, @ogiroux, @binji
A proposal for synchronics in JS is up. The intent is to replace futexes with these.
Comments and feedback on the proposal would be most welcome (notably see the Discussion section, where there are some items that are really questions and open issues), this bug is a good place for feedback. If all I hear is crickets I will contact some of you directly next week.
The proposal text is in this repo on the branch "synchronic", in tc39/synchronic.html.
binji commentedon Feb 29, 2016
I like the proposal. Have you explored porting the emscripten pthread support using synchronics instead of futexes? I'm not too concerned about code that uses futexes currently; it sounds like you didn't find much.
OTOH, I am curious if there are many examples of implementations of various synchronization primitives using synchronics. There are many with futexes. Though maybe this is a good thing, as it will discourage people from implementing their own primitives. :)
lars-t-hansen commentedon Mar 1, 2016
I have looked at that some. It's a mixed bag (this is from looking at the MUSL implementation that we use for Emscripten): Some places the library uses futex-in-a-loop to implement a synchronic, sometimes even with a preceding spin-wait. Other places it's more complicated.
I'm starting to believe that synchronics are complementary to futexes, or that futexWait is a variation on expectUpdate that checks its condition going in but not after that, but I'm not quite there yet.
I spent some time today building a lock and condition variable implementation on top of synchronics. Effectively - to get the desirable semantics - I ended up reimplementing in JS some of the logic from the futex implementation, notably in order to be able to wake just one waiter. That's not necessarily a problem, since synchronics got the job done, the code may well be faster than the futex-based implementation, and synchronics can be used for much faster custom synchronization. It just adds to the burden for the application programmer, if that's all we provide.
ogiroux commentedon Mar 1, 2016
In my github there are example implementations of various locks and barriers. Easing the emulation of condition variables was not really a goal and I agree that you end up rolling your own futex in order to do that.
Just having support for the wake-one semantic carries a cost to performance even if you never use it. I don’t have a good sense of how often that is really necessary in practice. My sense is that most people will not write that code you wrote to emulate it, because they don’t actually need it - for example, you should not feel like you need it for locks and barriers.
Then, if I had a choice of two features to have, then I’d prefer {synchronic + condition variable} over {synchronic + futex}.
27 remaining items
ogiroux commentedon Mar 22, 2016
On the strawman nature of std::mutex : I think I'm fine with that because during this work I have already caused some shame to one vendor, who happened to improve their std::mutex tremendously in the next release. Everyone got a win out of that. Would be nice if that happened on OS X too. :^)
On the allocation idea : I didn't mean to say that the synchronic object needed to live in the shared array, but I wanted to point out that the user's one special ability was the ability to use words in that memory. It might make for an ugly API but as a thought experiment, imagine if calls of synchronic member functions were provided with locations in that memory to use for acceleration. Then the overarching goals could still be met within the envelope -- but until someone has a clever idea the API would be ugly.
pizlonator commentedon Mar 22, 2016
@ogiroux I think that such an API would be harder to use than the futex API.
jfbastien commentedon Mar 22, 2016
IIUC @pizlonator your main objection is that the spec currently limits 1 synchronic per SAB?
A developer can of course create multiple SABs, but that's silly. What about SAB+int?
pizlonator commentedon Mar 22, 2016
-Filip
Are you proposing that every client will preallocate a pool of synchronics and then hash mutex addresses to select some synchronic? That sounds like what futexes do for you already, except than futexes do it a lot better.
If you have N synchronics then you have to choose between some ugly solutions:
every call to lock/unlock hashes the lock address to compute a synchronic index. This slows down uncontended critical sections, probably by a lot more than we want.
use synchronics like you use futexes: only access the synchronic on the slow path of your own locking algorithm. This eliminates any advantages of synchronic since now the client must write their own wait loop.
Both approaches require the client to manage their own concurrent hashing of synchronics, which is something that futexes do for you. The first approach is hella slow and the second approach requires the client to implement their own futex-style concurrent hashing.
I still believe that this is the wrong approach. We should stick with futexes.
ogiroux commentedon Mar 23, 2016
I join in doubt that the approach strawman just outlined is a good one.
One would probably either allocate exactly as many instances of synchronic state as needed (however that is done with the api) or would treat it the same as Futex by e.g. considering notify() to be expensive. It follows that if you can only have one copy of synchronic state and that is not the exact number you need, then you would treat it as being expensive.
There is a way to tell synchronic that you think it's expensive already in the C++ paper p0126r2 (note: this is the one part that is handled slightly differently in the implementation, which I think is further to the benefit of this type of use actually). When you use this option, it basically becomes a pass-through to Futex on platforms that have it. On platforms that don't have Futex, it has the freedom to desugar into something that is still less than Futex polyfill at least in part because "notify one" is always only a hint for synchronic. On your platform it could literally use your parking lot.
Still, it's better if you can have enough state so that you can leave it on full-automatic. It's too bad that is difficult to do with the TC39 proposal.
taisel commentedon Mar 23, 2016
What I think the underlying issue here is that Synchronics is only one tool, and is not always the best tool to use. That being said, there are numerous cases where it is the best tool, but the older, more familiar futex and mutex tools have their own use cases as well.
The question should be then, what is there against having more than one "tool" available? I see the primary way to avoid misuse is by presenting properly made tutorials on these APIs, rather than by limiting the amount of tools in the tool shed you can use.
lars-t-hansen commentedon Mar 23, 2016
The issue that the SharedArrayBuffer is the only shared object type was known from the start, see my earliest remarks on this bug and the reason why I was resistant to synchronics at the time. Futexes were chosen at the outset of the SAB project explicitly because there is no object management to worry about other than picking a word in memory. (The performance issues described above were not a consideration - or at least not to my knowledge - only the fit to the problem.) Futexes were also an obvious good fit for implementing pthreads, as Filip also points out.
The JS proposal for synchronics was developed to stay within the constraint of being able to share only SharedArrayBuffer objects, and not allowing the internal state of the synchronic to be visible in the SharedArrayBuffer. As Filip noted above, this forces an internal representation where data are managed behind the program's back by the implementation of synchronics. For the small thread counts that we're currently seeing this might not have been a terrible problem but it's clearly true that it would not scale well.
I think it's time to put synchronics aside for now and move forward with the futexes we have - they are probably the better fit for the constraints we have.
And I apologize for not making this excursion properly data-driven. One data point is hardly sufficient.
(The discussion opens up a couple of issues around the TC39 futexes too, eg whether the fairness baked into them will get in the way of parallelism and whether it will now be useful, as very early versions of the spec had it, to expose relax/yield/pause type primitives to aid fast locks. But I will open separate issues for those.)
taisel commentedon Mar 23, 2016
Aww, the API was flawed on a low level? No possibility of providing their benefit over futexes in another proposal, or will that be rolled into futexes as well? I'm still looking forward to platform specific spins being hidden behind an API.
Edit: I agree about leaving futexes in, but I'm wondering what's blocking attempts to cover all optimal threading cases in further API additions if synchronics in the current proposal is unfit.
ogiroux commentedon Mar 23, 2016
I don't disagree with the outcome here given the context. I would like to end on a summary of why the outcome is right.
For efficient waiting, the combination of user + platform code needs to use some byte(s) of shared memory to decide if the slow path or the fast path should be taken. Also, the association between that state and the synchronization variable has to be O(1), which usually means they are side-by-side. As things stand with SAB only the user can use SAB, and in particular emplace "objects" there.
The consequence is that only the user can implement waiting prior to the slow-path-taken decision. A user could write synchronic on his own, with state in the SAB, but one can't be provided for him.
@taisel: if my conclusion is correct, then it casts a shadow over any prospective encapsulation of waiting that helps programmers use futex well.
@lars-t-hansen: I don't see how you could avoid relax/yield/sleep. You are set on a path where you'll need them. Wouldn't you say?
jfbastien commentedon Mar 23, 2016
Right, synchronic would need to be an actual JS object, not magically tied to a SAB, to be efficient.
@lars-t-hansen IIUC that wasn't considered because of asm.js? If we ignore asm.js and look at SAB from a pure JS perspective, would it make sense to have synchronic then?
pizlonator commentedon Mar 23, 2016
@jfairbank @lars-t-hansen I think it comes down to what is easier to reduce to what. You can implement synchronic on top of futex, or you can implement futex on top of synchronic. But if you implement futex on top of synchronic (or, rather, a bunch of synchronics) then unless you do some tricks you will have bad performance. Probably you'll have to implement your own concurrent hash map. On the other hand implementing synchronic on top of futex is less difficult.
From that standpoint, even if asm.js wasn't the primary use case, we would still want futex over synchronic. Futex is the better "kernel" feature, since it's easier to reduce other primitives to it. Synchronic is something you add when you already have other stuff.
(Thinking bigger, I think that in future languages any memory location that is shared should support the following primitives in addition to read/write:
This would mirror the way it works in C if you have a futex library lying around.)
jfbastien commentedon Mar 24, 2016
I'm somewhat loath to let web developers figure out the right balance between spin, yield and sleep. Sure it'll be done by toolchains, but what I like about synchronic is that the VM figures it out for you instead. We can change it as the platforms evolve and we can also prioritize things based on factors the web cares about more than typical native platforms.
It's still possible for developers to silly-spin, but something like synchronic gives them the tool to do the Right Thing. I feel like in most cases futex gives them that tool a bit too late, and it's somewhat blunt.
Assuming the storage issue (which leads to a fast-path slowdown) is solved, do you have other concerns @pizlonator?
pizlonator commentedon Mar 24, 2016
@jfbastien in a perfect world where doing the side-table lookup is free, I would have no objections.
I object to the suggestion that a side table lookup can be made to be free. Note that the fastest possible unlock path is a CAS, which is much cheaper than a side-table lookup. A side-table lookup will either have to acquire and release some other lock or it will have to use high-overhead lock-free hash map things. Either way that's super expensive. I believe that we are talking about a fundamental trade-off here and the futex API is the way that it is because that's how you ensure that fast paths are fast.
lars-t-hansen commentedon Mar 24, 2016
@ogiroux:
That's what I fear. As I wrote above, a very early version of this spec had an Atomics.pause() operation that was simply meant to have the effect of the PAUSE instruction of the x86. I am older and wiser now, and see that that may not be sufficient. I've opened Issue #87, let's take the discussion there.