[cpp-threads] Belated comments on dependency-based ordering proposal

[Boehm, Hans]

Here are some reactions to N2360
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2360.html),
and also to some extent N2359 and N2361, Paul's dependency-based
ordering proposals.

Although I realize that I'm late in replying, I think it might be useful
to have a bit more discussion, and possibly an updated proposal, before
Kona.

This is a bit different from where I thought we were headed in Toronto.

I'll use a couple of examples topoint out where I think my prior
understanding diverge from the proposal.

Consider example 1:

atomic<int *> x;
int y;
int v[N];

void f()
{
	int *i = x.load(memory_order_dependency);
	int j = *i;

	...

	y = j;
}

int g()
{
	return v[y];
}


Clearly the load of *i is dependent on the initial load of x, and hence
ordered relative to it.  But if I call f(); g(), is  the load of v[y] in
g() part of the same dependency tree?  Does this change if g is
annotated in some way?

My intuition is that the answer has to be no to both questions.
Otherwise it is very unlikely that the compiler will be able to see
enough of the dependency tree to take advantage of hardware
dependency-based ordering.  But I don't read the proposal that way.

Consider example 2:


atomic<int> x;
vector<int> v;

void f()
{
	int i = x.load(memory_order_dependency);
	int j = v[i];
	...
}

I don't think we can reasonably annotate the standard vector class.
Thus I don't know how to enforce the dependency ordering here, since
operator[] is elsewhere and not annotated.  If you don't enforce
ordering here, it seems to me the code becomes brittle in that if you
change a C array to a C++ library one, things are allowed to break.

I thought we had tentatively concluded in Toronto that all "data
dependent" loads occurring as a result of the execution of f() should be
in the dependency tree anyway, no matter whether they occurred as a
result of a nested function call or not.  If the value flows into a
separately compiled function, the compiler has to back off and treat
memory_order_dependency as memory_order_acquire.  This may add
unexpected overhead in some cases.  But examples like the above will be
guaranteed to work as expected.

But I think this also isn't reflected here?

My guess is that the N2360 approach (if I understood it correctly) might
be viable for C, where function calls are obvious in the source.  But
too many things in C++ are a function call behind the scenes.  I'm not
very comfortable with an approach that treats v[i] differently depending
on whether v is a C int[10] or a C++ std::array<int, 10>.  I think we'll
encounter many more problems along these lines, e.g also with loads in
destructors.

I suspect we need more work defining what it means t "consume the result
of a prior evaluation".  But someone from the C++ standards committee
core group will have to help there.

Hans