ALP User Documentation 0.7.0
Algebraic Programming User Documentation
Classes | Public Types | Public Member Functions | List of all members
Vector< D, implementation, C > Class Template Reference

A GraphBLAS vector. More...

#include <vector.hpp>

Classes

class  const_iterator
 A standard iterator for the Vector< D > class. More...
 

Public Types

typedef D & lambda_reference
 Defines a reference to a value of type D. More...
 
typedef D value_type
 The type of elements stored in this vector.
 

Public Member Functions

 Vector (const size_t n)
 Creates an ALP/GraphBLAS vector. More...
 
 Vector (const size_t n, const size_t nz)
 Creates an ALP/GraphBLAS vector. More...
 
 Vector (Vector< D, implementation, C > &&x) noexcept
 Move constructor. More...
 
 ~Vector ()
 Default destructor. More...
 
const_iterator begin () const
 Same as cbegin(). More...
 
template<Descriptor descr = descriptors::no_operation, class Accum = typename operators::right_assign< D, D, D >, typename fwd_iterator = const D * __restrict__>
RC build (const Accum &accum, const fwd_iterator start, const fwd_iterator end, fwd_iterator npos)
 Copy from raw user-supplied data into a vector. More...
 
template<Descriptor descr = descriptors::no_operation, class Accum = operators::right_assign< D, D, D >, typename ind_iterator = const size_t * __restrict__, typename nnz_iterator = const D * __restrict__, class Dup = operators::right_assign< D, D, D >>
RC build (const Accum &accum, const ind_iterator ind_start, const ind_iterator ind_end, const nnz_iterator nnz_start, const nnz_iterator nnz_end, const Dup &dup=Dup())
 Copy from raw user-supplied data into a vector. More...
 
template<Descriptor descr = descriptors::no_operation, typename mask_type , class Accum , typename ind_iterator = const size_t * __restrict__, typename nnz_iterator = const D * __restrict__, class Dup = operators::right_assign< D, typename nnz_iterator::value_type, D >>
RC build (const Vector< mask_type, implementation, C > &mask, const Accum &accum, const ind_iterator ind_start, const ind_iterator ind_end, const nnz_iterator nnz_start, const nnz_iterator nnz_end, const Dup &dup=Dup())
 Copy from raw user-supplied data into a vector. More...
 
const_iterator cbegin () const
 Provides the only mechanism to extract data from this GraphBLAS vector. More...
 
const_iterator cend () const
 Indicates the end to the elements in this container. More...
 
const_iterator end () const
 Same as cend(). More...
 
template<typename T >
RC nnz (T &nnz) const
 Return the number of nonzeroes in this vector. More...
 
template<class Monoid >
lambda_reference operator() (const size_t i, const Monoid &monoid=Monoid())
 Returns a lambda reference to an element of this sparse vector. More...
 
Vector< D, implementation, C > & operator= (Vector< D, implementation, C > &&x) noexcept
 Move-from-temporary assignment. More...
 
lambda_reference operator[] (const size_t i)
 Returns a lambda reference to an element of this vector. More...
 
template<typename T >
RC size (T &size) const
 Return the dimension of this vector. More...
 

Detailed Description

template<typename D, enum Backend implementation, typename C>
class grb::Vector< D, implementation, C >

A GraphBLAS vector.

This is an opaque data type that can be provided to any GraphBLAS function, such as, grb::eWiseMulAdd, for example.

Template Parameters
DThe type of an element of this vector. D shall not be a GraphBLAS type.
implementationAllows different backends to implement different versions of this data type.
CThe type of the class that keeps track of sparsity structure.
Warning
Creating a grb::Vector of other GraphBLAS types is not allowed. Passing a GraphBLAS type as template parameter will lead to undefined behaviour.
Note
The implementation found in the same file as this documentation catches invalid backends only. This class should never compile.
See also
grb::Vector< D, reference, C > for an actual implementation example.

Member Typedef Documentation

◆ lambda_reference

typedef D& lambda_reference

Defines a reference to a value of type D.

This reference is only valid when used inside a lambda function that is passed to grb::eWiseLambda().

Warning
Any other use of this reference incurs undefined behaviour.
Example.
An example valid use:
void f(
const Vector< D > &v
) {
grb::eWiseLambda( [x,y](const size_t i) {
x += y;
}, v );
}
D & lambda_reference
Defines a reference to a value of type D.
Definition: vector.hpp:124
RC eWiseLambda(const Func f, const Vector< DataType, backend, Coords > &x, Args...)
Executes an arbitrary element-wise user-defined function f on any number of vectors of equal length.
Definition: blas1.hpp:3746
This code adds y to x for every element in v. For a more useful example, see grb::eWiseLambda.
Warning
Note that, unlike the above, this below code is illegal since it does not evaluate via a lambda passed to any of the above GraphBLAS lambda functions (such as grb::eWiseLambda). Also this usage is illegal since it does not rely on any GraphBLAS-approved function listed above:
void f(
) {
std::functional< void() > f =
[x,y](const size_t i) {
x += y;
};
f();
}
There is no similar concept in the official GraphBLAS specs.
See also
grb::Vector::operator[]()
grb::eWiseLambda

Constructor & Destructor Documentation

◆ Vector() [1/3]

Vector ( const size_t  n,
const size_t  nz 
)
inline

Creates an ALP/GraphBLAS vector.

The given dimension will be fixed throughout the lifetime of this container. After instantiation, the vector will contain no nonzeroes.

Parameters
[in]nThe dimension of this vector.
[in]nzThe minimal initial capacity of this vector.

The argument nz is optional. Its default value is n.

Performance semantics
A backend must:
  1. define cost in terms of work,
  2. define intra-process data movement costs,
  3. define inter-process data movement costs,
  4. define whether inter-process synchronisations occur,
  5. define memory storage requirements and may define this in terms of n and/or nz, and
  6. must define whether system calls may be made, and in particular whether allocation or freeing of dynamic memory occurs or may occur.
Warning
Most backends will require work, intra-process data movement, and system calls for the dynamic allocation of memory areas, all of (at least the complexity of) \( \Omega( \mathit{nz} ) \). Hence avoid the use of this constructor within performance-critical code sections.

◆ Vector() [2/3]

Vector ( const size_t  n)
inline

Creates an ALP/GraphBLAS vector.

This constructor is specified as per the above where nz is to taken equal to n.

◆ Vector() [3/3]

Vector ( Vector< D, implementation, C > &&  x)
inlinenoexcept

Move constructor.

This will make the new vector equal the given GraphBLAS vector while destroying the supplied GraphBLAS vector.

This function always succeeds and will not throw exceptions.

Parameters
[in]xThe GraphBLAS vector to move to this new container.
Performance semantics
  1. This constructor completes in \( \Theta(1) \) time.
  2. This constructor does not allocate new data on the heap.
  3. This constructor uses \( \mathcal{O}(1) \) more memory than already used by this application at constructor entry.
  4. This constructor incurs at most \( \mathcal{O}(1) \) bytes of data movement.

◆ ~Vector()

~Vector ( )
inline

Default destructor.

Frees all associated memory areas.

Performance semantics
  1. This destructor contains \( \mathcal{O}(n) \) work, where \( n \) is the capacity of this vector.
  2. This destructor is only allowed to free memory, not allocate.
  3. This destructor uses \( \mathcal{O}(1) \) more memory than already used by this application at entry.
  4. This destructor shall move at most \( \mathcal{O}(n) \) bytes of data.
  5. This destructor will make system calls.
Warning
Avoid the use of this destructor within performance critical code sections.
Note
Destruction of this GraphBLAS container is the only way to guarantee that any underlying dynamically allocated memory is freed.

Member Function Documentation

◆ begin()

const_iterator begin ( ) const
inline

Same as cbegin().

Since iterators are only supplied as a data extraction mechanism, there is no overloaded version of this function that returns a non-const iterator.

◆ build() [1/3]

RC build ( const Accum &  accum,
const fwd_iterator  start,
const fwd_iterator  end,
fwd_iterator  npos 
)
inline

Copy from raw user-supplied data into a vector.

This is the dense unmasked variant.

Template Parameters
descrThe pre-processing descriptor to use.
fwd_iteratorThe type of input iterator. By default, this will be a raw unaliased pointer.
AccumThe accumulator type used to merge incoming new elements with existing contents, if any.
Parameters
[in]accumThe accumulator used to merge incoming new elements with existing content, if any.
[in]startThe iterator to the first element that should be copied into this GraphBLAS vector.
[in]endIterator shifted exactly one past the last element that should be copied into this GraphBLAS vector.
[out]nposThe last iterator position after exiting this function. In most cases this will equal end. This parameter is optional.

The first element from it will be copied into the element with index \( 0 \) in this vector. The \( k \)-th element will be copied into the element with index \( k - 1 \). The iterator start will be incremented along with \( k \) until it compares equal to end, or until it has been incremented n times, where n is the dimension of this vector. In the latter case, any remaining values are ignored.

Returns
grb::SUCCESS This function always succeeds.
Note
The default accumulator expects val to be of the same type as nonzero elements in this function, and will cause old values to be overwritten by the incoming new values.
Previous contents of the vector are retained. If these are to be cleared first, see clear(). The default accumulator is NOT an alternative since any pre-existing values corresponding to entries in the mask that evaluate to false will be retained.
The parameter n can be used to ingest only a subset of a larger data structure pointed to by start. At the end of the call, start will then not be equal to end, but instead point to the first element of the remainder of the larger data structure.
Valid descriptors
grb::descriptors::no_operation, grb::descriptors::no_casting.
Note
Invalid descriptors will be ignored.

If grb::descriptors::no_casting is specified, then 1) the first domain of accum must match the type of val, 2) the second domain must match the type D of nonzeroes in this vector, and 3) the third domain must match D. If one of these is not true, the code shall not compile.

Performance semantics
If the capacity of this container is sufficient to perform the requested operation, then:
  1. This function contains \( \Theta(n) \) work.
  2. This function will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
  3. This function moves at most \( n ( 2\mathit{sizeof}(D) + \mathit{sizeof}(\mathit{bool}) ) + \mathcal{O}(1) \) bytes of data.
Performance exceptions
If the capacity of this container at function entry is insufficient to perform the requested operation, then, in addition to the above:
  1. this function allocates \( \Theta(n) \) bytes of memory .
  2. this function frees \( \mathcal{O}(n) \) bytes of memory.
  3. this function will make system calls.
Note
An implementation may ensure that at object construction the capacity is maximised. In that case, the above performance exceptions will never come to pass.
See also
grb::buildVector for the ALP/GraphBLAS standard dispatcher to this function.

◆ build() [2/3]

RC build ( const Accum &  accum,
const ind_iterator  ind_start,
const ind_iterator  ind_end,
const nnz_iterator  nnz_start,
const nnz_iterator  nnz_end,
const Dup &  dup = Dup() 
)
inline

Copy from raw user-supplied data into a vector.

This is the sparse non-masked variant.

Template Parameters
descrThe pre-processing descriptor to use.
AccumThe type of the operator used to combine newly input data with existing data, if any.
ind_iteratorThe type of index input iterator. By default, this will be a raw unaliased pointer to elements of type size_t.
nnz_iteratorThe type of nonzero input iterator. By default, this will be a raw unaliased pointer to elements of type D.
DupThe type of operator used to combine any duplicate input values.
Parameters
[in]accumThe operator to be used when writing back the result of data that was already in this container prior to calling this function.
[in]ind_startThe iterator to the first index value that should be added to this GraphBLAS vector.
[in]ind_endIterator corresponding to the end position of ind_start.
[in]nnz_startThe iterator to the first nonzero value that should be added to this GraphBLAS vector.
[in]nnz_endIterator corresponding to the end position of nnz_start.
[in]dupThe operator to be used when handling multiple nonzero values that are to be mapped to the same index position.

The first element from nnz_start will be copied into this vector at the index corresponding to the first element from ind_start. Then, both nonzero and index value iterators advance to add the next input element and the process repeats until either of the input iterators reach nnz_end or ind_end, respectively. If at that point one of the iterators still has remaining elements, then those elements are ignored.

Returns
grb::MISMATCH When attempting to insert a nonzero value at an index position that is larger or equal to the dimension of this vector. When this code is returned, the contents of this container are undefined.
grb::SUCCESS When all elements are successfully assigned.
Note
The default accumulator expects D to be of the same type as nonzero elements of this operator, and will cause old values to be overwritten by the incoming new values.
The default dup expects D to be of the same type as nonzero elements of this operator, and will cause duplicate values to be discarded in favour of the last seen value.
Previous contents of the vector are retained. If these are to be cleared first, see clear(). The default accumulator is NOT an alternative since any pre-existing values corresponding to entries in the mask that evaluate to false will be retained.
Valid descriptors
grb::descriptors::no_operation, grb::descriptors::no_casting, grb::descriptors::no_duplicates.
Note
Invalid descriptors will be ignored.

If grb::descriptors::no_casting is specified, then 1) the first domain of accum must match the type of D, 2) the second domain must match nnz_iterator::value_type, and 3) the third domain must D. If one of these is not true, the code shall not compile.

Performance semantics.
  1. This function contains \( \Theta(n) \) work.
  2. This function will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
  3. This function moves at most \( n ( 2\mathit{sizeof}(D) + \mathit{sizeof}(\mathit{bool}) ) + \mathcal{O}(1) \) bytes of data.
Performance exceptions
If the capacity of this container at function entry is insufficient to perform the requested operation, then, in addition to the above:
  1. this function allocates \( \Theta(n) \) bytes of memory .
  2. this function frees \( \mathcal{O}(n) \) bytes of memory.
  3. this function will make system calls.
Note
An implementation may ensure that at object construction the capacity is maximised. In that case, the above performance exceptions will never come to pass.
See also
grb::buildVector for the ALP/GraphBLAS standard dispatcher to this function.

◆ build() [3/3]

RC build ( const Vector< mask_type, implementation, C > &  mask,
const Accum &  accum,
const ind_iterator  ind_start,
const ind_iterator  ind_end,
const nnz_iterator  nnz_start,
const nnz_iterator  nnz_end,
const Dup &  dup = Dup() 
)
inline

Copy from raw user-supplied data into a vector.

This is the sparse masked variant.

Template Parameters
descrThe pre-processing descriptor to use.
mask_typeThe value type of the mask vector. This type is not required to be bool.
AccumThe type of the operator used to combine newly input data with existing data, if any.
ind_iteratorThe type of index input iterator. By default, this will be a raw unaliased pointer to elements of type size_t.
nnz_iteratorThe type of nonzero input iterator. By default, this will be a raw unaliased pointer to elements of type D.
DupThe type of operator used to combine any duplicate input values.
Parameters
[in]maskAn element is only added to this container if its index \( i \) has a nonzero at the same position in mask that evaluates true.
[in]accumThe operator to be used when writing back the result of data that was already in this container prior to calling this function.
[in]ind_startThe iterator to the first index value that should be added to this GraphBLAS vector.
[in]ind_endIterator corresponding to the end position of ind_start.
[in]nnz_startThe iterator to the first nonzero value that should be added to this GraphBLAS vector.
[in]nnz_endIterator corresponding to the end position of nnz_start.
[in]dupThe operator to be used when handling multiple nonzero values that are to be mapped to the same index position.

The first element from nnz_start will be copied into this vector at the index corresponding to the first element from ind_start. Then, both nonzero and index value iterators advance to add the next input element and the process repeats until either of the input iterators reach nnz_end or ind_end, respectively. If at that point one of the iterators still has remaining elements, then those elements are ignored.

Returns
grb::MISMATCH When attempting to insert a nonzero value at an index position that is larger or equal to the dimension of this vector. When this code is returned, the contents of this container are undefined.
grb::SUCCESS When all elements are successfully assigned.
Note
The default accumulator expects D to be of the same type as nonzero elements of this operator, and will cause old values to be overwritten by the incoming new values.
The default dup expects D to be of the same type as nonzero elements of this operator, and will cause duplicate values to be discarded in favour of the last seen value.
Previous contents of the vector are retained. If these are to be cleared first, see clear(). The default accumulator is NOT an alternative since any pre-existing values corresponding to entries in the mask that evaluate to false will be retained.
Valid descriptors
grb::descriptors::no_operation, grb::descriptors::no_casting, grb::descriptors::invert_mask, grb::descriptors::no_duplicates.
Note
Invalid descriptors will be ignored.

