Ranges: Usage Examples

Here we highlight the ways in which we would like the usage of the ranges library to look like.

helpers

A typedef for a vector to use aligned allocator.

template <typename T>
using aligned_vector = std::vector<T, eve::aligned_allocator<T, sizeof(eve::wide<T>)>;

A complex predicate that the user might want to avoid unrolling

auto complex_check = [threshold = eve::wide<float>(0.3f)](eve::wide<float> x) { return eve::sin(x) < threshold; };

find a number

find(int const*, int const*, int) -> int const*
find(std::vector<int> const&, int) -> std::vector<int>::const_iterator

This use-case illustrates that we need to do one of two things: either propagate iterators all the way through the system or have some sort of interface unification on the top level.

find a number matching some condition

find_if(int const*, int const*, [](eve::wide<int> x) { return x > 5; }) -> int const*
find_if(float const*, float const*, complex_check) -> float const*

We are illustrating here that the predicate always accepts wide<int> and the user does not have to deal with different widths. This is especially useful if the user needs to drop down to the intrinsic level from eve.

find with aligned start

find(aligned_ptr<int const>, int const*, int) -> int const*
find(aligned_vector<int> const&, int) -> aligned_vector<int>::const_iterator

We should be able to pass an aligned_ptr instead of the first argument. However we can't return aligned_ptr since the position might be not aligned.

disable unrolling

find(eve::ranges::no_unrolling, eve::aligned_ptr<float const>, float const*, complex_check) -> float const*
find(eve::ranges::no_unrolling, const aligned_vector<float>&, complex_check) -> aligned_vector<float>::const_iterator

The default unrolling in my experiments should probably be 4. However, the user should be able to tweak it. When she has a complicated check - the unroll should be disabled by the user. One possible way to control it is with optional traits parameter.

aligned end

find(eve::ranges::aligned_from_both_sides(aligned_vector<float>::const_iterator, aligned_vector<float>::const_iterator),
     complex_check) -> float const*

When executing implementing a both multithreaded and simd optimized search, we can control the division in sub ranges. In this case we might want to align both sides so there are no ends to clean up for most threads. EVE should support this. One way'd be to pass aligned_ptr for both begin/end or here we use example of aligned_from_both_sides helper.

Mismatch using find

Fundamentally, mismatch and find are the same algorithm, just operating on zipped ranges. We need to take into account the conversions. If with other examples we were quite sure on how it's going to look, this one is very much up in the air.

// We are better off using structs instead of functions since we
// can share some properties between different algorithms.

namespace eve::ranges {

struct mismatch_t {
  // We want to reuse the default traits from find.
  static constexpr auto default_traits = eve::ranges::find_t::default_traits;

  // Basic version
  template <
            input_iterator I1, input_iterator I2, // eve has to have it's own iterator concept see below
            typename P                            // concept on the predicate is a touch tricky
           >
  auto operator()(
    auto traits,
    I1 f1,            // Since we can do aligned/non-aligned pointers 
    sentinel<I1> l1,  // we need to have different types for begin/end
    I2 f2,
    P p,
  ) const 
 -> std::pair<unaligned_iterator<I1>, unaligned_iterator<I2>> // We need to strip alignment from result type
  {
    // We need to understand the cardinality we operate on. Each iterator has it's cardinality. 
    // Traits can supply custom cardinality.
    auto N = select_cardinality(traits, eve::cardinality<I1>{}, eve::cardinality<I2>{});

    // Get a zipped range, length == to the [f1, l1)
    // Maybe we need to put some of the cardinality business in zip.
    auto zipped = zip(cardinality_cast<N>(range_pair{f1, l1}), cardinality_cast<N>(f2));

    auto [r1, r2] = find_if(traits, zipped,
       [&](
         // Element type of the zipped is a tuple of wides
         // for each range. They have to have the same cardinality.
         tuple<
            eve::wide<value_type<I1>, N>,
            eve::wide<value_type<I2>, N>
          > e
       ) {
         // After the bugs we reported to compilers, we expect negation to be properly optimized
         return !p(get<0>(e), get<1>(e)));
       });

    // After zip we need to undo our zipping. The find will already deal with unwrapping alignments.
    return std::pair{ cardinality_cast<cardinality<I1>>(r1), 
                      cardinality_cast<cardinality<I2>>(r2) };
  }

  // Using default equality
  template <input_iterator I1, input_iterator I2>
  // requires is again tricky
  auto operator()(auto traits, I1 f1, sentinel<I1> l1, I2 l2) const
    -> std::pair<unaligned_iterator<I1>, unaligned_iterator<I2>>
 {
    // Equality can only be applied to the same type. 
    // Assuming we can `load(as_)` we can have a converting_iterator.
    using common_t = std::common_type<value_type<I1>, value_type<I2>>;

    auto [r1, r2] = operator()(
                      traits,
                      make_converting_iterator<common_t>(f1), make_converting_iterator<common_t>(l1),
                      make_converting_iterator<common_t>(f2), 
                      eve::is_equal);

    // The interface here seriously needs more thinking
    return std::pair{iter_cast<unaligned_iterator<I1>>(r1.base()), iter_cast<unaligned_iterator<I2>>(r2.base())};
  }
} constexpr mismatch;

}  // namespace eve::ranges