c++ - void * 到运行时 std::tuple 的第 n 个元素

Question

假设我有一个 std::tuple<T...>我想有效地访问它的第 n 个元素，其中 n 仅在运行时已知。由于类型 T...是异构的，我只能得到一个 void *我对此没有意见。这是我的结论:

template <size_t ... Indexes, class Tuple>
void * get_element_pointer(std::index_sequence<Indexes...>, Tuple & t, size_t idx) {
    static size_t offsets[] = {(size_t)(void *)&std::get<Indexes>(t) - (size_t)(void *)(&t)...};
    return (void *)((size_t)(void *)(&t) + offsets[idx]);
}

然后你可以这样调用它:

get_element_pointer(std::index_sequence_for<T...>{}, some_tuple, some_index);

要点是静态创建一个 size_t数组 offsets其中包含每个元组元素的偏移量列表。然后，在运行时，我可以查找偏移量并将其添加到传递的元组中。

我的解决方案有两个问题困扰着我:

1. offsets是在第一次调用此函数时创建的，它是基于当时传递的元组实例创建的。我觉得这有点奇怪。我可以创建一个类型为 Tuple 的虚假临时文件，但它可能不是默认可构造的。或者，我可以投 nullptr到 Tuple * ，然后是 std::get<Indexes>(*(Tuple *)(nullptr)) UB 尖叫道。
2. (size_t)(void *)(&t)和 (void *)((size_t)(void *)(&t) + offsets[idx])指针杂耍是我能找到的阻止编译器给我警告的唯一方法。我知道当你有虚函数等时，指针转换可能会很棘手而且很重要。所以我担心我可能会遗漏一些东西。

您认为我的解决方案可以接受吗？您能想出一个更简单的指针操作更少的解决方案吗？

Answer 1

在查看了解决方案后，我将您对性能的担忧牢记在心，并决定看看我们是否可以做得更好。

有趣的是，我尝试使用 constexpr 进行优化的结果因编译器而异。

我将在这里比较 gcc 5.3 和 apple clang 的输出:

这是我的解决方案:

#include <utility>
#include <tuple>
#include <iostream>


template<class Tuple, size_t Index> 
  void* get_address(Tuple& t)
{
  return std::addressof(std::get<Index>(t));
}

template <size_t ... Indexes, class Tuple>
constexpr void* get_element_pointer(Tuple & t, 
                          size_t idx, 
                          std::index_sequence<Indexes...>) 
{
  using function_type = void* (*)(Tuple&); 
  function_type constexpr ptrs[] = 
  {
    &get_address<Tuple, Indexes>...
  };
    return ptrs[idx](t);
}


template<class Tuple>
__attribute__((noinline))
constexpr 
  void * get_element_pointer(Tuple& t, size_t index)
{
  return get_element_pointer(t, 
                             index, 
                             std::make_index_sequence<std::tuple_size<Tuple>::value>());
}

int main()
{
  std::tuple<int, int, int, int, int, int, int , int, int, int> x;
  x = std::make_tuple(4, 5, 6, 7, 8, 9, 10, 11, 12, 13);
  std::cout << *reinterpret_cast<int*>(get_element_pointer(x, 1)) << std::endl;
}

(为清晰起见，使用 -O2 -fomit-frame-pointer 编译)

clang 的解决方案是这样的:

__Z19get_element_pointerINSt3__15tupleIJiiiiiiiiiiEEEEPvRT_m:
    .align  4, 0x90
    leaq    __ZZ19get_element_pointerIJLm0ELm1ELm2ELm3ELm4ELm5ELm6ELm7ELm8ELm9EENSt3__15tupleIJiiiiiiiiiiEEEEPvRT0_mNS0_16integer_sequenceImJXspT_EEEEE4ptrs(%rip), %rax
    jmpq    *(%rax,%rsi,8)          ## TAILCALL

正如预期的那样，它指的是编译时生成的跳转表:

__ZZ19get_element_pointerIJLm0ELm1ELm2ELm3ELm4ELm5ELm6ELm7ELm8ELm9EENSt3__15tupleIJiiiiiiiiiiEEEEPvRT0_mNS0_16integer_sequenceImJXspT_EEEEE4ptrs:
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm0EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm1EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm2EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm3EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm4EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm5EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm6EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm7EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm8EEPvRT_
    .quad   __Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm9EEPvRT_

其中每个访问器函数都很简单(提供了一个示例):

__Z11get_addressINSt3__15tupleIJiiiiiiiiiiEEELm2EEPvRT_:
    leaq    8(%rdi), %rax
    retq

这是我假设编译器会做的，是“如果我正在编写机器代码我会做的”

然而 gcc 似乎错过了一个优化跳转表并在使用前在内存中构建它的机会!

void* get_element_pointer<std::tuple<int, int, int, int, int, int, int, int, int, int> >(std::tuple<int, int, int, int, int, int, int, int, int, int>&, unsigned long):
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 0ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -88(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 1ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -80(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 2ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -72(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 3ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -64(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 4ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -56(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 5ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -48(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 6ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -40(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 7ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -32(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 8ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -24(%rsp)
        movq    void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 9ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&), -16(%rsp)
        movq    -88(%rsp,%rsi,8), %rax
        jmp     *%rax

在调用类似的普通访问器之前:

void* get_address<std::tuple<int, int, int, int, int, int, int, int, int, int>, 3ul>(std::tuple<int, int, int, int, int, int, int, int, int, int>&):
        leaq    24(%rdi), %rax
        ret

所以我并没有被吓倒，我想知道在非 constexpr 实现中常量折叠是否会做得更好:

template <size_t ... Indexes, class Tuple>
void* get_element_pointer(Tuple & t, 
                          size_t idx, 
                          std::index_sequence<Indexes...>) 
{
  using function_type = void* (*)(Tuple&); 
  function_type static const ptrs[] = 
  {
    &get_address<Tuple, Indexes>...
  };
    return ptrs[idx](t);
}

事实证明确实如此 - 我现在在 gcc 上获得了与使用 constexpr 解决方案生成的 clang 相同的代码:

void* get_element_pointer<std::tuple<int, int, int, int, int, int, int, int, int, int> >(std::tuple<int, int, int, int, int, int, int, int, int, int>&, unsigned long):
        movq    void* get_element_pointer<0ul, 1ul, 2ul, 3ul, 4ul, 5ul, 6ul, 7ul, 8ul, 9ul, std::tuple<int, int, int, int, int, int, int, int, int, int> >(std::tuple<int, int, int, int, int, int, int, int, int, int>&, unsigned long, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul, 6ul, 7ul, 8ul, 9ul>)::ptrs(,%rsi,8), %rax
        jmp     *%rax

clang 对此做了什么？

__Z19get_element_pointerINSt3__15tupleIJiiiiiiiiiiEEEEPvRT_m:
    movq    __ZZ19get_element_pointerIJLm0ELm1ELm2ELm3ELm4ELm5ELm6ELm7ELm8ELm9EENSt3__15tupleIJiiiiiiiiiiEEEEPvRT0_mNS0_16integer_sequenceImJXspT_EEEEE4ptrs@GOTPCREL(%rip), %rax
    jmpq    *(%rax,%rsi,8)          ## TAILCALL

令人高兴的是相同的结果。

所以这是最终的、可证明的最佳解决方案:

template<class Tuple, size_t Index>
void* get_address(Tuple& t)
{
    return std::addressof(std::get<Index>(t));
}

template <size_t ... Indexes, class Tuple>
void* get_element_pointer(Tuple & t,
                                    size_t idx,
                                    std::index_sequence<Indexes...>)
{
    using function_type = void* (*)(Tuple&);
    function_type static const ptrs[] =
    {
        &get_address<Tuple, Indexes>...
    };
    return ptrs[idx](t);
}


template<class Tuple>
__attribute__((noinline))
constexpr
void * get_element_pointer(Tuple& t, size_t index)
{
    return get_element_pointer(t,
                               index,
                               std::make_index_sequence<std::tuple_size<Tuple>::value>());
}