Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

Реализация двухстековой модели размещения данных

У процессора 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

Оцените

Отзывы

     2015/02/11 12:35, Павел          # 

А как же адрес возврата?

     2015/02/11 17:09, Автор сайта          # 

Адрес возврата лежит в стеке, ячейка с адресом возврата адресуется регистром EBP — всё как обычно.

     2019/03/13 16:02, Бурановский дедушка          # 

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

     2019/03/20 00:33, ВежливыйЛис          # 

Здравствуйте. У меня четырёхсокетная машина с 36-ядерными процессорами, и в программе много параллельно работающих нитей. Функция может быть вызвана любой нитью. У каждой нити свой стек. Как функция будет вычислять адрес альтернативного стека в этом случае. Спасибо.

     2019/03/21 16:52, Автор сайта          # 

У каждой нити должно быть два стека, а не один. Вот и всё.

     2019/03/22 11:14, ВежливыйЛис          # 

Было бы интересно, ЕЩЁ (дополнительно), рассмотреть общие данные нитей, и передачу из одной нити в другую. С кучей-то всё просто, она одна общая.

     2019/03/22 22:58, Автор сайта          # 

Для общих данных ещё есть статическая память. Но она на то и статическая, что динамически не расширяется. Куча в этом плане удобнее. Многопоточность — тема сложная и интересная. Но зрелых мыслей на эту тему пока нет. Озвучивать же незрелые смысла нет.

     2019/03/20 09:05 (перемещено), ВежливыйЛис          # 

