Реализация двухстековой модели размещения данныхУ процессора x86, к сожалению, всего один стек. Как тогда заставить работать двухстековую модель? Один стек в программе уже имеется, это аппаратный стек процессора, с которым работают через регистры ESP и EBP. Чтобы пользоваться вторым стеком, надо однократно зарезервировать под него память. Указатель на эту область памяти запишем в глобальную переменную «другой стек». Перед вызовом функции, которая возвращает объект переменной длины, пишем: XCHG ESP, другой стекДалее вызывается, к примеру, такая функция: Таблица БД* поставщики = Конструктор таблицы БД (список поставщиков);которая будет выглядеть на ассемблере так: PUSH <параметр 1> . . . PUSH <параметр N> CALL Конструктор таблицы БДВнутри вызванной функции уменьшаем указатель вершины другого стека на длину объекта: mov EAX, длина объекта sub другой стек, EAXПосле вызова функции для восстановления актуального значения ESP опять делаем обмен значений: XCHG ESP, другой стекВ качестве послесловия стоит упомянуть о двухстековой модели языка Forth. В нём один стек используется для данных, а другой — для хранения адресов возвратов. Слова языка Forth (термин «слово» этого языка подразумевает функции, процедуры, операции) могут как брать из стека произвольное количество данных, так и класть в него (т.е. возвращать) произвольное количество данных. При всём достоинстве такого подхода сам язык не пользуется успехом по ряду причин. Одна из них такова, что такая работа со стеком исключает совместимость программ на Forth с программами на C, Pascal и проч. Редактор связей может собрать исполняемый модуль из объектных файлов, полученных компиляцией программ на разных языках типа C, C++, Pascal, Ada. Forth же придерживается иной, не совместимой архитектуры вызовов. Рассмотренная выше организация работы с двумя стеками отличается от фортовской и реализует её меньшим количеством машинных команд и совместима с программами на самых распространённых языках. Читаем далее следующую статью: Двухстековая модель: тесты на скорость. Почитайте ещё:
Опубликовано: 2014.07.27, последняя правка: 2018.10.29 16:03
Отзывы
Ну и хотелось бы внятное пояснение — за счёт чего именно достигается увеличение быстродействия. Пока такого пояснения нет. Например, как вся эта машинерия будет работать в случае рекурсивной сборки длинной строки из результатов работы маленьких функций в паттерне Visitor.
К слову, о диспетчере памяти Java. Вот что пишет Лидия Васильевна Городняя, ученица академика Ершова, кандидат физико-математических наук, доцент, старший научный сотрудник Института систем информатики им. А.П. Ершова Сибирского отделения РАН: Вчера у нас на семинаре выступал сотрудник неплохой фирмы Эксельсиор, унаследовавшей задел Ершовских школ юных программистов и лаборатории Поттосина, занимающейся разработкой компиляторов. Говорил он о проблеме сборки мусора в Java-машине, но фактически оказалось, что проблемой является невозможность исправления спящих ошибок в стандартных библиотеках, т.к. их исправление нарушает официальную спецификацию Java-машины. Ошибка существует с первых версий, т. е. более 20-ти лет её никто не замечал или как-то обходил. Я уже писал, почему память в стеке выделяется чрезвычайно быстро. Потому что на это уходит всего две машинные команды: «MOV» и «SUB». Возможно, это Вам ничего не говорит. Тогда советую почитать книги про ассемблер, в сети немало хороших.Цитата же от Лидии Васильевны подсказывает, что две машинные команды — это ещё и надёжнее, чем диспетчер памяти JVM.
В рантайме с GC у них при распределении тоже две команды — MOV и ADD, если Вам это о чём-то говорит. Ну и почитайте про ассемблер, вдруг команда ADD Вам неизвестна.
У Вас в стеке будут образовываться дыры, такие же как и в куче. Ну что Вы. Стек - это LIFO. В нём не может быть дыр по этой единственной причине. Я бы и дальше продолжил, но Вас, похоже, задевают призывы разобраться в теории вопроса.В рантайме с GC у них при распределении тоже две команды — MOV и ADD. Я уже писал, что есть разные стратегии выделения динамической памяти. Если память в «куче» выделяется самым простым образом — «MOV» и «ADD», то когда-нибудь наступает расплата в виде паузы на «сборку мусора»: утилизации участков памяти, ранее помеченных как свободных. Т.е. если malloc быстрая, то free медленная. И наоборот: если malloc медленная, то free быстрая. Но чтобы обе функции были быстрыми, да ещё с константным временем работы — такого не бывает. В стеке же память освобождается единственной машинной командой, модифицирующей значение регистра ESP.Ну и почитайте про ассемблер, вдруг команда ADD Вам неизвестна. Я ранее разложил ситуацию с двумя стеками что называется до атомов. Описал на уровне машинных команд. Ниже, чем этот микроуровнь, не бывает. Но Вы пишите, что Вам не понятно. Вот я и предположил, что Вы ассемблера не знаете, раз это не дало Вам ключа к пониманию. Не знать ассемблер — это не оскорбительно, я знаком такими программистами, весьма хорошего уровня. Зато у них хорошо с макроуровнем. А я вот порою мучаюсь с макроуровнем: не въезжаю, пока не расшифрую его до микроуровня.
Вот я и предположил Предположили неправильно, и сразу после этого нахамили. Демонстрирую ещё раз. Вы не понимаете мою мысль. Сделаю-ка я *предположение*, что это потому, что Вы школьник (могу не проверять и не спрашивать? Никакого fact checking. Ну Вы так сделали). Так вот, *мальчик*, Вы ошибаетесь.Появятся в сети отзывы, мол мы использовали систему Автора, но она поедает всю память стеком и выходит из строя. Или "у нас в стеке появляются неиспользуемые области, несмотря на то, что Автор заявляет что так быть не может". Ещё иногда бывает так, что люди попав в сложную ситуацию не понимают как себя вести. Надо извиниться, причём так, чтобы Вам поверили. Либо можно и дальше продолжать "не понимать" и размахивать своей уверенностью (Многие так и умирают с уверенностью в своей правоте и верой в плоскую землю). Мне не нужно будет ничего доказывать, просто надо подождать лет 20, когда Вам станет очевидна ошибочность Вашего подхода, как она очевидна мне сейчас. Жизнь сама всё покажет.
с моей точки зрения этот метод ХУЖЕ, чем сборка мусора. Своё мнение надо подкреплять исходными кодами, легко проверяемыми фактами, ссылками на авторитетные источники. Я это делал, а Вы — нет.у нас в стеке появляются неиспользуемые области Почитайте, пожалуйста, Википедию про стек и не позорьтесь. В стеке не может возникнуть дыра, ибо первым со стека снимается элемент на вершине. Из средины элементы не вытаскиваются, соответственно и дыра не возникнет.после этого нахамили. Во-первых, не искушайте, утверждая, что «пока такого пояснения нет», когда Вам в тексте выше всё разложили по полочкам, вплоть до машинных команд. Во-вторых, это Вы мне предложили название результата своих трудов: «ЯОСЛИК».Всего хорошего.
не вытаскиваются Им и не нужно, им достаточно не использоваться для разумных целей и при этом оставаться в стеке занимая память.Ну я понял, что хамить Вы не прекратите, так что как более вежливый зверь прекрашу разговаривать я.
int f2 (int d, int e);Тогда стек после вызова f1, но перед вызовом f2 принимает такой вид: ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐где █ — служебные поля для сохранения регистров и адреса возврата. Стек растёт в сторону меньших адресов (дурдом, но в архитектуре x86 этот так). Меньшие адреса — слева, старшие — справа. После вызова f2 картина будет уже такая: ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐Функция f2 и f3 в свою очередь определены так: struct S {int x; int z;};После вызова f2 и перед вызовом f3 картина в стеке будет такая (под g место выделено, но g ещё не инициализировано):───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐После вызова f3 стек примет такое состояние: ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐Когда f3 отработает, в стеке будет то же самое, только g уже инициализировано: ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐Соблюдается дисциплина LIFO. Освободить ячейки a, b, c, d, e, g мы не можем: они ещё нужны — все до единого! Поэтому дыры невозможны. А вот всё, что за вершиной стека (это слева) — свободно. После выхода из f2 стек становится таким: ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐Это я рассказал Вам теорию, почему при дисциплине LIFO не возникает дыр — потому что нет необходимости освобождать ранее занятые ячейки. Занятие участков памяти и их освобождение выполняется исключительно автоматически, здесь нет дилемы: ручное управление памятью или автоматическое. Соответственно и нет проблем с дефрагментацией памяти. Единственная проблема — возможное переполнение стека, когда существует много незаконченных вызовов подпрограмм. Простейший способ переполнить стек — организовать бесконечную рекурсию. Но эта опасность грозит что одностековой, что двухстековой модели памяти. А вот утечек памяти по вине стека никогда не было! Идём дальше. Представим себе, что переменная g — это не структура фиксированного размера, а строка переменного размера. У нас картина мира рушится: как в средине стека (уже после вызова f3) зарезервировать место под g, если размер g становится известным в последний момент? ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐Эту проблему я решаю за счёт второго стека. как более вежливый ... я. Ага. «О своей скромности я могу рассказывать часами».Написать автору можно на электронную почту |
2015/02/11 12:35, Павел