Просмотр полной версии : Рапределение памяти при работе компилятора ЯВУ
Среди различных глупостей, которыми я занимаюсь, есть компилятор Паскаля. Задача: запустить его на Спектруме 48к или подобной платформе. Допустим, у этой платформы всё-таки есть некий дисковый/флэш накопитель с произвольным посекторным доступом.
В данный момент с использованием динамического распределения памяти на различные структуры при компиляции требуется раз в 50 больше памяти, чем занимают исходники. Понятно, что как ни уменьшай использование памяти, в 48 кБайтах компилятор работать не сможет. Как реализовать "виртуальную память" на несколько мегабайт? Самое простое что приходит на ум: хранить все структуры в одном временном файле на диске, а для ускорения работы потом прикрутить кеширование.
Другой вопрос: есть какие-то "серьёзные" компиляторы (не кросс-компиляторы) для Спектрума с поддержкой указателей, массивов, структур, объектов, "умной линковки" и прочего?
IMHO, если нужен серьёзный компилятор, используй cp/m. Cp/m на разных машинах предоставляет разный объём ОЗУ для программ (в т.ч. компилятора). Нужна такая машинка, которая предоставляет максимум ОЗУ, почти все 64 Кб, для этого она должна не держать в ОЗУ процессора видеопамять. По этой причине многие разновидности cp/m на базе спектрума не подходят, потому что они держат видеоОЗУ в начале третьего (если считать с 0) банка, и поэтому не могут предоставить программам более 48 кб. Сюда относятся скорпион, хоббит. Про профи и атм не знаю, как там реализовано...
А какие компиляторы под CP/M есть?
Но всё равно мне это просто чтобы посмотреть что бывает. Речь идёт не о запуске просто какого-то компилятора, а о написании собственного, который мог бы запуститься и на 32 килобайтах, и не только на Z80.
Не, я тут прикинул размеры, а ещё оказалось что FPC как-то интересно память распределяет... В общем, когда мой компилятор сможет собирать сам себя и будет кодогенератор для Z80, тогда и надо будет пытаться запихнуть его в 32к.
Хех, затронул тему которая тут обсуждалась в скользь в разных темах уже несколько раз. Глобальная проблема тут в том что современные программисты хотят программировать в "бесконечном адресном пространстве" и никогда не парится с overlay-ями. Оно и понятно проще выделить еще один кусок земли для сарая и гаража чем думать как его построить гараж трансформируемый в сарай и обратно по желанию.
Но решить задачу всеже можно, главная предпосылка к решению это то что в каждый единичный момент времени программа работает всего лишь с 1-й процедурой которая манипулирует только к ней относящимися структурами данных. А это значит что для speccy48 можно писать процедуры которые вместе с ихними данными занимают: (49152-6912-стэк-диспечер) байтов памяти. Стэк может быть и 1кб а диспечер должен уметь делать замену "текущей" процедуры на "вызываемую" или на "вызвавшую". Понятное дело что "вызовы" и "возвраты" в такой схеме будут тормозить выполнение алгоритма по сравнению с работой того же кода в "бесконечном адресном пространстве", кроме того алгоритмы работы с "длинными массивами" или рекурсию прийдется отправить на мусорку. Но зато такой способ не потребует больше НИКОГДА расширять адресное пространство процессора (хотя если адресное пространство УЖЕ 64bit... то следующего "расширения" ждать прийдется еще очень долго)
То есть грузить в память по одной процедуре/функции? В этом что-то есть. И даже рекурсию в мусорку можно не отправлять. Можно сделать ещё круче: замутить виртуальную машину, саму машину в RAM, а память виртуальной машины на диске.
У меня проблема не в размере кода, а в размере данных. Препроцессор и лексический анализатор уже почти отдельная программа, думаю, можно и дальше компилятор делить на отдельные процессы, которые будут обмениваться данными через файлы. Проблема в том, что при работе получается много структур, которые хранить в RAM негде, а на диске медленно и неудобно. Перехватил в FPC GetMem() для подсчёта расхода памяти, получилось где-то в 50-100 раз больше исходника. То есть если сам компилятор сейчас килобайт 100, то ему для компиляции самого себя потребуется мегабайт 10, а то и больше, для хранения типов, идентификаторов и прочего.
В общем, как я уже написал, надо сначала разобраться с алгоритмами, пусть даже им потребуется "бесконечное адресное пространство". А потом может и вообще отказаться от идеи запуска в 32 килобайтах.
А какие компиляторы под CP/M есть? К примеру: http://www.cpm.z80.de/binary.html Но это далеко не всё, что существует под cp/m...
Barmaley_m
03.10.2014, 15:03
А какие компиляторы под CP/M есть?
Мне очень понравился Turbo Pascal 3.0 под CP/M. Быстрая компиляция, проблем с нехваткой памяти не было. Легок в использовании.
Типа опрос.
1. Какие есть компиляторы Паскаля, работающие прямо на Спектруме? Что в них нравится и что не нравится?
2. Нужен ли ещё один такой компилятор? :)
3. Если нужен, то какой - со всеми прибамбасами, в том числе с поддержкой модулей (units), или так, сотню-другую строк скомпилировать?
4. Или запилить кросс-компилятор под Windows/Linux и не заморачиваться?
как простое решение, можно разместить в непереключаемой памяти менеджер, код процедур компилить в окно переключаемой памяти. При компиляции каждый вызов процедуры компилить в чтото вроде такого кода:
LD HL,procedure_address
CALL MANAGER_CALL
менеджер по табличке будет находить в какой странице находится процедура, переключать страницу и делать вызов процедуры. По возврату управление опять передается в менеджер, он переключает страницу назад и после этого возвращает управление назад в вызвавший процедуру код.
Как альтернативу, можно передавать менеджеру вместе с адресом процедуры также и страницу, где она находится, тогда не нужно будет хранить таблицу страниц, но код вызова увеличится.
Чтобы не портить регистры, можно использовать такой подход:
CALL MANAGER_CALL
DW procedure_addr
DB procedure_page
Менеджер посмотрит откуда произошел вызов и прочитает адрес процедуры и номер страницы памяти. А при возврате добавит к значению в стеке 3, чтобы управление вернулось на следующую инструкцию. Минус - такой код тяжелее будет отлаживать в отладчике, т.к. DW и DB будут рассматриваться дизассемблером как инструкции.
Тут есть простор для фантазии. Можно адрес процедуры и номер страницы загонять в стек перед вызовом. Правда все это увеличивает размер кода производящего вызов.
С указателями тяжелее, тут нужно искать компромисс между коррекцией страницы памяти при каждой модификции указателя (заметно снизит производительность при поэлементном доступе к массивам) и анализом кода на предмет необходимости переключения страниц для используемого диапазона индексов относительно указателя.
Barmaley_m
04.11.2014, 01:35
Я думаю, надо объединять процедуры и данные, принадлежащие каждому оверлею, чтобы при каждом вызове или использовании указателя не было этих накладных расходов. Во времена 16-битного 8086-кода (дос, винда 3.11) в си и паскале были же разные типы вызовов и указателей - Near и Far. Первые были дешевыми в использовании, вторые - дорогими. И вообще, если данные лежат в другой странице - то может быть эффективнее скопировать их в общую область памяти, чем переключать страницы при доступе к каждому байту.
У меня проблема не в размере кода, а в размере данных, которые на части пока плохо делятся. Не исключаю вариант, что я не понимаю что-то очень простое.
140 килобайт исходника на данный момент при обработке дают в общей сложности 3 мегабайта структур, и это ещё не все задумки реализованы. Можно, конечно, разбирая исходник сразу код генерировать, я так уже делал - фигня получается :)
Видимо, на портирование компилятора на спектрум придётся забить и делать только кросс.
Andrew771
04.11.2014, 20:26
Есть HiSoft Pascal, работает на Спектруме 48к, сделан еще в начале 80х.
Нет xor. Целые только integer. Нет string. Нет процедурных типов. Нет приведения типов. Указатель на указатель нельзя. Не понял есть ли в нём получение указателя "@".
Зато можно делать так:
type item=record value:integer; next:^item; end;
Free Pascal на это ругается Error: Type "item" is not completely defined и я его в этом не понимаю.
Ну и, скорее всего, никакой оптимизации кода и "умной линковки" там нет. Но штука очень интересная.
p.s. Написал, а потом нашёл документацию к другим версиям. Стало ещё интересней.
Andrew771
04.11.2014, 21:42
Я щас лабаю кросс-компилятор Паскаля, только целочисленные типы и выражения, а также строки. Плюс встроенная библиотека процедур вывода спрайтов, текста и карт, будут вызываться специфическими операторами. Остальное, ИМХО, для написания игр на Спектруме не нужно.
Нет, у меня если и будет, то нечто универсальное и кроссплатформенное, которое может скомпилировать само себя. Начиналось с кросс-компилятора для 8-битных микроконтроллеров.
Andrew771
04.11.2014, 22:41
тогда тебе можно заглянуть сюда: http://zx-pk.ru/showthread.php?t=18472
Заглядывал. Олег не хочет заниматься генерацией машинного кода, я не хочу использовать прослойку в виде Си. Потом несложно будет приделать backend хоть для Си, хоть для LLVM.
Barmaley_m
05.11.2014, 01:00
Можно, конечно, разбирая исходник сразу код генерировать, я так уже делал - фигня получается :)
А кстати, так поступали почти все компиляторы времен 8-битных ЭВМ. Даже компилятор Microsoft Visual C++ "пожирает" структуры по мере обработки исходника. Об этом я читал в статье, где обосновывалась невозможность экспорта из него AST программы.
Я бы решал задачу по частям. Сначала сделал наиболее простым образом кросс-компилятор без ограничений по ресурсам. А потом уже пытался его оптимизировать по памяти, стремясь в конце концов уложиться в память ZX. Кстати, 140 килобайт исходника на Спектруме - это как-то многовато. Такой исходник даже сам по себе в 128К памяти не влезет. Большие программы обычно разбиваются на части с раздельной компиляцией, тогда памяти хватает.
Кстати, 140 килобайт исходника на Спектруме - это как-то многовато. Такой исходник даже сам по себе в 128К памяти не влезет. Большие программы обычно разбиваются на части с раздельной компиляцией, тогда памяти хватает.
на мой взгляд 140 кб исходника это маленькая библиотечка :smile:
denpopov
05.11.2014, 05:50
http://www.baltissen.org/htm/pcomp.htm
не тестил, руки не дошли еще..
http://www.baltissen.org/htm/pcomp.htm
не тестил, руки не дошли еще..
Да, на макросах я тоже пробовал. Понял, что в плане оптимизации кода это не самый лучший вариант, хотя очень простой в плане добавления нового процессора.
на мой взгляд 140 кб исходника это маленькая библиотечка :smile:
Это исходники компилятора ;)
denpopov
05.11.2014, 10:24
. Понял, что в плане оптимизации кода это не самый лучший вариант,
По опыту мучений с SDCC - лишь бы сырок выдал, сам оптимизирую:)
Так может тогда выдавать всё на неком промежуточном макроязыке, а кому надо прикрутит поддержку нужного процессора? LLVM, вид сбоку :)
Или выдавать байт-код виртуальной машины, а для целевого процессора достаточно написать несложный интерпретатор или JIT-транслятор. JAVA/.NET, вид оттуда же :)
Andrew771
05.11.2014, 23:14
сделай хоть что-нибудь, а то пока одна болтология годами (не от тебя) :)
Болтология потому что это то, чем занимаешься в свободное время для собственного удовольствия, при этом кроме себя самого это всё никому не нужно. А в какой-то момент приходит понимание что и самому себе этот онанизм как-то не особо нужен.
Болтология потому что это то, чем занимаешься в свободное время для собственного удовольствия, при этом кроме себя самого это всё никому не нужно. А в какой-то момент приходит понимание что и самому себе этот онанизм как-то не особо нужен.
Нет, задача сама по себе очень сложная, куча архитектур с 16bit адресным (а если брать в расчет pdp-8 то и 32kW адресного) "погибли" так и не найдя легкого способа совладать с этими ограничениями.
У разработчиков линкера для RSX11 на табло желаемых фич висел во ВСЕ времена 1 незакрытый запрос - "same day service" и это естественно, даже просто задача линкера сборщика задача довольно ресурсоемкая (не говоря о задаче оптимального использования памяти в алгоритмах).
Сейчас посмотрите что происходит - еще 7...10 лет назад говорили что 64-bit адресное нужно будет только для специфических задач а сегодня все ждут выхода 64bit ARM-a как единственного возможного пути развития так как в телефонах уже 2GB это не новость а через год два уже упруться в 4GB потолок. Переучивать программеров писать проги под оверлеи и сегменты никто не будет - это 100% (и это все по той же причине, задача эта сложная).
Я говорил не конкретно про программирование с модулями и оверлеями, а вообще про все эти занятия типа написания компиляторов.
Не покидает меня мысль запуска всего этого в 16-битном адресном пространстве, и в частности на ZX :)
Чего на данный момент есть более-менее стандартного для Спектрума кроме дискет на 640 кБайт и TR-DOS? Чтобы там временные файлы хранить.
Не покидает меня мысль запуска всего этого в 16-битном адресном пространстве, и в частности на ZX :)
Чего на данный момент есть более-менее стандартного для Спектрума кроме дискет на 640 кБайт и TR-DOS? Чтобы там временные файлы хранить.
tape 100% standard :)
James DiGreze
11.01.2015, 07:41
Сложно сказать насчёт стандартности, но более ли менее распространённая система iSDOS позволяет работать с винтами и довольно большими разделами (~30Mb). Система неплохо документирована. Правда там памяти под исполняемый код не густо, но можно работать с оверлеями и RAM-диском (должно быть ОЗУ 128К или более).
Andrew771
30.01.2015, 16:51
У меня проблема не в размере кода, а в размере данных, которые на части пока плохо делятся. Не исключаю вариант, что я не понимаю что-то очень простое.
140 килобайт исходника на данный момент при обработке дают в общей сложности 3 мегабайта структур, и это ещё не все задумки реализованы. Можно, конечно, разбирая исходник сразу код генерировать, я так уже делал - фигня получается
До сих пор не вкурю, какие-такие огромные данные ты собираешь хранить? Дерево разбора? Библиотеки процедур?
У меня в создаваемом компиляторе в памяти формируется только таблица констант, переменных и имен процедур, с несколькими параметрами. Занимает копейки. А код генерируется по-ходу. Но можно генерировать промежуточный код для последующей оптимизации. Промежуточный код тоже занимает немного, по-сути каждая команда байтов по 3-5 (если писать на Спекки).
Правда там памяти под исполняемый код не густо, но можно работать с оверлеями и RAM-диском (должно быть ОЗУ 128К или более).
вот бы глянуть пример работы с оверлеем
James DiGreze
01.02.2015, 10:05
Увы и ах, своего ничего не осталось после трагической гибели hdd с iSDOS.
Где-то в недрах тырнета должны попадаться обрывки документации, по крайней мере когда-то давно мне попадались.
До сих пор не вкурю, какие-такие огромные данные ты собираешь хранить? Дерево разбора? Библиотеки процедур?
У меня в создаваемом компиляторе в памяти формируется только таблица констант, переменных и имен процедур, с несколькими параметрами. Занимает копейки. А код генерируется по-ходу.
Да, в основном это дерево разбора. Но его можно сократить на треть и больше, надо только подумать к чему приведёт удаление некоторых полей. Есть и другие мысли по поводу оптимизации дерева, в том числе использование промежуточного кода. Таблица имён действительно занимает копейки, килобайт 100, но это полная, хранить можно только видимые.
Кроме констант, переменных и процедур есть ещё таблица типов. Andrew771, какие типы поддерживает или будет поддерживать создаваемый компилятор? Указатели, массивы, структуры, указатели на структуры, многомерные массивы указателей на структуры...? У меня заложена поддержка всего этого, а ещё поддержка модулей, процедурных и файловых типов, полиморфных и inline-процедур, переопределение операторов, умная линковка, условная компиляция {$IFDEF}...{$ENDIF}, и сам уже не помню что ещё :) Всё это требует памяти. К генерации кода по ходу разбора может потом и вернусь, но только для того чтобы всё-таки запустить это в 64 килобайтах :)
Максагор
01.02.2015, 21:41
iSDOS позволяет работать с винтами и довольно большими разделами (~30Mb).
Поправочка - 16Мб
Увы и ах, своего ничего не осталось после трагической гибели hdd с iSDOS.
Где-то в недрах тырнета должны попадаться обрывки документации, по крайней мере когда-то давно мне попадались.
А что было и что погибло?
Andrew771
02.02.2015, 12:13
Andrew771, какие типы поддерживает или будет поддерживать создаваемый компилятор? Указатели, массивы, структуры, указатели на структуры, многомерные массивы указателей на структуры...? У меня заложена поддержка всего этого, а ещё поддержка модулей, процедурных и файловых типов, полиморфных и inline-процедур, переопределение операторов, умная линковка, условная компиляция {$IFDEF}...{$ENDIF}, и сам уже не помню что ещё Всё это требует памяти. К генерации кода по ходу разбора может потом и вернусь, но только для того чтобы всё-таки запустить это в 64 килобайтах
Поддерживаются только типы Byte, Word, String, а также одномерные и двумерные массивы из них. Почему так - вот моя позиция (http://zx-pk.ru/showpost.php?p=484862&postcount=131). У тебя-то конечно всё по-максимуму поддерживается. Но нужно ли это на Спектруме?
На Спектруме может и не нужно, а вообще пригодится.
Немного статистики.
4900 строк, 127000 символов.
17500 токенов, 60000 символов. (т.е. комментарии составляют половину текста)
900 идентификаторов, около 100 килобайт для хранения.
8200 узлов синтаксического дерева, около 600 килобайт для хранения.
Не могу понять одну вещь. Почему так? Это особенность FPC или так и должно быть?
const
c1:array [1..10] of byte=(0,1,2,3,4,5,6,7,8,9);
c2:string='qwe';
c3='qwe';
var
p:pointer;
begin
p:=@c1; // Ok
p:=@c2; // Ok
p:=@c3; // Error: Can't take the address of constant expressions
end.
Andrew771
17.02.2015, 09:32
Не могу понять одну вещь. Почему так? Это особенность FPC или так и должно быть?
фиг знает. Видать, не нравится нетипизированная константа.
---------- Post added at 09:32 ---------- Previous post was at 09:30 ----------
возможно, в компилированный код подставляет непосредственное значение, а не хранит его в памяти в отдельной ячейке. Поэтому отсутствует физически указатель.
Ну да,
It is not possible to get the address of a constant, because they aren't stored in memory, you can try making it a typed constant.
но всё равно не понимаю.
Andrew771
18.02.2015, 10:54
но всё равно не понимаю.
При компиляции в код подставляется непосредственно значение константы, а не ссылка на ячейку с ней. Т.е., к примеру, если константа в ЯВУ задана ccc=2, то в компилируемом коде подставляется ld a,2, а не ld a,(ccc). А эта ссс вообще не записывается нигде. Поэтому и указатель на нее невозможно создать.
То есть если этой константе, которая явно string, не указать тип, то в памяти она не хранится? :)
Andrew771
19.02.2015, 11:10
По-видимому, хранится непосредственно в команде в качестве аргумента.
Вот столько памяти компилятору нужно для обработки самого себя:
LEX
before: 5382 lines, 143737 chars
after: 18924 tokens, 64656 chars
SYNTAX
930 IDs // sizeof=70 bytes, total 65100
677 vars // sizeof=14 bytes, total 9478
188 subrs // sizeof=79 bytes, total 14852
178 types // sizeof=32 bytes, total 5696
8503 nodes // sizeof=71 bytes, total 603713
Хранить синтаксическое дерево полностью не требуется, достаточно хранить только для одной обрабатываемой в данный момент подпрограммы, тогда оно займёт не более 30 килобайт.
Плюс сам компилятор (на данный момент 50 килобайт, но будет больше).
Итого, чтобы компилятор мог собрать сам себя на целевой системе нужна система с каким-то диском и минимум 256 кБайт RAM. IBM PC AT? :)
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot