# New Rules for Array Sections in Intel® Cilk™ Plus

By Arch D. Robison (Intel), published on July 26, 2011

Fans of Cilk Plus or language specifications may be interested in the revised specification of Intel® Cilk™ Plus posted at http://software.intel.com/file/37679/Intel_Cilk_plus_lang_spec_2.htm . Clark Nelson did most of the work for turning the previous specification into something closer to standardese and illuminating ambiguities in the previous specification. I'll mention two important changes that the new specification to improve the language extension. One permits compilers to generate more efficient code. The other resolves a fundamental conflict that array sections brought up.

## More Efficient Handling of Array Sections

Suppose p and q are pointers. Consider the following array-section assignment:

p[0:n] = q[0:n]+1;

This statement sets p[i]=q[i]+1 for i in {0...n-1}. But what happens if these two sequences overlap in memory? In our original specification, we followed the practice of APL and Fortran 90, and said that the right side must be evaluated first before it is assigned to the left side. This practice makes the example well defined regardless of whether there is overlap.

However, a key principle of C++ is "abstraction with minimal penalty". The APL and Fortran 90 approach violates this principle, because it requires the compiler to generate a temporary array for the right side result whenever the compiler cannot *prove *that there is no overlap. In many practical situations, the compiler cannot prove absence of overlap, even though the programmer knows there is no overlap. Thus with the old specification, the programmer ended up paying a penalty for using array notation.

The revised specificaiton makes the partial overlap case undefined. The compiler is free to compile the example without generating a temporary array. Indeed, under some circumstances, the the array sections can conceivably be compiled into more efficient code than their Fortran counterparts. Now it is a programmer error if p and q point to partially overlapping arrays. However, if the overlap is *exact, *the code is well defined. This is important for keeping the equivalence of common update idioms like "p[0:n]+=1" and "p[0:n] = p[0:n]+1".

The new specification makes the overlap rules for array sections consistent with the existing ones for structs/classes/unions. If I write "*p = *q" and the pointers point to structs, the assignment is well defined only if p and q point to non-overlapping structures, or point to exactly the same structure. That way, the compiler can avoid generating unnecessary temporary structures. Now the rule and its benefits apply to array sections too.

The change will break existing code that relied on the temporary arrays. It's an inconvenience that in some cases might require revising existing code, but I believe it's justified by the greater long-term good for Array Notation.

## Rank of "Pointer + Int" Resolved

In Array Notation, "x op y" is normally performed elementwise if x or y is an array section. For example, "z[0:n] = x[0:n]+y[0:n];" sets z[i] to x[i]+y[i] for i in {0..n-1}. One-dimensional sections are said to have rank 1. The rule extends to multidimensional arrays. For instance, "a[0:m][0:n] = x[0:m][0:n] + y[0:m][0:n];" does elemntwise addition and assignment across two dimensions. The array sections are said to have rank 2. In general, in "x op y", if both x and y have non-zero rank, they must match, and the rank of the result is the same.

But there is a an important exception for the subscript operator. Suppose *x *and *i *are expressions with non-zero rank. The rank of x[i] must be the sum of the ranks of x and i. This is because expressions like x[0:m][0:n] are equivalent to (x[0:m])[0:n]. That is, subscripting is always a one-dimensional operation in C++, and multiple dimensions are "faked" by multiple subscript operations.

So far, this is plain stuff, and seems non-controversial. The tricky issue is determining the rank of p+i when p is a pointer and i is an integer, both with non-zero rank. Should it follow the normal "x op y" rule, or the array subscript rule? Either way breaks one of two fundamental identities in C++:

- (p+i)+j == p+(i+j)

- p[i] == *(p+i)

Following the "x op y" rule preserves identity 1, but breaks identity 2. To see this, suppose p, i, and j are expressions with rank 1. Then both sides of identity 1 have rank 1 under the "x op y" rule. But in identity 2, the sides have different rank: "p[i]" has rank 2 and "*(p+i)" has rank 1.

An alternative would be to treat "p+i" similarly to "p[i]", and say that the rank is the sum of the ranks of the operands. That preserves identity 2. But it breaks 1, because then "(p+i)+j" has rank 3, but "p+(i+j)" has rank 2.

So one of the identities must break. The tie-breaker is consideration of templates and possible future extension to user-defined operators. In those cases, we want a uniform rule for "x + y" that does not depend on the types of x and y. So we broke identity 2, and kept rank of "p+i" is the same as for any other "p op i". Subscripting is the only special operator with respect to rank.

## Summary

The revised specification resolves some important issues in Array Notation. It should make it much clearer to both users and implementers, and enable "abstraction with minimal penalty" for Array Notation.