Discussion:
A Proposal for C++ Concurrency
(too old to reply)
Mingxin Wang
2017-04-21 10:35:59 UTC
Permalink
In the past two years, I have been trying to conclude the lack of support
for various concurrent programming requirements among existing solutions.
After 87 times of reconstruction, I have concluded the issue into two major
problems and solved them.

*The Problems*

*1. The architecture: how to structure concurrent programs like serial ones
as flexible as function calls*

“Function” and “Invoke” are the basic concepts of programming, enabling
users to wrap their logic into units and decoupling every parts from the
whole program. Based on my solution, these concepts can be naturally
generalized in concurrent programming, *enabling u**sers to structure
concurrent programs like serial ones as flexible as function calls*.

*2. The algorithm: how to implement synchronization requirements to adapt
to different runtime environment and performance requirements*


*void solve_1(std::size_t n) { std::vector<std::future<void>> v; for
(std::size_t i = 0; i < n; ++i) {
v.emplace_back(std::async(do_something)); } for (auto& f : v) {
f.wait(); }}Figure 1void solve_2(std::size_t n) { std::atomic_size_t
task_count(n); std::promise<void> p; for (std::size_t i = 0; i < n; ++i)
{ std::thread([&] { do_something(); if
(task_count.fetch_sub(1u, std::memory_order_release) == 1u) {
std::atomic_thread_fence(std::memory_order_acquire); p.set_value();
} }).detach(); } p.get_future().wait();}Figure 2*

Suppose there’s a common requirement to implement a model that *launch n
async tasks and wait for their completion*. Implementations

- may maintain *n* "promises" for each task and perform several Ad-hoc
synchronization operations (some other advanced solutions e.g. the “
*Coroutine*” work on the same principle), as is shown in *Figure 1*, or
- may manage an atomic integer maintaining the unfinished number of
tasks (initially, *n*) with lock-free operations, and let the first (*n
- 1*) finished tasks synchronize with the last finished one, then let
the last finished task perform an Ad-hoc synchronization operation to
unblock the model (some other advanced solutions such as the “*Latch*”
or the “*Barrier*” work on the same principle), as is shown in *Figure 2*
.

It is true that "*sharing is the root of all contention*". The first
implementation may introduce more context switching overhead, but the
contention is never greater than 2. Although the second implementation has
better performance with low concurrency, when concurrency is high, the
contention may vary from 1 to n, and may prevent progress. For some
performance sensitive requirements, *a "compromise" of the two solutions is
probably more optimal*. With the support of my solution, *users are free
to **choose algorithms for synchronizations based on platform or
performance considerations*.

*Thanks to the Concepts TS*, I was able to implement the entire solution in
C++ gracefully, making it easier for users to debug their code implemented
with my solution. *I hope this solution is positive for improving the C++
programming language.*

*Considerations*

*Execution Structures*

In concurrent programs, executions of tasks always depend on one another,
thus the developers are required to control the synchronizations among the
executions; these synchronization requirements can be divided into 3 basic
categories: *“one-to-one”, “one-to-many”, “many-to-one”*. Besides, there
are “many-to-many” synchronization requirements; since they are usually not
“one-shot”, and often be implemented as a “many-to-one” stage and a
“one-to-many” stage, they are not fundamental ones.

“Function” and “Invoke” are the basic concepts of programming, enabling
users to wrap their logic into units and decoupling every parts from the
entire program. Are these concepts able to be generalized in concurrent
programming? The answer is *YES*, and that’s what my work revolves around.

When producing a “Function”, only the requirements (pre-condition), input,
output, effects, synchronizations, exceptions, etc. for calling this
function shall be considered; who or when to “Invoke” a “Function” is not
to be concerned about. When it comes to concurrent programming, there shall
be a beginning and an ending for each “Invoke”; in other words, a
“Concurrent Invoke” shall begin from “one” and end up to “one”, which forms
a “*one-to-many-to-one*” synchronization.

<Loading Image...>
*Figure 3*

The most common concurrent model is starting several independent tasks and
waiting for their completion. I define this model as "*Sync Concurrent
Invoke*". A typical scenario for the "Sync Concurrent Invoke" model is
shown in *Figure 3*.

<Loading Image...>
*Figure 4*

<Loading Image...>
*Figure 5*

*Figure 4* is one slide from *Herb Sutter's* previous talk: "*blocking is
harmful*", and "you can always turn blocking into non-blocking at a cost of
occupying a thread". Nonetheless, is there a "more elegant" way to avoid
blocking? Yes, there is, *just let the execution agent that executes the
last finished task in a "Sync Concurrent Invoke" to do the rest of the
works* (*the concept "execution agent" is defined in C++ ISO standard
30.2.5.1: An execution agent is an entity such as a thread that may perform
work in parallel with other execution agents*). I define this model as "*Async
Concurrent Invoke*". A typical scenario for the "Async Concurrent Invoke"
model is shown in *Figure 5*.

<Loading Image...>
*Figure 6*

The "Sync Concurrent Invoke" and the "Async Concurrent Invoke" models are
the static execution structures for concurrent programming, but not enough
for runtime extensions. For example, when implementing a concurrent
quick-sort algorithm, it is hard to predict how many subtasks will be
generated. So we need a more powerful execution structure that can expand a
concurrent invocation, which means, to add other tasks executed
concurrently with the current tasks in a same concurrent invocation at
runtime. I define this model as "*Concurrent Fork*". A typical scenario for
the "Concurrent Fork" model is shown in *Figure 6*.

<Loading Image...>
*Figure 7*

<Loading Image...>
*Figure 8*

With the concept of the "Sync Concurrent Invoke", the "Async Concurrent
Invoke" and the "Concurrent Fork" models, we can easily build concurrent
programs with complex dependencies among the executions, meanwhile, stay
the concurrent logic clear. *Figure 7* shows a typical scenario for a
composition of the "Sync Concurrent Invoke" and the "Concurrent Fork"
models; *Figure 8* shows a more complicated scenario.

From the "Sync Concurrent Invoke", the "Async Concurrent Invoke" and the
"Concurrent Fork" models, we can tell that:

- the same as serial invocations, the "Sync Concurrent Invoke" and the
"Async Concurrent Invoke" models can be applied recursively, and
- by changing "Sync Concurrent Invoke" into "Async Concurrent Invoke",
we can always turn blocking into non-blocking at a cost of managing the
execution agents, because it's hard to predict which task is the last
finished; users are responsible for the load balance in the entire program
when applying the "Async Concurrent Invoke" model, and
- applying the "Concurrent Fork" model requires one concurrent
invocation to expand, no matter the invocation is a "Sync" one or an
"Async" one.

*Synchronizations*

*One-to-one*

The "one-to-one" synchronization requirements are much easier to implement
than the other two. Providing there are two tasks named A and B, and B
depends on the completion of A, we can simply make a serial implementation
(sequentially execute A and B) with no extra context switching overhead. If
task A and B are supposed to be executed on different execution agents
(maybe because they attach to different priorities), extra overhead for the
synchronization is inevitable, we may let another execution agent to
execute B after A is completed. Usually we can implement such "one-to-one"
synchronization requirements by starting a thread or submitting a task to a
threadpool, etc.; besides, many patterns and frameworks provide us with
more options, for example, the well-known "Future" pattern.

<Loading Image...>
*Figure 9*

Currently in C++, the "Future" plays an important role in concurrent
programming, which provides Ad-hoc synchronization from one thread to
another, as is shown in *Figure 9*. It is apparent that "one-to-many" and
"many-to-one" synchronization requirements can be converted into multiple
"one-to-one" ones. Thus the "Future" can be used to deal with any
synchronization situation with nice composability.

Besides, there are many primitives supported by various platforms, such as
the "Futex" in modern Linux, the "Semaphore" defined in the POSIX standard
and the "Event" in Windows. The "work-stealing" strategy is sometimes used
for the "one-to-one" synchronization requirements, such as the Click
programming language, the "Fork/Join Framework" in the Java programming
language and the "TLP" in the .NET framework.

*One-to-many*

The "one-to-many" synchronization requirements are just as easy as the
"one-to-one" ones most of the time. However, when a "one-to-many"
synchronization requirement is broken down into too many "one-to-one" ones,
it will introduce too much extra overhead.

One solution to this problem is to perform these "one-to-one"
synchronization operations concurrently. Suppose we have 10000 tasks to
launch asynchronously, we can divide the launching work into 2 phases,

- launch other 100 tasks,
- each task launched in the previous step launches 100 tasks
respectively.

So that we can finish launching within 200 (instead of 10000) units of
"one-to-one" synchronization time, and that’s the bottle neck for 2 phases.
Similarly, if we divide the launching work into 4 phases, we can finish
launching within 40 (instead of 200) units of "one-to-one" synchronization
time.

<Loading Image...>
*Figure 10 - f(x) = x*n^(1/x), for n = 10000*

Generally, if we divide a launching work of *n* tasks into *x* phases, the
minimum unit of time required to finish it is a function of *x*, *f(x) =
x*n^(1/x)*, whose graph is similar with *Figure 10*. It is apparent that
*f(0+)->+∞* and *f(+∞)->+∞*. Let *f'(x)=0* and we obtain *x=ln(x)*, where
*f(x)* is minimum. When *x=ln(x)*, the ideal maximum number of tasks that
each task may split into is *n^(1/ln(n))=e*, which is a constant
number greater than *2* and less than *3*. When the maximum number of tasks
that each task may split into is *x*, the minimum unit of time required to
finish the work is a function of *n* and *x*, *g(n, x)=x*log(x,n)*, it is
apparent that *g(n,2)>g(n,3)* holds when *x* is greater than *1*, thus when
a launching work of *n* tasks is divided into some phases, and adequate
execution resources are provided, *it is theoretically optimal to divide
each work into 3 smaller ones.*

*Many-to-one*

<Loading Image...>
*Figure 11*

As mentioned earlier, the most common methods to implement the
"many-to-one" synchronization requirements are to break it down into
multiple "one-to-one" synchronizations, and to use an atomic integer
maintaining with lock-free operations to let the first finished tasks
synchronize with the last finished one. The advantages and disadvantages of
the two methods complement each other, as is shown in *Figure 11*.

void solve_2(std::size_t n) {
std::atomic_size_t task_count(n - 1u);
std::promise<void> p;
for (std::size_t i = 0; i < n; ++i) {
std::thread([&] {
do_something();
if (task_count.fetch_sub(1u, std::memory_order_release) == 0u) {
std::atomic_thread_fence(std::memory_order_acquire);
p.set_value();
}
}).detach();
}
p.get_future().wait();
}
*Figure 12*

void solve_2(std::size_t n) {
std::atomic_size_t task_count(n - 1u);
std::promise<void> p;
for (std::size_t i = 0; i < n; ++i) {
std::thread([&] {
do_something();
if (task_count.fetch_sub(1u, std::memory_order_release) == 0u) {
std::atomic_thread_fence(std::memory_order_acquire);
p.set_value();
}
}).detach();
}
p.get_future().wait();
}
*Figure 13*

Note that the state of "0" for the atomic integers is never utilized, when
using atomic integers to maintain the number of unfinished tasks. The
number of unfinished tasks is able to map to range *[0, n)*, so that the
implementation shown in *Figure 2* can be reconstructed, as is shown in *Figure
12* and *Figure 13*.

Inspired from the class "*LongAdder*" in the Java programming language, I
found it helpful to split one atomic integer into many "cells" to decrease
contention and increase concurrency in operations on the integers.
Unfortunately, although this method can reduce the complexity of writing,
it increases the complexity of reading, e.g. if we are to check whether an
integer becomes 0 and subtract 1 from it (this is exactly the requirement
in the preceding paper), the operations that a "LongAdder" will likely
perform are as follows:

- sum up the cells [1, 2, 3] and we get 6,
- check whether 6 equals to 0, and we get [FALSE],
- choose a cell at random [1, 2, 3],
- subtract 1 from the chosen cell [1, 1, 3], and the total complexity is
O(*number of cells*).

Other algorithms and data structures such as the "combining tree" models
and the "counting network" models also introduce diverse extra overhead
while used to solve this challenge.

<Loading Image...>
*Figure 14*

Then I learnt from the class "*Phaser*" in the Java programming language
that instead of splitting an integer into independent "cells", it is better
to "*tiering them up to form a tree*". Since the class "Phaser" has more
functions than just "tiering", and it is not convenient to control
contentions on each node, I improved the design based on "single
responsibility principle" that enables users to set the upper limit of the
contention as they expect. I define the new design as "*Tree Atomic Counter*",
whose property is shown in *Figure 14*.

