Почему std :: remove_if создает так много замыканий? - PullRequest
Новая
       11

Почему std :: remove_if создает так много замыканий?

0 голосов
/ 26 августа 2018

В этом примере экземпляр foo ничего не делает, кроме печати, независимо от того, создан он копией или перемещен. 

#include <iostream>
#include <algorithm>
#include <vector>

struct foo {
    foo()=default;
    foo(foo &&) { std::cout << "move constructed\n"; }
    foo(const foo &) { std::cout << "copy constructed\n"; }
};

int main()
{
    foo x;
    std::vector<int> v; // empty

    std::remove_if(v.begin(), v.end(),
                   [x=std::move(x)](int i){ return false; });
}

Это дает следующий вывод: 

move constructed
copy constructed
move constructed
move constructed
copy constructed
copy constructed

Вопросы:

  • Почему std::remove_if создает так много замыканий?
  • Даже если необходимо несколько промежуточных экземпляров, можно ожидать, что все они являются значениями; так почему некоторые из них построены по принципу копирования?

Компилятор gcc 8.1.1

1 Ответ

0 голосов
/ 26 августа 2018

Если мы посмотрим на реализацию std::remove_if в libstdc ++ gcc - v3 , мы заметим, что предикат передается по цепочке вызовов (по значению, иногда) за несколько шагов до достижения самая нижняя функция __find_if (используется remove_if).

Давайте посчитаем ходы и копии:

  1. move constructed когда предикат (включая захваченный x) отправляется по значению, но не как lvalue, на std::remove_if точку входа

  2. copy constructed при передаче функции __gnu_cxx::__ops::__pred_iter(...), которая, в свою очередь:

  3. вызывает макрос _GLIBCXX_MOVE , то есть move constructed,

  4. , который перемещает предикат в _Iter_pred ctor , который перемещает его (move constructed) в _M_pred член.

  5. Вызов с std::remove_if на std::__remove_if кажется оптимизированным, так как _Iter_pred, я думаю, не является lvalue, но __remove_if в свою очередь передает завернутый предикат по значению std::__find_if для другого copy constructed вызова.

  6. std::__find_if, в свою очередь, перенаправляет завернутый предикат по значению в другую __find_if перегрузку , которая в конечном итоге является приемником этой цепочки вызовов, и окончательный copy constructed .

Может быть интересно сравнить, например, с реализация clang из std::remove_if, поскольку clang (6.0.1) не создает эту цепочку перемещения-копирования для примера OP std::remove_if. Быстрый взгляд показывает, что кажется, что clang использует черты в предикате типа , чтобы убедиться, что предикат передан в качестве lvalue-ссылки .

И clang, и gcc создают одинаковые цепочки move / copy для следующего надуманного примера, который показывает цепочку, аналогичную реализации gcc: 

#include <iostream>
#include <utility>

struct foo {
    foo() = default;
    foo(foo &&) { std::cout << "move constructed\n"; }
    foo(const foo &) { std::cout << "copy constructed\n"; }
};

template <typename Pred>
struct IterPred {
    Pred m_pred;
    explicit IterPred(Pred pred) : m_pred(std::move(pred)) {}
};

template <typename T>
inline IterPred<T> wrap_in_iterpred (T l) { 
    return IterPred<T>(std::move(l)); 
}

template <typename T>
void find_if_overload(T l) {
    (void)l;
}

template <typename T>
void find_if_entrypoint(T l) { 
    find_if_overload(l);
}

template <typename T>
void remove_if_entrypoint(T l) { 
    find_if_entrypoint(
        wrap_in_iterpred(l));
}

int main()
{
    foo x;
    remove_if_entrypoint([x=std::move(x)](int){ return false; });
}

Где gcc (8.2.0) и clang (6.0.1) создают следующую цепочку: 

move constructed
copy constructed
move constructed
move constructed
copy constructed
...