If grb::descriptors::no_casting is specified, then 1) the first domain of accum must match the type of D, 2) the second domain must match nnz_iterator::value_type, and 3) the third domain must D. If one of these is not true, the code shall not compile.

Performance semantics.
  1. This function contains \( \Theta(n) \) work.
  2. This function will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
  3. This function moves at most \( n ( 2\mathit{sizeof}(D) + \mathit{sizeof}(\mathit{bool}) ) + \mathcal{O}(1) \) bytes of data.
Performance exceptions
If the capacity of this container at function entry is insufficient to perform the requested operation, then, in addition to the above:
  1. this function allocates \( \Theta(n) \) bytes of memory .
  2. this function frees \( \mathcal{O}(n) \) bytes of memory.
  3. this function will make system calls.
Note
An implementation may ensure that at object construction the capacity is maximised. In that case, the above performance exceptions will never come to pass.
See also
grb::buildVector for the ALP/GraphBLAS standard dispatcher to this function.

◆ cbegin()

const_iterator cbegin ( ) const
inline

Provides the only mechanism to extract data from this GraphBLAS vector.

The order in which nonzero elements are returned is undefined.

Returns
An iterator pointing to the first element of this vector, if any; or an iterator in end position if this vector contains no nonzeroes.
Note
An ‘iterator in end position’ compares equal to the const_iterator returned by cend().
Performance semantics
  1. This function contains \( \mathcal{O}(1) \) work.
  2. This function is allowed allocate dynamic memory.
  3. This function uses up to \( \mathcal{O}(1) \) more memory than already used by this application at entry.
  4. This function shall move at most \( \mathcal{O}(1) \) bytes of data.
  5. This function may make system calls.
Warning
Avoid the use of this function within performance critical code sections.
Note
This function may make use of a const_iterator that is buffered, hence possibly causing its implicitly called constructor to allocate dynamic memory.

◆ cend()

const_iterator cend ( ) const
inline

Indicates the end to the elements in this container.

Returns
An iterator at the end position of this container.
Performance semantics
  1. This function contains \( \mathcal{O}(1) \) work.
  2. This function is not allowed allocate dynamic memory.
  3. This function uses up to \( \mathcal{O}(1) \) more memory than already used by this application at entry.
  4. This function shall move at most \( \mathcal{O}(1) \) bytes of data.
  5. This function shall not induce any system calls.
Note
Even if cbegin() returns a buffered const_iterator that may require dynamic memory allocation and additional data movement, this specification disallows the same to happen for the construction of an iterator in end position.

◆ end()

const_iterator end ( ) const
inline

Same as cend().

Since iterators are only supplied as a data extraction mechanism, there is no overloaded version of this function that returns a non-const iterator.

◆ nnz()

RC nnz ( T &  nnz) const
inline

Return the number of nonzeroes in this vector.

Template Parameters
TThe integral output type.
Parameters
[out]nnzWhere to store the number of nonzeroes contained in this vector. Its initial value is ignored.
Returns
grb::SUCCESS When the function call completes successfully.
Note
This function cannot fail.
Performance semantics
This function
  1. contains \( \Theta(1) \) work,
  2. will not allocate new dynamic memory,
  3. will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
  4. will move at most \( \mathit{sizeof}(T) + \mathit{sizeof}(\mathit{size\_t}) \) bytes of data.

◆ operator()()

lambda_reference operator() ( const size_t  i,
const Monoid monoid = Monoid() 
)
inline

Returns a lambda reference to an element of this sparse vector.

A lambda reference to an element of this vector is only valid when used inside a lambda function evaluated via grb::eWiseLambda. The lambda function is called for specific indices only– that is, the GraphBLAS implementation decides at which elements to dereference this container. Outside this scope the returned reference incurs undefined behaviour.

Warning
In particular, for the given index i by the lambda function, it shall be illegal to refer to indices relative to that i; including, but not limited to, \( i+1 \), \( i-1 \), et cetera.
Note
As a consequence, this function cannot be used to perform stencil or halo based operations.

