Много boost::range::join приводит к stack overflow
От: ArtDenis Россия  
Дата: 23.07.20 10:35
Оценка:
Привествую. Не могу понять на что расходуется стэк. Вроде как в нем нету тяжёлых объектов или передачи аргументов по значению. Вот код для воспроизведения:

#include <vector>
#include <iostream>
#include <boost/range/join.hpp>

template <typename R1, typename R2, typename ... Other>
auto join_ranges(const R1 & r1, const R2 & r2, const Other& ... other)
{
    if constexpr (sizeof ... (other) == 0)
        return boost::range::join(r1, r2);
    else
        return join_ranges(boost::range::join(r1, r2), other...);
}

int main()
{
    std::vector<int> v = {1, 2, 3};
    auto joined = join_ranges(v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v, v);
    for (int i : joined)
        std::cout << i;
}

Если уменьшать количество аргументов при вызове join_ranges, то stack overflow перестаёт выскакивать. Поломал голову, но не смог понять куда уходит стэк.

Сейчас решил проблему через boost::any_range:
template <typename Ret, typename Item, typename ... Other>
void join_ranges_impl(Ret & result, const Item & range, const Other& ... other)
{
    result = boost::range::join(result, range);
    if constexpr (sizeof ... (other) != 0)
        join_ranges_impl(result, other...);
}

template <typename Item, typename ... Other>
auto join_ranges(const Item & range, const Other& ... other)
{
    using T = std::remove_reference_t<decltype(*std::begin(range))>;
    boost::any_range<const T, boost::random_access_traversal_tag, const T> result = range;
    join_ranges_impl(result, other...);
    return result;
}

Но решение мне очень не нравится, т.к. в прошлом имел кучу проблем, где на ровном месте при работе с boost::any_range ловил UB. Слишком опасная штука и легко ошибиться.

Ищу решение как это сделать без boost::any_range

PS: Последний Visual Studio 2017. Компилю в x86, запускаю под дебагом, /std:c++17
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Re: Много boost::range::join приводит к stack overflow
От: B0FEE664  
Дата: 23.07.20 11:11
Оценка:
Здравствуйте, ArtDenis, Вы писали:

AD>Привествую. Не могу понять на что расходуется стэк. Вроде как в нем нету тяжёлых объектов или передачи аргументов по значению. Вот код для воспроизведения:


AD>
AD>template <typename R1, typename R2, typename ... Other>
AD>auto join_ranges(const R1 & r1, const R2 & r2, const Other& ... other)
AD>{
AD>    if constexpr (sizeof ... (other) == 0)
AD>        return boost::range::join(r1, r2);
AD>    else
AD>        return join_ranges(boost::range::join(r1, r2), other...);
AD>}
AD>


У join_ranges очень тяжёлый возвращаемый объект.
И каждый день — без права на ошибку...
Re[2]: Много boost::range::join приводит к stack overflow
От: ArtDenis Россия  
Дата: 23.07.20 11:23
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE>У join_ranges очень тяжёлый возвращаемый объект.


Похоже на то:
    std::vector<int> v = {1, 2, 3};

    auto joined1 = boost::range::join(v, v);
    std::cout << sizeof(joined1) << std::endl;

    auto joined2 = boost::range::join(joined1, v);
    std::cout << sizeof(joined2) << std::endl;

    auto joined3 = boost::range::join(joined2, v);
    std::cout << sizeof(joined3) << std::endl;

    auto joined4 = boost::range::join(joined3, v);
    std::cout << sizeof(joined4) << std::endl;

    auto joined5 = boost::range::join(joined4, v);
    std::cout << sizeof(joined5) << std::endl;

    auto joined6 = boost::range::join(joined5, v);
    std::cout << sizeof(joined6) << std::endl;

    auto joined7 = boost::range::join(joined6, v);
    std::cout << sizeof(joined7) << std::endl;

    auto joined8 = boost::range::join(joined7, v);
    std::cout << sizeof(joined8) << std::endl;

    auto joined9 = boost::range::join(joined8, v);
    std::cout << sizeof(joined9) << std::endl;

    auto joined10 = boost::range::join(joined9, v);
    std::cout << sizeof(joined10) << std::endl;


80
216
488
1032
2120
4296
8648
17352
34760
69576


Но почему Как эту фигню обойти?
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Re[3]: Много boost::range::join приводит к stack overflow
От: B0FEE664  
Дата: 23.07.20 12:05
Оценка:
Здравствуйте, ArtDenis, Вы писали:

BFE>>У join_ranges очень тяжёлый возвращаемый объект.


AD>Похоже на то:

AD>
AD>80
AD>216
AD>488
AD>1032
AD>2120
AD>4296
AD>8648
AD>17352
AD>34760
AD>69576
AD>


AD>Но почему

Я просто прочитал исходник тут и констатировал простой факт: joined_range содержит в себе два итератора, которые содержат в себе два итератора, которые содержат в себе два итератора, которые содержат в себе два итератора, которые содержат в себе два итератора...

AD>Как эту фигню обойти?


Первое, что приходит в голову:
template <typename R1, typename R2, typename ... Other>
auto join_ranges(const R1 & r1, const R2 & r2, const Other& ... other)
{
    if constexpr (sizeof ... (other) == 0)
        return boost::range::join(r1, r2);

    if constexpr (sizeof ... (other) == 1)
        return join_ranges(boost::range::join(r1, r2), other...);

  return boost::range::join(boost::range::join(r1, r2), join_ranges(other...);
}


По идее должно помочь, но кардинально это проблему не решит. Т.е. я хочу сказать, что должно быть решение лучше, просто я не очень опытен в вариадиках, поэтому сходу написать не могу.
И каждый день — без права на ошибку...
Re[4]: Много boost::range::join приводит к stack overflow
От: watchmaker  
Дата: 23.07.20 12:27
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE> Т.е. я хочу сказать, что должно быть решение лучше


Например, перейти на использование стандартного #include <ranges> Или на библиотеку range-v3, которая для с++20 послужила прототипом
Re[4]: Много boost::range::join приводит к stack overflow
От: ArtDenis Россия  
Дата: 23.07.20 13:12
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE> ... Т.е. я хочу сказать, что должно быть решение лучше ...


Я уже попытался решить проблему более кардинально. Плюнул на лишние выделения памяти и задействовал std::unique_ptr. Теперь boost::range::joined_range выделяется на куче, а не в стэке.

#include <vector>
#include <iostream>
#include <memory>
#include <boost/range/join.hpp>

template <typename R1, typename R2, typename ... Other>
auto join_ranges(const R1 & r1, const R2 & r2, const Other& ... other)
{
    using joined_range_t = boost::range::joined_range<const R1, const R2>;

    auto joined_r1_r2 = std::make_unique<joined_range_t>(r1, r2);

    if constexpr (sizeof ... (other) == 0)
        return joined_r1_r2;
    else
        return join_ranges(*joined_r1_r2, other...);
}

int main()
{
    std::vector<int> v = {1, 2, 3};
    auto joined = join_ranges(v, v, v, v, v, v, v, v, v, v, v, v, v, v);

    for (int i : *joined)
        std::cout << i;
}


Но stack overflow всё равно происходит в конструкторе joined_range! Вот теперь-то он откуда?
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Re[5]: Много boost::range::join приводит к stack overflow
От: goloveshin Россия  
Дата: 23.07.20 15:03
Оценка:
как вариант, но оно тоже падает...

template <typename R, typename ... Other>
decltype(auto) join_ranges(R&& r, Other&& ... other)
{
    if constexpr (sizeof ... (other) == 0)
        return std::forward<R>(r);
    else
        return boost::range::join(std::forward<R>(r), join_ranges(std::forward<Other>(other)...));
}
Re[6]: Много boost::range::join приводит к stack overflow
От: ArtDenis Россия  
Дата: 23.07.20 15:46
Оценка:
Здравствуйте, goloveshin, Вы писали:

G>как вариант, но оно тоже падает...


G> if constexpr (sizeof ... (other) == 0)

G> return std::forward<R>(r);
Нету смыла от forward в return. Компилятор сам сделает перемещение в этом случае, если оно возможно. Или я ошибаюсь?

G> else

G> return boost::range::join(std::forward<R>(r), join_ranges(std::forward<Other>(other)...));
А это как поможет-то? 1) для меня forward излишен, 2) и у моём и в твоём случае (с forward) передаются ссылки, а они очень мало влияют на размер стэка и в x86 занимают в стеке всего 4 байта
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Re[7]: Много boost::range::join приводит к stack overflow
От: ArtDenis Россия  
Дата: 23.07.20 16:27
Оценка:
Здравствуйте, ArtDenis, Вы писали:

G>> if constexpr (sizeof ... (other) == 0)

