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

D	The type of an element of this vector. D shall not be a GraphBLAS type.
implementation	Allows different backends to implement different versions of this data type.
C	The 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(

Vector< D >::lambda_reference x,

const Vector< D >::lambda_reference y,

const Vector< D > &v

) {

grb::eWiseLambda( [x,y](const size_t i) {

x += y;

}, v );

}

grb::Vector::lambda_reference
D & lambda_reference
Defines a reference to a value of type D.
Definition: vector.hpp:124

grb::eWiseLambda
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).
void f(

Vector< D >::lambda_reference x,

const Vector< D >::lambda_reference y

) {

x += y;

}

Also this usage is illegal since it does not rely on any GraphBLAS-approved function listed above:
void f(

Vector< D >::lambda_reference x,

const Vector< D >::lambda_reference y

) {

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]	n	The dimension of this vector.
[in]	nz	The minimal initial capacity of this vector.

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

Performance semantics

A backend must:

define cost in terms of work,
define intra-process data movement costs,
define inter-process data movement costs,
define whether inter-process synchronisations occur,
define memory storage requirements and may define this in terms of n and/or nz, and
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] x The GraphBLAS vector to move to this new container.

Performance semantics

This constructor completes in \( \Theta(1) \) time.
This constructor does not allocate new data on the heap.
This constructor uses \( \mathcal{O}(1) \) more memory than already used by this application at constructor entry.
This constructor incurs at most \( \mathcal{O}(1) \) bytes of data movement.

◆ ~Vector()

~Vector ( )

inline

Default destructor.

Frees all associated memory areas.

Performance semantics

This destructor contains \( \mathcal{O}(n) \) work, where \( n \) is the capacity of this vector.
This destructor is only allowed to free memory, not allocate.
This destructor uses \( \mathcal{O}(1) \) more memory than already used by this application at entry.
This destructor shall move at most \( \mathcal{O}(n) \) bytes of data.
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

descr	The pre-processing descriptor to use.
fwd_iterator	The type of input iterator. By default, this will be a raw unaliased pointer.
Accum	The accumulator type used to merge incoming new elements with existing contents, if any.

Parameters

[in]	accum	The accumulator used to merge incoming new elements with existing content, if any.
[in]	start	The iterator to the first element that should be copied into this GraphBLAS vector.
[in]	end	Iterator shifted exactly one past the last element that should be copied into this GraphBLAS vector.
[out]	npos	The 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:

This function contains \( \Theta(n) \) work.
This function will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
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:

this function allocates \( \Theta(n) \) bytes of memory .
this function frees \( \mathcal{O}(n) \) bytes of memory.
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

descr	The pre-processing descriptor to use.
Accum	The type of the operator used to combine newly input data with existing data, if any.
ind_iterator	The type of index input iterator. By default, this will be a raw unaliased pointer to elements of type size_t.
nnz_iterator	The type of nonzero input iterator. By default, this will be a raw unaliased pointer to elements of type D.
Dup	The type of operator used to combine any duplicate input values.

Parameters

[in]	accum	The operator to be used when writing back the result of data that was already in this container prior to calling this function.
[in]	ind_start	The iterator to the first index value that should be added to this GraphBLAS vector.
[in]	ind_end	Iterator corresponding to the end position of ind_start.
[in]	nnz_start	The iterator to the first nonzero value that should be added to this GraphBLAS vector.
[in]	nnz_end	Iterator corresponding to the end position of nnz_start.
[in]	dup	The 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.

This function contains \( \Theta(n) \) work.
This function will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
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:

this function allocates \( \Theta(n) \) bytes of memory .
this function frees \( \mathcal{O}(n) \) bytes of memory.
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

descr	The pre-processing descriptor to use.
mask_type	The value type of the mask vector. This type is not required to be bool.
Accum	The type of the operator used to combine newly input data with existing data, if any.
ind_iterator	The type of index input iterator. By default, this will be a raw unaliased pointer to elements of type size_t.
nnz_iterator	The type of nonzero input iterator. By default, this will be a raw unaliased pointer to elements of type D.
Dup	The type of operator used to combine any duplicate input values.

Parameters

[in]	mask	An element is only added to this container if its index \( i \) has a nonzero at the same position in mask that evaluates true.
[in]	accum	The operator to be used when writing back the result of data that was already in this container prior to calling this function.
[in]	ind_start	The iterator to the first index value that should be added to this GraphBLAS vector.
[in]	ind_end	Iterator corresponding to the end position of ind_start.
[in]	nnz_start	The iterator to the first nonzero value that should be added to this GraphBLAS vector.
[in]	nnz_end	Iterator corresponding to the end position of nnz_start.
[in]	dup	The 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.

This function contains \( \Theta(n) \) work.
This function will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
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:

this function allocates \( \Theta(n) \) bytes of memory .
this function frees \( \mathcal{O}(n) \) bytes of memory.
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

This function contains \( \mathcal{O}(1) \) work.
This function is allowed allocate dynamic memory.
This function uses up to \( \mathcal{O}(1) \) more memory than already used by this application at entry.
This function shall move at most \( \mathcal{O}(1) \) bytes of data.
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

This function contains \( \mathcal{O}(1) \) work.
This function is not allowed allocate dynamic memory.
This function uses up to \( \mathcal{O}(1) \) more memory than already used by this application at entry.
This function shall move at most \( \mathcal{O}(1) \) bytes of data.
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

T	The integral output type.

Parameters

[out] nnz Where 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

contains \( \Theta(1) \) work,
will not allocate new dynamic memory,
will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
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

fail outright,
work on stale data,
work on incorrect data, or
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]	i	Which element to return a lambda reference of.
[in]	monoid	Under 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] x The 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

This move assignment completes in \( \Theta(1) \) time.
This move assignment may not make system calls.
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] i Which 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

T	The integral output type.

Parameters

[out] size Where 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

contains \( \Theta(1) \) work,
will not allocate new dynamic memory,
will take at most \( \Theta(1) \) memory beyond the memory already used by the application before the call to this function.
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:

vector.hpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ lambda_reference

Constructor & Destructor Documentation

◆ Vector() [1/3]

◆ Vector() [2/3]

◆ Vector() [3/3]

◆ ~Vector()

Member Function Documentation

◆ begin()

◆ build() [1/3]

◆ build() [2/3]

◆ build() [3/3]

◆ cbegin()

◆ cend()

◆ end()

◆ nnz()

◆ operator()()

◆ operator=()

◆ operator[]()

◆ size()