4. `LvArray::SortedArray`¶

The LvArray::SortedArray functions similarly to a std::set except that unlike a std::set the values are stored contiguously in memory like a std::vector. Like the std::set the cost of seeing if a LvArray::SortedArray a contains a value is $O(log(N))$ however the const of inserting or removing a value is $O(N)$ where N = a.size().

4.1. Template arguments¶

The LvArray::SortedArray requires three template arguments.

T: The type of values stored in the set.
INDEX_TYPE: An integral type used in index calculations, the suggested type is std::ptrdiff_t.
BUFFER_TYPE: A template template parameter specifying the buffer type used for allocation and de-allocation, the LvArray::SortedArray contains a BUFFER_TYPE< T >.

Note

Unlike std::set, LvArray::SortedArray does not yet support a custom comparator, it us currently hard coded to operator< to sort values from least to greatest.

4.2. Creating and accessing a `LvArray::SortedArray`¶

The LvArray::SortedArray has a single default constructor which creates an empty set. The only way to modify the set is through the methods insert and remove. These methods are similar to the std::set methods of the same name except that when inserting or removing multiple values at once the values need to be sorted and unique. LvArray::SortedArray also has an operator[] and data method that provide read only access to the values.

TEST( SortedArray, construction )
{
  // Construct an empty set.
  LvArray::SortedArray< std::string, std::ptrdiff_t, LvArray::MallocBuffer > set;
  EXPECT_TRUE( set.empty() );

  // Insert two objects one at a time.
  EXPECT_TRUE( set.insert( "zebra" ) );
  EXPECT_TRUE( set.insert( "aardvark" ) );

  // "zebra" is already in the set so it won't be inserted again.
  EXPECT_FALSE( set.insert( "zebra" ) );

  // Query the contents of the set.
  EXPECT_EQ( set.size(), 2 );
  EXPECT_TRUE( set.contains( "zebra" ) );
  EXPECT_FALSE( set.contains( "whale" ) );

  // Insert two objects at once.
  std::string const moreAnimals[ 2 ] = { "cat", "dog" };
  EXPECT_EQ( set.insert( moreAnimals, moreAnimals + 2 ), 2 );

  // Remove a single object.
  set.remove( "aardvark" );

  EXPECT_EQ( set.size(), 3 );
  EXPECT_EQ( set[ 0 ], "cat" );
  EXPECT_EQ( set[ 1 ], "dog" );
  EXPECT_EQ( set[ 2 ], "zebra" );
}

[Source: examples/exampleSortedArray.cpp]

4.3. `LvArray::SortedArrayView`¶

LvArray::SortedArrayView is the view class of LvArray::SortedArray and it shares all the same template parameters. To construct a LvArray::SortedArrayView you must call toView() on an existing LvArray::SortedArray or create a copy of an existing LvArray::SortedArrayView. The LvArray::SortedArrayView is not allowed to insert or remove values. As such the return type of LvArray::SortedArray< T, ... >::toView() is an LvArray::SortedArrayView< T const, ... >

Note

Unlike LvArray::ArrayView the LvArray::SortedArrayView does not yet support default construction.

4.4. Usage with `LvArray::ChaiBuffer`¶

When using the LvArray::ChaiBuffer as the buffer type the LvArray::SortedArray can exist in multiple memory spaces. It can be explicitly moved between spaces with the method move. Because the SortedArrayView cannot modify the values the data is never touched when moving to device, even if the optional touch parameter is set to false.

It is worth noting that after a LvArray::SortedArray is moved to the device it must be explicitly moved back to the host by calling move( MemorySpace::host ) before it can be safely modified. This won’t actually trigger a memory copy since the values weren’t touched on device, its purpose is to let CHAI know that the values were touched on the host so that the next time it is moved to device it will copy the values back over.

CUDA_TEST( SortedArray, ChaiBuffer )
{
  // Construct an empty set consisting of the even numbers { 0, 2, 4 }.
  LvArray::SortedArray< int, std::ptrdiff_t, LvArray::ChaiBuffer > set;
  int const values[ 4 ] = { 0, 2, 4 };
  EXPECT_EQ( set.insert( values, values + 3 ), 3 );
  EXPECT_EQ( set.size(), 3 );

  // Create a view and capture it on device, this will copy the data to the device.
  RAJA::forall< RAJA::cuda_exec< 32 > >(
    RAJA::TypedRangeSegment< std::ptrdiff_t >( 0, set.size() ),
    [view = set.toView()] __device__ ( std::ptrdiff_t const i )
  {
    LVARRAY_ERROR_IF_NE( view[ i ], 2 * i );
    LVARRAY_ERROR_IF( view.contains( 2 * i + 1 ), "The set should only contain odd numbers!" );
  }
    );

  // Move the set back to the CPU and modify it.
  set.move( LvArray::MemorySpace::host );
  set.insert( 6 );

  // Verify that the modification is seen on device.
  RAJA::forall< RAJA::cuda_exec< 32 > >(
    RAJA::TypedRangeSegment< std::ptrdiff_t >( 0, 1 ),
    [view = set.toView()] __device__ ( std::ptrdiff_t const )
  {
    LVARRAY_ERROR_IF( !view.contains( 6 ), "The set should contain 6!" );
  }
    );
}

[Source: examples/exampleSortedArray.cpp]

4.5. Usage with `LVARRAY_BOUNDS_CHECK`¶

Like LvArray::Array when LVARRAY_BOUNDS_CHECK is defined access via operator[] is checked for invalid access. If an out of bounds access is detected the program is aborted. In addition calls to insert and remove multiple values will error out if the values to insert or remove aren’t sorted and unique.

TEST( SortedArray, boundsCheck )
{
  // Create a set containing {2, 4}
  LvArray::SortedArray< int, std::ptrdiff_t, LvArray::MallocBuffer > set;
  set.insert( 4 );
  set.insert( 2 );

  // Invalid access.
  EXPECT_DEATH_IF_SUPPORTED( set[ 5 ], "" );

  // Attempt to insert unsorted values.
  int const unsortedInsert[ 2 ] = { 4, 0 };
  EXPECT_DEATH_IF_SUPPORTED( set.insert( unsortedInsert, unsortedInsert + 2 ), "" );

  // Attempt to insert nonUnique values.
  int const notUnique[ 2 ] = { 5, 5 };
  EXPECT_DEATH_IF_SUPPORTED( set.insert( notUnique, notUnique + 2 ), "" );

  // Attempt to remove unsorted values.
  int const unsortedRemove[ 2 ] = { 4, 2 };
  EXPECT_DEATH_IF_SUPPORTED( set.remove( unsortedRemove, unsortedRemove + 2 ), "" );
}

[Source: examples/exampleSortedArray.cpp]

4.6. Guidelines¶

Batch insertion and removal is much faster than inserting or removing each value individually. For example calling a.insert( 5 ) has complexity O( a.size() ) but calling a.insert( first, last ) only has complexity O( a.size() + std::distance( first, last ) ). The function LvArray::sortedArrayManipulation::makeSortedUnique can help with this as it takes a range, sorts it and removes any duplicate values. When possible it is often faster to append values to a temporary container, sort the values, remove duplicates and then perform the operation.

TEST( SortedArray, fastConstruction )
{
  LvArray::SortedArray< int, std::ptrdiff_t, LvArray::MallocBuffer > set;

  // Create a temporary list of 100 random numbers between 0 and 99.
  std::vector< int > temporarySpace( 100 );
  std::mt19937 gen;
  std::uniform_int_distribution< int > dis( 0, 99 );
  for( int i = 0; i < 100; ++i )
  {
    temporarySpace[ i ] = dis( gen );
  }

  // Sort the random numbers and move any duplicates to the end.
  std::ptrdiff_t const numUniqueValues = LvArray::sortedArrayManipulation::makeSortedUnique( temporarySpace.begin(),
                                                                                             temporarySpace.end() );

  // Insert into the set.
  set.insert( temporarySpace.begin(), temporarySpace.begin() + numUniqueValues );
}

[Source: examples/exampleSortedArray.cpp]

4. LvArray::SortedArray¶

4.1. Template arguments¶

4.2. Creating and accessing a LvArray::SortedArray¶

4.3. LvArray::SortedArrayView¶

4.4. Usage with LvArray::ChaiBuffer¶

4.5. Usage with LVARRAY_BOUNDS_CHECK¶

4.6. Guidelines¶

4.7. Doxygen¶

4. `LvArray::SortedArray`¶

4.2. Creating and accessing a `LvArray::SortedArray`¶

4.3. `LvArray::SortedArrayView`¶

4.4. Usage with `LvArray::ChaiBuffer`¶

4.5. Usage with `LVARRAY_BOUNDS_CHECK`¶