Ranges, what it should look like

[DenisYaroshevskiy]

I started writing a wiki page: https://github.com/jfalcou/eve/wiki/Ranges
At this point could be good for others to have a look.

[jfalcou]

Here is a first bunch of comments on the main goal pages:

GOALS

Potential for all STL algorithms

Even though some algorithms like sort, remove or merge require quite complicated simd operations that I don’t see in our immediate future, we have to have a clear understanding on how we would like them to look.

We agree. We should also be flexible enough to cover new state of the art algorithms that don't exist in std::

ZIP support

There are two ways of structuring data: AoS (array of structs) and SoA (structs of arrays). For SIMD however using AoS is much worse since one would need to do complicated shuffles in order to extract fields. Which means we need to support SoA as a first class citizen - hense ZIP.

Agree

Close to STL / ranges interface by default

C++ developers are familiar with STL and we want to capitalize on that experience. However in some cases the STL interfaces will be extremely inefficient (for example - copy_if requires to know the output size in SIMD implementation), in which case we want to be very explicit about it and guarantee compilation breakage.

We must be as familiar as possible till the point it deserves us. I think that if somethign can't be done efficiently usign std interface, we must change it.

Alternative: we can sacrifice the consistency with STL in order to be internally consistent, for example since we need to know the output size for copy_if we can demand it for transform as well.

Can't using range-like object (ie begin/end pair in a single object) helps us in this point ?

Customisability

Even though we want simplicity by default, SIMD is mostly about efficiency, so we want to provide nobs to tweak things like unrolling, guarantee that the range length is divisible by the cardinality of the register etc. The specific tweaks are algorithm specific.

I think this is where our named parameters support will come handy cause it won't clutter the interface. Especially now that raberu supports concepts over keywords.

One argument type for callbacks

There are maybe some incentives to use different register width within the same algorithm. However it makes writing custom predicates much more complicated. Consider a trick with implementing is_space with a shuffle on sse4. We want to just be able to pass that to find without needing to deal with different wide cardinalities.

Are we OK we still support the case where people actually pass us a polymorphic lambda using cardinal-agnostic code?

NON-GOALS

Non contiguous ranges

Theoretically using gather and scatter we could implement support for non contiguous ranges. However, we believe it to be a very niche use case and do not take it into account at the moment.

Yes, they are too niche to be used generically. We may end up usign scatter/gather in higher level constructs that may end up in aside libraries.

Conceptually different iterator/sentinel types

Though std::ranges found a great use out of smth like counted ranges, we do not yet see how to incorporate them efficiently.

Agree

[DenisYaroshevskiy]

We must be as familiar as possible till the point it deserves us. I think that if somethign can't be done efficiently usign std interface, we must change it.

Yep. For example an interface for std::remove_copy(f, l, o) does not work for us. We need remove_copy(f, I l, o_f, o_l) to know how much space we have. In case of trying to right more data than is available in the output, we can assert for example.

However, given that we have these modified interfaces, what about interfaces where we do not need the output size. For example transform(f, l, o) is perfectly fine. However, maybe we want to require (f, l, o_f, o_l) for consistency.
There are also some unclear implications of what if distance(f, l) > distance(o_f, o_l). Maybe just an assert or some semantics to that.

Another thing I didn't mention is that we can get some efficiency from knowing that the operation is performed in place. So transform(f, l) where the output iterator is implicitly the input iterator should also be available.

Can't using range-like object (ie begin/end pair in a single object) helps us in this point ?

Sure, any place where we accept an iterator pair (or maybe even a single iterator?) should be able to accept a range instead.

I think this is where our named parameters support will come handy cause it won't clutter the interface. Especially now that raberu supports concepts over keywords.

Sure, why not. I would maybe bind them all together in one traits parameter but this is a 100% bike-shedding question.

Are we OK we still support the case where people actually pass us a polymorphic lambda using cardinal-agnostic code?

I am not sure what you mean.

I think that all of the following should be fine:

find(const char*, const char*, [](auto x) { return x == 0; });
find(const char*, const char*, [](eve::wide<char> x) { return x == 0; });
find(const char*, const char*, [](__m128i x) {
  static_assert(eve::current_api <= eve::avx2);
  // use intrinsics
  return eve::logical<eve::wide<char>>(x);  // Would prefer to force the cast to logical on user
                                            // because then you can do a conversion inside
});

[jfalcou]

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

helpers

I guess this section is just saying we define those types for further discussion? Or do we want to provide such things as aligned_vector?

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.

I thought we were looking at find returning an std::optional<T> ?

find a number matching some condition

This is especially useful if the user needs to drop down to the intrinsic level from eve.
Normally, this should happen rarely anyway ?

disable unrolling

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.

FYI, Raberu gives use

template<rbr::keyword_parameter... Options>
find(eve::aligned_ptr<float const>, float const*, complex_check, Options&& ... args) -> float const*
requires( rbr::match<Options...>::with( eve::unroll_factor | eve::no_unrolling) )

aligned end

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.

Old Boost.SIMD had a aligned_range(T*, T*) that returned a pair of pointer pre-realigned. Is it what we want here ?

[DenisYaroshevskiy]

I guess this section is just saying we define those types for further discussion? Or do we want to provide such things as aligned_vector?

Yeah, this is just for examples to work. We'd need to probably understand that the aligned_vector begin is aligned.

I thought we were looking at find returning an std::optional<T> ?

I am not sure what would that mean. You want to return a copy of the value we found? That doesn't seem very helpful.
And index we could make work but I'd just follow how stl does it.

Here is a prototype from some time back:
https://github.com/DenisYaroshevskiy/unsq_eve/blob/977794c06f504ee03c027e9415f4a451b2ceb5d9/src/unsq_eve/find.h#L100

FYI, Raberu gives use ...

More than happy to hear suggestions.

Old Boost.SIMD had a aligned_range(T*, T*) that returned a pair of pointer pre-realigned. Is it what we want here ?

I don't think so. I should've been clearer in the example.

