[trick] for_each_field
От: Evgeny.Panasyuk Россия  
Дата: 16.01.17 08:45
Оценка: 130 (8)
EDIT: в комментариях указали на то, что похожую технику уже презентовал на CppCon 2016 Антон Полухин. Плюс есть дополнения от Bruno Dutra.
https://github.com/apolukhin/magic_get
http://apolukhin.github.io/magic_get/index.html
https://www.youtube.com/watch?v=abdeAew3gmQ
слайды


for_each_field Proof-of-Concept

Пример обхода полей

В этом примере обходятся поля свежеопределенной структуры Gadget. Эти поля нигде кроме как в определении структуры не перечисляются.
#include "for_each_field.hpp"

#include <iostream>

using namespace std;
using namespace proof_of_concept;

struct Gadget
{
    field<int> x;
    field<char> y;
    field<double> z;
};

int main()
{
    Gadget gadget{42, 'J', 3.1415926};

    for_each_field(gadget, [](auto x)
    {
        cout << x << endl;
    });
}

Вывод

42
J
3.14159

Live Demo


Детали реализации

Нам требуется каким-то образом опросить все поля, причём не называя их по имени. Трюк заключается в вытаскивании данных о полях через список инициализации агрегата.
Например объект типа struct Pair {int x; double y;}; можно сконструировать следующим образом: Pair{42, 3.1415926} — не объявляя при этом специального конструктора. Как видно здесь имеется как минимум односторонняя тропинка — мы передаём число 42, которое отправляется во внутрь структуры инициализировать поле Pair::x, при этом не называя его по имени.
Для организации обратной связи от поля будем использовать обёртку field:
template<typename T>
struct field
{
    template<typename U>
    field(field_visitor<U> &&s);

    field(T x);

    T value;
};

Идея заключается в том, что агрегат вида struct Pair {field<int> x; field<double> y;}; можно инициализировать двумя способами:

Всё что нам нужно от конкретного поля — узнать его this. Эту информацию поле сообщит нашему подсадному посетителю, который вломится через чёрный вход:
template<typename T> template<typename U>
field<T>::field(field_visitor<U> &&f)
{
    f(this);
}

Очевидно что таким образом — из конструктора — напрямую прочитать информацию из ранее проинициализированного поля не получится, так как оно уже сконструировано до нас. Поэтому нам придётся идти другим путём.
Помимо this конкретного экземпляра поля, мы также можем получить адрес по которому находится объект самой структуры Pair. Зная эти два значения можно вычислить смещение поля относительно начала структуры Pair, то есть получается эдакий offsetof. После чего это смещение можно применить к другому(интересующему нас) объекту типа Pair.
Это всё конечно на грани фола UB, и нужно внимательно свериться со стандартом, выбрать правильные ограничения (standard layout type?). Но даже в случае если в каком-то из вариантов окажется UB — то на конкретных компиляторах это вполне может работать, необходимо лишь скрупулёзно протестировать.

Теперь, для того чтобы обойти все поля, нам нужно узнать их количество — это осуществляется через SFINAE.
SFINAE проверка опирается на decltype и выглядит следующим образом:
...
    template<typename U>
    static auto check(int) ->
        decltype(U{Xs{}...}, yes_type{});
...

Тут особенность в том, что список инициализирующий агрегат может содержать меньше значений чем всего в структуре полей, и оставшиеся поля в таком случае будут value-initialized. Поэтому нам нужно найти не просто такое количество значений при котором подстановка не фейлится, а границу количества при котором происходит фейл. Это реализуется например перебором от нуля значений и до забора первого фейла.

Сравнение с ручным вариантом

В ручном варианте (функция test_handwritten ниже) обход полей производится вручную:
#include "for_each_field.hpp"

#include <vector>

using namespace proof_of_concept;

template<typename T>
void use_field(T &);

/****************************************************************/
struct Widget
{
    field<int> x;
    field<std::vector<int>> y;
    field<char> z;
};

void test_handwritten(Widget &w)
{
    use_field(w.x.value);
    use_field(w.y.value);
    use_field(w.z.value);
}

void test_for_each_field(Widget &w)
{
    for_each_field(w, [](auto &x)
    {
        use_field(x);
    });
}

Benchmark

Никакой benchmark не нужен, так как результирующий ассемблерный код в обоих вариантах идентичен

Скрипт сравнения ассемблерного кода вариантов

g++ versus_handwritten.cpp -std=c++17 -O3 -Wall -pedantic -DNDEBUG -S -masm=intel &&
cat versus_handwritten.s | c++filt > versus_handwritten.filtered.s &&

sed -n '/test_for_each_field(Widget&):$/,/seh_endproc/p' versus_handwritten.filtered.s > for_each_field.s &&
sed -n '/test_handwritten(Widget&):$/,/seh_endproc/p' versus_handwritten.filtered.s > handwritten.s &&