G>> return std::forward<R>(r);
AD>Нету смыла от forward в return. Компилятор сам сделает перемещение в этом случае, если оно возможно. Или я ошибаюсь?

А всё, понял для чего это. У тебя же возвращаемый тип decltype(auto)
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Re[5]: Много boost::range::join приводит к stack overflow
От: B0FEE664  
Дата: 23.07.20 17:44
Оценка: +1
Здравствуйте, ArtDenis, Вы писали:

AD>Но stack overflow всё равно происходит в конструкторе joined_range! Вот теперь-то он откуда?


Слушайте, там удвоение размера на каждом шаге, как не крути, стека не хватит хотя бы просто потому, что конструктор там тоже рекурсивный. Да что стека, просто памяти не хватит!

80
216
488
1032
2120
4296
8648
17352
34760
69576

С такой-то тенденцией, на тридцатом шаге потребуется где-то 64 гигабайта памяти, а на сороковом — 64 терабайта памяти, а если вы захотите объединить это несчастный вектор сотню раз, то количество необходимой памяти превысит число атомов в наблюдаемой вселенной.

Да это просто шедевр какой-то!
И каждый день — без права на ошибку...
Re: Много boost::range::join приводит к stack overflow
От: Шахтер Интернет  
Дата: 23.07.20 19:52
Оценка:
Здравствуйте, ArtDenis, Вы писали:

/* main.cpp */

#include <CCore/inc/Print.h>
#include <CCore/inc/Array.h>

using namespace CCore;

/* JoinRange */

template <class F,class T>
struct JoinRange
 {
  F f;
  T t;

  JoinRange(const F &f_,const T &t_) : f(f_),t(t_) {}

  bool operator + () const { return +f || +t ; }

  bool operator ! () const { return !f && !t ; } 

  auto operator * () const { return (+f)? *f : *t ; }

  void operator ++ () { if( +f ) ++f; else ++t; }

  bool operator != (NothingType) const { return +(*this); }
 };

template <class F,class T>
auto begin(JoinRange<F,T> r) { return r; }

template <class F,class T>
NothingType end(JoinRange<F,T>) { return Null; }

/* JoinRanges() */

template <class T>
auto JoinRanges(const T &t)
 {
  return Range(t);
 }

template <class T,class ... TT>
auto JoinRanges(const T &t,const TT & ... tt)
 {
  return JoinRange(Range(t),JoinRanges(tt...));
 }

/* main() */

template <class T>
void Show(const T &list)
 {
  for(const auto &obj : list ) Printf(Con,"#; , ",obj);

  Putobj(Con,"\n\n"_c);
 }

int main() 
 {
  DynArray<int> v{1,2,3,4,5};

  Show(v);  

  Show(JoinRanges(v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v,v));

  return 0;
 }


И всё работает без проблем. здесь
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[6]: Много boost::range::join приводит к stack overflow
От: ArtDenis Россия  
Дата: 24.07.20 05:22
Оценка:
Здравствуйте, B0FEE664, Вы писали:

AD>>Но stack overflow всё равно происходит в конструкторе joined_range! Вот теперь-то он откуда?

BFE>Слушайте, там удвоение размера на каждом шаге, как не крути, стека не хватит хотя бы просто потому, что конструктор там тоже рекурсивный. Да что стека, просто памяти не хватит!
Да. Но std::make_unique создаёт объект в куче. Возврат из функции через std::unuque_ptr. Стэк не должен задействоваться в таком объёме.


BFE>Да это просто шедевр какой-то!

Согласен )
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Отредактировано 24.07.2020 5:23 ArtDenis . Предыдущая версия . Еще …
Отредактировано 24.07.2020 5:23 ArtDenis . Предыдущая версия .
Re[2]: Много boost::range::join приводит к stack overflow
От: ArtDenis Россия  
Дата: 24.07.20 06:20
Оценка:
Здравствуйте, Шахтер, Вы писали:

Ш>И всё работает без проблем.


Написать сам я смогу. Но хочется иметь ка можно меньше велосипедов в проекте
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Re: Много boost::range::join приводит к stack overflow
От: ArtDenis Россия  
Дата: 24.07.20 06:34
Оценка:
Здравствуйте, ArtDenis, Вы писали:

AD>Сейчас решил проблему через boost::any_range:


И в этом решении есть UB, если передавать туда transformed range, что я и делаю

https://svn.boost.org/trac10/ticket/10493
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.