Similar with other widely used tree-shaped data structures, a "Tree Atomic
Counter" is composed of several nodes. Each node holds an atomic integer
and a reference to its parent. Each "Tree Atomic Counter" associates with a
constant integer *MAX_N*, which represents the maximum count of its each
node, in other words, the count of each node belongs to the interval *[0,
MAX_N]*. This property guarantees that the contention on each node never
exceeds *(MAX_N + 1)*. When tiering one node to another, the count of the
parent node is increased by *1*.

The structure of the "Tree Atomic Counter" has the following properties:

- the count represented by a "Tree Atomic Counter" equals to the sum of
the count held by all its nodes,
- the root node holds an invalid reference (e.g. a null pointer).


<Loading Image...>
*Figure 15*

Unlike other widely used tree-shaped data structures such as the "Red-black
Tree" or the "AVL Tree", *the "Tree Atomic Counter" doesn’t require to be
balanced*. Moreover, *the shape of a "Tree Atomic Counter" has no effects
on its use or performance*. For the initialization of a "Tree Atomic
Counter", we can make it either balanced or completely unbalanced, as is
shown in *Figure 15*, just like a forward list!

<Loading Image...>
*Figure 16*

<Loading Image...>
*Figure 17*

When increasing a count on a node, there are two strategies:

- directly add the count to the node if the total count on this node
won’t exceed *MAX_COUNT*, as is shown in *Figure 16*, or
- attach a new tree on the node otherwise, as is shown in *Figure 17*.


If we are to check whether a "Tree Atomic Counter" becomes 0 and subtract 1
from it with a node, there are three strategies:

- decrease 1 from the node if the count of the node is not 0, or
- recursively perform this operation to the parent node if the parent
node is valid and the count of the current node equals to 0, or
- do nothing otherwise.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/026add85-da1b-449d-baa1-98954f2246fa%40isocpp.org.
Jens Maurer
2017-04-21 12:16:39 UTC
Permalink
In the past two years, I have been trying to conclude the lack of support for various concurrent programming requirements among existing solutions. After 87 times of reconstruction, I have concluded the issue into two major problems and solved them.
This is the std-proposals mailing list.

I have skimmed your text, but I'm not seeing proposed additions
to the C++ standard in there. Did I miss them? If not, which
classes or functions do you propose to be added in a future
revision of C++?

Jens
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/58F9F827.4070605%40gmx.net.
Mingxin Wang
2017-04-21 12:32:20 UTC
Permalink
Actually, I haven't submitted the draft for the solution yet because I
followed the first instruction on the "How To Submit a Proposal
<https://isocpp.org/std/submit-a-proposal>" page. It says only an initial
brief description is needed so far.