diff -u handwritten.s for_each_field.s > result.diff &&
cat result.diff

ASM diff

--- handwritten.s   2017-01-16 11:43:08.199916500 +0300
+++ for_each_field.s    2017-01-16 11:43:08.171914900 +0300
@@ -1,5 +1,5 @@
-test_handwritten(Widget&):
-.LFB1456:
+test_for_each_field(Widget&):
+.LFB1457:
    push    rbx
    .seh_pushreg    rbx
    sub rsp, 32

Live Demo


Конструктор по умолчанию

Как видно из сравнения, компилятор успешно выкинул все вспомогательные runtime вызовы и вычисления сдвигов. Но, тем не менее, относительно производительности есть значимый недостаток — при обходе полей посетителем посредством конструирования дополнительного объекта, также будут конструироваться поля оригинальных типов (field::value) посредством default initialization. Если у объекта тяжёлый конструктор по-умолчанию, то он будет вызван и тем самым повлияет на производительность.
Но, к счастью, большинство конструкторов по умолчанию простые, и могут быть выкинуты компилятором — так как эти поля никак не используются — как например произошло в случае со std::vector выше (собственно для демонстрации этого он и был туда добавлен).

Как вариант можно добавить дополнительный шаблонный параметр в field и протаскивать его из внешней структуры, и в зависимости от его состояния глушить создание лишних полей, но это уже намного более громоздко для пользователя — лучше наверное взять BOOST_FUSION_DEFINE_STRUCT/BOOST_HANA_DEFINE_STRUCT, X Macros и прочие макросы высшего порядка.

Альтернативные возможности

Есть и другие варианты с помощью можно "пошевилить" поля не обращаясь к ним по имени, и они доступны даже для C++98. Например для этой же цели можно запрячь конструктор копирования или оператор присваивания сгенерированные компилятором — ведь там автоматически осуществляется поэлементное передёргивание полями. Но, в таком случае код посещения будет в обёртке field, и видимо придётся жонглировать через глобальный/TLS контекст, что уже крайне маловероятно поддастся оптимизатору.

Файлы

  for_each_field.hpp 
// Copyright Evgeny Panasyuk 2017.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

// e-mail: E?????[dot]P???????[at]gmail.???

// for_each_field Proof-of-Concept

#ifndef FOR_EACH_FIELD_HPP
#define FOR_EACH_FIELD_HPP

/******************************************************************************/
#include <type_traits>
#include <utility>
#include <tuple>
#include <array>
/******************************************************************************/

namespace proof_of_concept
{

/******************************************************************************/
#ifdef __GNUC__
    #define NOINLINE __attribute__((noinline))
#else
    #define NOINLINE
#endif

/******************************************************************************/

/****************************************************************/
struct to_any
{
    template<typename T> operator T();
};

/****************************************************************/
template<typename T, typename Pack> struct arity_test;

template<typename T, typename ...Xs>
struct arity_test<T, std::tuple<Xs...>>
{
    using yes_type = std::array<char, 2>;
    using no_type  = std::array<char, 1>;

    template<typename U>
    static auto check(int) ->
        decltype(U{Xs{}...}, yes_type{});

    template<typename U>
    static no_type check(...);

    constexpr static auto value =
        sizeof(check<T>(0)) == sizeof(yes_type);
};

/****************************************************************/
template
<
    typename T,
    typename Pack = std::tuple<to_any>,
    bool cond = arity_test<T, Pack>::value
>
struct fields_count_aux
{
    constexpr static auto value = fields_count_aux
    <
        T,
        decltype(std::tuple_cat(Pack{}, std::tuple<to_any>{}))
    >::value;
};

template<typename T, typename Pack>
struct fields_count_aux<T, Pack, false>
{
    constexpr static auto value = std::tuple_size<Pack>::value - 1;
    // or std::tuple_size_v when available
};

template<typename T>
constexpr auto fields_count =
    fields_count_aux<std::remove_reference_t<T>>::value;

/****************************************************************/
template<typename F>
struct field_visitor
{
    F f;

    template<typename T>
    void operator()(T *field_this)
    {
        f(field_this);
    }
};

template<>
struct field_visitor<void> // for is_fields_sequence
{
    template<typename T> void operator()(T*);
};

template<typename F>
constexpr auto make_field_visitor(F f)
{
    return field_visitor<F>{f};
}

template<typename T>
struct field
{
    template<typename U>
    field(field_visitor<U> &f)
    {
        f(this);
    }

    field(field_visitor<void>); // for is_fields_sequence

    // std::forward would require constructor template
    // and additional restriction
    field(T x) : value(std::move(x)) {}
    field(T &x) : value(x) {}

