that's not the popular approach these days. Java's JVM and Microsoft's CLR use the hardware stack and contiguous memory.
там же:
«It is just an accident of history that we happened to decide for a few decades that languages with activation frames that are created and destroyed in a strictly ordered manner were fashionable.
Since modern languages increasingly lack this property, expect to see more and more languages that reify continuations onto the garbage-collected heap, rather than the stack.»
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Аппаратный стек тогда бы содержал только один указатель на фрейм и адрес возврата. ЭФ>Либо даже адрес возврата был бы тоже во фрейме, например первым.
ЭФ>Да, это дополнительная косвенность, но кого это вообще волнует в наши времена быстрых процессоров?
Не только дополнительная косвенность, есть еще временные затраты на выделение/освобождение памяти. В стеке для этого достаточно регистр поменять, а в куче надо свободный регион найти или вернуть. Если несколько потоков с общей кучей, то надо еще синхронизацию потоков при этом обеспечить.
C> регистр поменять, а в куче надо свободный регион найти или вернуть.
В куче со сборкой мусора это тоже одну переменную увеличить — верхушку кучи.
C> Если несколько потоков с общей кучей, то надо еще синхронизацию потоков при этом обеспечить.
Сделать несколько куч, и в своей куче собирать мусор своим потоком?
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>В куче со сборкой мусора это тоже одну переменную увеличить — верхушку кучи.
Да, но для освобождения памяти придется периодически сборку мусора запускать, одной переменной не отделаться.
ЭФ>Сделать несколько куч, и в своей куче собирать мусор своим потоком?
Где-то же нужно хранить данные общие для нескольких потоков. Где?
C> Где-то же нужно хранить данные общие для нескольких потоков. Где?
В отдельном процессе и коммуницировать с ним через gRPC,
так рекомендует делать Microsoft, которые закопали Remoting с его Shared Memory каналами.
Они точно знают как надо, потому что провалили исследовательский проект Singularity.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Аппаратный стек тогда бы содержал только один указатель на фрейм и адрес возврата. ЭФ>Либо даже адрес возврата был бы тоже во фрейме, например первым.
Здравствуйте, Эйнсток Файр, Вы писали:
C>> регистр поменять, а в куче надо свободный регион найти или вернуть. ЭФ>В куче со сборкой мусора это тоже одну переменную увеличить — верхушку кучи.
С чего бы это?
Re[2]: Почему жаба фреймы стека не выделяет в куче?
Здравствуйте, удусекшл, Вы писали:
CC>>Ты бы хоть уточнил в самом начале что ты конкретно про жабу спрашиваешь. У>А тормоза такой подход даст в любом языке, поэтому смысл — уточнять?
А ничего что для того, чтобы выделить место в куче надо заюзать стек, переменным для которого надо выделить место в куче, для чего надо заюзать стек...
Когда стек у тебя не машинный а всем этим рулит сторонний рантайм — тогда можно уже изгаляться.
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Re[4]: Почему жаба фреймы стека не выделяет в куче?
Здравствуйте, CreatorCray, Вы писали:
CC>>>Ты бы хоть уточнил в самом начале что ты конкретно про жабу спрашиваешь. У>>А тормоза такой подход даст в любом языке, поэтому смысл — уточнять?
CC>А ничего что для того, чтобы выделить место в куче надо заюзать стек, переменным для которого надо выделить место в куче, для чего надо заюзать стек...
Зачем стек? Регистры. Единственная проблема, может быть — это как передать требуемый размер стека в условную функцию alloc_stack — но тут можно соглашение о вызовах сделать таким, что несколько первых параметров передаются через регистры
CC>Когда стек у тебя не машинный а всем этим рулит сторонний рантайм — тогда можно уже изгаляться.
Когда машинный — тоже. Указатель стека кладем в регистр, по которому можно косвенно адресоваться, и все стековые переменные — просто индексы относительно него
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Аппаратный стек тогда бы содержал только один указатель на фрейм и адрес возврата. ЭФ>Либо даже адрес возврата был бы тоже во фрейме, например первым.
Сами понятия "куча", "стек" — не более чем условность. Всё это — память процесса (давайте не будем касаться экзотических архитектур, где стек вообще отдельный тип памяти, адресуется по своей щине и не зависит от процессов). Это просто разные кучки байтов, для которых мы определяем правила использования. Иногда сюда могут добавиться аппаратные мульки типа Prevent on-stack execution (запрещает интерпретировать содержимое стека как исполняемый код) но сути это не меняет.
ЭФ>А раньше, говорят, выделяли: ЭФ>https://softwareengineering.stackexchange.com/questions/113019/why-does-garbage-collection-only-sweep-the-heap ЭФ>
that's not the popular approach these days. Java's JVM and Microsoft's CLR use the hardware stack and contiguous memory.
Если мы вернёмся во времена x86 сегментной модели, то стек выделялся в сегменте SS, и все смещения шли относительно этого базового адреса (если не ошибаюсь, в обратную сторону). Теоретически, можно было установить SS на тот же участок памяти, что и сегмент данных DS, и наслаждаться сайд-эффектами
А уж XZ Spectrum (Z80 CPU, улучшенный Intel 8080) вообще разрешал использовать для стека тот же участок памяти, что использовался видеоадаптером для отрисовки экрана. Просто устанавливали одинаковые атрибуты background/foreground для визуальной маскировки (а иногда даже этим не заморачивались).
Здравствуйте, Эйнсток Файр, Вы писали: ЭФ>Аппаратный стек тогда бы содержал только один указатель на фрейм и адрес возврата.
И сразу же вопрос. А что будет храниться в этом фрейме? Например, в Java фрейм состоит из трех частей: локальные переменные, адрес возврата и стек вычислений. Я последнее объясню на всякий случай. JVM (байткод) — это код для стековой машины. Все операции работают со стеком. Например, iadd снимает два целых (32-битных) числа со стека и кладет их сумму. Или aload_1 считывает значение первой локальной переменной и сохраняет его на вершине стека. Вот этот "стек вычислений" является частью кадра стека вызовов.
Вопрос достаточно важный для создания замыканий. Если мы храним "все", после выхода из метода в куче остается куча неиспользуемого пространства. В замыканиях могут использоваться локальные переменные но не "локальный" стек вычислений. А если мы храним не все, нужно создавать уже не один, а два разных объекта.
Но это все лирика. Суровая реальность состоит в том, что в Java вообще нет замыканий в традиционном понимании ("изменяемые переменные"). Методы из локальных классов, определенных внутри методов, могут ссылаться только на локальные константы (условно — неизменяемые переменные) этих методов. Java просто добавляет синтетические поля во вложенные классы для хранения значений. Компиляторы языков с поддержкой замыканий (Scala, например), реализуют их через явное создание объектов для фрейма.
ЭФ>Либо даже адрес возврата был бы тоже во фрейме, например первым.
Это не очень полезно для замыкания (мусор после завершения метода, когда замыкание может еще быть достижимо). Плюс усложняет сборку мусора. Появляется новый концепт — "адрес возврата", который должен уметь обрабатывать сборщик мусора. Ну или грязная магия с маскированием всего этого под какой-нибудь int или long. Это в целом можно было бы решить. Но есть следующая проблема.
ЭФ>Зато все значения переменных хранились бы в памяти, и к ним можно было бы осуществлять одинаковый доступ (например при сборке мусора).
Вот с одинаковый доступ вы очень сильно погорячились . Сборщику мусора для работы нужно знать структуру объекта, с которым он работает. Например, он должен отличать обычный int (с которым ничего не надо делать) и ссылку на объект (по которой нужно идти дальше). С обычными объектами этоне проблема. Есть ссылка на дескриптор класса, откуда можно всю нужную информацию извлечь. А вот с фреймами не так. Его структура зависит от "адреса возврата" (точнее, от instruction pointer в рамках того метода). Пример в рамках стека вычислений:
ldc 42 // pushes int 42 on stack
ldc 53 // pushes int 53 on stack
// Stack map: [int, int]
iadd // pops, sums, pushes 95
new java.lang.Object() // Creates an instance of object
// Stack map: [int, uninitialized java.lang.Object()]
В один момент у нас хранится два инта. Через пару инструкций — число и ссылка (еще и с невызыванными инициализаторам, но в рамках данной дискуссии это не важно). Примерно та же история с локальными переменными. Да, одна и та же ячейка может переиспользоваться под различные типы! Так что вместо "простого дескриптора объекта" в сборщике мусора придется писать сложный парсер и поддержку этих фреймов. Или "динамически менять" опиастели фрейма на каждый вызов метода. Со специализированным стеком как раз проще. Cначала выполняется специализированный проход по стеку для определения "живых" объектов. Код смотрит на дескрипторы/фреймы, определяет объекты и помечает для следующей фазы. На следующей фазе начинается обход графа объектов. В момент этого обхода все структуры уже описываются вполне регулярными дескрипторами классов.
ЭФ>Since modern languages increasingly lack this property, expect to see more and more languages that reify continuations onto the garbage-collected heap, rather than the stack.»
Ну вообще да. В языках с замыканиями (continuations) гораздо больше шансов, что все будет выделяться в куче. И какие-нибудь интерпретаторы наподобие JS могут это сходу делать (насколько я знаю — не делают). Все зависит от внутренней реализации. Вот cpython вроде бы тоже использует стековый калькулятор во внутреннем представлении (похоже на механику Java). В замыкании стек вычислений не нужен и приводит к куче проблем. Поэтому удобно и полезно иметь отдельный "стек вычислений" (где могут быть адреса возврата и промежуточные результаты вычислений). А раз такой стек есть, на нем становится удобно хранить и локальные переменные, которые не нужны для замыкания.
Потому что куча имеет свойство фрагментироваться и имеет нетривиальное время выделения/освобождения. А стек это делает за константное время, не подвержен фрагментации, да и еще и статическому анализу поддается на ура. Это просто подарок какой-то а не структура данных.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Аппаратный стек тогда бы содержал только один указатель на фрейм и адрес возврата. ЭФ>Либо даже адрес возврата был бы тоже во фрейме, например первым.
ЭФ>Да, это дополнительная косвенность, но кого это вообще волнует в наши времена быстрых процессоров? ЭФ>https://stackoverflow.com/questions/26741925/is-frame-in-jvm-heap-allocated-or-stack-allocated
Более-менее всех.
Смотрите, стек можно организовывать одним из трёх способов:
1. Полностью непрерывная область памяти, положить/снять со стека эквивалентно икременту/декременту stack pointer-а.
2. Связный список фреймов: каждый фрейм выделяется в куче, ссылается на предыдущий фрейм.
3. Комбинация подходов: связный список сегментов.
Второй способ применяется только в нишевых скриптовых движках, где быстродействие стоит на последнем месте.
Потому, что каждый вызов — это выделение в куче. Даже если мы в цикле вызываем один и тот же метод. Такой подход выжирает кучу космическими темпами, и провоцирует невероятно частую сборку мусора.
Ну, и собственно стоимость вызова резко увеличивается из-за подготовки фрейма — его же надо не просто выделить, но и проинициализировать указатель на предыдущий фрейм.
Плюс к этому размывается локальность кэша — на каждой итерации мы лезем к новым адресам за параметрами и переменными.
третий способ применялся на разных этапах развития многих языков, в частности Go и Rust. Практика показала, что никаких преимуществ этот подход не даёт, зато регулярно стреляет в пересечение границы сегмента кодом в плотном цикле. Это приводит к резкой просадке производительности на ровном месте.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Эйнсток Файр, Вы писали:
S>> Даже если мы в цикле вызываем один и тот же метод.
ЭФ>Мне же предлагали про циклы подумать. Где циклы, там муть (mut). Значит и место для всех вызовов подпрограмм можно заранее рассчитать и выделить.
Ок, давайте разовьём вашу мысль.
1. "Заранее рассчитать и выделить" — то есть вы предполагаете, что мы выделяем не один фрейм, а сразу блок (сегмент). Это один из подвариантов варианта 3. С его недостатками — в частности, сама функция не может знать, вызывают ли её в цикле, т.е. не выделен ли ей заранее целый сегмент. Значит, её пролог будет довольно сложно устроен — надо сравнить её потребности в стеке с остатком места в текущем сегменте стека, и в зависимости от этого либо просто инкрементировать стек-поинтер, либо выделять в куче новый сегмент. При этом опять же, при выходе из этой функции выделенный ею сегмент будет гарантированно больше не нужен, то есть мы должны его как-то "освободить", и на следующей итерации придётся заново выделять ещё один такой же сегмент.
2. Давайте теперь поговорим про саму возможность рассчитать заранее вызовы всех подпрограмм.
Рассмотрим простейший код, который подсчитывает количество листьев у дерева:
public int Count<T>(this T root) where T:IEnumerable<T>
{
int c = 0;
foreach(var child in root) // вот он цикл
c += // вот она муть
Count(child); // вот он вызов подпрограммыreturn c;
}
сколько места вы заложите на "все вызовы подпрограмм"?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S> сколько места вы заложите на "все вызовы подпрограмм"?
Результат(А) Функция НекаяФункция(КопируемыеПараметры(Б), ПараметрыПоСсылкамИУказателям (Б2) )
Начало(Т1)
Локальные переменные, под которые не нужно место
Циклы
Мутабельные переменные циклов, под которые место потребуется(В)
Циклы более вложенные
Мутабельные переменные вложенных циклов, под которые место потребуется(Г)
Вызовы других функций (Д,Т2)
Конец вложенного цикла
Конец цикла
Финальное вычисление и возвращение результата
Конец функции
До выполнения точки Т1 мы должны выделить
А+Б+В+Г+Д(количество вызовов других функций)*размер указателя на блок для функции
единиц памяти.
Там же мы должны создать сразу блоки под каждую из других функций.
А в точке T2 должны проделать то же самое для функций, вызываемых из других функций (вызываемых непосредственно из этой функции).
Но не выделяем пока память под блоки для функций, вызываемых глубже (вассал моего вассала не мой вассал).
То есть, память выделяем не всю сразу, а на одно углубление по стеку.
При этом, при вызове функции в итерации цикла мы переиспользуем уже выделенный блок памяти
не обращаясь к механизму выделения.
В принципе, указатели (Д) наверное и не нужны. А вот место под Б2 наверное надо выделить (но я тут не уверен, не подумал достаточно хорошо).
Т.е. под функцию main выделяем блок, размер которого определяется переменными, которые использует main и размерами стеков функций,
которые main вызывает непосредственно.
---
Идея заключается в том, чтобы моменты выделения/удаления блоков (памяти, необходимых для работы циклов)
соответствовали не вызовам функций, а входам и выходам из циклов.
Поэтому точки Т1 и Т2 наверное не очень правильно расположены, я их расположил так по инерции мышления.
И, даже, наверное не по циклы влияют, а ветвления. Надо ещё подумать.
Проходя через заголовок функции, мы копируем некоторые параметры, но это ничего не значит,
потому что это нужно просто для обеспечения гарантии того, что функция ничего лишнего не изменит.
(и наверное это можно выоптимизировать)
Прохождение через границу модуля это другое дело, так как модуль мог быть собран другими инструментами
и может не поддерживать этот подход.
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>Но не выделяем пока память под блоки для функций, вызываемых глубже (вассал моего вассала не мой вассал). ЭФ>То есть, память выделяем не всю сразу, а на одно углубление по стеку. ЭФ>При этом, при вызове функции в итерации цикла мы переиспользуем уже выделенный блок памяти ЭФ>не обращаясь к механизму выделения. ЭФ>Т.е. под функцию main выделяем блок, размер которого определяется переменными, которые использует main и размерами стеков функций, ЭФ>которые main вызывает непосредственно. ЭФ>Идея заключается в том, чтобы моменты выделения/удаления блоков (памяти, необходимых для работы циклов) ЭФ>соответствовали не вызовам функций, а входам и выходам из циклов.
Вы рассмотрите пример, который я привёл. Ну, допустим, у нас весь фрейм стека функции имеет размер X. Поскольку никаких других функций в примере нету, то все фреймы того же размера x.
Допустим, мы написали такую умную виртуальную машину, которая умеет детектировать циклы; так что фрейм стека под вызов выделяется ровно один раз и переиспользуется.
Итак, мы вызываем нашу функцию Count на каком-то объекте (пока не в цикле). Под неё выделен фрейм размером X (F1).
В начале цикла мы выделяем ещё один фрейм размером X для вызовов (F2).
Делаем вызов на первом ребёнке; исполнение снова доходит до цикла, чтобы подсчитать "внуков". Теперь нам опять нужно выделить фрейм размером X — назовём его F3.
Не будем пока лезть в рекурсию дальше — но к моменту возврата со 2го уровня на 1й мы теряем информацию о фрейме F3 — её просто негде сохранить. Она была частью информации о выполнении вызова на первом ребёнке, и она нам более недоступна.
Поэтому, несмотря на то, что мы обрабатываем второго ребёнка с тем же фреймом F2, что и первого, фрейм F3 придётся выделять заново.
То есть мы всего лишь отложили проблему на 1 уровень.
И это никак не связано с рекурсией — точно так же себя будет вести система вложенных вызовов A()->B()->C(), где циклы расположены в A и B.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
. Сборщику мусора для работы нужно знать структуру объекта, с которым он работает. Например, он должен отличать обычный int (с которым ничего не надо делать) и ссылку на объект (по которой нужно идти дальше). С обычными объектами этоне проблема. Есть ссылка на дескриптор класса, откуда можно всю нужную информацию извлечь. А вот с фреймами не так. Его структура зависит от "адреса возврата" (точнее, от instruction pointer в рамках того метода). Пример в рамках стека вычислений:
