Ranges: Iterator concept

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.

Examples

Here are some of the things we would like to be iterators or at least be usable in the interface level in place of iterators (there is a possibility of some conversion layer).

• pointer
• aligned_ptr
• converting_iterator (that loads from an iterator of one type and converts it to another using load(as) that we don't have yet.
• zip_iterator<iterator, ...> - loads and stores to multiple parallel iterators
• std::vector::const_iterator
• reverse_iterator (on load/store reverses the wide).

Dealing with cardinality

SIMD ranges iteration needs to know how many elements are in one block (cardinality).

There are two options:

• pass cardinality independently.
• attach the notion of cardinality to the iterator.

The problem with the second approach is that it doesn't work terribly well for aligned_ptr. You cannot add an arbitrary number < alignment to aligned_ptr and neither you can load a wide of bigger cardinality from it.

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

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.

• eve::load[ignore](it) (for input) or eve::store[ignore](it) (for output)

For ptr or aligned ptr these operate on wide. However for zip_iterator they should operate on tuple of components. There should be some type traits way to get the type that iterators operate on, like eve::wide_value_type or smth.

• 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.

• std::ptrdiff_t operator-(sentinel<I>, I)

For unrolling we need to be able to compute the distance between beginning and end.

• bool operator==(I, sentinel<I>), bool operator==(I, I)

We need to be able to compare against the end and against some specific positions.

These requirements enough for implementing a simplified any or transform in-place.

Requirements to do find

For find we have an extra requirement - we need to be able to represent an arbitrary position in our input range. However, the aligned_ptr does not allow us to do that.

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.

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.

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.

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.

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.

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.

However, just cardinality is not enough. For very many algorithms we need to do conversions to the biggest type. 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.

At the moment not going to suggest how this should look like.