Стек и куча (память)?

Question

[avion]

Почему, относительно кучи, стек на столько мал 1 - 8 мб в среднем? Стек работает быстрее, почему бы не выделить для него больше памяти?

Comments

[Данил Тунев]

Тут надо смотреть компилятор, почему куча настолько велика?) Юзай Си, выноси "кучи|стеки" в глобальный массив, и да, при программировании на ассемблере, даже под Linux, можно обходиться без стеков и кучь) Сейчас уже 2020!

Answer 1

[jcmvbkbc]

почему бы не выделить для него больше памяти?

Действительно, почему бы и нет, учитывая, что эта настройка в руках программиста собирающего (на венде, см. cl /F) или запускающего (в *nix, см. ulimit -s) программу?

Стек работает быстрее

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

Answer 2

[Griboks]

Вы можете выделить столько память, сколько требуется, однако следует учитывать, что:
1. чем больше стек, тем он медленнее
2. 99% программ не используют даже маленький стек полностью
3. хранить большие переменные на стеке неэффективно

Comments

[Максим Мосейчук]

> чем больше стек, тем он медленнее
Это как?

[Griboks]

Максим Мосейчук, чем больше стек, тем больше выполняется операций по работе с ним => тратится больше тактов процессора на несвязанные с программой действия => коэффициент утилизации падает.

[Максим Мосейчук]

Griboks, выделение и освобождение памяти в стеке это изменение одного регистра, один такт.

Это на порядки быстрее кучи.

[Griboks]

Максим Мосейчук,

чем больше стек, тем он медленнее

Это на порядки быстрее кучи.

Хмм... Могу только сказать, это на порядки медленнее машинного кода.

[Максим Мосейчук]

Griboks, у вас какая-то бессвязная речь.

Причем тут машинный код?
Увеличение значения регистра это и есть машинный код.

Куда уж быстрее, чем один такт? Полтакта? Компьютеры так не работают.

[Griboks]

Максим Мосейчук, это у вас какая-то бессвязная речь. Я про стек - вы про кучу. Причём тут куча? Зачем вы это написали?

Куда уж быстрее, чем один такт?

Любой более высокий уровень даёт оверхед, в том числе и для работы со стеком. Даже программа на ассемблере работает медленнее аналога на машинном коде.

Полтакта? Компьютеры так не работают

А ещё существуют микропрограммы. Они работают быстрее машинного когда и как раз умеют в дробные такты.

[Максим Мосейчук]

> Даже программа на ассемблере работает медленнее аналога на машинном коде

Что простите? Ассемблер это просто человекочитаемый машинный код.

Каждая строчка на ассемблере однозначно кодируется машинной командой с точностью до смещений.

Вы так и не объяснили, почему большой стек медленнее маленького?

Различие между ними лишь в значении регистра.

[Максим Мосейчук]

@Griboks

> Они работают быстрее машинного когда и как раз умеют в дробные такты.

Какие ваши доказательства?
Один такт это одно переключение транзистора.

Как можно сделать какую-то работу, не переключив ничего?

[Griboks]

Максим Мосейчук,

Что простите? Ассемблер это просто человекочитаемый машинный код.

Ассе́мблер (от англ. assembler — сборщик) — транслятор исходного текста программы, написанной на языке ассемблера, в программу на машинном языке.
Также результатом ассемблирования может быть не исполняемый, а объектный модуль... в дальнейшем с помощью редактора связей может быть получен исполнимый файл.

Каждая строчка на ассемблере однозначно кодируется машинной командой с точностью до смещений.

Например, команда call вызывает процедуру, и транслируется в несколько инструкций (операций). Даже если подобные инструкции однозначны, они дают оверхед.

Вы так и не объяснили, почему большой стек медленнее маленького?

Не просто большой стек, а большой высоко утилизированный много фрагментированный (короче обычный) стек. Аналогично жёсткому диску, фрагментация замедляет работу.

Какие ваши доказательства?
Один такт это одно переключение транзистора.
Как можно сделать какую-то работу, не переключив ничего?

Микроко́д — программа, реализующая набор инструкций процессора. Так же как одна инструкция языка высокого уровня преобразуется в серию машинных инструкций, в процессоре, использующем микрокод, каждая машинная инструкция реализуется в виде серии микроинструкций — микропрограммы, микрокода.

