On Thu, 30 Mar 2000 jsiek@lsc.nd.edu wrote:
> Ok, that seems like an improvement, but how does it handle the
> following situation?
>
> In STL, often times a few special cases of a generic algorithm are
> specialized, for instance take copy(). In one specialization it calls
> memmove() to do the work. Now, suppose memmove() has restrict in its
> parameter list. What happens when someone calls the generic copy()
> with non-restrict pointers?
It doesn't cause a problem. One of the design goals for the
restrict qualifier was that it could be added to the prototype
for memmove without raising any type compatibility issues in
existing uses of that function. And it achieves that goal
because type qualifiers (at the "top level") on arguments and
parameters are ignored for the purpose of checking type
compatibility in C, or for overload resolution in C++.
>
> template <class _Tp>
> inline _Tp*
> __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) {
> memmove(__result, __first, sizeof(_Tp) * (__last - __first));
> return __result + (__last - __first);
> }
This example raise other issues, however. See below.
> The problem I'm trying to get at is that if the generic function
> depends on how it is used (instantiated) as to whether the input is
> unaliased, then the library writer can't make optimizations like the
> call to memmove above. To enable such optimizations the library writer
> needs to be able to declare the generic copy() function to take only
> unaliased iterators, no matter how it is instantiated.
In fact, the semantics of copy would not allow it to be declared
with unaliased iterators, because some aliasing is allowed:
25.2.1 Copy
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
1 Effects: Copies elements in the range [first, last) into
the range [result, result + (last-first))
starting from first and proceeding to last.
For each non-negative integer n < (last-first),
performs *(result+n) = *(first+n).
2 Returns: result + (lastfirst).
3 Requires: result shall not be in the range [first,last).
4 Complexity: Exactly last-first assignments.
This allows a call of the form copy(p+1,p+100,p).
(I realize this is somewhat tangential, but notice that
specializing copy to __copy_trivial as above for a type such
as (char *) is not portable. Doing so assumes that memmove
copies from lowest address up, but there is no such
requirement on memmove in the C standard. On some types of
machines, it might be faster to divide the source into
multiple blocks, and move them in parallel to the
destination. So a library writer cannot use the above
specialization without knowing how memmove is implemented.)
So adding restrict to some calls of copy would be compatible
with a library using a specialization like this for improved
performance, though it might largely eliminate the need for the
specialization (assuming the compiler can be relied upon to
reduce the copy operation to a simple loop for a type with a
trivial copy assignment). For a programmer who wishes to add
new types and algorithms, restrict would seem preferable because
it does not require him to be privy to the non-portable details
of such specializations.
Bill Homer
(651) 683-5606 Cray 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:12 EST