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

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

Вняв совету заняться прототипом, провожу эксперименты. В чём минусы практических попыток создания компилятора? Уходит время, приходится переключать мозги с макроуровня на микроуровень. Приходится покидать мир высоких абстракций и продвинутых концепций и опускаться на грешную землю и пахать её байт за байтом. Вынужден ползать на уровне Си или ассемблера, а не парить в облаках. Но тут уже была тема для такого низкого уровня — двухстековое распределение памяти. И эту тему, как оказалось, можно лучше проработать.

            Уже задавался вопрос:

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

В чём проблема? Стек процессора x86 растёт в сторону уменьшения адресов. Объекты же типа строк и массивов растут в сторону увеличения адресов.
Изменение длины объекта в стеке во время исполнения
            Нулевые элементы массивов на рисунке имеют наименьший адрес, элементы с наибольшим номером имеют наибольший адрес. Но когда помещаем в стек массив с номер 0, то куда можно поместить массив с номером 1? Стек растёт в сторону младших адресов, поэтому все объекты (на рисунке — это массивы 1, 2 и т.д.) размещаются на рисунке «левее». Можно ли длину массива 2 «нарастить»? Сделать её равной не k, а k+1? Нельзя, поскольку элемент k+1 наложится на элемент 0 массива 1. Что нужно, чтобы добавить новые элементы в массив?
  • Узнать, сколько дополнительной памяти для этого потребуется,
  • сдвинуть указатель стека на эту величину,
  • переписать весь массив по новому адресу,
  • добавить в конец новые элементы.
Это необходимый минимум. Могут быть и другие сложности. Ведь на этот массив могут ссылаться другие объекты. Плюс ссылки могут быть внутри самого массива. Вот и думалось: может, бросить эту затею? Ведь когда-то хотел сделать стек программным. Это будет помедленнее, но зато проще.

            По поводу таких особенностей архитектуры x86 хочется сказать «большое спасибо» разработчикам Intel: у них не только порядок байтов обратный (little-endian, малым концом — «остроконечники» по классификации Джонатана Свифта), но ещё и стек растёт в обратном направлении. Если бы всё сделать, как у людей, то помещённый в стек объект мог бы расти. И стек, и объект росли бы в одну и ту же сторону.

            И вот, поругивая Intel, я занимался практической реализаций объектов, помещаемых в стек. Честно говоря, получалось не очень. Как-то всё сложно выходило. Но тут однажды осенила идея… Мы должны развернуть строки и массивы в обратном направлении! Чтобы направление роста стека и массивов было одинаковым:
Изменение длины объекта в стеке во время исполнения
            После такого решения многие моменты встают на свои места. Добавление новых элементов к последнему массиву лишь сдвигает указатель вершины стека. Код, над которым я работал, был переписан. Он сразу стал короче, освободился от многих неестественных функций. Правда, появилась одна неестественность: адресом массива остался нулевой элемент, но это элемент с наибольшим адресом, а не с наименьшим. Да и то я упростил картину. На самом деле массивы имеют в своём составе поле «количество элементов». Именно его адрес является адресом массива. А вот «слева» от него — элемент 0, затем 1 и т. д.
Изменение длины объекта в стеке во время исполнения
            Будет любопытно поработать с такими массивами и строками «шиворот на выворот». Понаблюдаю и поделюсь выводами :)

Последняя правка: 2018-11-09    12:26

Оцените

Отзывы

     2018/11/11 16:18, Александр Коновалов aka Маздайщик

Если язык программирования существует «в вакууме», то элементы массива могут отображаться в любом порядке. Но на практике придётся взаимодействовать с существующими API, а это значит, что придётся писать переходники, которые обращают массивы и строки до и после вызова.

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

     2018/11/11 23:39, Автор сайта

на практике придётся взаимодействовать с существующими API... придётся писать переходники, которые обращают массивы и строки до и после вызова.

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

     2018/11/15 13:40, kt

Аппаратные особенности могут раздражать, но программные выкрутасы — прямо бесят. Я намучался из-за единственной глупой команды. Win-64 сейчас требует, чтобы стек программы при исключениях ВСЕГДА был кратен 8, хотя физически процессору на это наплевать. И эта проверка стоит в системном обработчике исключений. Получается идиотская ситуация: произошло исключение, для него написан свой обработчик, Windows его нашла и собирается передать управление и вдруг, о, ужас! Стек не кратен 8! Программа принудительно снимается. При этом в этот момент действует стек обработчика и он кратен 8. Козлы они, а не разработчики! В 32-разрядном режиме этой глупости нет. А так получается вот что: лежит в стеке строка и я хочу отрезать у нее первый символ. Раньше я просто сдвигал указатель стека вверх на байт, а теперь отрезанную строку еще надо так сдвинуть в стеке, чтобы ее начало опять было кратно 8. И приходится двигать и вправо и влево. Из-за одной единственной дурацкой проверки в системной библиотеке Windows.

     2018/11/15 17:46, Автор сайта

В языке Rust как-то обходятся без исключений. Там другой механизм обработки ошибок. И он мне нравится. Но и его можно сделать лучше :)

     2018/11/15 18:43, Comdiv

А насколько это вообще влияет на полезные свойства транслятора? Сколько раз в практической задаче будет встречаться единственный локальный массив, который необходимо растить?

     2018/11/15 20:55, Автор сайта

Транслятор читает входной поток, анализирует и накапливает результаты анализа. Куда он должен сохранить эти результаты, если они промежуточные и ещё нужны при генерации кода? Можно в файл, но можно и в память. В последнем случае можно в «кучу», а можно попробовать в стек. Вот этим и занимаюсь в экспериментах. При этом стараюсь код на Си писать, насколько это возможно, похожим на будущий язык, используя накопленные задумки. В будущем это пригодится для раскрутки компилятора.

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

     2018/11/16 18:43, Comdiv

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

На самом деле, динамически меняющие размер объекты — не редкость, вполне обычное явление

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

     2018/11/17 00:05, Автор сайта

Длина идентификатора становится известной после прочтения, соответственно ему нельзя статически выделить памяти ровно столько, сколько он занимает места. Тот же словарь идентификаторов — это контейнер, куда помещаются идентификаторы с заранее неизвестной длиной и в заранее неизвестном количестве.

хотелось бы увидеть некое численное выражение пользы.

Пока рано говорить о каком-то числовом выражении.

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

Если не секрет, что это за проект?

     2018/11/17 03:28, Comdiv

Проект "Восток" - транслятор Оберон-07 https://github.com/Vostok-space/vostok/

Написать отзыв

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

Авторизация

Регистрация

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

Карта сайта


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комментарии

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

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

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

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

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

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

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

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

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

Циклы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компилятор

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

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

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

Прочее

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

2018/11/20 20:13 ••• ivan.ee
✎ Программирование без программистов — это медицина без врачей

2018/11/18 17:14 ••• kt
✎ Экстракоды при синтезе программ

2018/11/18 15:26 ••• Freeman
✎ Так ли нужны операции «&&», «||» и «^^»?

2018/11/18 15:21 ••• Freeman
✎ Устарел ли текст как форма представления программы

2018/11/17 03:28 ••• Comdiv
✎ Изменение длины объекта в стеке во время исполнения

2018/11/16 12:53 ••• Автор сайта
✎ Помеченные комментарии

2018/11/11 14:01 ••• Александр Коновалов aka Маздайщик
✎ Нерабочий код

2018/11/11 13:39 ••• Александр Коновалов aka Маздайщик
✎ О русском языке в программировании

2018/11/11 12:57 ••• Александр Коновалов aka Маздайщик
✎ Об одной реализации специализированных операторов ввода-вывода

2018/11/03 22:43 ••• rst256
✎ Непрерывное компилирование

2018/11/02 23:23 ••• Неслучайный читатель
✎ Сколько проходов должно быть у транслятора?

2018/11/01 19:10 ••• Автор сайта
✎ Об исключенных командах или за что «списали» инструкцию INTO?