C++ Data-Dependency Ordering: Function Annotation

ISO/IEC JTC1 SC22 WG21 N2643 = 08-0153 - 2008-05-16

Paul E. McKenney, paulmck@linux.vnet.ibm.com
Lawrence Crowl, crowl@google.com, Lawrence@Crowl.org

Introduction

Data dependency ordering can provide significant performance improvements to concurrent data structures that are read frequently and seldom modified. The rationale and primary design for data dependency ordering is in the primary proposal, N2556. An understanding of that proposal is necessary to understanding this proposal.

Reasonable compilation strategies for data dependencies will truncate the dependencies at function boundaries when the implementations of those functions are unknown or unmodifiable. This document presents function annotations that assist compilers in following those data dependencies across function and translation-unit boundaries, avoiding prematurely truncating the data dependency tree, and thus improving program performance and scalability.

This proposal does not affect existing standard library functions. Such changes (for example, annotating the Vector templates) were considered, but rejected because current uses of data dependency ordering are generally restricted to highly tuned concurrent data structures using only basic operations such as indirection, field selection, array access, and casting. Longer term experience might indicate that a future proposal affecting library classes is warranted, however, there is insufficient motivation for such a proposal at this time.

This proposal is based on N2153 by Silvera, Wong, McKenney, and Blainey, on N2176 by Hans Boehm, on N2195 by Peter Dimov, on N2359, N2360, N2361 by Paul E. McKenney, on N2492 by Paul E. McKenney, Hans-J. Boehm, and Lawrence Crowl, on N2493 by Paul E. McKenney and Lawrence Crowl, on discussions on the cpp-threads list, on discussions in the concurrency workgroup at the 2007 Oxford, Toronto, and Bellevue meetings, and in particular discussions with Hans Boehm.

Proposal

We propose to annotate function declarations so that compilers may assume that compilation on the other side of the the function boundary will properly respect data dependency ordering. In analogy with the definition of data depencency ordering, we use the annotation [[carries_dependency]] to indicate that the compiler should not truncate the dependency tree. Such annotations attach to parameter declarations, and to the function declaration for its return value.

If a given function is annotated, the compilation of the caller must preserve dependency ordering on the function return value. If a particular argument of a given function is annotated, the compilation of the callee must preserve dependency ordering on the function argument.

We believe the syntax of the attributes is consistent with N2553 Towards support for attributes in C++ (Revision 3). In any event, we will adapt this proposal to the final attribute proposal.

For example, the following carries dependencies through argument y to the return value:

int *f(int *y [[carries_dependency]]) [[carries_dependency]]
{
        return y;
}

The following example carries dependency trees in, but not out:

int f(int *y [[carries_dependency]])
{
        return *y;
}

The following carries dependency trees out, but not in:

struct foo *f(int i) [[carries_dependency]]
{
        return foo_head[i].load(memory_order_consume);
}

In N2176, Hans Boehm lists a number of example optimizations that can break dependency trees. Most of these are addressed in N2556. the last is covered below.

N2176 example code:

r1 = x.load(memory_order_consume);
if (r1)
	f(&y);
else
	g(&y);

In this case, there is no data dependency leading into f() and g(), so this code-dependency example is out of scope. Modifying the example by replacing &y with r1 to create a data dependency leading into the two functions:

r1 = x.load(memory_order_consume);
if (r1)
	f(r1);
else
	g(r1);

In this case, an implementation might emit a memory fence prior to calling f() and g(). (Of course, a more sophisticated implementation with visibility into these two functions might be able to optimize this memory fence away). In order to prevent the fence, the programmer would annotate f() and g().

Recoding this based on this proposal and on N2556.

void f(struct foo * p [[carries_dependency]]);
void g(struct foo * p [[carries_dependency]]);

r1 = x.load(memory_order_consume);
if (r1)
	f(r1);
else
	g(r1);

Assuming that x is an atomic, the x.load(memory_order_consume) will form the head of a dependency tree. The [[carries_dependency]] annotations will inform the compiler that it can assume data depencencies are properly respected within f() and g(), so that the compiler need not emit a memory fence prior to invoking these functions.

Alternatives Considered

• Require the compiler globally analyze the program to infer which dependency trees must be preserved. This conflicts with the common practice of compiling C++ programs on a module-by-module basis, so this alternative was rejected.
• Prohibit dependency trees from crossing function boundaries. There are a large number of examples of RCU dependency trees crossing function boundaries in the Linux kernel, so this alternative was rejected.
• Prohibit dependency trees from crossing compilation-unit boundaries. There are a large number of examples of RCU dependency trees crossing compilation-unit boundaries in the Linux kernel. In some cases, the overall overhead of the instructions making up the dependency tree overwhelms that of a memory fence, however, in a number of cases, the actual number of instructions is small, so that the overhead of a memory fence would still be prohibitive. Therefore, this alternative was rejected.
• Allow dependency trees to be truncated, but without requiring that the implementation emit appropriate memory fences, when the dependency tree would flow through an unannotated function return value or an unannotated argument of a called function. However, this would result in annotations changing the meaning of the program. Therefore, this alternative was rejected.

Implementation

For trivial implementations of data dependency ordering, implementations of [[carries_dependency]] simply ignore this attribute.

For non-trivial implementations of data dependency ordering, there are three implementation options for the [[carries_dependency]] attribute:

• Do full compilation analysis to preserve the dependencies carried by the attribute.
• Ignore the attribute. However, implementations do so at the risk of binary compatiblity with more sophisticated implementations, which leads to the third option.
• Emit a memory fences immediately after entry to a function with annotated arguments and immediately after calling an annotated function result. This implementation trivially meets the annotation contract, though without an additional performance, and enables future optimization.

Wording

Add a new section 29.4.5 dcl.attr.carries_dependency:

29.4.5 The carries_dependency attribute

The attribute-token carries_dependency on a parameter declaration specifies that a dependency-ordering tree may enter a function through the corresponding argument. The attribute-token carries_dependency on a function type specifies that a dependency-ordering tree may leave a function through its return value. [Note: the carries_dependency attribute-token does not change the meaning of the program, but may result in generation of more efficient code.]

[ Example:

/* Compilation unit A. */

struct foo { int *a; int *b; };
struct foo *foo_head[10];

struct foo *f(int i) [[carries_dependency]]
{
    return foo_head[i].load(memory_order_consume);
}

int g(int *x, int *y [[carries_dependency]])
{
    return kill_dependency(foo_array[*x][*y]);
}

/* Compilation unit B. */

struct foo *f(int i) [[carries_dependency]];
int *g(int *x, int *y [[carries_dependency]]);

int c = 3;

void h(int i)
{
    struct foo *p;

    p = f(i);
    do_something_with(g(&c, p->a));
    do_something_with(g(p->a, &c));
}


The annotation on function f means that the dependency chain leaves f through its return value, so that the implementation need not constrain ordering upon return from f. Function g's second argument is annotated, but its first argument is not. Therefore, function h's initial call to g can rely on dependency ordering, however, its second call to g cannot. The implementation might therefore need to constrain ordering prior to the second call to g. ]