[Максим Мосейчук]

Griboks

Я знаю что такое микрокод.
Вы привидите пример CISC команды исполняемой за один такт, которая транслируется в более чем одну команду RISC.

[Максим Мосейчук]

Griboks,

Например, команда call вызывает процедуру, и транслируется в несколько инструкций (операций). Даже если подобные инструкции однозначны, они дают оверхед.

Ну давайте разбираться в сколько инструкций транслируется CALL.
https://godbolt.org/z/JLG3VH

Опа, одна инструкция `e8 rel32`, корректное смещение будет подставлено на этапе линковки.
Лезем в мануал интела
https://www.intel.com/content/dam/www/public/us/en...

Раздел 3-122 CALL—Call Procedure

И смотрим, что вариантов CALL несколько. Могут быть вызовы процедуры по аболютному адресу как far, так и near. У нас тут вариант вызова по смещению.
Но ни один из вариантов не транслируется в 2 команды или более.

О каком оверхеде вы говорите?

Не просто большой стек, а большой высоко утилизированный много фрагментированный (короче обычный) стек. Аналогично жёсткому диску, фрагментация замедляет работу.

Вы о каком стеке говорите то? Аппаратный стек в x86, arm и куче других архитектур не может быть фрагментирован никак. Вы не можете выделить или освободить память в нем в середине. Только сверху.
Что бы освободить память где-то в середине, то вам придется выйти из всей цепочки функций вплоть до той стекфрейм которой вы хотите освободить.

чем больше стек, тем больше выполняется операций по работе с ним => тратится больше тактов процессора на несвязанные с программой действия => коэффициент утилизации падает.

Все еще не понятно. Текущий размер стека определяется значением в регистре ESP (для x86). И все. Больше ничем. Изменить значение в этом регистре можно обычным mov за один такт изменить. Как это влияет на производительность?

Микроко́д — программа, реализующая набор инструкций процессора.

Микрокод преобразует одну сложную CISC команду в набор RISC.
Но ни одна RISC команда не может быть обработана меньше чем за такт. Это ограничение схемотехники процессоров. Если команда имеет результат какой-то (а иначе она бесмыссленна), то она должна поменять что-то в процессоре. Значение какого-то регистра например. А сделать это можно лишь при очередном сигнале от тактового генератора. Даже ничего не делающий NOP имеет результат - изменение значения в регистре RIP. И он не может быть исполнен быстрее чем за один такт.

хранить большие переменные на стеке неэффективно

Тут есть доля истинны. Большие переменные на самом деле хранить на стеке очень эффективно, пока они влязят в стек. Просто структуры переменного размера (например списки) на стеке хранить невозможно приципиально, т.к. нельзя "довыделить" память в середине стека.
Можно конечно попробовать размотать его, поменять адреса возврата. Но это будет жутко неоптимально и сложно. К тому же абсолютные адреса будут поломаны.

[Griboks]

Максим Мосейчук,

О каком оверхеде вы говорите?

Процессор выполняет следующие действия при вызове подпрограммы:
1. сохранить текущую позицию управления
2. передать управление подпрограмме

Затем выполняется какой-то код. Далее следует "return":
1. загрузить предыдущую позицию управления
2. передать управление этой позиции
3.* Почистить локальные переменные (не всегда)
4.* Вернуть какое либо значение (не всегда)

Получается, что оверхед по командам составляет минимум 2х, а по времени - минимум 4х.

Вы о каком стеке говорите то?

Стек - это ограниченная по длине последовательность ячеек памяти заданной размерности. Для стека определены две операции:
1. Добавить ячейку в начало последовательности
2. Удалить первую ячейку последовательности и получить её значение

Пусть наша подпрограмма использует стек длины L. Допустим, что мы обновили программу и начали использовать стек длины 5L. Тогда получаем, что на придётся выполнить минимум в 5 раз больше операции на стеке, следовательно, в 5 раз больше времени на это потратить. Предположим, что реально из-за ветвлений программы используется лишь 1/5 стека. Тогда оверхед составит 4L.

Рассмотрим большую переменную, которая занимает N ячеек памяти стека. Тогда все операции с переменной занимаю тоже в N раз больше времени.

Я знаю что такое микрокод.

Это хорошо. Значит вы знаете, что некоторые команды в действительности являются микропрограммами. Но с точки зрения универсальной архитектуры - это атомарные операции. Поэтому с этой точки зрения микрокод выполняется за дробное количество операций.

Куда уж быстрее, чем один такт? Полтакта? Компьютеры так не работают.

Стек - это... ну я уже выше написал. Он никак не привязан к тактам, регистрам или чему-то ещё. Это абстракция. Куча - это тоже абстракция. Кстати, регистры - это тоже своего рода физическая абстракция, т.к. для процессора регистры являются такой же памятью, как и l1,l2,l3,ram,ПЗУ.

[Максим Мосейчук]

Griboks,

Получается, что оверхед по командам составляет минимум 2х, а по времени - минимум 4х.

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

Что бы достать значение из стека не обязательно доставать элементы по очереди. Достаточно по абсолютному адресу обратиться. Никакого оверхеда.

Поэтому с этой точки зрения микрокод выполняется за дробное количество операций.

Вы не правы. Процессор это дискретное устройство, он не может изменить заряд на затворе транзистора без помощи тактового генератора.
Ни одна команда или микрокоманда не может быть исполнена менее чем за 1 такт.
Если я не прав, то вам не составит труда найти это в любом мануале.

Он никак не привязан к тактам

Операции привязаны.

Кстати, регистры - это тоже своего рода физическая абстракция, т.к. для процессора регистры являются такой же памятью, как и l1,l2,l3,ram,ПЗУ

Раз это такая же память, то как получить адрес регистра?

[Griboks]

Максим Мосейчук,

Т.е. когда вы будете в куче выделять память, то оверхеда не будет?

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

Что бы достать значение из стека не обязательно доставать элементы по очереди.

Обязательно. В противном случае, эта абстракция называлась бы по-другому.

Ни одна команда или микрокоманда не может быть исполнена менее чем за 1 такт.

Если вы говорите про такты как про электрические импульсы, а не шаги выполнения машинного кода, тогда всё ещё проще. Одна команда выполняется за несколько тактов, состоит из нескольких микрокоманд, которые выполняются за 1 такт.

Раз это такая же память, то как получить адрес регистра?

Адреса регистров заранее известны. Получить их можно из спецификации. Процессору нет дела до вида памяти, это просто каскад электросхем, у которого есть входы и выходы. Какой выход подключён, туда и записывается результат (грубо говоря).

[Максим Мосейчук]

Т.е. если бы вы писали на машинном коде, у вас бы программа работала бы быстрее, чем на ассемблере.

Я могу написать "CALL 0xffffffff" а потом транслировать в машинный код. Могу сразу "e8 ff ff ff' а потом записать в бинарном виде. В чем разница? Может вы говорите про микрокод именно, а не машинный код?

Одна команда выполняется за несколько тактов, состоит из нескольких микрокоманд, которые выполняются за 1 такт.

Наконец-то. Да, именно об этом я и говорю.

Обязательно. В противном случае, эта абстракция называлась бы по-другому.

https://godbolt.org/z/ZFKFd4
Доступ к переменной 'a' расположенной в глубине стека по указателю (адресу) без раскрутки самого стека. Ничем не отличается от доступа к любой другой переменной по адресу `addl $0x1,(%rdi)`
Или вот с рекурсией https://godbolt.org/z/NzqfTG. Глубина рекурсии 1000, но переменная 'a' все так же доступна по прямому адресу.
Число операций для доступа к 'a' в обоих случаях одинакого.

Адреса регистров заранее известны

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

[Griboks]

Максим Мосейчук,

В чем разница?

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

Число операций для доступа к 'a' в обоих случаях одинакого.

struct stack
{
    char *data;
    struct stack *next;
};

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

Вы спрашиваете про адрес. Затем вы говорите про физический носитель. Так адрес или носитель? Вы уж определитесь.

[Максим Мосейчук]

Griboks,

struct stack
{
char *data;
struct stack *next;
};

Это структура данных под названием стек. Это не тоже самое что и аппаратный стек в процессоре.

Мы с вами говорим об совсем разных сущностях.

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