    field() {}

    T value;
};

/****************************************************************/
template<typename T, typename F, size_t ...Is>
void for_each_field_aux(T &x, F &f, std::index_sequence<Is...>)
{
    std::aligned_union_t<1, T> storage;
    auto placement_addr = reinterpret_cast<char*>(&storage);

    auto action = make_field_visitor([&](auto *field_this)
    {
        using field_type = std::remove_reference_t<decltype(*field_this)>;
        auto byte_shift = reinterpret_cast<char*>(field_this) - placement_addr;
        auto field_addr = reinterpret_cast<char*>(&x) + byte_shift;
        auto current_field = reinterpret_cast<field_type*>(field_addr);
        f(current_field->value);
    });
    (void)action;
    new (placement_addr) T{((void)Is, action)...};
    reinterpret_cast<T*>(placement_addr)->~T();
}

template<typename T, typename F>
auto for_each_field(T &&x, F f)
{
    for_each_field_aux(x, f, std::make_index_sequence<fields_count<T>>{});

    return f;
}

/****************************************************************/
template<typename T, size_t ...Is>
constexpr bool is_fields_sequence_aux(std::index_sequence<Is...>)
{
    return arity_test
    <
        T,
        std::tuple<decltype(((void)Is, field_visitor<void>{}))...>
    >::value;
}

template<typename T>
constexpr bool is_fields_sequence()
{
    return is_fields_sequence_aux<T>
    (
        std::make_index_sequence<fields_count<T>>{}
    );
}

/****************************************************************/
} // namespace end

#endif
  versus_handwritten.cpp 
#include "for_each_field.hpp"

#include <vector>

using namespace proof_of_concept;

template<typename T>
void use_field(T &);

/****************************************************************/
struct Widget
{
    field<int> x;
    field<std::vector<int>> y;
    field<char> z;
};

void test_handwritten(Widget &w)
{
    use_field(w.x.value);
    use_field(w.y.value);
    use_field(w.z.value);
}

void test_for_each_field(Widget &w)
{
    for_each_field(w, [](auto &x)
    {
        use_field(x);
    });
}
  for_each_field.s 
test_for_each_field(Widget&):
.LFB1457:
    push    rbx
    .seh_pushreg    rbx
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    mov rbx, rcx
    call    void use_field<int>(int&)
    lea rcx, 8[rbx]
    call    void use_field<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> >&)
    lea rcx, 32[rbx]
    add rsp, 32
    pop rbx
    jmp void use_field<char>(char&)
    .seh_endproc
  handwritten.s 
test_handwritten(Widget&):
.LFB1456:
    push    rbx
    .seh_pushreg    rbx
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    mov rbx, rcx
    call    void use_field<int>(int&)
    lea rcx, 8[rbx]
    call    void use_field<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> >&)
    lea rcx, 32[rbx]
    add rsp, 32
    pop rbx
    jmp void use_field<char>(char&)
    .seh_endproc
  versus_handwritten.filtered.s 
    .file   "versus_handwritten.cpp"
    .intel_syntax noprefix
    .text
    .p2align 4,,15
    .globl  test_handwritten(Widget&)
    .def    test_handwritten(Widget&);  .scl    2;  .type   32; .endef
    .seh_proc   test_handwritten(Widget&)
test_handwritten(Widget&):
.LFB1456:
    push    rbx
    .seh_pushreg    rbx
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    mov rbx, rcx
    call    void use_field<int>(int&)
    lea rcx, 8[rbx]
    call    void use_field<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> >&)
    lea rcx, 32[rbx]
    add rsp, 32
    pop rbx
    jmp void use_field<char>(char&)
    .seh_endproc
    .p2align 4,,15
    .globl  test_for_each_field(Widget&)
    .def    test_for_each_field(Widget&);   .scl    2;  .type   32; .endef
    .seh_proc   test_for_each_field(Widget&)
test_for_each_field(Widget&):
.LFB1457:
    push    rbx
    .seh_pushreg    rbx
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    mov rbx, rcx
    call    void use_field<int>(int&)
    lea rcx, 8[rbx]
    call    void use_field<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> >&)
    lea rcx, 32[rbx]
    add rsp, 32
    pop rbx
    jmp void use_field<char>(char&)
    .seh_endproc
    .ident  "GCC: (GNU) 5.4.0"
    .def    void use_field<int>(int&);  .scl    2;  .type   32; .endef
    .def    void use_field<std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> >&);   .scl    2;  .type   32; .endef
    .def    void use_field<char>(char&);    .scl    2;  .type   32; .endef
Отредактировано 16.01.2017 10:03 Evgeny.Panasyuk . Предыдущая версия . Еще …
Отредактировано 16.01.2017 10:01 Evgeny.Panasyuk . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.