В языках со передвигающей сборкой мусора (Java, C#, возможно Lisp) поиск нового свободного участка это операция с константным временем — берётся адрес свободной памяти и всё. Поэтому некорректно сравнивать именно с malloc.

Ну и хотелось бы внятное пояснение — за счёт чего именно достигается увеличение быстродействия. Пока такого пояснения нет. Например, как вся эта машинерия будет работать в случае рекурсивной сборки длинной строки из результатов работы маленьких функций в паттерне Visitor.

     2019/03/21 17:04 (перемещено), Автор сайта          # 

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

К слову, о диспетчере памяти Java. Вот что пишет Лидия Васильевна Городняя, ученица академика Ершова, кандидат физико-математических наук, доцент, старший научный сотрудник Института систем информатики им. А.П. Ершова Сибирского отделения РАН:

Вчера у нас на семинаре выступал сотрудник неплохой фирмы Эксельсиор, унаследовавшей задел Ершовских школ юных программистов и лаборатории Поттосина, занимающейся разработкой компиляторов. Говорил он о проблеме сборки мусора в Java-машине, но фактически оказалось, что проблемой является невозможность исправления спящих ошибок в стандартных библиотеках, т.к. их исправление нарушает официальную спецификацию Java-машины. Ошибка существует с первых версий, т. е. более 20-ти лет её никто не замечал или как-то обходил.

Я уже писал, почему память в стеке выделяется чрезвычайно быстро. Потому что на это уходит всего две машинные команды: «MOV» и «SUB». Возможно, это Вам ничего не говорит. Тогда советую почитать книги про ассемблер, в сети немало хороших.

Цитата же от Лидии Васильевны подсказывает, что две машинные команды — это ещё и надёжнее, чем диспетчер памяти JVM.

     2019/03/22 11:07 (перемещено), ВежливыйЛис          # 

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

В рантайме с GC у них при распределении тоже две команды — MOV и ADD, если Вам это о чём-то говорит. Ну и почитайте про ассемблер, вдруг команда ADD Вам неизвестна.

     2019/03/23 19:29 (перемещено), Автор сайта          # 

У Вас в стеке будут образовываться дыры, такие же как и в куче.

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

В рантайме с GC у них при распределении тоже две команды — MOV и ADD.

Я уже писал, что есть разные стратегии выделения динамической памяти. Если память в «куче» выделяется самым простым образом — «MOV» и «ADD», то когда-нибудь наступает расплата в виде паузы на «сборку мусора»: утилизации участков памяти, ранее помеченных как свободных. Т.е. если malloc быстрая, то free медленная. И наоборот: если malloc медленная, то free быстрая. Но чтобы обе функции были быстрыми, да ещё с константным временем работы — такого не бывает. В стеке же память освобождается единственной машинной командой, модифицирующей значение регистра ESP.

Ну и почитайте про ассемблер, вдруг команда ADD Вам неизвестна.

Я ранее разложил ситуацию с двумя стеками что называется до атомов. Описал на уровне машинных команд. Ниже, чем этот микроуровнь, не бывает. Но Вы пишите, что Вам не понятно. Вот я и предположил, что Вы ассемблера не знаете, раз это не дало Вам ключа к пониманию. Не знать ассемблер — это не оскорбительно, я знаком такими программистами, весьма хорошего уровня. Зато у них хорошо с макроуровнем. А я вот порою мучаюсь с макроуровнем: не въезжаю, пока не расшифрую его до микроуровня.

     2019/03/23 20:32 (перемещено), ВежливыйЛис          # 

Ещё раз. Мне понятно всё, что Вы говорите, но с моей точки зрения этот метод ХУЖЕ, чем сборка мусора.

Вот я и предположил

Предположили неправильно, и сразу после этого нахамили. Демонстрирую ещё раз. Вы не понимаете мою мысль. Сделаю-ка я *предположение*, что это потому, что Вы школьник (могу не проверять и не спрашивать? Никакого fact checking. Ну Вы так сделали). Так вот, *мальчик*, Вы ошибаетесь.

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

Ещё иногда бывает так, что люди попав в сложную ситуацию не понимают как себя вести. Надо извиниться, причём так, чтобы Вам поверили. Либо можно и дальше продолжать "не понимать" и размахивать своей уверенностью (Многие так и умирают с уверенностью в своей правоте и верой в плоскую землю).

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

     2019/03/24 00:18 (перемещено), Автор сайта          # 

с моей точки зрения этот метод ХУЖЕ, чем сборка мусора.

Своё мнение надо подкреплять исходными кодами, легко проверяемыми фактами, ссылками на авторитетные источники. Я это делал, а Вы — нет.

у нас в стеке появляются неиспользуемые области

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

после этого нахамили.

Во-первых, не искушайте, утверждая, что «пока такого пояснения нет», когда Вам в тексте выше всё разложили по полочкам, вплоть до машинных команд. Во-вторых, это Вы мне предложили название результата своих трудов: «ЯОСЛИК».

Всего хорошего.

     2019/03/24 01:42 (перемещено), ВежливыйЛис          # 

не вытаскиваются

Им и не нужно, им достаточно не использоваться для разумных целей и при этом оставаться в стеке занимая память.

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

     2019/03/24 14:55 (перемещено), Автор сайта          # 

Рассказываю Вам теорию. Допустим. У нас есть такие функции:
int f2 (int d, int e);
int f1 (int a, int b, int c) {
return a+b+c+f2(1,2);
}
Тогда стек после вызова f1, но перед вызовом f2 принимает такой вид:
 ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │ │ █ │ a │ b │ c │
───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
где █ — служебные поля для сохранения регистров и адреса возврата. Стек растёт в сторону меньших адресов (дурдом, но в архитектуре x86 этот так). Меньшие адреса — слева, старшие — справа. После вызова f2 картина будет уже такая:
 ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ █ │ d │ e │ █ │ a │ b │ c │
───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Функция f2 и f3 в свою очередь определены так:
struct S {int  x; int z;};
struct S f3 (int h, int i) {
. . .
return ...; // возвращает структуру фиксированного размера
}
int f2 (int d, int e) {
struct S g;
g.x = d; g.y = e;
. . .
return ...;
}
После вызова f2 и перед вызовом f3 картина в стеке будет такая (под g место выделено, но g ещё не инициализировано):
 ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ g │ █ │ d │ e │ █ │ a │ b │ c │
───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
После вызова f3 стек примет такое состояние:
 ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ █ │ h │ i │ g │ █ │ d │ e │ █ │ a │ b │ c │
───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Когда f3 отработает, в стеке будет то же самое, только g уже инициализировано:
 ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ g │ █ │ d │ e │ █ │ a │ b │ c │
───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Соблюдается дисциплина LIFO. Освободить ячейки a, b, c, d, e, g мы не можем: они ещё нужны — все до единого! Поэтому дыры невозможны. А вот всё, что за вершиной стека (это слева) — свободно. После выхода из f2 стек становится таким:
 ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │ │ █ │ a │ b │ c │
───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Это я рассказал Вам теорию, почему при дисциплине LIFO не возникает дыр — потому что нет необходимости освобождать ранее занятые ячейки. Занятие участков памяти и их освобождение выполняется исключительно автоматически, здесь нет дилемы: ручное управление памятью или автоматическое. Соответственно и нет проблем с дефрагментацией памяти. Единственная проблема — возможное переполнение стека, когда существует много незаконченных вызовов подпрограмм. Простейший способ переполнить стек — организовать бесконечную рекурсию. Но эта опасность грозит что одностековой, что двухстековой модели памяти. А вот утечек памяти по вине стека никогда не было!

Идём дальше. Представим себе, что переменная g — это не структура фиксированного размера, а строка переменного размера. У нас картина мира рушится: как в средине стека (уже после вызова f3) зарезервировать место под g, если размер g становится известным в последний момент?
 ───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ █ │ h │ i │ g │ █ │ d │ e │ █ │ a │ b │ c │
───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Эту проблему я решаю за счёт второго стека.

как более вежливый ... я.

Ага. «О своей скромности я могу рассказывать часами».

Добавить свой отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Устарел ли текст как форма представления программы

Русский язык и программирование

Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

Некоторые «вкусности» Алгол-68

«Двухмерный» синтаксис Python

Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

Должна ли программа быть удобочитаемой?

Стиль языка программирования

Тексто-графическое представление программы

●  Разделители

●  Строки программы

●  Слева направо или справа налево?

Комментарии

●  Длинные комментарии

●  Короткие комментарии

●  Комментарии автоматической генерации документации

●  Нерабочий код

●  Помеченные комментарии

Нужны ли беззнаковые целые?

Шестнадцатиричные и двоичные константы

Условные операторы

Переключатель

Циклы

●  Продолжение цикла и выход из него

Некошерный «goto»

Изменение приоритетов операций

Операции присвоения и проверки на равенство. Возможно ли одинаковое обозначение?

Так ли нужны операции «&&», «||» и «^^»?

Постфиксные инкремент и декремент

Почему в PHP для конкатенации строк используется «.»?

Указатели и ссылки в C++

●  Обработка ошибок

Использование памяти

Почему динамическое распределение памяти — это плохо

Как обеспечить возврат функциями объектов переменной длины?

●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●  Массивы переменной длины в C/C++

●  Размещение объектов в стеке, традиционный подход

●  Размещение объектов переменной длины с использованием множества стеков

●  Размещение объектов переменной длины с использованием двух стеков

●  Реализация двухстековой модели размещения данных

●  Двухстековая модель: тесты на скорость

●  Изменение длины объекта в стеке во время исполнения

●  Размещение объектов переменной длины с использованием одного стека

Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

Безопасность и размещение объектов переменной длины в стеке

Массивы, структуры, типы, классы переменной длины

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

Реализация параметрического полиморфизма

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Новости и прочее

Последние комментарии

2019/06/18 11:28 ••• MikeZ
Идеальный транслятор

2019/06/05 23:21 ••• kt
К вопросу о совершенствовании языка программирования

2019/06/04 14:52 ••• Неслучайный читатель
Деньги = работа / знание

2019/05/29 00:42 ••• rst256
Программирование без программистов — это медицина без врачей

2019/05/14 16:10 ••• utkin
Обработка ошибок

2019/05/09 18:05 ••• евгений
Русский язык и программирование

2019/04/28 14:08 ••• Автор сайта
Статьи Дмитрия Караваева

2019/04/22 16:19 ••• Автор сайта
Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

2019/04/03 22:24 ••• Антон
Все голосования

2019/04/02 12:28 ••• Автор сайта
Шестнадцатиричные и двоичные константы

2019/04/02 12:25 ••• Автор сайта
Выбор кодировки для компилятора

2019/03/24 14:55 ••• Автор сайта
Реализация двухстековой модели размещения данных