Doc. No.: WG21/N0929=X3J16/96-0111 Date: 21 May 1996 Project: C++ Standard Library Reply to: David Vandevoorde vandevod@cs.rpi.edu High-performance C++ implementations for valarrays (Rev. 2) Description It is not known how to implement the valarray template (as currently included in the working paper) with realistic performance using the core C++ language. By realistic performance, I think of no more than 20% increase in run-time and O(1) increase in storage requirements for typical arraywise operations. Discussion Todd Veldhuizen and myself have (independently) shown how template techniques can be used to implement valarray-like functionality with low overhead. Todd Veldhuizen (who coined the technique ``expression templates'') provides a detailed discussion on-line: http://monet.uwaterloo.ca/ ~tveldhui/papers/Expression-Templates/exprtmpl.html I made an implementation with most of the valarray functionality available at: ftp://ftp.cs.rpi.edu/pub/vandevod/Valarray/ We both report performance that is within a few percent of hand-coded C for arrays of sizes larger than about 25. For smaller arrays, the overhead can reduce performance dramatically (especially for 1 or 2 element arrays), but still much less so than alternative techniques. Indeed, while for medium-to-large sized arrays (sizes 1000 and up) expression templates lead to run-times about half those of the known alternative techniques (involving extraneous copying and/or run-time expression analysis), small arrays result in ``order of magnitude'' speed improvements when using expression templates. There are various ways to enable expression template techniques. The one proposed here results in minimal changes for the user as to what constitutes a valid ``valarray expression'' (compared with the current specifications). It also considerably simplifies the overall specification for valarrays (no need for ``helper class'' with properties subtly different from valarrays etc.); the document would be shorter, yet not drastically different from the existing text. Proposed Resolution Replace the valarray specification by those below. This is mostly an adaptation of the existing (post-"Santa Cruz") text for the technique described above, but also implements a few other changes presented as (fairly minor) valarray issues; among them: . no more gslices and gslice_arrays . generic apply and reduce functions . signed index/stride types (size_t becomes ptrdiff_t) . length() becomes size() ---8<------------------------------------------------------------------------- 26.1 Numeric type requirements [ Verse 2 mentions valarray; it should probably be replaced by valarray if these changes are included. Perhaps some adjustements in verses 1 and 3 would be desirable as well, but it doesn't seem essential. ] 26.3 Numeric arrays [lib.numarray] [ Footnote: [ In what follow, the types denoted by Rn and Wn (e.g., `R31') are [ implementation dependent. Header synopsis #include // for ptrdiff_t namespace std { template class valarray; // An array of type T class slice; // A BLAS-like slice // out of an array // Unary operators template valarray operator+(const valarray&); template valarray operator-(const valarray&); template valarray operator~{}(const valarray&); template valarray operator!(const valarray&); // Binary operators template valarray operator*(const valarray&, const valarray&); template valarray operator*(const valarray&, const T&); template valarray operator*(const T&, const valarray&); template valarray operator/(const valarray&, const valarray&); template valarray operator/(const valarray&, const T&); template valarray operator/(const T&, const valarray&); template valarray operator%(const valarray&, const valarray&); template valarray operator%(const valarray&, const T&); template valarray operator%(const T&, const valarray&); template valarray operator+(const valarray&, const valarray&); template valarray operator+(const valarray&, const T&); template valarray operator+(const T&, const valarray&); template valarray operator-(const valarray&, const valarray&); template valarray operator-(const valarray&, const T&); template valarray operator-(const T&, const valarray&); template valarray operator^(const valarray&, const valarray&); template valarray operator^(const valarray&, const T&); template valarray operator^(const T&, const valarray&); template valarray operator&(const valarray&, const valarray&); template valarray operator&(const valarray&, const T&); template valarray operator&(const T&, const valarray&); template valarray operator|(const valarray&, const valarray&); template valarray operator|(const valarray&, const T&); template valarray operator|(const T&, const valarray&); template valarray operator<<(const valarray&, const valarray&); template valarray operator<<(const valarray&, const T&); template valarray operator<<(const T&, const valarray&); template valarray operator>>(const valarray&, const valarray&); template valarray operator>>(const valarray&, const T&); template valarray operator>>(const T&, const valarray&); template valarray operator&&(const valarray&, const valarray&); template valarray operator&&(const valarray&, const T&); template valarray operator&&(const T&, const valarray&); template valarray operator||(const valarray&, const valarray&); template valarray operator||(const valarray&, const T&); template valarray operator||(const T&, const valarray&); template valarray operator==(const valarray&, const valarray&); template valarray operator==(const valarray&, const T&); template valarray operator==(const T&, const valarray&); template valarray operator!=(const valarray&, const valarray&); template valarray operator!=(const valarray&, const T&); template valarray operator!=(const T&, const valarray&); template valarray operator<(const valarray&, const valarray&); template valarray operator<(const valarray&, const T&); template valarray operator<(const T&, const valarray&); template valarray operator>(const valarray&, const valarray&); template valarray operator>(const valarray&, const T&); template valarray operator>(const T&, const valarray&); template valarray operator<=(const valarray&, const valarray&); template valarray operator<=(const valarray&, const T&); template valarray operator<=(const T&, const valarray&); template valarray operator>=(const valarray&, const valarray&); template valarray operator>=(const valarray&, const T&); template valarray operator>=(const T&, const valarray&); // Reductions template T reduce(Fr&, const valarray&); template T min(const valarray&); template T max(const valarray&); template T sum(const valarray&); // Unary functions template valarray apply(Fu&, const valarray&); template valarray abs(const valarray&); template valarray acos(const valarray&); template valarray asin(const valarray&); template valarray atan(const valarray&); template valarray cos(const valarray&); template valarray cosh(const valarray&); template valarray exp(const valarray&); template valarray log(const valarray&); template valarray log10(const valarray&); template valarray sin(const valarray&); template valarray sinh(const valarray&); template valarray sqrt(const valarray&); template valarray tan(const valarray&); template valarray tanh(const valarray&); // Binary functions template valarray apply(Fb&, const valarray&, const valarray&); template valarray apply(Fb&, const valarray&, const T&); template valarray apply(Fb&, const T&, const valarray&); template valarray atan2(const valarray&, const valarray&); template valarray atan2(const valarray&, const T&); template valarray atan2(const T&, const valarray&); template valarray min(const valarray&, const valarray&); template valarray min(const valarray&, const T&); template valarray min(const T&, const valarray&); template valarray max(const valarray&, const valarray&); template valarray max(const valarray&, const T&); template valarray max(const T&, const valarray&); template valarray pow(const valarray&, const valarray&); template valarray pow(const valarray&, const T&); template valarray pow(const T&, const valarray&); } // End namespace std 1 The header defines a class template valarray and a set of related function signatures for representing and manipulating arrays of values. 2 In `valarray', T is called the element type and M is called the storage model. The element type can be any type that satisfies the numeric type requirements of _lib.numeric.requirements_, but users can only directly instantiate valarray with storage model M=void. [ Footnote: [ The storage model allows implementations to treat functionalities [ with value and with reference semantics to be treated unformly. It [ also permits implementations based on expression templates, without [ imposing significant additional constraints on other techniques. 3 The implementation is however free to generate return values with other storage models denoted by Rn and Wn in subclause _lib.numarray_. The storage model void and the models introduced by the implementation as substitution for one or more Wn will be called ``writable''. Storage models introduced by an implementation only as subsitution for one or more Rn will by called ``read-only''. 4 Storage models denoted by Rn and Wn in subclause _lib.numarray_ may depend on the template parameters of the function templates in which they occur. However, they shall add no more than two levels of nesting compared to the deepest nesting level of the types of the argument and/or *this. [ Footnote: [ With the implementation-dependent limit on recursive template [ instantiations, this guarantees a minimum allowable complexity for [ expressions involving valarrays. 5 The valarray classes are defined to be free of certain forms of aliasing, thus allowing operations on these classes to be optimized more aggressively. 6 These library functions are permitted to throw a bad_alloc (_lib.bad.alloc_) exception if there are not sufficient resources available to carry out the operation (except where otherwise specified). Note that the exception is not mandated. 7 An implementation is permitted to qualify any of the functions and member function declared in as inline. Template class valarray [lib.template.valarray] namespace std { template class valarray { public: // _lib.valarray.cons_ construct/destroy: valarray(); explicit valarray(ptrdiff_t); valarray(ptrdiff_t, const T&); valarray(ptrdiff_t, const T*); template valarray(const valarray&); ~valarray(); // _lib.valarray.assign_ assignment: template valarray& operator=(const valarray&); valarray& operator=(const T&); // _lib.valarray.access_ element access: T operator[](ptrdiff_t) const; T& operator[](ptrdiff_t); // _lib.valarray.subset_ subset operations: valarray operator[](slice) const; valarray operator[](slice); template valarray operator[](const valarray&) const; template valarray operator[](const valarray&); // _lib.valarray.mask_ assignment mask: template valarray mask(const valarray&); // _lib.valarray.cassign_ computed assignment: template valarray& operator*=(const valarray&); template valarray& operator/=(const valarray&); template valarray& operator%=(const valarray&); template valarray& operator+=(const valarray&); template valarray& operator-=(const valarray&); template valarray& operator^=(const valarray&); template valarray& operator|=(const valarray&); template valarray& operator&=(const valarray&); template valarray& operator<<=(const valarray&); template valarray& operator>>=(const valarray&); valarray& operator*= (const T&); valarray& operator/= (const T&); valarray& operator%= (const T&); valarray& operator+= (const T&); valarray& operator-= (const T&); valarray& operator^= (const T&); valarray& operator&= (const T&); valarray& operator|= (const T&); valarray& operator<<=(const T&); valarray& operator>>=(const T&); // _lib.valarray.members_ member functions: ptrdiff_t size() const; void resize(ptrdiff_t, const T&) void free(); operator T*(); operator const T*() const; valarray shift (int) const; valarray cshift(int) const; }; } 1 The template class valarray is a one-dimensional smart array, with elements numbered sequentially from zero. It is a representation of the mathematical concept of an ordered set of values. 2 The intent is to specify an array template that has the minimum functionality necessary to address aliasing ambiguities and the proliferation of temporaries. Thus, the valarray template is neither a matrix class nor a field class. However, it is a very useful building block for designing such classes. valarray constructors [lib.valarray.cons] 1 These constructors are only mandated for the standard storage model void. If an implementation introduces other storage models, the corresponding valarray types do not have to include these constructors and may provide others instead. 2 These constructors may allocate memory using the global new and new[] operators, using a new or new[] operator overloaded for the element type or using any other method. The selected method is implementation dependent. valarray(); 3 Constructs an object of class valarray, which has zero length until the member function resize is invoked for it. This default constructor is essential, since arrays of valarray are likely to prove useful. There must also be a way to change the size of an array after initialization; this is supplied by the resize member function. [ Footnote: [ For convenience, such objects are referred to as ``arrays'' throughout the [ remainder of subclause _lib.numarray_. explicit valarray(ptrdiff_t); 4 The array created by this constructor has a length equal to the value of the argument. The elements of the array are constructed using the default constructor for the instantiating type T. valarray(ptrdiff_t n, const T&); 5 The array created by this constructor has a length equal to the first argument. The elements of the array are initialized with the value of the second argument. valarray(ptrdiff_t n, const T*); 6 The array created by this constructor has a length equal to the first argument. The values of the elements of the array are initialized with the first n values pointed to by the first argument. If the value of the second argument is greater than the number of values pointed to by the first argument, the behavior is undefined. This constructor is the preferred method for converting a C array to a valarray object. template valarray(const valarray&); 7 The array created by this constructor has the same length as the argument array. The elements are initialized with the values of the corresponding elements of the argument array. This copy constructor creates a distinct array rather than an alias. Implementations in which arrays share storage are permitted, but they must implement a copy-on-reference mechanism to ensure that arrays are conceptually distinct. 8 An implementation must support void and any other storage model it introduces as substitutions for M2. ~valarray(); 9 The destructor may not throw an exception. valarray assignment [lib.valarray.assign] 1 An implementation is not required to support assignment to valarrays with a read-only storage model. template valarray& operator=(const valarray&); 2 Each element of the *this array is assigned the value of the corresponding element of the argument array, unless that element is masked off as the result of a call to the member function mask. The resulting behavior is undefined if the length of the argument array is not equal to the length of the *this array. 3 If the value of an element in the left hand side of a valarray assignment operator depends on the value of another element in that left hand side, the resulting behavior is undefined. 4 An implementation must support void and any other storage model it introduces as substitutions for M2. valarray& operator=(const T&); 5 The scalar assignment operator causes each element of the *this array to be assigned the value of the argument, unless that element is masked off as the result of a call to the member function mask. valarray element access lib.valarray.access] T operator[](ptrdiff_t) const; T& operator[](ptrdiff_t); 1 When applied to a constant array, the subscript operator returns the value of the corresponding element of the array. Valarrays with a read-only storage model are not required to support the non-const subscript operator. When applied to a non-constant array, the subscript operator returns a reference to the corresponding element of the array. 2 Thus, the expression (a[i] = q, a[i]) == q evaluates as true for any non-constant valarray a, any T q, and for any ptrdiff_t i such that the value of i is less than the length of a (W is a writable storage model). 3 The expression &a[i+j] == &a[i] + j evaluates as true for all ptrdiff_t i and ptrdiff_t j such that i+j is less than the length of the non-constant valarray a, where W is a writable storage model. 4 Likewise, the expression &a[i] != &b[j] evaluates as true for any two non-constant arrays a and b (whose storage model is a writabl storage model) and for any ptrdiff_t i and ptrdiff_t j such that i is less than the length of a and j is less than the length of b. This property indicates an absence of aliasing and may be used to advantage by optimizing compilers. [ Footnote: [ Compilers may take advantage of inlining, constant propagation, loop fusion, [ tracking of pointers obtained from operator new, and other techniques to [ generate efficient valarrays. 5 The reference returned by the subscript operator for a non-constant array is guaranteed to be valid until the the member function resize(ptrdiff_t, const T&) (_lib.valarray.members_) is called for that array or until the lifetime of that array ends, whichever happens first. 6 If the subscript operator is invoked with a ptrdiff_t argument whose value is not less than the length of the array, the behavior is undefined. valarray subset operations [lib.valarray.sub] 1 Each of these operations returns a subset of the array. Arrays whose storage model is read-only are not required to support the non-const versions of these operations. 2 The const-qualified versions return this subset as a valarray with value semantics wrt. the *this array. The non-const versions return a class template object which has reference semantics to the original array. valarray operator[](slice s) const; valarray operator[](slice s); 3 The size of the array returned is s.size(). Element numbered i of the array returned corresponds to element numbered (s.start()+i*s.stride()) of the *this array. template valarray operator[](const valarray& a) const; template valarray operator[](const valarray& a); 4 The size of the array returned is s.size(). Element numbered i of the array returned corresponds to element number a[i] of the *this array. 5 An implementation must support void and any other storage model it introduces as substitutions for M2. 6 [ Example: valarray a(1000), b(1000); // Default storage model (void) valarray p(200); // ... a[p] += (2.0*b)[slice(3, 200, 2)]; // Assign 3rd, 5th, ..., 401st // element of 2.0*b to a[p[3]], // a[p[5]], ..., a[p[401]]. (b[slice(3, 200, 2)])[16] = 1.0; // Equivalent to b[35] = 1.0. --- end example ] valarray assignment masking [lib.valarray.mask] template valarray mask(const valarray&); 1 An implementation is not required to provide this member for read-only arrays. 2 The returned array has reference semantics wrt. the *this array and has size equal to that of the *this array. If x is a writable valarray, then &(mask(x))[i] == &x[i] for any nonnegative i smaller than x.size(). 3 The returned array modifies the behavior of assignment and computed assignments in such a way that elements at positions for which the corresponding element in the argument array is false, are not modified by these operations. 4 If the array and the argument array do not have the same length, the behavior is undefined. valarray computed assignment [lib.valarray.cassign] 1 An implementation is not required to support computed assignment for read-only storage models. template valarray& operator*=(const valarray&); template valarray& operator/=(const valarray&); template valarray& operator%=(const valarray&); template valarray& operator+=(const valarray&); template valarray& operator-=(const valarray