Можно какой-нибудь пример простенький?
Я вас не понимаю. Дело в том, что ассемблер и машинный код это одно и тоже записанное разными символами. Множесто строк ассемблера и множество байт машинных кодов изоморфны. Между ними есть биекция.

[Griboks]

Максим Мосейчук,

выделение и освобождение памяти в стеке это изменение одного регистра, один такт.

Мы с вами говорим об совсем разных сущностях.

Да неужели?

Между ними есть биекция.

Макроассемблер (от греч. μάκρος — большой, обширный) — макропроцессор, базовым языком которого является язык ассемблера.
Возможно, конкретно в вашем ассемблере на вашем компьютере с конкретно вашей архитектурой есть биекция. Но не у всех всё так просто. А когда дело доходит до виртуальных машин, всё становится ещё сложнее.

[Максим Мосейчук]

Griboks,

Да неужели?

Да. Нет никаких структур в аппаратном стеке. Есть 2 регистра ESP и EBP (говорю про x86) и линейная область памяти зарезервированная под стек. Все, этими двумя регистрами и происходит все управление стеком. Нет никаких структур, которые ссылаются куда-то.
Уменьшили значение в ESP - зарезервировали память для своих нужд. Увеличили - освободили память. (тут не ошибка, стек растет снизу вверх). Стек еще называют памятью с автоматическим управлением

То о чем вы говорите с примером со структурой это просто структура данных стек. Она не относится к аппаратной части процесора. И по большей части распологается она в куче.

https://rsdn.org/article/cpp/ObjectsAndPointers.xm...

Макроассемблер

Речь не идет о макроассемблере. Макросы просто позволяют не вычислять руками некотоые данные (например использовать метки вместо смещений). Но никто не запрещает вместо метки использовать непосредственно смещение или адрес, но его придется вычислить руками.

А когда дело доходит до виртуальных машин, всё становится ещё сложнее.

Причем тут они? О них речь не шла.

[Griboks]

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

Речь не идет о макроассемблере.

Именно, речь идет об оверхеде. Он есть в ассемблере. Точнее: утверждение, что любой ассемблер для любого процессора любой архитектуры даёт биекцию между командами и опкодами, неверно. Это утверждение опровергается контрпримером. В качестве контрпримера можно использовать виртуальную машину.

[Максим Мосейчук]

Griboks,

Почему вы продолжаете мне рассказывать про строение аппаратного стека?

Потому что в этом заключался вопрос на который вы ответили. Речь шла о куче и аппаратном стеке. Но вы зачем-то приплели в своем ответе программный стек.

[Griboks]

Максим Мосейчук, Не уверен, что речь шла об аппаратном стеке. В тегах указано именно программирование, а решением отмечен текст про программный стек.

[Максим Мосейчук]

Griboks, не понимаю как виртуальная машина это опровергает и какое отношение к ассемблеру вообще имеет.

Возьмём jvm например. class-файл не является машинным кодом для платформы. Это байт-код для виртуальной машины. Он в любом случае будет либо скомпилирован в машинный код платформы либо интерпретирован на ней же с помощью инструкций процессора.

class- файл можно однозначно дизессамблировать в S-выражения и потом обратно. Например https://github.com/minad/chasm

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

[Максим Мосейчук]

Griboks, вы про ответ jcmvbkbc?

ulimit -s изменяет размер аппаратного стека для процесса

[Griboks]

Максим Мосейчук, всё-равно не уверен. Если это правда, то мой ответ не подходит к этому вопросу.

[Максим Мосейчук]

Griboks, https://www.remoteshaman.com/unix/common/about-sta...

Answer 3

[carakan]

Нужно понимать почему стек эффективен. Это не от того, что там как-то по особенному выделили память, а потому, как его по особому используют.
Там лежать только относительно маленькие локальные переменные. Работаешь ты только с верхушкой стека. Поэтому вся она хранится в кеш памяти. Если кеш специально раздувать (например делать вместо динамических массивов в куче массив на стеке с запасом), он утратит свою эффективность.
Так как переменные в стеке лёжат подряд, мы не может там реализовать new. А без динамических массивов особо много памяти и не нужно. Выделенного по умолчанию значения обысно хватает на все случаи жизни. Увеличивать стоит только если действительно не хватает. Но это может случиться только, например, при работе с глубокими графами.