If a previously non-existing entry of the vector is requested, a new nonzero is added at position i in this vector. The new element will have its initial value equal to the identity corresponding to the given monoid.

Warning
In parallel contexts the use of a returned lambda reference outside the context of an eWiseLambda will incur at least one of the following ill effects: it may
  1. fail outright,
  2. work on stale data,
  3. work on incorrect data, or
  4. incur high communication costs to guarantee correctness. In short, such usage causes undefined behaviour. Implementers are not advised to provide GAS-like functionality through this interface, as it invites bad programming practices and bad algorithm design decisions. This operator is instead intended to provide for generic BLAS1-type operations only.
Note
For I/O, use the iterator retrieved via cbegin() instead of relying on a lambda_reference.
Parameters
[in]iWhich element to return a lambda reference of.
[in]monoidUnder which generalised monoid to interpret the requested \( i \)th element of this vector.
Note
The monoid (or a ring) is required to be able to interpret a sparse vector. A user who is sure this vector is dense, or otherwise is able to ensure that the a lambda_reference will only be requested at elements where nonzeroes already exists, may refer to Vector::operator[],
Returns
A lambda reference to the element i of this vector.
Example.
See grb::eWiseLambda() for a practical and useful example.
Warning
There is no similar concept in the official GraphBLAS specs.
See also
lambda_reference For more details on the returned reference type.
grb::eWiseLambda For one legal way in which to use the returned lambda_reference.

◆ operator=()

Vector< D, implementation, C > & operator= ( Vector< D, implementation, C > &&  x)
inlinenoexcept

Move-from-temporary assignment.

Parameters
[in,out]xThe temporary instance from which this instance shall take over its resources.

After a call to this function, x shall correspond to an empy vector.

Performance semantics
  1. This move assignment completes in \( \Theta(1) \) time.
  2. This move assignment may not make system calls.
  3. this move assignment moves \( \Theta(1) \) data only.

◆ operator[]()

lambda_reference operator[] ( const size_t  i)
inline

Returns a lambda reference to an element of this vector.

Warning
This functionality may only be used within the body of a lambda function that is passed into grb::eWiseLambda.

The user must ensure that the requested reference only corresponds to a pre-existing nonzero in this vector.

Warning
Requesting a nonzero entry at a coordinate where no nonzero exists results in undefined behaviour.

A lambda reference to an element of this vector is only valid when used inside a lambda function evaluated via grb::eWiseLambda. The lambda function is called for specific indices only– that is, ALP/GraphBLAS decides at which elements to dereference this container.

If such a lambda function dereferences multiple vectors, then the sparsity structure of the first vector passed as an argument to grb::eWiseLambda after the lambda function defines at which indices the vectors will be referenced. The user must ensure that all vectors dereferenced indeed have nonzeroes at every location this "leading vector" has a nonzero.

Warning
In particular, for the given index i by the lambda function, it shall be illegal to refer to indices relative to that i; including, but not limited to, \( i+1 \), \( i-1 \), et cetera.
Note
As a consequence, this function cannot be used to perform stencil or halo type operations.
For I/O purposes, use the iterator retrieved via cbegin() instead of relying on a lambda_reference.
Parameters
[in]iWhich element to return a lambda reference of.
Returns
A lambda reference to the element i of this vector.
Example.
See grb::eWiseLambda for a practical and useful example.
See also
lambda_reference For more details on the returned reference type.
grb::eWiseLambda For one way to use the returned lambda_reference.

◆ size()

RC size ( T &  size) const
inline

Return the dimension of this vector.

Template Parameters
TThe integral output type.
Parameters
[out]sizeWhere to store the size of this vector. The initial value is ignored.
Returns
grb::SUCCESS When the function call completes successfully.
Note
This function cannot fail.
Performance semantics
This function
  1. contains \( \Theta(1) \) work,
  2. will not allocate new dynamic memory,
  3. will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
  4. will move at most \( \mathit{sizeof}(T) + \mathit{sizeof}(\mathit{size\_t}) \) bytes of data.

The documentation for this class was generated from the following file: