А почему бы не сделать стек еще умнее?
От: Kingofastellarwar Украина  
Дата: 13.11.16 12:40
Оценка:
фича для компилятора:
вот например передаем мы чтото или создаем локальную переменую, а почему бы если нет особых указаний, то все что будет динамически выделено этим и производными объектами не выделять тоже в стеке?
т.е. все операторы new вызванные в методах этого объекта, если нет особых указаний, будут аллокейтить в стеке
например при передаче строк, можно вообще тогда обойтись без обращения к куче
Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не более года. (с) Эксперт, авторитет и профессионал из 1957 г.
Re: А почему бы не сделать стек еще умнее?
От: lpd Черногория  
Дата: 13.11.16 12:49
Оценка: +1 :)
Здравствуйте, Kingofastellarwar, Вы писали:

K>фича для компилятора:

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

Чем тебе не нравятся обращения к куче? Стек последовательный и при выделениях и последующих освобождениях будет быстро фрагментироваться(быстрее, чем куча). Можно обойтись одной кучей без стека, используя какие-то другие структуры данных, — стек просто удобен для реализации вложенных вызовов процедур, и поддерживается процессором.
У сложных вещей обычно есть и хорошие, и плохие аспекты.
Берегите Родину, мать вашу. (ДДТ)
Отредактировано 13.11.2016 12:50 lpd . Предыдущая версия .
Re: А почему бы не сделать стек еще умнее?
От: Ops Россия  
Дата: 13.11.16 12:53
Оценка: +1
Здравствуйте, Kingofastellarwar, Вы писали:

K>фича для компилятора:

K>вот например передаем мы чтото или создаем локальную переменую, а почему бы если нет особых указаний, то все что будет динамически выделено этим и производными объектами не выделять тоже в стеке?
Потому что стек не резиновый.
K>т.е. все операторы new вызванные в методах этого объекта, если нет особых указаний, будут аллокейтить в стеке
K>например при передаче строк, можно вообще тогда обойтись без обращения к куче
Реализации строк и так умеют SSO. В общем случае, классу лучше знать, выделять память динамически, или нет.
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Re: А почему бы не сделать стек еще умнее?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 13.11.16 17:48
Оценка: -1
Здравствуйте, Kingofastellarwar, Вы писали:

K>фича для компилятора:

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

Welcome to Rust
Умолчание — на стеке или в куче, дело компилятора — но только пока живёт данный вызов функции. Хочешь, чтобы объект прожил дольше — явно создаёшь Box<T>, Rc<T> или аналогичное — и тогда вопрос передаётся по наследству.
The God is real, unless declared integer.
Re: А почему бы не сделать стек еще умнее?
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 14.11.16 08:04
Оценка:
Здравствуйте, Kingofastellarwar, Вы писали:

K>фича для компилятора:

K>вот например передаем мы чтото или создаем локальную переменую, а почему бы если нет особых указаний, то все что будет динамически выделено этим и производными объектами не выделять тоже в стеке?
K>т.е. все операторы new вызванные в методах этого объекта, если нет особых указаний, будут аллокейтить в стеке

Я в своем компиляторе и ВМ так и делал, совместил стек и кучу в одном флаконе, наложив ряд ограничений в одних местах и болт в других:
http://thedeemon.livejournal.com/10126.html

А в JVM escape analysis это сейчас делает для джавы и, говорят, довольно успешно.
Re: А почему бы не сделать стек еще умнее?
От: Pzz Россия https://github.com/alexpevzner
Дата: 14.11.16 08:22
Оценка:
Здравствуйте, Kingofastellarwar, Вы писали:

K>например при передаче строк, можно вообще тогда обойтись без обращения к куче


Потому что если строка константная, казалось бы, можно вообще обойтись без динамического выделения памяти. А если она вычисляется в процессе, то без выделения памяти под промежуточные состояния не обойтись. А стек для таких произвольных манипуляций с памятью не очень-то подходит.
Re[2]: А почему бы не сделать стек еще умнее?
От: Pzz Россия https://github.com/alexpevzner
Дата: 14.11.16 08:23
Оценка:
Здравствуйте, lpd, Вы писали:

lpd>Чем тебе не нравятся обращения к куче? Стек последовательный и при выделениях и последующих освобождениях будет быстро фрагментироваться(быстрее, чем куча). Можно обойтись одной кучей без стека, используя какие-то другие структуры данных, — стек просто удобен для реализации вложенных вызовов процедур, и поддерживается процессором.


Что такое фрагментирование стека?
Re: А почему бы не сделать стек еще умнее?
От: _hum_ Беларусь  
Дата: 14.11.16 08:29
Оценка:
Здравствуйте, Kingofastellarwar, Вы писали:

K>фича для компилятора:

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

так размер стека же неизвестен. как в таком случае организовать корректную работу проги?

п.с. попутные вопросы спецам
— почему все-таки с++ не предоставил возможность узнавать этот размер?
— есть какая-то гарантия, что все локальные статические переменные (хотя бы по одной копии) влезут в стек? (то есть, делает ли компилятор что-то вроде анализа,к акой стек нужен, чтоб вместить все эти переменные, и такой стек и выделяет)?
Re[3]: А почему бы не сделать стек еще умнее?
От: lpd Черногория  
Дата: 14.11.16 08:50
Оценка:
Здравствуйте, Pzz, Вы писали:

Pzz>Здравствуйте, lpd, Вы писали:


lpd>>Чем тебе не нравятся обращения к куче? Стек последовательный и при выделениях и последующих освобождениях будет быстро фрагментироваться(быстрее, чем куча). Можно обойтись одной кучей без стека, используя какие-то другие структуры данных, — стек просто удобен для реализации вложенных вызовов процедур, и поддерживается процессором.


Pzz>Что такое фрагментирование стека?


Если выделить место в стеке, потом сделать много push, затем освободить выделенный на верхнем уровне вызвовов участок памяти, то место будет пустовать но останется не занятымЮ пока popы не вернутся на верхний уровень. То есть занятая память в стеке будет чредоваться с пустыми кусками. Можно сказать, что это фрагментация стека.
У сложных вещей обычно есть и хорошие, и плохие аспекты.
Берегите Родину, мать вашу. (ДДТ)
Re[2]: А почему бы не сделать стек еще умнее?
От: _smit Россия  
Дата: 14.11.16 20:13
Оценка:
Здравствуйте, _hum_, Вы писали:


__>так размер стека же неизвестен. как в таком случае организовать корректную работу проги?


__>п.с. попутные вопросы спецам

__>- почему все-таки с++ не предоставил возможность узнавать этот размер?
__>- есть какая-то гарантия, что все локальные статические переменные (хотя бы по одной копии) влезут в стек? (то есть, делает ли компилятор что-то вроде анализа,к акой стек нужен, чтоб вместить все эти переменные, и такой стек и выделяет)?

размещением в памяти занимается не компилятор а линкер. Это платформо- и аппаратно-зависимая процедура. Для "bare metal" программист сам определяет размер стека и кучи в линкер-скрипте и может поместить стек полностью как в кэш процессора, так и во внешнюю память. Для ознакомления можно глянуть статьи: https://www.opennet.ru/docs/RUS/gnu_ld/gnuld-3.html и https://habrahabr.ru/post/150327/
В операционной системе стек и куча управляются менеджером памяти операционной системы.
Статические переменные определяются в отдельной секции памяти и не занимают ни стек ни кучу, их время жизни равно времени жизни (работы) программы.
Re: А почему бы не сделать стек еще умнее?
От: Pavel Dvorkin Россия  
Дата: 15.11.16 06:05
Оценка:
Здравствуйте, Kingofastellarwar, Вы писали:

K>фича для компилятора:

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

https://msdn.microsoft.com/ru-ru/library/wb1s57t5.aspx
https://msdn.microsoft.com/ru-ru/library/5471dc8s.aspx

Так что выделять память в стеке вполне можно. А вот делать то автоматически — могут быть проблемы.

Если функция A установила этот режим — действует ли он на функцию B, которая вызывается из A ? Если действует — как быть в случае, если B вызывается не из A ?
Если память выделена в стеке — что будет, если, забыв об этом, передать указатель на нее в другой поток ?
И т.д.
With best regards
Pavel Dvorkin
Re[2]: А почему бы не сделать стек еще умнее?
От: _smit Россия  
Дата: 15.11.16 08:39
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>https://msdn.microsoft.com/ru-ru/library/wb1s57t5.aspx

PD>https://msdn.microsoft.com/ru-ru/library/5471dc8s.aspx

PD>Так что выделять память в стеке вполне можно. А вот делать то автоматически — могут быть проблемы.


PD>Если функция A установила этот режим — действует ли он на функцию B, которая вызывается из A ? Если действует — как быть в случае, если B вызывается не из A ?

PD>Если память выделена в стеке — что будет, если, забыв об этом, передать указатель на нее в другой поток ?
PD>И т.д.

стек -- специфичная (быстрая) область памяти, предназначенная для хранения временных переменных в локальной области видимости (в пределах фигурных скобок кода). например:

void foo()
{// выделился фрейм 1 на стеке и вначале фрейма сохранился адрес программного кода куда надо возвратиться при выходе из функции,
 // а также может добавиться код защиты стека stack_smashing_protector (http://wiki.osdev.org/Stack_Smashing_Protector)
   char str[10];
   int b;
    
   {// выделился фрейм 2 на стеке
      int k;
      int d;
   } // фрейм 2 освободился на стеке, k и d освободились (разрушились)

   // если (намеренно или по недосмотру) в str функцией memcpy больше 10 байт то можно перезаписать адрес возврата из foo(),
   // осуществив атаку на стек (передать код вирусу или уйдя в undefined behavor, а лучшем случае terminate SIGSEGV)

}// фрейм 1 освободился на стеке, str и b освободились (разрушились)


Если вы заметили, то компилятор всегда знает размер всех объектов и переменных в блоке и, соответственно, размещает их во фрейме стека (выделяет место под них). Для этих целей в стандарте С++ был введен тип std::array<>, объекты которого подобно С массиву размещается на стеке, в отличие от std::vector<>, данные которого размещаются в куче. На этом принципе строится статический анализ глубины использования стека.
Если по каким либо причинам вам не ведом размер массива на этапе компиляции, его длина вычисляется в процессе работы, но есть требование или другие веские причины разместить данные в стеке, то в код можно вставить вышеуказанную "функцию управления" стеком _malloca, взяв при этом на себя всю ответственность за последствия её использования (включая запрет на возможность статического анализ глубины использования стека). Но это тоже временные данные, живущие в пределах фигурных скобок.
Для постоянных данных существует куча и не надо использовать память не по назначению (ну разве что забавы ради или для экспериментов).
Re[3]: А почему бы не сделать стек еще умнее?
От: _smit Россия  
Дата: 15.11.16 08:50
Оценка:
Здравствуйте, _smit, Вы писали:

_>размещением в памяти занимается не компилятор а линкер. Это платформо- и аппаратно-зависимая процедура.

_>Для "bare metal" программист сам определяет размер стека и кучи в линкер-скрипте...

немного себя поправлю, в линкер-скрипте только размечается память которая будет либо для кода, либо для данных, включая флаги RW (модифицируема) или RO (для чтения только), а начало стека и начало кучи назначается (присваивается) программистом в стартовом коде для bare metal, или системной функцией запуска приложения в ОС.
Re: А почему бы не сделать стек еще умнее?
От: VTT http://vtt.to
Дата: 15.11.16 09:33
Оценка:
Здравствуйте, Kingofastellarwar, Вы писали:

K>фича для компилятора:

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

Эта фича называется Avoiding/fusing allocations и входит как необязательная часть стандарта C++14.

An implementation is allowed to omit a call to a replaceable global allocation function (18.6.1.1, 18.6.1.2). When it does so, the storage is instead provided by the implementation...


А вообще для переопределения механизма динамического выделения памяти в С++ существует концепция аллокаторов.
И уже есть готовые реализации стековых аллокаторов, если не хочется надеяться на компилятор или он не поддерживает эту фичу.

В С динамическое выделение памяти на стеке реализовали в виде VLA.
Говорить дальше не было нужды. Как и все космонавты, капитан Нортон не испытывал особого доверия к явлениям, внешне слишком заманчивым.
Re[3]: А почему бы не сделать стек еще умнее?
От: Pavel Dvorkin Россия  
Дата: 15.11.16 11:49
Оценка: 1 (1) +1
Здравствуйте, _smit, Вы писали:

Почти все верно


_>
_>void foo()
_>{// выделился фрейм 1 на стеке и вначале фрейма сохранился адрес программного кода куда надо возвратиться при выходе из функции,
_>   {// выделился фрейм 2 на стеке
_>      int k;
_>      int d;
_>   } // фрейм 2 освободился на стеке, k и d освободились (разрушились)

_>}// фрейм 1 освободился на стеке, str и b освободились (разрушились)
_>


В действительности по крайней мере VC++ так не делает. Память для всех локальных переменных отводится при входе в функцию (думаю, на максимальный суммарный объем, хотя точно не знаю, не проверял) , хотя переменные, конечно, "логически"перестают существовать при выходе на свою "}". Однако память при этом не освобождается.

"Идейно" было бы правильно сделать, как отметили Вы, но в реальности делается иначе.

void f() {
    int a[100];
    for (int i = 0; i < 100; i++)
        a[i] = i;
    int x = 10;
    if (x == 10) {
        int b[100];
        for (int i = 0; i < 100; i++)
            b[i] = i;
    }
}


void f() {
00EE3C10  push        ebp  
00EE3C11  mov         ebp,esp  
00EE3C13  sub         esp,414h  // выделение памяти на все локальные переменные
00EE3C19  push        ebx  
00EE3C1A  push        esi  
00EE3C1B  push        edi  
00EE3C1C  lea         edi,[ebp-414h]  
00EE3C22  mov         ecx,105h  
00EE3C27  mov         eax,0CCCCCCCCh  
00EE3C2C  rep stos    dword ptr es:[edi]  
    int a[100];
    for (int i = 0; i < 100; i++)
00EE3C2E  mov         dword ptr [ebp-1A0h],0  
00EE3C38  jmp         f+39h (0EE3C49h)  
00EE3C3A  mov         eax,dword ptr [ebp-1A0h]  
00EE3C40  add         eax,1  
00EE3C43  mov         dword ptr [ebp-1A0h],eax  
00EE3C49  cmp         dword ptr [ebp-1A0h],64h  
00EE3C50  jge         f+57h (0EE3C67h)  
        a[i] = i;
00EE3C52  mov         eax,dword ptr [ebp-1A0h]  
00EE3C58  mov         ecx,dword ptr [ebp-1A0h]  
00EE3C5E  mov         dword ptr a[eax*4],ecx  
00EE3C65  jmp         f+2Ah (0EE3C3Ah)  
    int x = 10;
00EE3C67  mov         dword ptr [x],0Ah  
    if (x == 10) {
00EE3C71  cmp         dword ptr [x],0Ah  
00EE3C78  jne         f+0A3h (0EE3CB3h)  
        int b[100]; // а здесь ничего не выделяется
        for (int i = 0; i < 100; i++)
00EE3C7A  mov         dword ptr [ebp-350h],0  
00EE3C84  jmp         f+85h (0EE3C95h)  
00EE3C86  mov         eax,dword ptr [ebp-350h]  
00EE3C8C  add         eax,1  
00EE3C8F  mov         dword ptr [ebp-350h],eax  
00EE3C95  cmp         dword ptr [ebp-350h],64h  
00EE3C9C  jge         f+0A3h (0EE3CB3h)  
            b[i] = i;
00EE3C9E  mov         eax,dword ptr [ebp-350h]  
00EE3CA4  mov         ecx,dword ptr [ebp-350h]  
00EE3CAA  mov         dword ptr [ebp+eax*4-344h],ecx  
00EE3CB1  jmp         f+76h (0EE3C86h)  
    }
}
00EE3CB3  push        edx  
00EE3CB4  mov         ecx,ebp  
00EE3CB6  push        eax  
00EE3CB7  lea         edx,ds:[0EE3CCCh]  
00EE3CBD  call        @_RTC_CheckStackVars@8 (0EE108Ch)  
00EE3CC2  pop         eax  
00EE3CC3  pop         edx  
00EE3CC4  pop         edi  
00EE3CC5  pop         esi  
00EE3CC6  pop         ebx  
00EE3CC7  mov         esp,ebp  // а вот здесь освобождение - esp восстанавливается на значение до входа в функцию
00EE3CC9  pop         ebp  
00EE3CCA  ret


