C++ Data-Dependency Ordering: Function Annotation

ISO/IEC JTC1 SC22 WG21 N2782 = 08-0292 - 2008-09-18

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, N2664, which has since been incorporated into the Working Draft. An understanding of that proposal is necessary to understanding this proposal.

We define a dependency-ordering tree to be a set of evaluations, with the root of the tree being a consume operation. If any evaluation A that is a member of a given dependency-ordering tree carries a dependency to evaluation B, then B is also a member of that dependency-ordering tree and is a child of A. Note that it is possible for a given evaluation to be a member of multiple dependency-ordering trees.

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-ordering 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 N2556 by Paul E. McKenney, Hans-J. Boehm, and Lawrence Crowl, on N2643 by Paul E. McKenney and Lawrence Crowl, on N2664 by Paul E. McKenney, Hans-J. Boehm, and Lawrence Crowl, on discussions on the cpp-threads list, on discussions in the concurrency workgroup at the 2007 Oxford, Toronto, Bellevue, and Nice 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-ordering 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 N2751 Towards support for attributes in C++ (Revision 5). 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 [[carries_dependency]] (int *y [[carries_dependency]])
{
        return y;
}

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

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

The following carries dependency-ordering trees out, but not in:

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

In N2176, Hans Boehm lists a number of example optimizations that can break dependency-ordering trees. Most of these are addressed in N2664. 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 N2664.

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-ordering 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.

This proposal does not address lambda expressions, nor does it address pointers to functions. The latter will likely require integration of attributes into the type system.

Alternatives Considered

• Require the compiler globally analyze the program to infer which dependency-ordering 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-ordering trees from crossing function boundaries. There are a large number of examples of RCU dependency-ordering trees crossing function boundaries in the Linux kernel, so this alternative was rejected.
• Prohibit dependency-ordering trees from crossing compilation-unit boundaries. There are a large number of examples of RCU dependency-ordering trees crossing compilation-unit boundaries in the Linux kernel. In some cases, the overall overhead of the instructions making up the dependency-ordering 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-ordering trees to be truncated, but without requiring that the implementation emit appropriate memory fences, when the dependency-ordering 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 7.1.10 dcl.attr.carries_dependency (not shown in bold below):

Drafting note: the section numbering should probably be changed to 7.6.x, depending on the disposition of the editor note in the attributes proposal N2761.

7.1.10 The carries_dependency attribute

The attribute-token carries_dependency specifies dependency propagation into and out of functions. It shall appear at most once in each attribute-list and no attribute-argument-clause shall be present. The attribute applies to the declarator-id of a parameter-declaration, in which case it specifies that the initialization of the parameter carries a dependency to (1.10) each lvalue-to-rvalue conversion (4.1) of that object. The attribute also applies to the declarator-id of a function declaration, in which case it specifies that the return value carries a dependency to the evaluation of the function call expression.

The first declaration of a function shall specify the carries_dependency attribute for its declarator-id if any declaration of the function specifies that carries_dependency attribute. Furthermore, the first declaration of a function shall specify the carries_dependency attribute for a parameter if any declaration of that function specifies the carries_dependency attribute for that parameter. If a function or one of its parameters is declared with the carries_dependency attribute in its first declaration in one translation unit and the same function or one of its parameters is declared without the carries_dependency attribute in its first declaration in another translation unit, the program is ill-formed; no diagnostic required.

[Note: the carries_dependency attribute 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 [[carries_dependency]] (int i)
{
    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 [[carries_dependency]] (int i);
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 return value carries a dependency out of f, 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 carries a dependency into g, however, its second call to g does not. The implementation might therefore need to constrain ordering prior to the second call to g.

— end Example ]