Here is a more complete version (didn't test obviously, sorry for bugs)

const int* find(std::execution::parallel_unsequenced_policy, const int* f, const int* l, int v) { 
  int concurrency = std::thread::hardware_concurrency();
  int chunk_size = (f - l) / concurrency / eve::expected_cardinality<int> * eve::expected_cardinality<int>;

  // We want the chunks in the middle to be aligned from both sides
  eve::aligned_ptr end_of_first_chunk = eve::previous_aligned_address(f + chunk_size);
  eve::aligned_ptr start_of_last_chunk = eve::previous_aligned_address(l - chunk_size);

  int chunk_count = /*..*/
  std::vector<const int*> local_results (nullptr, chunk_count);
  std::vector<std::jthread> threads;

  auto find_in_chunk = [&](int chunk_num, auto f, auto l) {
     // here this `aligned_from_both_sides ` could be used for intermediate chunks
     // We didn't need it however because we used the eve::aligned_ptr
     const int* found = eve::find(f, l, v); 
     if (found != l) local_results[chunk_num] = found;
  };

  threads.push_back(find_in_chunk, f, end_of_first_chunk);
  auto f = end_of_first_chunk;
  while (f != start_of_last_chunk) {
    auto l = f + chunk_size;
    threads.push_back(find_in_chunk, f, l);
  }
  threads.push_back(find_in_chunk, start_of_last_chunk, l);
  
  for (auto& t: threads) t.join();
  
  return *eve::find_if(local_results, [](auto x) { return x != 0; }); 
}

Hmm here find_if returning an optional makes some sense. But I still think that find should return a position and maybe we want find_value algorithm as well.

But the point was that due to how algorithm is structured, I new that both ends were isolated. If I didn't use aligned_ptrs I'd need to convey that information in some way.

[jfalcou]

Difference from STL/ranges.

Differences are:

• We do not support non-contiguous iterators.
• We do not step by 1
• The while (f != l) ++f; while trivial for STL is not for us and needs to be reused between algorithms.
• One operator* for both load and store do not work for us - we need different operations.

Yes to all of that

Dealing with cardinality

Therefore at the moment we think that cardinality should be attached to the iterator.

Yes

Fundamental iterator interface

This is not a complete iterator interface but it's the very minimum.
We propose that the operations for iterators should be in eve namespace and be extensible via tagged_dispatch.

You mean using the same system we internally use in EVE or another kind of tag dispatch ?

operator+=(std::ptrdiff_t n) [n must be divisible by cardinality]
We need to be able to advance. For unrolling we need to be able to advance by multiple cardinalities at one step. We also don't
have a single example of an iterator where this can't be an arbitrary number divisible by cardinality, so we don't see any reason
to relax this requirement.

This is similar to what aligned_ptr does? I guess we should aim at having aligned_ptr just be a simd_iterator and fix accordingly

Requirements to do find

Which leads us to believe that we need to concepts of iterators: aligned and unaligned.
There should be a way to cast from aligned to unaligned.
Something like zip_iterator would be aligned if at least one of its components is aligned.

I agree

There is no way to provide a general purpose cast from unaligned to aligned since there is zip where some components might be aligned while the other are not. On the other hand I'd expect to be able to do strlen like algorithms on aligned, maybe this should be partially_aligned or smth.

I don't get it.

To tell the library that the iterator is aligned we can use a traits mechanism:
Iterator might define an internal typedef unaligned_iterator.
We can access it via: eve::unaligned<I>.
unaligned can be explicitly convertible from aligned. This would require to put and explicit operator T* in aligned_ptr.

Again, I'm a bit lost

Requirement to go to an aligned iteration.

For pointer we can compute a previous_aligned_address and iterate faster from that point. The suggestion is to allow a hook into a previous_aligned_address. previous_aligned_address should return an aligned iterator where unaligned is the original iterator.

OK

Requirements to do zip

The main requirement to do zip is to ensure consistent cardinality between components.
For example zip(const int*, const char*) would have to operate on cardinality of int.

Do we? Or can we choose which one of the type give us the correct cardinal? Or can't we infer it by takign the smallest cardinal for all the type ?

One way to do it would be to have a eve::cardinality_cast<N>(I) which again has to be a customisation point.
This implies existence of unaligned_pointer<T, eve::fixed<N>> or something that attaches a cardinality to a pointer.

eve::unaligned_ptr is indeed an oversight, we need that.

This implies that we need to

• identify that biggest type, which is not trivial when zip_iterator is one of the components.
• replace an iterator with a converting iterator. At the simplest level this can use eve::convert for individual parts but we maybe want to hook into individual parts as well.
• convert back from converting iterators to the input ones, expected by the user.

This is a larger question I guess :/

[DenisYaroshevskiy]

You mean using the same system we internally use in EVE or another kind of tag dispatch ?

I'm sorry, I assumed we talked about the same type of tagged dispatch.

The one I was talking about is this good extension mechanism based on ADL.
Here is an example: https://godbolt.org/z/z7oW1eT8q
There was a talk by Gasper, I'd need to find it.

I don't get it.
Again, I'm a bit lost

Sorry about that.

Let's say we have a zip_iterator<aligned_ptr<const int>, const int*>
For it the unaligned version is zip_iterator<const int*, const int*>.
However zip_iterator<aligned_ptr<const int>, aligned_ptr<const int> has the same unaligned version.
There is no way to provide "cast this to aligned" functionality.

Also the question is zip_iterator<aligned_ptr<const int>, const int*> aligned depends on the context.
If I am choosing which iteration algorithm to use - I should choose the one for aligned iterators.
However if we asking the question: can I use this for an unguarded search, the answer should be no (where I can use a completely aligned iterator).
So - there needs to be some sort of different concepts.

Do we? Or can we choose which one of the type give us the correct cardinal? Or can't we infer it by takign the smallest cardinal for all the type ?

I am not sure yet tbh. So I am fairly certain there should be one cardinality per all iterators in the zip.
However, the question is do we always need to cast to the biggest type for the user? What about mixing int32 and float?
Also I am not sure if there are use-cases for converting to a smaller type on load.

[DenisYaroshevskiy]

Added first list of tasks to do: https://github.com/jfalcou/eve/wiki/Ranges:-Stories-sketch
Comment and we can start doing things for the approved ones.

[DenisYaroshevskiy]

Sketch of the first algorithm: https://github.com/jfalcou/eve/pull/694/files

[DenisYaroshevskiy]

Generate looks a touch weird: https://github.com/jfalcou/eve/wiki/Ranges:-Generate-is-weird

Any thoughts?

[DenisYaroshevskiy]

tuple<wide...> - ooff.

https://github.com/jfalcou/eve/wiki/Ranges:-tuple&lt;wide,...&gt;-is-not-that-simple

What do you think

[DenisYaroshevskiy]

Thoughts on bundle and what we can do with it:

https://github.com/jfalcou/eve/wiki/Ranges:-bundles,-objects-and-zips

[jtlap]

for the math case I think the functions are not to be all extended as is to bundles.

Some are: I think those which are deeply element-wise in essence. I mean for which we do not see any inheritance which will not be element-wise.

I include add, sub, plus, minus (but not mul etc.) average and perhaps bit_wise operators but not a bunch more. Peculiarly not the relation ops except (perhaps) == and != but which will return an element-wise logical, element_wise for each element of the bundles ith-tuple

Other functions are to be thought through some simple filters and bundles being the underlying class to extensions as RN complex doubledouble quaternion auto_derivative etc. where they will get proper meaning and implementation

[DenisYaroshevskiy]

I agree with the first part and I did not understand the last part but I trust you on that.

Peculiarly not the relation ops except (perhaps) == and != but which will return an element-wise logical, element_wise for each element of the bundles ith-tuple

With this I don't agree. I'm not sure I am right, we can postpone until we see more.

My thinking is:
Individual tuple_like is an object. bundle<tuple_like> is a wide for that object.

Let's see example:

struct coordinate {
  int x, y;

  // do the enablement to be product like
};

bool has_zero_coordinates(std::vector<int> x, std::vector<int> y) {
   return eve::algo::find(eve::algo::zip(x, y), coordinate{0, 0});
}

Same way as it works for int.
But it means that operator== should return one eve::logical

[DenisYaroshevskiy]

This is not immediately necessary - let's maybe see some more use-cases?

[DenisYaroshevskiy]

Reduce interface:
https://github.com/jfalcou/eve/wiki/Ranges:-reduce-interface

[jfalcou]

Reduction to a bigger type

The problem is with the number of lanes. The correct way to add let's say short to int on avx2 is to load by 8 shorts and convert them to 8 ints. However, the way we use to specify the number of lanes to use in the algorithm, is with iterator::cardinal. But that cardinal is for shorts not ints. So it seems like we don't respect what user asked of us.

In my mind, 99% of people will pass T* to those algorithms. The one passing aligned_ptr or some such are power users.
Then again, why does the # of lanes of the input data has to do with the result ? We return a scalar anyway ?

[DenisYaroshevskiy]

How to name a shuffle?
https://github.com/jfalcou/eve/wiki/Ranges:-scan-shuffle-naming-problem

[jfalcou]

First shuffle

[0 a 0 c ]

is not slide_right.

The old boost.SIMD slide(a,b) was defined as

a = [a1 a2 ... aN]
b = [b1 b2 ... bN]

slide<+1>(a,b) = [ a2 a3 ... aN b1]
slide<-1>(a,b) = slide(b,a) = [ bN a1 a2 ... aN-1]

Those were designed like this because their main usage was stencil computation.

The issue is that alignr8 etc on AVX2 don't follow the same pattern than SSE. It "fucks up" the 128 bits boundary.
So I would prefer we find another name OR we just use itnrinsic.

Second Shuffle

[0 0 a + b a + b ] 

is it really a shuffle cause you do arithmetic in the middle ?