В остальном вполне согласен.
With best regards
Pavel Dvorkin
Отредактировано 15.11.2016 11:52 Pavel Dvorkin . Предыдущая версия . Еще …
Отредактировано 15.11.2016 11:50 Pavel Dvorkin . Предыдущая версия .
Re[4]: А почему бы не сделать стек еще умнее?
От: _smit Россия  
Дата: 15.11.16 12:14
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, _smit, Вы писали:


PD>Почти все верно

...
PD>В действительности по крайней мере VC++ так не делает. Память для всех локальных переменных отводится при входе в функцию (думаю, на максимальный суммарный объем, хотя точно не знаю, не проверял) , хотя переменные, конечно, "логически"перестают существовать при выходе на свою "}". Однако память при этом не освобождается.

Да, всё верно, с блоками слегка погорячился, это всё же накладная операция, действует в рамках вызова функций. Gcc поступает также, т.н. "Calling Convention".
Re[5]: А почему бы не сделать стек еще умнее?
От: Pavel Dvorkin Россия  
Дата: 15.11.16 12:30
Оценка: +2
Здравствуйте, _smit, Вы писали:


_>Да, всё верно, с блоками слегка погорячился, это всё же накладная операция, действует в рамках вызова функций. Gcc поступает также, т.н. "Calling Convention".


Calling convention — это другое. Это правила передачи параметров функции (слева направо(сейчас нет уже, было в Win16) или справа налево, через стек и/или регистры, кто очищает стек при выходе (вызывающая или вызываемая). К отведению места в стеке под локальные переменные функции это отношения не имеет.

Ну и проблема не в том, что это накладная операция. Сейчас все локальные переменные — это просто смещения от ebp. Там таких ebp-const разбросано немало. Если же выделять память при каждом входе в блок, то одним ebp не обойдешься, придется целый менеджер памяти заводить, который будет определять адреса переменных на i-ом уровне вложенности фигурных скобок с учетом того, что было на всех предыдущих i-1 уровнях.
With best regards
Pavel Dvorkin
Отредактировано 15.11.2016 12:36 Pavel Dvorkin . Предыдущая версия .
Re[5]: кстати
От: Pavel Dvorkin Россия  
Дата: 15.11.16 12:47
Оценка:
Здравствуйте, _smit, Вы писали:

Забавное следствие. Вот такой жуткий код

void f() {
    int x = 10;
    int * p = NULL;
    if (x == 10) {
        int b[100];
        for (int i = 0; i < 100; i++)
            b[i] = i;
        p = b;
    } // 1
      // 2
    for (int i = 0; i < 100; i++) 
        printf("%d\n", p[i]);
}


тем не менее работать будет, правда, до тех пор, пока между //1 и // 2 не будет вставлен иной код, в котором отводится память.

Упаси бог кого-нибудь от мысли, что я советую так писать
With best regards
Pavel Dvorkin
Re[6]: кстати
От: uzhas Ниоткуда  
Дата: 15.11.16 12:58
Оценка: +2
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, _smit, Вы писали:


PD>Забавное следствие.


еще такое наблюдение: http://ideone.com/E7vANn
то есть компилятор может реюзать стековую память для других переменных, если время жизни предыдущих закончилось
Re[7]: кстати
От: Pavel Dvorkin Россия  
Дата: 15.11.16 13:17
Оценка: -1
Здравствуйте, uzhas, Вы писали:

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


Думаю, что не может, а обязан. Иначе объем памяти может возрасти в N раз без всякого смысла.

Алгоритм тут ИМХО должен быть примерно следующий.

Пусть входим в блок уровня вложенности N, тогда нам уже известен суммарный объем переменных S в блоках уровня 0, 1... N-1 для этого блока. Вот от него и размещаем эти переменные блока уровня N. При выходе из блока уровня N считаем эту память свободной и, если будет еще один блок уровня N, размещаем опять, начиная с S. Суммарный объем для блока уровня 0 равен 0 (точнее, сумме размеров тех переменных, которые компилятор завел по своей инициативе)
With best regards
Pavel Dvorkin
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.