www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - restrict in practice

reply bearophile <bearophileHUGS lycos.com> writes:
This is a paper by Markus Mock is about the usefulness of the "restrict"
annotation in medium-sized C programs:
http://www.cs.pitt.edu/~mock/papers/clei2004.pdf

The author finds that restrict is not significantly useful in the bulk of
programs, while it can be useful in computational kernels (small routines that
perform heavy array operations).

I think what the paper says is not very useful now because:
- It uses the Sparc V9 and Itanium 2 CPUs. Itanium has hardware that greatly
reduces the need of the restrict annotation. But I think Core2 and i7 CPUs
don't have such feature.
- GCC 4.5 seens able to use restrict well, while older GCCs where not good (but
this article doesn't use GCC).

A downside of the restrict of C is that the compiler is not able to spot if the
annotation is used in the wrong place.

Compared to the inline annotation the situation is different because today
compiler backends like LLVM/GCC are good enough at choosing what functions to
inline, while for them finding what pointers aren't an alias of each other is
not easy still.

The LLVM backend of LDC is able to use annotations that define pointers as
unique.

So it can be useful to have ways for the D compiler to know what pointers in a
computational kernel aren't alias of each other, but I'd like this to be safer,
unlike C. Unique & lend for class references may be usable for pointers too.

Bye,
bearophile
Jan 03 2010
next sibling parent Don <nospam nospam.com> writes:
bearophile wrote:
 This is a paper by Markus Mock is about the usefulness of the "restrict"
annotation in medium-sized C programs:
 http://www.cs.pitt.edu/~mock/papers/clei2004.pdf
 
 The author finds that restrict is not significantly useful in the bulk of
programs, while it can be useful in computational kernels (small routines that
perform heavy array operations).

[snip]
 So it can be useful to have ways for the D compiler to know what pointers in a
computational kernel aren't alias of each other, but I'd like this to be safer,
unlike C. 

Unique & lend for class references may be usable for pointers too. I think we're actually in good shape here. Note that D's array operations cover some of the simplest (but most important) use cases. When dealing with a D array, the compiler has a _lot_ more information than with a pointer.
Jan 03 2010
prev sibling next sibling parent #ponce <nospam nospam.com> writes:
VisualDSP++ has a great deal of pragmas to deal with aliasing and optimization
at the loop-level. They are quite handy and require less work than restrict
imho. Aliasing is especially annoying with loops.

// tell the optimizer there is no pointer aliasing in the whole loop
#pragma no_alias  

// minimum and maximum loop count
#pragma loop_count(24, 48, 8)  

// tell the optimizer this loop can be run in parallel
// implies no_alias 
// (similar to #pragma omp parallel for)
#pragma vector_for 
for (i=0;i<taps;i++)
    acc += x[i]*y[i];

Of course array slices operations are a convenient way to prevent aliasing
problems but carrying the length information is an overhead and could prevent
loop-unrolling.
Jan 04 2010
prev sibling parent Walter Bright <newshound1 digitalmars.com> writes:
bearophile wrote:
 A downside of the restrict of C is that the compiler is not able to
 spot if the annotation is used in the wrong place.

That's a near fatal problem with it, because: 1. restrict is difficult to understand 2. it is prone to being used erroneously due to misunderstanding 3. it is not checkable by the compiler 4. even if used correctly, it can be broken by seemingly minor changes done later
Jan 04 2010