jsiek wrote:
> Of course, ultimately it would be nice if programmers were given the
> language constructs needed to express exactly what they mean. Then
> they could stop lying and playing tricks. That way experienced
> programmers and library implementors could provide the kind of
> information needed for compilers. restrict is a step in the right
> direction... but, as I said before, much work needs to be done to
> generalize it for use in modern codes (that use abstractions such as
> iterators).
Before the current discussion dies away, I'd like to pursue the
question of what could be done with the restrict qualifier alone,
and whether higher level constructs are required.
Let me make some claims, and invite your comments.
1. There is a straightforward extension of the restrict
qualifier, based on its specification in C, allowing it to
qualify reference types and the "this" pointer.
2. The restrict qualifier is compatible with the iterator style
of programming. In particular:
typedef double * restrict T;
void f(T a, T a_end, T b) {
while(a != a_end) {
*a++ = *b++;
}
}
The use of restrict in the type of a, by itself, asserts
that none of the elements modified using a are also accessed
through b. Though not needed for optimization, it is
important that the restrict qualifier can be used for a_end
and b so that all can have a common type. In particular,
note that there is no problem with a and a_end pointing to
the same array, because a_end is not used to reference any
elements of that array.
3. The restrict qualifier can be used to assert the absence of
aliasing in list-based operations.
typedef struct s { double value; struct s * next; } S;
typedef S * restrict T;
void f(T a, T a_end, T b) {
while(a != a_end) {
a->value = b->value;
a = a->next;
b = b->next;
}
}
As in the previous example, the use of restrict asserts that
none of the objects modified as a->value is also referenced
as b->value.
4. For generic programming, the restrict qualifier can be
packaged in much the same way as the const qualifier.
In particular, we could add a typedef for, say,
restrict_iterator to those for iterator and const_iterator
in an STL-style container. So, for example, if an
implementation uses (void *) members for the links in the
iterator class for list, then it would use (void * restrict)
members for the links in the restrict_iterator class.
(Those members will have to be cast to other types, but the
semantics of the restrict qualifier is not affected by that.)
Note that only a new typedef name is added, not new
semantics for the restrict qualifier.
Note that restrict_const_iterator might also be interesting,
because traversing a list with such an iterator asserts that
its nodes (both values and links) will not be modified,
either in that loop or anywhere else during the execution of
the block in which the iterator is declared.
5. The restrict qualifier can/will be adequately supported by
compilers and used in programs that could substantially
benefit from it. Who knows? Compiler support for simple
uses of restricted pointers is not that hard, but more than
that will be required for our purposes. At least, a
compiler that tries to minimize the the "abstraction
penalty" will be likely to expose the underlying restricted
pointers in an iterator.
6. Providing a general means to make precise aliasing assertions
in C/C++ is not easy. Any but the most narrowly focused
proposal is going to encounter the same issues (such as the
scope of the assertion, and dealing with multiple levels of
indirection) that made restricted pointers a challenge to
specify in the C language and to support in compilers.
-- Bill Homer (651) 683-5606 Silicon Graphics, Inc. homer@cray.com 655F Lone Oak Drive, Eagan, MN 55121--------------------- Object Oriented Numerics List -------------------------- * To subscribe/unsubscribe: use the handy web form at http://oonumerics.org/oon/ * If this doesn't work, please send a note to owner-oon-list@oonumerics.org
This archive was generated by hypermail 2b29 : Wed Feb 20 2002 - 03:20:11 EST