6. LvArray::ArrayOfSets

The LvArray::ArrayOfSets is very similar to the LvArray::ArrayOfArrays except that the values of the inner arrays are sorted an unique like the LvArray::SortedArray. If you are familiar with both of these classes the functionality of the LvArray::ArrayOfSets should be pretty straightforward.

6.1. Template arguments

The LvArray::ArrayOfArrays requires three template arguments.

  1. T: The type of values stored in the inner arrays.
  2. INDEX_TYPE: An integral type used in index calculations, the suggested type is std::ptrdiff_t.
  3. BUFFER_TYPE: A template template parameter specifying the buffer type used for allocation and de-allocation, the LvArray::ArrayOfArrays contains a BUFFER_TYPE< T > along with two BUFFER_TYPE< INDEX_TYPE >.

6.2. Usage

All of the functionality for modifying the outer array from LvArray::ArrayOfArrays is present in the LvArray::ArrayOfSets although it might go by a different name. For example instead of appendArray there is appendSet. However like LvArray::SortedArray the only options for modifying the inner sets are through either insertIntoSet` or ``removeFromSet.

TEST( ArrayOfSets, examples )
{
  LvArray::ArrayOfSets< std::string, std::ptrdiff_t, LvArray::MallocBuffer > arrayOfSets;

  // Append a set with capacity 2.
  arrayOfSets.appendSet( 2 );
  arrayOfSets.insertIntoSet( 0, "oh" );
  arrayOfSets.insertIntoSet( 0, "my" );

  // Insert a set at the beginning with capacity 3.
  arrayOfSets.insertSet( 0, 3 );
  arrayOfSets.insertIntoSet( 0, "lions" );
  arrayOfSets.insertIntoSet( 0, "tigers" );
  arrayOfSets.insertIntoSet( 0, "bears" );

  // "tigers" is already in the set.
  EXPECT_FALSE( arrayOfSets.insertIntoSet( 0, "tigers" ) );

  EXPECT_EQ( arrayOfSets( 0, 0 ), "bears" );
  EXPECT_EQ( arrayOfSets( 0, 1 ), "lions" );
  EXPECT_EQ( arrayOfSets( 0, 2 ), "tigers" );

  EXPECT_EQ( arrayOfSets[ 1 ][ 0 ], "my" );
  EXPECT_EQ( arrayOfSets[ 1 ][ 1 ], "oh" );
}

[Source: examples/exampleArrayOfSets.cpp]

LvArray::ArrayOfSets also has a method assimilate which takes an rvalue-reference to an LvArray::ArrayOfArrays and converts it to a LvArray::ArrayOfSets. LvArray::ArrayOfArrays also has a similar method.

TEST( ArrayOfSets, assimilate )
{
  LvArray::ArrayOfSets< int, std::ptrdiff_t, LvArray::MallocBuffer > arrayOfSets;

  // Create an ArrayOfArrays and populate the inner arrays with sorted unique values.
  LvArray::ArrayOfArrays< int, std::ptrdiff_t, LvArray::MallocBuffer > arrayOfArrays( 3 );

  // The first array is empty, the second is {0} and the third is {0, 1}.
  arrayOfArrays.emplaceBack( 1, 0 );
  arrayOfArrays.emplaceBack( 2, 0 );
  arrayOfArrays.emplaceBack( 2, 1 );

  // Assimilate arrayOfArrays into arrayOfSets.
  arrayOfSets.assimilate< RAJA::loop_exec >( std::move( arrayOfArrays ),
                                             LvArray::sortedArrayManipulation::Description::SORTED_UNIQUE );

  // After being assimilated arrayOfArrays is empty.
  EXPECT_EQ( arrayOfArrays.size(), 0 );

  // arrayOfSets now contains the values.
  EXPECT_EQ( arrayOfSets.size(), 3 );
  EXPECT_EQ( arrayOfSets.sizeOfSet( 0 ), 0 );
  EXPECT_EQ( arrayOfSets.sizeOfSet( 1 ), 1 );
  EXPECT_EQ( arrayOfSets.sizeOfSet( 2 ), 2 );
  EXPECT_EQ( arrayOfSets( 1, 0 ), 0 );
  EXPECT_EQ( arrayOfSets( 2, 0 ), 0 );
  EXPECT_EQ( arrayOfSets( 2, 1 ), 1 );

  // Resize arrayOfArrays and populate it the inner arrays with values that are neither sorted nor unique.
  arrayOfArrays.resize( 2 );

  // The first array is {4, -1} and the second is {4, 4}.
  arrayOfArrays.emplaceBack( 0, 3 );
  arrayOfArrays.emplaceBack( 0, -1 );
  arrayOfArrays.emplaceBack( 1, 4 );
  arrayOfArrays.emplaceBack( 1, 4 );

  // Assimilate the arrayOfArrays yet again.
  arrayOfSets.assimilate< RAJA::loop_exec >( std::move( arrayOfArrays ),
                                             LvArray::sortedArrayManipulation::Description::UNSORTED_WITH_DUPLICATES );

  EXPECT_EQ( arrayOfSets.size(), 2 );
  EXPECT_EQ( arrayOfSets.sizeOfSet( 0 ), 2 );
  EXPECT_EQ( arrayOfSets.sizeOfSet( 1 ), 1 );
  EXPECT_EQ( arrayOfSets( 0, 0 ), -1 );
  EXPECT_EQ( arrayOfSets( 0, 1 ), 3 );
  EXPECT_EQ( arrayOfSets( 1, 0 ), 4 );
}

[Source: examples/exampleArrayOfSets.cpp]

6.3. LvArray::ArrayOfSetsView

The LvArray::ArrayOfSetsView is the view counterpart to LvArray::ArrayOfSets. Functionally it is very similar to the LvArray::ArrayOfArraysView in that it cannot modify the outer array but it can modify the inner sets as long as their capacities aren’t exceeded. Unlike LvArray::ArrayOfArraysView however it doesn’t have the CONST_SIZES template parameter. This is because if you can’t change the size of the inner arrays then you also can’t modify their values. Specifically an LvArray::ArrayOfSetsView< T, INDEX_TYPE, BUFFER_TYPE > contains the following buffers:

  1. BUFFER_TYPE< T > values: Contains the values of each inner set.
  2. BUFFER-TYPE< std::conditional_t< std::is_const< T >::value, INDEX_TYPE const, INDEX_TYPE > >: Of length array.size(), sizes[ i ] contains the size of the inner set i.
  3. BUFFER_TYPE< INDEX_TYPE > offsets: Of length array.size() + 1, inner set i begins at values[ offsets[ i ] ] and has capacity offsets[ i + 1 ] - offsets[ i ].

From an LvArray::ArrayOfSets< T, INDEX_TYPE, BUFFER_TYPE > you can get three view types by calling the following methods

  • toView() returns an LvArray::ArrayOfSetsView< T, INDEX_TYPE const, BUFFER_TYPE >.
  • toViewConst() returns an LvArray::ArrayOfSetsView< T const, INDEX_TYPE const, BUFFER_TYPE >.
  • toArrayOfArraysView() returns an LvArray::ArrayOfArraysView< T const, INDEX_TYPE const, true, BUFFER_TYPE >.

6.4. Usage with LvArray::ChaiBuffer

The two types of LvArray::ArrayOfSetsView obtainable from an LvArray::ArrayOfSets act differently when moved to a new memory space.

  • LvArray::ArrayOfSetsView< T, INDEX_TYPE const, LvArray::ChaiBuffer >, obtained by calling toView(). When it is moved to a new space the values are touched as well as the sizes. The offsets are not touched.
  • LvArray::ArrayOfSetsView< T const, INDEX_TYPE const, LvArray::ChaiBuffer >, obtained by calling toViewConst(). None of the buffers are touched in the new space.

Calling the explicit move method with the touch parameter set to true on a view type has the behavior described above. However calling move( MemorySpace::host ) on an LvArray::ArrayOfSets will also touch the offsets (if moving to the GPU the offsets aren’t touched). This is the only way to touch the offsets so if an LvArray::ArrayOfSets was previously on the device then it must be explicitly moved and touched on the host before any modification to the offsets can safely take place.

6.5. Usage with LVARRAY_BOUNDS_CHECK

When LVARRAY_BOUNDS_CHECK is defined access via operator[] and operator() is checked. If an invalid access is detected the program is aborted. Methods such as sizeOfArray, insertArray and emplace are also checked. The values passed to insertIntoSet and removeFromSet are also checked to ensure they are sorted and contain no duplicates.

6.6. Guidelines

Like LvArray::SortedArray batch insertion and removal from an inner set is much faster than inserting or removing each value individually.

All the tips for efficiently constructing an LvArray::ArrayOfArrays apply to constructing an LvArray::ArrayOfSets. The main difference is that LvArray::ArrayOfSets doesn’t support concurrent modification of an inner set. Often if the sorted-unique properties of the inner sets aren’t used during construction it can be faster to first construct a LvArray::ArrayOfArrays where each inner array can contain duplicates and doesn’t have to be sorted and then create the LvArray::ArrayOfSets via a call to assimilate.