Consider support for stateful dispatch about thrust HOT 12 CLOSED

About the two issues arising from the tag-explicit form:

1. I wouldn't mind if explicit tag-iterator tag mismatches were a compile error. I'm not a fan of hidden, implicit, expensive coercions of the sort that would be induced if you made these mismatches "work".
2. If you provide explicit tag versions of all Thrust algorithms, then you could pass the explicit tag around to ensure that lowerings onto other Thrust algorithms use the explicit tag dispatch - in this case I don't think you'd need to retag the iterators.

Alternatively, you could define the explicit tag version in terms of retagging (note retag has to take a tag argument):

template<typename Tag, typename Iterator>
void thrust::algo(Tag tag, Iterator first, Iterator last) {
    return thrust::algo(thrust::retag<Tag>(tag, first), thrust::retag<Tag>(tag, last));
}

from thrust.

Another issue to resolve is how to pass the state.

Tags are currently passed by value. We could continue that approach:

template<typename State, typename Iterator>
  Iterator algo(State state, Iterator first, Iterator last);

But this would create lots of temporaries during dispatch, which we'd wish to avoid. std::reference_wrapper would be the workaround that the user would have to apply.

The alternative is to pass the state by reference, but this implies tripling the interface's surface area:

template<typename State, typename Iterator>
  Iterator algo(State &state, Iterator first, Iterator last);

template<typename State, typename Iterator>
  Iterator algo(const State &state, Iterator first, Iterator last);

Since this is truly a forwarding problem, one way to avoid the interface explosion would be through && references:

template<typename State, typename Iterator>
  Iterator algo(State &&state, Iterator first, Iterator last);

&&state should be able to bind to const, non-const, and rvalue references. state could be forwarded along with std::forward or an equivalent. The problem is that nvcc cannot deal with &&, and in any case, we'd have to provide a path for users with older compilers.

from thrust.

Another issue to resolve is whether or not introducing a new parameter will ambiguate function invocation.

thrust::reduce currently has three overloads. This proposal would introduce at least three more. The question is whether the invocation

thrust::reduce(my_state, first, last);

Can be disambiguated from

thrust::reduce(first, last, init);

In all cases and for all Thrust functions.

from thrust.

Stateful tags would be a good way to implement a dynamic or variant backend. The backend's tag would be a variant of tags of more primitive backends. Dispatch for the backend would implement something like Boost apply_visitor.

from thrust.

Introducing a new argument does cause ambiguities in general:

#include <iterator>
#include <iostream>

namespace ns
{

template<typename Iterator, typename T>
T reduce(Iterator, Iterator, T)
{
  std::cout << "reduce(Iterator,Iterator,T)" << std::endl;
  return 0;
}

template<typename State, typename Iterator>
  typename std::iterator_traits<Iterator>::value_type
    reduce(State&, Iterator, Iterator)
{
  std::cout << "reduce(State &,Iterator,Iterator)" << std::endl;
  return 0;
}

}

int main()
{
  int *ptr;

  ns::reduce(ptr,ptr,ptr+1);

  return 0;
}

Produces

$ g++ ambiguous.cpp 
ambiguous.cpp: In function ‘int main()’:
ambiguous.cpp:93:27: error: call of overloaded ‘reduce(int*&, int*&, int*)’ is ambiguous
ambiguous.cpp:93:27: note: candidates are:
ambiguous.cpp:18:5: note: T ns::reduce(Iterator, Iterator, T) [with Iterator = int*, T = int*]
ambiguous.cpp:56:5: note: typename std::iterator_traits<_ForwardIterator2>::value_type ns::reduce(State&, Iterator, Iterator) [with State = int*, Iterator = int*, typename std::iterator_traits<_ForwardIterator2>::value_type = int]

A stateful API's entry points would need to occupy a separate namespace or otherwise be disambiguated, e.g.:

namespace ns
{

template<typename State, typename Iterator, typename T>    
T reduce(detail::foo<State&> state, Iterator first, Iterator last, T init);

template<typename State>
detail::foo<State&> bar(State &x);

}

int main()
{
  int *ptr;

  ns::reduce(ns::bar(ptr), ptr, ptr);
  return 0;
}

from thrust.

Nathan: here's the case that concerns me:

algo(tag1, iterX, iterY, iterZ)

suppose algo makes a call to algo2, but with a subset of the iterators

which version of the second algo is invoked?

me: tag1

Nathan: I don't know if that's actually desirable though

the other rule would bet to select_system again inside algo2

from thrust.

In retrospect, it would probably be sufficient to pass the state as a non-const reference for the c++03 case. All interesting operations on the state would mutate it.

For c++11, we can pass as a && reference.

from thrust.

It might be possible to disambiguate all algorithms in all cases simply by demanding that the algorithm's first two arguments be of different type:

namespace thrust
{

template<typename State, typename Iterator>
  typename thrust::detail::disable_if_same<State,Iterator>::type
    algo(State &state, Iterator first, Iterator last);

}

We might be able to populate thrust:: with both the tag-explicit and tag-implicit forms unambiguously this way, which may be desirable. It might even not be necessary to decorate the tag-implicit forms with enable_if, which is desirable.

The limitation would be that users would not be able to use the same type of iterator as state unambiguously without manually instantiating the template.

from thrust.

Here's a new problem related to Nathan's issue above I don't know how to solve.

Suppose the user wants to specialize get_temporary_buffer, but not sort. When sort is dispatched, the type of his state will be erased:

#include <iostream>

namespace base
{
struct tag {};

void get_temporary_buffer(tag &system)
{
  std::cout << "base::get_temporary_buffer() called" << std::endl;
};

void sort(tag &system)
{
  get_temporary_buffer(system);
}

}

struct my_system : base::tag {};

void get_temporary_buffer(my_system &system)
{
  std::cout << "get_temporary_buffer(my_system) called" << std::endl;
}

int main()
{
  my_system system;

  sort(system);

  return 0;
}

We can't make sort and get_temporary_buffer function templates because it would lead to ambiguities during dispatch if there was a third tag in this example. It's unclear how to recover the type of the user's state without adding a template parameter to sort.

from thrust.

I remember now how to resolve this problem -- it's the same way that generic::get_temporary_buffer works.

The idea is to:

1. Make the function in question (sort in this example) a function template with the tag type a parameter
2. Remove the function in question from the overload set (using enable_if) if another version exists

This implies of course that we have to guard every dispatch target with an enable_if.

It's not clear that this will work with multiple backends, some of which inherit from each other.

from thrust.

Unfortunately, the above suggestion does not work in general; it only works for the special case of the generic backend.

It seems that the only way to reconcile user state with tag dispatch is to introduce a system::whatever::state template which encodes the type of the user state. The backends' tags would be typedefs of this type. The state template uses the CRTP to retrieve the type of the user's state. The below code example demonstrates:

#include <iostream>
#include <typeinfo>

namespace system1
{

template<typename Derived>
  struct state
{
  Derived &derived()
  {
    return static_cast<Derived&>(*this);
  }
};

template<> struct state<void>
{
  state<void> &derived()
  {
    return *this;
  }
};

typedef state<void> tag;

template<typename System>
  void get_temporary_buffer(state<System> &system)
{
  std::cout << "system1::get_temporary_buffer() called with type " << typeid(System).name() << std::endl;
}

template<typename System>
  void sort(state<System> &system)
{
  std::cout << "system1::sort() called with type " << typeid(tag).name() << std::endl;

  get_temporary_buffer(system.derived());
}

}

namespace system2
{

template<typename Derived>
  struct state : system1::state<Derived>
{};

typedef state<void> tag;

template<typename System>
  void get_temporary_buffer(state<System> &system)
{
  std::cout << "system2::get_temporary_buffer() called with " << typeid(System).name() << std::endl;
}

template<typename System>
void sort(state<System> &system)
{
  std::cout << "system2::sort() called with type " << typeid(System).name() << std::endl;
  get_temporary_buffer(system.derived());
}

}

struct my_system : system2::state<my_system> {};

void get_temporary_buffer(my_system &system)
{
  std::cout << "my_system::get_temporary_buffer() called with type " << typeid(my_system).name() << std::endl;
}


int main()
{
  system1::tag system1;
  system2::tag system2;
  my_system    system;

  std::cout << "should call system1::sort() with type " << typeid(system1::tag).name() << std::endl;
  sort(system1);

  std::cout << "should call system2::sort() with type " << typeid(system2::tag).name() << std::endl;
  sort(system2);

  std::cout << "should call my_system::sort() with type " << typeid(my_system).name() << std::endl;
  sort(system);

  return 0;
}

Unfortunately, it means that if a user wants to both (1) customize a backend and (2) forward state through the dispatch, he needs to inherit from state<Derived> rather than tag.

from thrust.

If we switched to this new method of dispatch, it would break user code from 1.6 whose user tags were deriving from thrust::cuda::tag et al.

To support that old mode, we'd need two overloads per dispatch target:

template<typename Iterator>
void algo1(cuda::tag, Iterator first, Iterator last)
{
  thrust::algo2(first,last);
}

template<typename System, typename Iterator>
void algo1(cuda::state<System> &state, Iterator first, Iterator last)
{
  thrust::algo2(state, first, last);
}

In the first overload, the tag user tag will be reified again by select_system inside of thrust::algo2. In the second overload, the user state is forwarded to thrust::algo. If we only supported the second overload, any existing algo2(my_tag, first, last) would be silently ignored by dispatch.

We could issue an error if c++11 final were available, which would make it illegal to derive any type from thrust::system::tag. There might be a way to support this behavior in c++03 with a hack.

from thrust.