Make C++14 constexpr function C++11 compatible

Asked 19/5, 2018 at 8:41 Answered 19/5, 2018 at 11:50

Solved c++c++11 templates variadic-templates template-meta-programming

I have written a class multi_array which is sort of an extension of std::array to multiple dimensions.

template <typename T, std::size_t... N>
class multi_array {
    template <std::size_t... I, typename... Idx>
    constexpr std::size_t linearized_index(meta::index_sequence<I...>,
                                           Idx... idx) const {
        std::size_t index = 0;
        using unpack = std::size_t[];
        (void)unpack{0UL,
                     ((void)(index = (index + unpack{std::size_t(idx)...}[I]) *
                                     meta::pack_element<I + 1, N...>::value),
                      0UL)...};
        return index + unpack{std::size_t(idx)...}[sizeof...(idx) - 1];
    }

    // Storage
    T m_data[meta::product<N...>::value];

    //...
};

I have managed to get constexpr element access but only in C++14. The problem is the function linearized_index. It computes the linearized index at compile-time. In order to do so it reduces the tuple of indices and the tuple of dimension in a certain manner. For this reduction I need a local variable inside the function but this is not allowed in C++11. My environment does not permit the usage of C++14. Can I somehow rewrite this function to work with C++11?

I have prepared a full (not so minimal) example which compiles in C++14.

#include <cstddef> // std::size_t

namespace meta {

// product

template <std::size_t...>
struct product;

template <std::size_t head, std::size_t... dim>
struct product<head, dim...> {
    static constexpr std::size_t const value = head * product<dim...>::value;
};

template <>
struct product<> {
    static constexpr std::size_t const value = 1;
};

// pack_element

template <std::size_t index, std::size_t head, std::size_t... pack>
struct pack_element {
    static_assert(index < sizeof...(pack) + 1, "index out of bounds");
    static constexpr std::size_t const value =
        pack_element<index - 1, pack...>::value;
};

template <std::size_t head, std::size_t... pack>
struct pack_element<0, head, pack...> {
    static constexpr std::size_t const value = head;
};

// index_sequence

// https://stackoverflow.com/a/24481400
template <std::size_t... I>
struct index_sequence {};

template <std::size_t N, std::size_t... I>
struct make_index_sequence : public make_index_sequence<N - 1, N - 1, I...> {};

template <std::size_t... I>
struct make_index_sequence<0, I...> : public index_sequence<I...> {};

} // namespace meta

template <typename T, std::size_t... N>
class multi_array {
    template <std::size_t... I, typename... Idx>
    constexpr std::size_t linearized_index(meta::index_sequence<I...>,
                                           Idx... idx) const {
        std::size_t index = 0;
        using unpack = std::size_t[];
        (void)unpack{0UL,
                     ((void)(index = (index + unpack{std::size_t(idx)...}[I]) *
                                     meta::pack_element<I + 1, N...>::value),
                      0UL)...};
        return index + unpack{std::size_t(idx)...}[sizeof...(idx) - 1];
    }

    // Storage
    T m_data[meta::product<N...>::value];

public:
    constexpr multi_array() {}

    template <typename... U>
    constexpr multi_array(U... data) : m_data{T(data)...} {}

    template <typename... Idx>
    constexpr T operator()(Idx... idx) const noexcept {
        std::size_t index = linearized_index(
            meta::make_index_sequence<sizeof...(idx) - 1>{}, idx...);
        return m_data[index];
    }
};

int main() {
    constexpr multi_array<double, 2, 2> const b = {0, 0, 0, 1};
    static_assert(b(1, 1) == 1, "!");
}

Live on Wandbox (C++14) and Live on Wandbox (C++11)

Assure answered 19/5, 2018 at 8:41 Comment(0)

The crucial part of your use of index is an iterative loop:

index = (index*a) + b

In your own C++14 solution, a trick of unpacking parameter pack is used. In C++11, you can formulate it in a recursive constexpr function:

struct mypair {
    size_t a;
    size_t b;
};

constexpr std::size_t foo(std::size_t init) {
    return init;
}

template<class... Pair>
constexpr std::size_t foo(std::size_t init, mypair p0, Pair... ps) {
    return foo((init+p0.a)*p0.b, ps...);
}

We use mypair instead of std::pair because the constructor of std::pair in C++11 is not constexpr. Then your iterative loop can be literally translated to:

    template <std::size_t... I, typename... Idx>
    constexpr std::size_t linearized_index(meta::index_sequence<I...>,
                                           Idx... idx) const {
        using unpack = std::size_t[];
        return foo(0, mypair{unpack{std::size_t(idx)...}[I], meta::pack_element<I+1, N...>::value}...) + unpack{std::size_t(idx)...}[sizeof...(idx) - 1];
    }

Live Demo

Pasquinade answered 19/5, 2018 at 9:46 Comment(0)

If in operator(), instead of calling

 std::size_t index = linearized_index(
    meta::make_index_sequence<sizeof...(idx) - 1>{}, idx...);

you call

 std::size_t index = linearized_index<N...>(idx...);

or better (to make operator() constexpr)

 return m_data[linearized_index<N...>(idx...)];

you can rewrite linearized_index() recursively as follows

  // ground case
  template <std::size_t>
  constexpr std::size_t linearized_index (std::size_t idx0) const
   { return idx0; }

  // recursive case
  template <std::size_t, std::size_t... Is, typename... Idx>
  constexpr std::size_t linearized_index (std::size_t idx0,
                                          Idx ... idxs) const
   { return idx0 * meta::product<Is...>::value
        + linearized_index<Is...>(idxs...); }

If you prefer, the ground case can be written as follows

  template <typename = void>
  constexpr std::size_t linearized_index () const
   { return 0; }

Observe that you don't need meta::index_sequence, meta::make_index_sequence or meta::pack_element anymore.

The following is a full C++11 compiling example

#include <cstddef> // std::size_t

namespace meta
 {
   template <std::size_t...>
    struct product;

   template <std::size_t head, std::size_t... dim>
   struct product<head, dim...>
    { static constexpr std::size_t const value
         = head * product<dim...>::value; };

   template <>
   struct product<>
    { static constexpr std::size_t const value = 1; };

} // namespace meta

template <typename T, std::size_t... N>
class multi_array
 {
   private:
      // ground case
      template <std::size_t>
      constexpr std::size_t linearized_index (std::size_t idx0) const
       { return idx0; }

      // alternative ground case
      //template <typename = void>
      //constexpr std::size_t linearized_index () const
      // { return 0; }

      // recursive case
      template <std::size_t, std::size_t... Is, typename... Idx>
      constexpr std::size_t linearized_index (std::size_t idx0,
                                              Idx ... idxs) const
       { return idx0 * meta::product<Is...>::value
            + linearized_index<Is...>(idxs...); }

      // Storage
      T m_data[meta::product<N...>::value];

   public:
      constexpr multi_array()
       { }

      template <typename ... U>
      constexpr multi_array(U ... data) : m_data{T(data)...}
       { }

      template <typename... Idx>
      constexpr T operator() (Idx... idx) const noexcept
       { return m_data[linearized_index<N...>(idx...)]; }
 };

int main()
 {
   constexpr multi_array<double, 2, 2> const b = {0, 0, 0, 1};

   static_assert( b(1, 1) == 1, "!" );

   constexpr multi_array<double, 4, 3, 2> const c
    { 0, 0,   0, 0,   0, 0,
      0, 0,   0, 0,   0, 0,
      0, 0,   2, 0,   0, 0,
      0, 0,   0, 0,   0, 1};

   static_assert( c(3, 2, 1) == 1, "!" );
   static_assert( c(2, 1, 0) == 2, "!" );
 }

Bonus suggestion: if you add the following constexpr functions (static methods inside multi_array?)

  constexpr static std::size_t prod ()
   { return 1U; }

  template <typename ... Args>
  constexpr static std::size_t prod (std::size_t v, Args ... vs)
   { return v * prod(vs...); }

you can delete the struct product calling

  // Storage
  T m_data[prod(N...)];

and

  // recursive case
  template <std::size_t, std::size_t... Is, typename... Idx>
  constexpr std::size_t linearized_index (std::size_t idx0,
                                          Idx ... idxs) const
   { return idx0 * prod(Is...) + linearized_index<Is...>(idxs...); }

Gaiser answered 19/5, 2018 at 11:50 Comment(3)

This is a very nice answer as well and I'll reward it with a small bounty soon. – Assure 19/5, 2018 at 23:3

BTW, I cannot make operator() constexpr in C++11 because there constexpr implies const (which is very annoying). – Assure 20/5, 2018 at 0:1

@HenriMenke - Maybe two versions, in the operator[]/at() tradition?

template <typename... Idx> constexpr T const & operator() (Idx... idx) const { return m_data[linearized_index<N...>(idx...)]; } template <typename... Idx> T & operator() (Idx... idx) { return m_data[linearized_index<N...>(idx...)]; }

? – Gaiser 20/5, 2018 at 1:48

Straightforward approach avoiding arrays:

#include <tuple>
#include <type_traits>
#include <cstddef>

template
<
    typename          x_IndexTypesTuple
,   ::std::size_t ... x_dimension
> class
t_MultiIndexImpl;

template
<
    typename          x_LeadingIndex
,   typename ...      x_Index
,   ::std::size_t     x_leadding_dimension
,   ::std::size_t ... x_dimension
> class
t_MultiIndexImpl
<
    ::std::tuple<x_LeadingIndex, x_Index ...>, x_leadding_dimension, x_dimension ...
> final
{
    static_assert
    (
        ::std::is_same<::std::size_t, x_LeadingIndex>::value
    ,   "index type must be ::std::size_t"
    );

    public: static constexpr auto
    Op
    (
        ::std::size_t const  stride_size
    ,   x_LeadingIndex const leading_index
    ,   x_Index const ...    index
    ) -> ::std::size_t
    {
        return stride_size * leading_index
            + t_MultiIndexImpl<::std::tuple<x_Index ...>, x_dimension ...>::Op
            (
                stride_size * x_leadding_dimension, index ...
            );
    }
};

template<> class
t_MultiIndexImpl<::std::tuple<>> final
{
    public: static constexpr auto
    Op(::std::size_t const /*stride_size*/) -> ::std::size_t
    {
        return ::std::size_t{0};
    }
};

template<::std::size_t ... x_dimension, typename ... x_Index> inline constexpr auto
Caclculate_MultiIndex(x_Index const ... index) -> ::std::size_t
{
    static_assert
    (
        sizeof...(x_dimension) == sizeof...(x_Index)
    ,   "arguments count must match dimensions count"
    );
    return t_MultiIndexImpl<::std::tuple<x_Index ...>, x_dimension ...>::Op(::std::size_t{1}, index ...);
}

online compiler | godbolt

Claqueur answered 19/5, 2018 at 10:21 Comment(4)

Eventually I want to use multi_array within CUDA code, so not std::tuple :( But of course +1 for your nice solution! – Assure 19/5, 2018 at 10:49

@HenriMenke Well, tuple here is used only to pack index types so technically it can be replaced with any random class template with parameter pack or removed completely. – Claqueur 19/5, 2018 at 10:53

Do you always prefix std with ::? Had you ever have any problem with simply std::something? – Rachelrachele 23/5, 2018 at 12:35

@Rachelrachele I prefix all the names from global namespace with ::. And yes, I do get problems with code not following the same convention on regular basis. I had some issues with std:: not being ::std:: as well: case 1 - library defines a nested std namespace with stuff implementing future standard (for backporting), case 2 - enum std{ vector, list ... (used for serialization of standard containers). So I don't see any reason to make an exception for std namespace and to not prefix it with ::. – Claqueur 23/5, 2018 at 12:55

I have managed to get a C++11 compatible solution by rewriting the function to evaluate recursively. This not only works but is also a lot nicer to read:

template <typename... Idx>
constexpr std::size_t linearized_index(std::size_t n, Idx... idx) const {
    using unpack = std::size_t[];
    return unpack{std::size_t(idx)...}[n] +
           (n == 0 ? 0
                   : unpack{std::size_t(N)...}[n] *
                         linearized_index(n - 1, idx...));
}

I have found another solution using template specializations which avoids the recursive function call and replaces it with recursive instantiation.

namespace meta {

template <size_t n, size_t... N>
struct linearized_index {
    template <typename... Idx>
    constexpr std::size_t operator()(Idx... idx) const {
        using unpack = std::size_t[];
        return unpack{std::size_t(idx)...}[n] +
               unpack{std::size_t(N)...}[n] *
                   linearized_index<n - 1, N...>{}(idx...);
    }
};

template <size_t... N>
struct linearized_index<0, N...> {
    template <typename... Idx>
    constexpr std::size_t operator()(Idx... idx) const {
        using unpack = std::size_t[];
        return unpack{std::size_t(idx)...}[0];
    }
};

} // namespace meta

and the multi_array call operator

template <typename... Idx>
constexpr T operator()(Idx... idx) const noexcept {
    return m_data[meta::linearized_index<sizeof...(idx) - 1, N...>{}(
        idx...)];
}

This produces perfect assembly: https://godbolt.org/g/8LPkBZ

Assure answered 19/5, 2018 at 9:45 Comment(2)

Unfortunately, this kills your optimizer. Original version. – Chrismatory 19/5, 2018 at 9:49

Oops I missed an expression. This does produce optimal assembly – Chrismatory 19/5, 2018 at 10:1

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Recommended topics

Hot tags