Do you mean that the draft is supposed to be submitted at this stage?
Post by Mingxin Wang
In the past two years, I have been trying to conclude the lack of
support for various concurrent programming requirements among existing
solutions. After 87 times of reconstruction, I have concluded the issue
into two major problems and solved them.
This is the std-proposals mailing list.
I have skimmed your text, but I'm not seeing proposed additions
to the C++ standard in there. Did I miss them? If not, which
classes or functions do you propose to be added in a future
revision of C++?
Jens
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/88202884-2e26-41cb-b2ea-0a889242440c%40isocpp.org.
Tony V E
2017-04-21 13:58:01 UTC
Permalink
Post by Mingxin Wang
Actually, I haven't submitted the draft for the solution yet because I
followed the first instruction on the "How To Submit a Proposal
<https://isocpp.org/std/submit-a-proposal>" page. It says only an initial
brief description is needed so far.
Do you mean that the draft is supposed to be submitted at this stage?
No, he means, of the things you talked about, what, exactly, do you want in
the next standard?
Do you want a function called std::solve_2()?
Do you want an "atomic tree counter"? What would that class look like?
(And have you looked at Lawrence Crawl's distributed counter papers?)

Can you show me C++17 code that I would need to write today, and then show
me how much better that code would look in C++20 if it had your new
features in C++20. Specifically - show me what _my_ code might look like,
if it used your new features. I don't need to see or know how your new
features were implemented, just the interfaces to those features. Mostly,
I need to see code that uses the features.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAOHCbitwpcimszf7YHOmTKy5bUgYF29Z82OQRWSEKVd6Qtg02Q%40mail.gmail.com.
Mingxin Wang
2017-04-21 14:22:51 UTC
Permalink
Thanks for your explanation! I was not familiar with the course. The
solution (together with the implementation and 5 examples) is as attached.
Post by Tony V E
Post by Mingxin Wang
Actually, I haven't submitted the draft for the solution yet because I
followed the first instruction on the "How To Submit a Proposal
<https://isocpp.org/std/submit-a-proposal>" page. It says only an
initial brief description is needed so far.
Do you mean that the draft is supposed to be submitted at this stage?
No, he means, of the things you talked about, what, exactly, do you want
in the next standard?
Do you want a function called std::solve_2()?
Do you want an "atomic tree counter"? What would that class look like?
(And have you looked at Lawrence Crawl's distributed counter papers?)
Can you show me C++17 code that I would need to write today, and then show
me how much better that code would look in C++20 if it had your new
features in C++20. Specifically - show me what _my_ code might look like,
if it used your new features. I don't need to see or know how your new
features were implemented, just the interfaces to those features. Mostly,
I need to see code that uses the features.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/26a66edc-b301-4de9-8478-64277609ba4a%40isocpp.org.
Jens Maurer
2017-04-21 18:59:01 UTC
Permalink
Thanks for your explanation! I was not familiar with the course. The solution (together with the implementation and 5 examples) is as attached.
I'm seeing a large-ish PDF with the following

- BinarySemaphore (only a concept; not a specific class, it seems)

As-is, this doesn't require that implementations of C++ standard libraries
actually provide a class (under which name?) that satisfies the concept.
While having the concept might be worthwhile, having a specific class
that actually is a binary semaphore also seems worthwhile.

- Atomic Counters

Again, this is just a concept, not actual classes people could use.
Are they supposed to be useful by themselves?
If so, why do we need three layers of abstraction here?
What's the difference / advantage over just using a std::atomic<unsigned long>
as a counter? Is there a useful self-contained abstraction
hidden somewhere here, e.g. a counting semaphore?

- ExecutionAgentPortal

I would much prefer to simply take a zero-argument "f"
(which might be a lambda) than to have a variadic "args..." interface.
The corresponding interface for std::thread was a design mistake.
Is there any advantage for the variadic interface, other than
proliferating more template arguments?

(lots more)


I'm still not seeing helpful examples here, or in the src.zip,
that I could connect to a real-world problem to be solved.

There is an Executors proposal currently under discussion
in SG1
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0443r1.html

that also tries to abstract the idea of an execution agent.
Can you solve your problems with that framework? If not, what is
missing?

Jens
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/58FA5675.5020005%40gmx.net.
Mingxin Wang
2017-04-22 01:25:28 UTC
Permalink
The Binary Semaphores and the Atomic Counters, ect., are required in the
core function templates (see the second clause in "*solution.pdf*"). Some
implementation for the requirements are provided in *src/solution* with *.h*
files, which are not completely documented (see *Figure 11* in "
*solution.pdf*"). As is mentioned in the "Intention" parts in the first
clause, these implementations may have various mechanisms, including some
primitives out of the C++ standard (for example, the "*Futex*"). These
implementations are only recomended, but not all of them are available on
every platform.

Examples are prepared to demonstrate basic usage for the library, and the
last example named "*example_5_application_concurrent_copy.cc*" shows an
application for concurrent copy algorithm. In order to make the examples
easy to understand, more complex applications are not provided, but that
not means those applications are not implementable with my solution. For
example, concurrent sort algorithms are much easier to implement with
"sync_concurrent_invoke" and "concurrent_fork" function templates.

I defined the "Execution Agent Portal" term because I found it helpful to
implement concurrent callable units. The "Execution Agent Portal" is more
abstract than the "Executor" proposed in this paper ("*A Unified Executors
Proposal for C++*"). "Execution Agent Portal" defined a method to submit an
execution task, no matter the task is executed sequentially (with the
current thread) or concurrently (with a new thread, a threadpool, ect.),
which means any "Executor" is convertible to an "Execution Agent Portal"
with a simple "Adapter" like this:
template <class Executor>
class ExecutorPortal {
public:
ExecutorPortal(Executor& executor) : executor_(executor) {}

template <class F, class... Args>
void operator()(F&& f, Args&&... args) {
executor_.execute(std::forward<F>(f), std::forward<Args>(args)...); //
Or maybe post or defer
}

private:
Executor& executor_;
};
Post by Mingxin Wang
Post by Mingxin Wang
Thanks for your explanation! I was not familiar with the course. The
solution (together with the implementation and 5 examples) is as attached.
I'm seeing a large-ish PDF with the following
- BinarySemaphore (only a concept; not a specific class, it seems)
As-is, this doesn't require that implementations of C++ standard libraries
actually provide a class (under which name?) that satisfies the concept.
While having the concept might be worthwhile, having a specific class
that actually is a binary semaphore also seems worthwhile.
- Atomic Counters
Again, this is just a concept, not actual classes people could use.
Are they supposed to be useful by themselves?
If so, why do we need three layers of abstraction here?
What's the difference / advantage over just using a std::atomic<unsigned long>
as a counter? Is there a useful self-contained abstraction
hidden somewhere here, e.g. a counting semaphore?
- ExecutionAgentPortal
I would much prefer to simply take a zero-argument "f"
(which might be a lambda) than to have a variadic "args..." interface.
The corresponding interface for std::thread was a design mistake.
Is there any advantage for the variadic interface, other than
proliferating more template arguments?
(lots more)
I'm still not seeing helpful examples here, or in the src.zip,
that I could connect to a real-world problem to be solved.
There is an Executors proposal currently under discussion
in SG1
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0443r1.html
that also tries to abstract the idea of an execution agent.
Can you solve your problems with that framework? If not, what is
missing?
Jens
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/6d6f9a00-fc4f-4306-9ca7-82a82999cdf6%40isocpp.org.
Mingxin Wang
2017-04-22 02:27:23 UTC
Permalink
I haven't read Lawrence Crawl's distributed counter papers yet, could you
please provide a full reference or a link? Thank you.
Post by Tony V E
Post by Mingxin Wang
Actually, I haven't submitted the draft for the solution yet because I
followed the first instruction on the "How To Submit a Proposal
<https://isocpp.org/std/submit-a-proposal>" page. It says only an
initial brief description is needed so far.
Do you mean that the draft is supposed to be submitted at this stage?
No, he means, of the things you talked about, what, exactly, do you want
in the next standard?
Do you want a function called std::solve_2()?
Do you want an "atomic tree counter"? What would that class look like?
(And have you looked at Lawrence Crawl's distributed counter papers?)
Can you show me C++17 code that I would need to write today, and then show
me how much better that code would look in C++20 if it had your new
features in C++20. Specifically - show me what _my_ code might look like,
if it used your new features. I don't need to see or know how your new
features were implemented, just the interfaces to those features. Mostly,
I need to see code that uses the features.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c41c5f33-b923-4ba1-82dc-64f344672170%40isocpp.org.
Tony V E
2017-04-22 03:25:57 UTC
Permalink
<html><head></head><body lang="en-US" style="background-color: rgb(255, 255, 255); line-height: initial;"> <div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br></div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br></div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);">‎http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0261r1.html</div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br></div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);">Google "Lawrence crawl distributed counter c++"</div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br></div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br></div> <div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br style="display:initial"></div> <div style="font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);">Sent&nbsp;from&nbsp;my&nbsp;BlackBerry&nbsp;portable&nbsp;Babbage&nbsp;Device</div> <table width="100%" style="background-color:white;border-spacing:0px;"> <tbody><tr><td colspan="2" style="font-size: initial; text-align: initial; background-color: rgb(255, 255, 255);"> <div style="border-style: solid none none; border-top-color: rgb(181, 196, 223); border-top-width: 1pt; padding: 3pt 0in 0in; font-family: Tahoma, 'BB Alpha Sans', 'Slate Pro'; font-size: 10pt;"> <div><b>From: </b>Mingxin Wang</div><div><b>Sent: </b>Friday, April 21, 2017 10:27 PM</div><div><b>To: </b>ISO C++ Standard - Future Proposals</div><div><b>Reply To: </b>std-***@isocpp.org</div><div><b>Subject: </b>Re: [std-proposals] A Proposal for C++ Concurrency</div></div></td></tr></tbody></table><div style="border-style: solid none none; border-top-color: rgb(186, 188, 209); border-top-width: 1pt; font-size: initial; text-align: initial; background-color: rgb(255, 255, 255);"></div><br><div id="_originalContent" style=""><div dir="ltr"><font face="georgia, serif">I haven't read Lawrence Crawl's distributed counter papers yet, could you please provide a full reference or a link? Thank you.</font><br><br>On Friday, April 21, 2017 at 9:58:06 PM UTC+8, Tony V E wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir="ltr"><br><div><br><div class="gmail_quote">On Fri, Apr 21, 2017 at 8:32 AM, Mingxin Wang <span dir="ltr">&lt;<a href="javascript:" target="_blank" gdf-obfuscated-mailto="_SHl_0oYDwAJ" rel="nofollow" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">***@163.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Actually, I haven't submitted the draft for the solution yet because I followed the first instruction on the "<a href="https://isocpp.org/std/submit-a-proposal" target="_blank" rel="nofollow" onmousedown="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fisocpp.org%2Fstd%2Fsubmit-a-proposal\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNGlLyCIYYQUZNTTJdUEpCYxvwG8Ig';return true;" onclick="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fisocpp.org%2Fstd%2Fsubmit-a-proposal\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNGlLyCIYYQUZNTTJdUEpCYxvwG8Ig';return true;">How To Submit a Proposal</a>" page. It says only an initial brief description is needed so far.<div><br></div><div>Do you mean that the draft is supposed to be submitted at this stage?<span><br></span></div></div></blockquote><div><br></div></div>No, he means, of the things you talked about, what, exactly, do you want in the next standard?<br></div><div>Do you want a function called std::solve_2()?<br></div><div>Do you want an "atomic tree counter"? What would that class look like?&nbsp; (And have you looked at Lawrence Crawl's distributed counter papers?)<br><br></div><div>Can you show me C++17 code that I would need to write today, and then show me how much better that code would look in C++20 if it had your new features in C++20.&nbsp; Specifically - show me what _my_ code might look like, if it used your new features.&nbsp; I don't need to see or know how your new features were implemented, just the interfaces to those features.&nbsp; Mostly, I need to see code that uses the features.<br><br><br></div></div>
</blockquote></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:std-proposals+***@isocpp.org">std-proposals+***@isocpp.org</a>.<br>
To post to this group, send email to <a href="mailto:std-***@isocpp.org">std-***@isocpp.org</a>.<br>
To view this discussion on the web visit <a href="https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c41c5f33-b923-4ba1-82dc-64f344672170%40isocpp.org?utm_medium=email&amp;utm_source=footer">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c41c5f33-b923-4ba1-82dc-64f344672170%40isocpp.org</a>.<br>
<br><!--end of _originalContent --></div></body></html>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:std-proposals+***@isocpp.org">std-proposals+***@isocpp.org</a>.<br />
To post to this group, send email to <a href="mailto:std-***@isocpp.org">std-***@isocpp.org</a>.<br />
To view this discussion on the web visit <a href="https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/20170422032557.5132370.26584.29071%40gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/20170422032557.5132370.26584.29071%40gmail.com</a>.<br />
Mingxin Wang
2017-04-22 06:19:22 UTC
Permalink
Dear Tony,

The paper provided
(‎http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0261r1.html)
proposes a design for the *distributed counter*, which reduces contention
in writing but "*increases costs to read the counter*". The mechanism of
the distributed counter is similar with the class "*LongAdder*" in the Java
programming language mentioned earlier in my post (Considerations,
many-to-one). Both "LongAdder" and the distributed counter split one atomic
integer into many independent units.

As the accurate value of the counter is not required at runtime in my
solution, *the "Tree Atomic Counter" is more optimal* because not only does
it reduce the contention, but also remains the complexity of reading always
to be *O(1)*, as is shown below.

<Loading Image...>
‎http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0261r1.html
Google "Lawrence crawl distributed counter c++"
Sent from my BlackBerry portable Babbage Device
*From: *Mingxin Wang
*Sent: *Friday, April 21, 2017 10:27 PM
*To: *ISO C++ Standard - Future Proposals
*Subject: *Re: [std-proposals] A Proposal for C++ Concurrency
I haven't read Lawrence Crawl's distributed counter papers yet, could you
please provide a full reference or a link? Thank you.
Post by Tony V E
Post by Mingxin Wang
Actually, I haven't submitted the draft for the solution yet because I
followed the first instruction on the "How To Submit a Proposal
<https://isocpp.org/std/submit-a-proposal>" page. It says only an
initial brief description is needed so far.
Do you mean that the draft is supposed to be submitted at this stage?
No, he means, of the things you talked about, what, exactly, do you want
in the next standard?
Do you want a function called std::solve_2()?
Do you want an "atomic tree counter"? What would that class look like?
(And have you looked at Lawrence Crawl's distributed counter papers?)
Can you show me C++17 code that I would need to write today, and then
show me how much better that code would look in C++20 if it had your new
features in C++20. Specifically - show me what _my_ code might look like,
if it used your new features. I don't need to see or know how your new
features were implemented, just the interfaces to those features. Mostly,
I need to see code that uses the features.
--
You received this message because you are subscribed to the Google Groups
"ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an
To view this discussion on the web visit
https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c41c5f33-b923-4ba1-82dc-64f344672170%40isocpp.org
<https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c41c5f33-b923-4ba1-82dc-64f344672170%40isocpp.org?utm_medium=email&utm_source=footer>
.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/9574f98d-8939-4c45-9559-be64c1ca3db2%40isocpp.org.
Jens Maurer
2017-04-21 14:13:41 UTC
Permalink
Actually, I haven't submitted the draft for the solution yet because I followed the first instruction on the "How To Submit a Proposal <https://isocpp.org/std/submit-a-proposal>" page. It says only an initial brief description is needed so far.
Do you mean that the draft is supposed to be submitted at this stage?
I'm not defining the rules, so I can't comment on "supposed".

You have given a long description (which I didn't read in detail),
but I'm missing specific (and preferably short) code examples showing
how to solve some specific problem with your proposed extension.
Showing the contrast of how you would solve the same problem without
using your extension often helps convincing, too.

Thanks,
Jens
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/58FA1395.7010107%40gmx.net.
dgutson .
2017-04-21 14:21:19 UTC
Permalink
Post by Mingxin Wang
Actually, I haven't submitted the draft for the solution yet because I
followed the first instruction on the "How To Submit a Proposal <
https://isocpp.org/std/submit-a-proposal>" page. It says only an initial
brief description is needed so far.
Post by Mingxin Wang
Do you mean that the draft is supposed to be submitted at this stage?
I'm not defining the rules, so I can't comment on "supposed".
You have given a long description (which I didn't read in detail),
but I'm missing specific (and preferably short) code examples showing
how to solve some specific problem with your proposed extension.
Showing the contrast of how you would solve the same problem without
using your extension often helps convincing, too.
Mingxin, I will echo Jens and Tony. It is evident that you spent a lot of
effort to write the email in a level of detail and beauty few times seen in
this list. The issue is, as Jens and Tony mention, that the following items
are not obvious or missing:

- Problem statement
- Why it is a problem
- How people is dealing with those problems nowadays (workaround?)
- What your solution is (as Tony suggests, a "before and after" your
proposed changes in terms of code, and if possible too, in terms of the
standard)

Please be as concise and brief as possible. I don't want you to be
discouraged of pursuing your idea, specially considering all the effort you
spent, so please focus on these observations so people can quickly spot
what are you talking about.

This should take no more than few lines.

Daniel.
Thanks,
Jens
--
You received this message because you are subscribed to the Google Groups
"ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an
To view this discussion on the web visit https://groups.google.com/a/
isocpp.org/d/msgid/std-proposals/58FA1395.7010107%40gmx.net.
--
Who’s got the sweetest disposition?
One guess, that’s who?
Who’d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-3z1ko14-e%2Bc2PW2xtZffRr_r5%2Bi6OZEs2itaMLsM_WqA%40mail.gmail.com.
Mingxin Wang
2017-04-21 14:45:35 UTC
Permalink
I suppose I have stated the issues at the beginning of my post. The two
problems are about the architecture and the synchronization algorithms
respectively. This proposal is designed to solve both problems.

Currently, some advanced solutions focus only on those "one-to-one"
synchronization requirements, such as the "Future" and the "Coroutine".
Although they have nice composability, they are usually not efficient
enough for those "many-to-one" synchronization requirements. And some other
solutions concentrate mainly on those "many-to-one" synchronization
requirements, such as the "Barrier" and the "Latch". They are usually
efficient but have less composability. Besides, it is not easy to control
the contention.
Post by dgutson .
Post by Mingxin Wang
Actually, I haven't submitted the draft for the solution yet because I
followed the first instruction on the "How To Submit a Proposal <
https://isocpp.org/std/submit-a-proposal>" page. It says only an initial
brief description is needed so far.
Post by Mingxin Wang
Do you mean that the draft is supposed to be submitted at this stage?
I'm not defining the rules, so I can't comment on "supposed".
You have given a long description (which I didn't read in detail),
but I'm missing specific (and preferably short) code examples showing
how to solve some specific problem with your proposed extension.
Showing the contrast of how you would solve the same problem without
using your extension often helps convincing, too.
Mingxin, I will echo Jens and Tony. It is evident that you spent a lot of
effort to write the email in a level of detail and beauty few times seen in
this list. The issue is, as Jens and Tony mention, that the following items
- Problem statement
- Why it is a problem
- How people is dealing with those problems nowadays (workaround?)
- What your solution is (as Tony suggests, a "before and after" your
proposed changes in terms of code, and if possible too, in terms of the
standard)
Please be as concise and brief as possible. I don't want you to be
discouraged of pursuing your idea, specially considering all the effort you
spent, so please focus on these observations so people can quickly spot
what are you talking about.
This should take no more than few lines.
Daniel.
Thanks,
Jens
--
You received this message because you are subscribed to the Google Groups
"ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an
To view this discussion on the web visit
https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/58FA1395.7010107%40gmx.net
.
--
Who’s got the sweetest disposition?
One guess, that’s who?
Who’d never, ever start an argument?
Who never shows a bit of temperament?
Who's never wrong but always right?
Who'd never dream of starting a fight?
Who get stuck with all the bad luck?
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/9f87ffe8-e7ab-4f4c-a183-28debc1ce670%40isocpp.org.
Vicente J. Botet Escriba
2017-04-22 14:02:33 UTC
Permalink
Hi,

I'm not sure you has been following the C++ Concurrency Wroking Group
proposals.
I would sugets you to take a look at the Concurrency TS, Parrallel
TS1/TS2, Couroutine TS and the papers associated to this working group
(if you have not already done it). Look for Concurrency.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/
...

There you will find the current trend. There are a lot of things on
going: more on memory model, more on atomics, Continuations, Executors,
task blocks, more Parallel Algorithms, Concurrent data structures, TLS,
Latches, Barriers, Distributed Counters, Concurrent queues, RCU,
Heterogeneous devices, Vectorization, SIMD, Fibers, Light-Weight
Execution Agents ...

If you don't find there what you are looking for then I will suggest you
to post here a concrete use case and why the current way has problems.
I'm not saying that there is nothing missing, sometime we don't know
everithing it is going on.

Then, if you believe you have a better solution, as suggested by others,
describe how we can solve it with C++17 + the current TS + the
proposals and how it could be solved with your prefered solution.

I'll suggest also to follow the schema: Motivation, Problem, proposal
with Before/After examples.

Vicente
Post by Mingxin Wang
I suppose I have stated the issues at the beginning of my post. The
two problems are about the architecture and the synchronization
algorithms respectively. This proposal is designed to solve both problems.
Currently, some advanced solutions focus only on those "one-to-one"
synchronization requirements, such as the "Future" and the
"Coroutine". Although they have nice composability, they are usually
not efficient enough for those "many-to-one" synchronization
requirements. And some other solutions concentrate mainly on those
"many-to-one" synchronization requirements, such as the "Barrier" and
the "Latch". They are usually efficient but have less composability.
Besides, it is not easy to control the contention.
Post by Mingxin Wang
Actually, I haven't submitted the draft for the solution yet
because I followed the first instruction on the "How To Submit
a Proposal <https://isocpp.org/std/submit-a-proposal
<https://isocpp.org/std/submit-a-proposal>>" page. It says
only an initial brief description is needed so far.
Post by Mingxin Wang
Do you mean that the draft is supposed to be submitted at
this stage?
I'm not defining the rules, so I can't comment on "supposed".
You have given a long description (which I didn't read in detail),
but I'm missing specific (and preferably short) code examples showing
how to solve some specific problem with your proposed extension.
Showing the contrast of how you would solve the same problem without
using your extension often helps convincing, too.
Mingxin, I will echo Jens and Tony. It is evident that you spent a
lot of effort to write the email in a level of detail and beauty
few times seen in this list. The issue is, as Jens and Tony
* Problem statement
* Why it is a problem
* How people is dealing with those problems nowadays (workaround?)
* What your solution is (as Tony suggests, a "before and after"
your proposed changes in terms of code, and if possible too,
in terms of the standard)
Please be as concise and brief as possible. I don't want you to be
discouraged of pursuing your idea, specially considering all the
effort you spent, so please focus on these observations so people
can quickly spot what are you talking about.
This should take no more than few lines.
Daniel.
Thanks,
Jens
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/bef7ee8a-bc91-ec69-3aa2-02f49ddc0011%40wanadoo.fr.
Mingxin Wang
2017-04-24 07:27:46 UTC
Permalink
Motivation

Executions, one-to-one synchronizations, many-to-one synchronizations and
one-to-many synchronizations are the basic concurrent programming
requirements (see my initial post, *Considerations part*). What we have for
the requirements in C++ is shown below.

<Loading Image...>

*My solution is particularly for the missing parts*, as is shown below
(items in red represent main content of my solution).

<Loading Image...>

The related proposals are shown below.

<Loading Image...>

Problems

(See my initial post, *Problems part*)

Proposal

(See *solution.pdf* attached with my earlier post)

Implementation

(See *src.zip/solution* attached with my earlier post)

<Loading Image...>

Examples

(See *src.zip/examples* attached with my earlier post)

<Loading Image...>

For the first example, I have 3 similar implementations without my solution
(see my initial post), which have limited extendibility as discussed
before, e.g., it is difficult for these implementations to control runtime
contention, but easy for implementations with support of my solution using
the explicit version for the “Concurrent Invoke” models and the “Tree
Atomic Counter”, as is shown below:

void solve(std::size_t n) {
std::atomic_size_t task_count(n);
std::promise<void> p;
for (std::size_t i = 0; i < n; ++i) {
std::thread([&] {
do_something();
if (task_count.fetch_sub(1u, std::memory_order_release) == 1u) {
std::atomic_thread_fence(std::memory_order_acquire);
p.set_value();
}
}).detach();
}
p.get_future().wait();
}
*Implementation before (1)*

void solve(std::size_t n) {
std::atomic_size_t task_count(n - 1u);
std::promise<void> p;
for (std::size_t i = 0; i < n; ++i) {
std::thread([&] {
do_something();
if (task_count.fetch_sub(1u, std::memory_order_release) == 0u) {
std::atomic_thread_fence(std::memory_order_acquire);
p.set_value();
}
}).detach();
}
p.get_future().wait();
}
*Implementation before (2)*

void solve(std::size_t n) {
std::atomic_size_t task_count(n - 1u);
std::promise<void> p;
for (std::size_t i = 0; i < n; ++i) {
std::thread([&] {
do_something();
std::atomic_thread_fence(std::memory_order_release);
std::size_t cur = task_count.load(std::memory_order_relaxed);
do {
if (cur == 0u) {
std::atomic_thread_fence(std::memory_order_acquire);
p.set_value();
break;
}
} while (!task_count.compare_exchange_weak(cur,
cur - 1u,

std::memory_order_relaxed));
}).detach();
}
p.get_future().wait();
}
*Implementation before (3)*

void solve(std::size_t n) {
con::sync_concurrent_invoke(
[] {},
con::make_concurrent_caller(
n,
con::make_concurrent_callable(
con::ThreadPortal<true>(),
con::make_concurrent_procedure(do_something))));
}
*Implementation after (1)*
void solve(std::size_t n) {
con::sync_concurrent_invoke_explicit(
con::TreeAtomicCounter<10u>::Initializer(),
con::DisposableBinarySemaphore(),
[] {},
con::make_concurrent_caller(
n,
con::make_concurrent_callable(
con::ThreadPortal<true>(),
con::make_concurrent_procedure(do_something))));
}
*Implementation after (2)*
It is more difficult to implement the other 4 examples above with full
considerations in architecture and performance (see my initial post, *Considerations
part*) without my solution.


On Saturday, April 22, 2017 at 10:02:40 PM UTC+8, Vicente J. Botet Escriba
Post by Vicente J. Botet Escriba
Hi,
I'm not sure you has been following the C++ Concurrency Wroking Group
proposals.
I would sugets you to take a look at the Concurrency TS, Parrallel
TS1/TS2, Couroutine TS and the papers associated to this working group (if
you have not already done it). Look for Concurrency.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/
...
more on memory model, more on atomics, Continuations, Executors, task
blocks, more Parallel Algorithms, Concurrent data structures, TLS,
Latches, Barriers, Distributed Counters, Concurrent queues, RCU,
Heterogeneous devices, Vectorization, SIMD, Fibers, Light-Weight Execution
Agents ...
If you don't find there what you are looking for then I will suggest you
to post here a concrete use case and why the current way has problems. I'm
not saying that there is nothing missing, sometime we don't know everithing
it is going on.
Then, if you believe you have a better solution, as suggested by others,
describe how we can solve it with C++17 + the current TS + the proposals
and how it could be solved with your prefered solution.
I'll suggest also to follow the schema: Motivation, Problem, proposal with
Before/After examples.
Vicente
I suppose I have stated the issues at the beginning of my post. The two
problems are about the architecture and the synchronization algorithms
respectively. This proposal is designed to solve both problems.
Currently, some advanced solutions focus only on those "one-to-one"
synchronization requirements, such as the "Future" and the "Coroutine".
Although they have nice composability, they are usually not efficient
enough for those "many-to-one" synchronization requirements. And some other
solutions concentrate mainly on those "many-to-one" synchronization
requirements, such as the "Barrier" and the "Latch". They are usually
efficient but have less composability. Besides, it is not easy to control
the contention.
Post by dgutson .
Post by Mingxin Wang
Actually, I haven't submitted the draft for the solution yet because I
followed the first instruction on the "How To Submit a Proposal <
https://isocpp.org/std/submit-a-proposal>" page. It says only an
initial brief description is needed so far.
Post by Mingxin Wang
Do you mean that the draft is supposed to be submitted at this stage?
I'm not defining the rules, so I can't comment on "supposed".
You have given a long description (which I didn't read in detail),
but I'm missing specific (and preferably short) code examples showing
how to solve some specific problem with your proposed extension.
Showing the contrast of how you would solve the same problem without
using your extension often helps convincing, too.
Mingxin, I will echo Jens and Tony. It is evident that you spent a lot of
effort to write the email in a level of detail and beauty few times seen in
this list. The issue is, as Jens and Tony mention, that the following items
- Problem statement
- Why it is a problem
- How people is dealing with those problems nowadays (workaround?)
- What your solution is (as Tony suggests, a "before and after" your
proposed changes in terms of code, and if possible too, in terms of the
standard)
Please be as concise and brief as possible. I don't want you to be
discouraged of pursuing your idea, specially considering all the effort you
spent, so please focus on these observations so people can quickly spot
what are you talking about.
This should take no more than few lines.
Daniel.
Thanks,
Jens
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/1c5b27d4-1509-457e-ae17-542a05b152a1%40isocpp.org.
Oliver Kowalke
2017-04-24 08:11:51 UTC
Permalink
What is the difference between utility and structural supports?
I would consider continuations as building blocks for fibers and coroutines.
A continuation acts as a ToE like threads.

Continuation (coroutine and fiber) can be used for n-m synchronization too
- it is not limited to 1-1 synchronization.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CA%2Bwfc19ezWXWrLWvxwfXxnjQ9o4k8G1EY4QOyyNdApPh%3DG%2BPgA%40mail.gmail.com.
Mingxin Wang
2017-04-24 09:41:10 UTC
Permalink
Here I mean,

- Utilities: the code we actually have (classes, functions...), and
- Interfaces: the code required for structuring (semantics,
requirements, concepts...), and
- Structural supports: how to build a program (methods, patterns,
language features...)

For example, for the basic function calls:

- The utilities are the functions in the standard library, and
- The interface is "function" itself, users are required to write code
with parameters and return values (and maybe exceptions, etc.), and
- The structural support is "invocation", and users are able to "invoke"
functions with specific syntax.


*Continuations do be able to be used for n-m synchronization*, and so do
any other solutions listed in the table. Because as mentioned in my initial
post, "'one-to-many' and 'many-to-one' synchronization requirements can be
converted into multiple 'one-to-one' ones". Although they can be used to
implement the synchronizations and have nice composability, *they are
usually not optimal in terms of performance*. For example, the "Latches"
usually have better performance than the "Futures" in many-to-one
synchronizations, as is shown below.

void solve(std::size_t n) {
std::vector<std::future<void>> v;
for (std::size_t i = 0; i < n; ++i) {
v.emplace_back(std::async(do_something));
}
for (auto& f : v) {
f.wait();
}
}
*Solve with the "Futures"*

void solve(std::size_t n) {
std::experimental::latch lat(n);
for (std::size_t i = 0; i < n; ++i) {
std::thread([&] {
do_something();
lat.count_down();
}).detach();
}
lat.wait();
}
*Solve with the "Latches"*
Post by Oliver Kowalke
What is the difference between utility and structural supports?
I would consider continuations as building blocks for fibers and
coroutines. A continuation acts as a ToE like threads.
Continuation (coroutine and fiber) can be used for n-m synchronization
too - it is not limited to 1-1 synchronization.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/4349ec3e-70c4-48fb-8125-ae7cbf3a118c%40isocpp.org.
Oliver Kowalke
2017-04-24 11:13:53 UTC
Permalink
Although they can be used to implement the synchronizations and have nice composability,
*they are usually not optimal in terms of performance*. For example, the
"Latches" usually have better performance than the "Futures" in many-to-one
synchronizations, as is shown below.
void solve(std::size_t n) {
std::experimental::latch lat(n);
for (std::size_t i = 0; i < n; ++i) {
std::thread([&] {
do_something();
lat.count_down();
}).detach();
}
lat.wait();
}
*Solve with the "Latches*
I don't see why equivalent code shouldn't be possible with continuations
(fibers).
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CA%2Bwfc187LODkY3p9yzm-pS0ibZBRuRX0pFWk3qV6UuYtp3JJAg%40mail.gmail.com.
Mingxin Wang
2017-04-24 16:06:19 UTC
Permalink
*Thank you for pointing out the problem about the charts!*

I am really sorry that the charts in the "Motivation" part were not
reasonable in the following aspects:

- The "Continuations" has nothing to do with synchronization, it is a
basic, low-level primitive, and
- The "Fibers" is defined as user-mode-scheduled-thread, which has
similar features with threads, thus it shall belong to the same category as
the "Threads" does, and
- The "Coroutines" is based on the concept of "Functions", which
introduces requirements for concurrent programming, thus it is an interface
(but it is not related to my solution), and
- All of the "Execution" requirements are "One-to-one synchronization"
requirements, and the two rows in the chart shall be merged.

The updated charts are as follows:

<Loading Image...>
*Before*

<Loading Image...>
*After*

<Loading Image...>
*Related Proposals*
Post by Oliver Kowalke
Although they can be used to implement the synchronizations and have nice composability,
*they are usually not optimal in terms of performance*. For example, the
"Latches" usually have better performance than the "Futures" in many-to-one
synchronizations, as is shown below.
void solve(std::size_t n) {
std::experimental::latch lat(n);
for (std::size_t i = 0; i < n; ++i) {
std::thread([&] {
do_something();
lat.count_down();
}).detach();
}
lat.wait();
}
*Solve with the "Latches*
I don't see why equivalent code shouldn't be possible with continuations
(fibers).
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3e8859f4-8ef7-44b1-9e8c-95b1d3aea474%40isocpp.org.
Mingxin Wang
2017-04-28 09:32:07 UTC
Permalink
Hello everyone,

Thanks to your suggestions, this proposal is available now.

I hope it is positive for improving the C++ programming language with your
instructions!

Sincerely,
Mingxin Wang
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/76d2d205-b447-4baf-9e3b-e727eb99bcee%40isocpp.org.
Loading...