[c++] растет стек от временных объектов

erotic

#include <iostream>

#include <vector>



using namespace std;



struct S

{

    S  { cout << "S " << this << endl; }

//    ~S  { cout << "~S " << this << endl; }

    S(const S& r)  { cout << "S(const S&) " << this << " " << &r << endl; }

    S(S&& r)  { cout << "S(S&&) " << this << " " << &r << endl; }

    S& operator= (const S& r) { cout << "S& operator=(const S&) " << this << " " << &r << endl;  return *this; }

    S& operator= (S&& r) { cout << "S& operator=(S&&) " << this << " " << &r << endl;  return *this; }

};



S cs

{

    return S;

}



int main

{

    vector<S> s;

    cout << "size " << s.size << " capacity " << s.capacity << endl;

    s.push_back(cs;

    cout << "size " << s.size << " capacity " << s.capacity << endl;

    s.push_back(cs;

    cout << "size " << s.size << " capacity " << s.capacity << endl;

    s.push_back(cs;

    cout << "size " << s.size << " capacity " << s.capacity << endl;

    s.push_back(cs;

    cout << "size " << s.size << " capacity " << s.capacity << endl;

    return 0;

}

Что я ожидаю увидеть - это то, что каждый временный объект типа S создается на стеке по одному и тому же адресу и впоследствии уничтожается. Это и наблюдается с gcc-4.9.2 (адрес напротив S:



size 0 capacity 0

S 0x7fffdcd7bb5f

S(S&&) 0x1589c20 0x7fffdcd7bb5f

size 1 capacity 1

S 0x7fffdcd7bb5f

S(S&&) 0x1589c41 0x7fffdcd7bb5f

S(const S&) 0x1589c40 0x1589c20

size 2 capacity 2

S 0x7fffdcd7bb5f

S(S&&) 0x1589c22 0x7fffdcd7bb5f

S(const S&) 0x1589c20 0x1589c40

S(const S&) 0x1589c21 0x1589c41

size 3 capacity 4

S 0x7fffdcd7bb5f

S(S&&) 0x1589c23 0x7fffdcd7bb5f

size 4 capacity 4

А если использовать clang-3.6.0:



size 0 capacity 0

S 0x7fffe8824df0

S(S&&) 0x21adc20 0x7fffe8824df0

size 1 capacity 1

S 0x7fffe8824de8

S(S&&) 0x21adc41 0x7fffe8824de8

S(const S&) 0x21adc40 0x21adc20

size 2 capacity 2

S 0x7fffe8824de0

S(S&&) 0x21adc22 0x7fffe8824de0

S(const S&) 0x21adc20 0x21adc40

S(const S&) 0x21adc21 0x21adc41

size 3 capacity 4

S 0x7fffe8824dd8

S(S&&) 0x21adc23 0x7fffe8824dd8

size 4 capacity 4

Т.е. стек постоянно растет от временных объектов. Все еще хуже, если я раскомментирую деструктор класса S - тогда и в g++ начинается подобное поведение:

 size 0 capacity 0

S 0x7fffe214b3bc

S(S&&) 0x6dbc20 0x7fffe214b3bc

~S 0x7fffe214b3bc

size 1 capacity 1

S 0x7fffe214b3bd

S(S&&) 0x6dbc41 0x7fffe214b3bd

S(const S&) 0x6dbc40 0x6dbc20

~S 0x6dbc20

~S 0x7fffe214b3bd

size 2 capacity 2

S 0x7fffe214b3be

S(S&&) 0x6dbc22 0x7fffe214b3be

S(const S&) 0x6dbc20 0x6dbc40

S(const S&) 0x6dbc21 0x6dbc41

~S 0x6dbc40

~S 0x6dbc41

~S 0x7fffe214b3be

size 3 capacity 4

S 0x7fffe214b3bf

S(S&&) 0x6dbc23 0x7fffe214b3bf

~S 0x7fffe214b3bf

size 4 capacity 4

~S 0x6dbc20

~S 0x6dbc21

~S 0x6dbc22

~S 0x6dbc23

Вероятно, это не бага, а просто я чего-то не понимаю, но чего?
Если засунуть наполнение вектора в цикл, а не делать это отдельными вызовами, то в обоих компиляторах временная переменная создается по одному и тому же адресу, что наводит на мысли о том, что временный объект хоть и уничтожается в конце полного выражения, как и положенно временному объекту, но память из-под него становится возможным использовать только после выхода из блока. Однако если в изначальном варианте каждый push_back поместить в отдельный блок, то все равно стек растет.
Как это объяснить?

Dasar

Как это объяснить?

Компилятор не достаточно оптимизирующий, и под каждую неявную переменную выделяет новое место на стеке, хотя мог бы использовать место от уже неиспользуемой предыдущей переменной.

marat7256

А зачем так делать?

erotic

Это единственное объяснение? clang и gcc даже с -O3 это не оптимизируют? Мне кажется это странным. Особенно поведение с добавлением деструктора.
Мне это ломает тесты

В тестах на каждый кейс в вектор пихается большой объект с тестовыми данными. Его размер на стеке где-то 40 Кб. Можно было бы читать из файла, но я задаю в коде подобным образом, как тут написано. Соответственно, через 200 тест-кейсов кончится стек - но до этого я еще не дошел, я дошел до того, что через 50 тест-кейсов валгринд ругается на большой скачок stack pointer'а - больше 2 Мб.
Как-то это можно обойти, я придумаю, но я два дня потратил на расковыривание того, что происходит, и до сих пор у меня нет объяснения такому нелепому расходованию памяти.

marat7256

Объясни, зачем создавать объекты в стеке.
Чем тебе new/delete не угодили?

Dimon89

А ты обратил внимание на количество конструкторов-деструкторов при каждом следующем вызове?



size 2 capacity 2

S 0x7fffe214b3be

S(S&&) 0x6dbc22 0x7fffe214b3be

S(const S&) 0x6dbc20 0x6dbc40

S(const S&) 0x6dbc21 0x6dbc41

~S 0x6dbc40

~S 0x6dbc41

~S 0x7fffe214b3be

size 3 capacity 4

stm5872449

Объясни, зачем создавать объекты в стеке.
Чем тебе new/delete не угодили?

Затем что аллокация на стеке намного быстрее? :confused:

Dimon89

Да, на всякий случай:



size 0 capacity 4

S 0015FCB7

S(S&&) 002A9408 0015FCB7

~S 0015FCB7

size 1 capacity 4

S 0015FCB7

S(S&&) 002A9409 0015FCB7

~S 0015FCB7

size 2 capacity 4

S 0015FCB7

S(S&&) 002A940A 0015FCB7

~S 0015FCB7

size 3 capacity 4

S 0015FCB7

S(S&&) 002A940B 0015FCB7

~S 0015FCB7

size 4 capacity 4

marat7256

Возможно, я что-то путаю, но при выходе из функции созданные внитури ее локальные перемнные из стека уничтожаются. Если функция возвращает объект, созданный в стеке, то его таки придется куда-то из стека скопировать, так что память где-то кроме стека все равно выделять. Так зачем это промежуточный стек? Или я что-то недопонимаю? Я как бы давно уже отстал от жизни компиляторов и языков, прошу пояснить.

stm5872449

Если функция возвращает объект, созданный в стеке, то его таки придется куда-то из стека скопировать, так что память где-то кроме стека все равно выделять. Так зачем это промежуточный стек?

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

marat7256

Проще сделать вектор ссылок, создавать отдельно в куче и вставлять ссылки в вектор.
Пока что я вижу стрельбу себе в ногу.

Dimon89

Проще сделать вектор ссылок, создавать отдельно в куче и вставлять ссылки в вектор.

Про это уже писали выше. Создание на стеке заметно быстрее.

marat7256

Можно как-то показать,что заметно быстрее?

Dimon89

Ну и как бы в реальных задачах у меня было бы так:

 

size 0 capacity 4

S 0056A4B8

size 1 capacity 4

S 0056A4B9

size 2 capacity 4

S 0056A4BA

size 3 capacity 4

S 0056A4BB

size 4 capacity 4

erotic

А ты обратил внимание на количество конструкторов-деструкторов при каждом следующем вызове?

Разумеется. Это элементарно объясняется тем, что вектору нужно переаллоцировать память. По адресам видно, что деструкторы вызываются как у объектов в куче - тех, которые уже в векторе, так и у объекта на стеке, который добавился в вектор последним. Происходит это когда size = capacity и, по-моему не имеет отношения к делу. Пример можно упростить, избавившись от векторов, до такого:



#include <iostream>



using namespace std;



struct S

{

    S  { cout << "S " << this << endl; }

    ~S  { cout << "~S " << this << endl; }

    S(const S& r)  { cout << "S(const S&) " << this << " " << &r << endl; }

    S(S&& r)  { cout << "S(S&&) " << this << " " << &r << endl; }

    S& operator= (const S& r) { cout << "S& operator=(const S&) " << this << " " << &r << endl;  return *this; }

    S& operator= (S&& r) { cout << "S& operator=(S&&) " << this << " " << &r << endl;  return *this; }

};



int main

{

    S;

    S;

    S;

    S;

    return 0;

}

Результат:



S 0x7fff5df38a88

~S 0x7fff5df38a88

S 0x7fff5df38a80

~S 0x7fff5df38a80

S 0x7fff5df38a78

~S 0x7fff5df38a78

S 0x7fff5df38a70

~S 0x7fff5df38a70

erotic

Да, на всякий случай:

Как ты добился такого эффекта?

Ну и как бы в реальных задачах у меня было бы так:

Чем реальные задачи отличаются от модельного примера?

Dimon89

 

int main

{

    S;

    S;

    S;

    S;

    return 0;

}

 

S 0028F92B

~S 0028F92B

S 0028F92B

~S 0028F92B

S 0028F92B

~S 0028F92B

S 0028F92B

~S 0028F92B

Проверь, включена ли оптимизация компилятора.

Dimon89

Как ты добился такого эффекта?

Избавился от реаллокации вектора.

Чем реальные задачи отличаются от модельного примера?

Возможностью использовать emplace =)

erotic

Проверь, включена ли оптимизация компилятора.

Собирал вызовом "clang++ sp.cpp -std=c++14 -O3".
> clang++ --version
Apple LLVM version 6.1.0 (clang-602.0.49) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix

Dasar

Проще сделать вектор ссылок, создавать отдельно в куче и вставлять ссылки в вектор.

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

oliver11

Это баг. http://llvm.org/bugs/show_bug.cgi?id=5629

Maurog

до сих пор у меня нет объяснения такому нелепому расходованию памяти

склоняюсь к тому, что это баг, а твои ожидания вполне разумны.
временный объект живет до конца выражения, затем должен быть вызван деструктор и освобождена занимаемая память. возможность реюза памяти в твоих примерах довольно очевидна, однако я сомневаюсь, что это (обязательный реюз и нераздувание памяти для временных переменных) зафиксировано в стандарте языка. так что текущее поведение компиляторов вполне соответствует официальному стандарту
стратегия аллоцирования объектов на стеке может быть сложнее и приводить к фрагментации (дыркам) имхо.
еще можно почитать доку к -fstack-reuse : http://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html , которая подтверждает наличие нескольких стратегий у компилятора

Maurog

Можно как-то показать,что заметно быстрее?

можно почитать в инетах:
http://stackoverflow.com/questions/5807612/on-the-use-and-ab...
http://stackoverflow.com/questions/714692/alloca-implementat...

stm5872449

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

Я тоже это сначала написал, но потом прочитал, что у автора объекты намного больше кэш-линии, так что этим эффектом вроде можно пренебречь.

erotic

Это баг. http://llvm.org/bugs/show_bug.cgi?id=5629

За 6 лет не починят такую важную проблему?

marat7256

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

Dasar

у автора объекты намного больше кэш-линии

Даже больше чем кэш второго и третьего уровня? :shocked:

Оставить комментарий