kokkos
Basic parallel version of std::iota
Feature request: would be nice for Kokkos_StdAlgorithms.hpp to support a basic version of std::iota, which fills an iterator range with k, k+1, k+1, ... k+n-1. Even though the real std::iota is defined in terms of operator++() and is not generally parallelizable, it would be fine for this version to only support integers (so doing x++ n times is equivalent to x += n).
We use this in KokkosKernels to initialize worklists in graph algorithms - initially all vertices 0...n-1 need to be processed, so the worklist should contain this whole sequence. This is the implementation we use now:
template <typename V>
struct SequentialFillFunctor {
using size_type = typename V::size_type;
using val_type = typename V::non_const_value_type;
SequentialFillFunctor(const V &v_, val_type start_) : v(v_), start(start_) {}
KOKKOS_INLINE_FUNCTION void operator()(size_type i) const {
v(i) = start + (val_type)i;
}
V v;
val_type start;
};
template <typename V>
void iota(const V &v, typename V::non_const_value_type start = 0) {
Kokkos::parallel_for(
Kokkos::RangePolicy<typename V::execution_space>(0, v.extent(0)),
SequentialFillFunctor<V>(v, start));
}
Would you instead consider providing a counting iterator or something like std::ranges::iota_view? That would make the iota algorithm superfluous; users could just for_each or transform with an iota_view and an output range.
@brian-kelley one reason we have not yet added iota (see #4084) is exactly your point of not being easily parallelizable.
We do have transform implemented so @mhoemmen 's idea can be done I think. But not sure how much it would save you from what you already have (beside saving you some code).
However, std::iota does not have an overload accepting a policy, so maybe we could do something similar.
I guess we have to discuss this further :)
Adding another overload of deep_copy would be painful, and maybe hides the desired meaning
I would support adopting some refinement of the SequentialFillFunctor shown in the initial post as a tiny utility inside Kokkos.
There is actually a std::ranges::iota proposal, P2440, currently under electronic polling.
One idea would be a
deep_copyfrom range i.e.deep_copy(v,pair{begin,end})
Why not spell it transform?
The reason not to spell it transform is because we already have transform and what they want is something which doesn't take a callable, but just does the defined behavior of filling something with a range of numbers.
Should we provide something like Kokkos::Experimental::fill_with_range or Kokkos::Experimental::fill_with_consecutive_range or something else?
I can take this on and add it to the algorithms. Or whatever variant we decide. I can work on proposing a few ideas on this (e.g. name, API, etc) if we want to support it.
Four options:
-
Address this (F, N, A) // Dont address it //SF F N A SA //0 3 7 4 1 F N A 9 5 2
-
Kokkos::iotawith strong constraint on type (i.e. only view of integer, floating point) SF F N A SA 1 10 7 2 1 A: don't name it iota since it doesn't do what iota does -
Kokkos::deep_copy(v, pair{begin,end}SF F N A SA 0 0 2 ... No one wants this -
Kokkos::fill_with_range(v, pair{begin,end})or maybefill_with_consecutive_values(v, init)SF F N A SA 3 8 5 1 0
Iota vs some other name (Iota SF, Other Name SA) SF F N A SA 1 2 5 7 3 SF: was because people know iota and want to do that even if constraint (in which case its identical)
Thanks for discussing and voting on this. If you were to do option 2 but want to name it something different, what about "linspace"? That's what it's called in matlab and numpy, so it would probably be familiar to as many people as "iota". But it frees you from explaining that it's not a full standard-compliant std::iota.
That last vote indicated a pretty solid preference for not naming it iota as you said Brian.
My suggestion below is purely a result of providing something that serves the usecase, and avoids calling it iota. I personally think that a more expressive name is better.
Kokkos::Exp::fill_consecutively_from_value(exespace, view, init_value); (1)
Kokkos::Exp::fill_consecutively_from_value(label, exespace, view, init_value);
Kokkos::Exp::fill_consecutively_from_value(exespace, view, init_value, step); (2)
Kokkos::Exp::fill_consecutively_from_value(label, exespace, view, init_value, step);
Kokkos::Exp::fill_consecutively_from_value(exespace, view, pair{begin, end}); (3)
// we can also add overloads accepting iterators
Kokkos::Exp::fill_consecutively_from_value(exespace, begin, end, init_value);
Kokkos::Exp::fill_consecutively_from_value(label, exespace, begin, end, init_value);
// ...
-
(1) is self-explanatory
-
(2) is useful to pass a non-unitary step
-
(3) I think it is somewhat redundant because the values between begin and end should fit in the view. But we could use this as a way to check.
-
I chose the word
consecutivelybecause 1,2,3,4,5 are consecutive, but also 1,5,9,13 are consecutive. -
we can restrict to integral first, but I would also vote to support any type that supports (+ increment)
struct MyType{
int m_something;
MyType operator+(const int increment){
MyType res{m_something + increment};
return res;
}
};
View<MyType*> a (...);
MyType init{22};
Kokkos::Exp::fill_consecutively_from_value(view, init_value);
note that
- overload (1) does what iota does but we don't call it so
- I think the name expresses what the function is doing
Other naming ideas
Kokkos::Exp::fill_with_increments_from(exespace, view, init_value);
Kokkos::Exp::fill_incrementally(exespace, view, init_value);
Kokkos::Exp::fill_incrementally_from(exespace, view, init_value);
Kokkos::Exp::incrementally_fill_starting_from(exespace, view, init_value);
I personally like "increment" because it conveys the idea of changing by adding to something.
@fnrizzi I like fill_incrementally, it's short but describes what this does. I think "from_value" or "starting_from" is redundant or more confusing if init_value defaults to 0, which i assume it would.
fill_incrementally_from_value(Exec, v); // what value?
fill_incrementally(Exec, v); // more clear
