Управление памятью в Форт
Так что я только изучаю Форт и мне было любопытно, если бы кто-нибудь мог помочь мне понять, как вообще работает управление памятью. На данный момент у меня есть только (некоторый) опыт работы с парадигмой C stack-vs-heap.
Из того, что я понимаю, можно выделить в словаре или в куче. Словарь быстрее / предпочтительнее, чем стек в C? Но, в отличие от C, здесь нет областей действия и автоматического восстановления стека, поэтому мне интересно, используется ли словарь только для глобальных структур данных (если вообще используется).
Что касается кучи, это очень похоже на C? Является ли управление кучей стандартной концепцией ( ANS) или оно определяется реализацией?
7 ответов
Это не словарь, или в куче - эквивалентом кучи является словарь. Однако, с серьезным ограничением, что он действует больше как стек, чем куча - новые слова добавляются в конец словаря (выделение ALLOT и освобождение ЗАБЫТОМ или БЕСПЛАТНЫМ (но освобождение всех новых слов - действуя скорее как множественные СОЗ)).
Реализация может управлять макетом памяти и, таким образом, реализовывать традиционную кучу (или сборку мусора). Примером является четвертая реализация структуры данных кучи для управления памятью (1984). Еще одна реализация - динамические кучи памяти для Quartus Forth (2000).
Многое зависит от реализации или расширений. Например, структура памяти часто с двумя блочными буферами (расположение BLOCK а также TIB), буфер ввода текста и значения и низкоуровневые / примитивные функции языка, в нижней части, словарь в середине (растущий вверх) и стек возврата и стек параметров в верхней части 1.
Адрес первого доступного байта над словарем возвращается HERE (меняется по мере расширения словаря).
Над словарем также имеется область блокнота (адрес, возвращаемый PAD) для временного хранения данных. Область блокнота может рассматриваться как свободная память.
Предпочтительный режим работы - максимально использовать стек вместо локальных переменных или кучи.
1 стр. 286 (о конкретном издании Forth, MMSFORTH) в главе "Память, словарь и словари FORTH", Forth: текст и ссылка. Махлон Дж. Келли и Николас Шпионы. ISBN 0-13-326349-5 / 0-13-326331-2 (pbk.). 1986 Прентис-Холл.
На фундаментальный вопрос, возможно, не ответили так, как этого требовал бы новый пользователь Forth, поэтому я попытаюсь в нем разобраться.
Память в Forth может сильно зависеть от цели, поэтому я ограничусь описанием самой простой моделью - плоской областью памяти, в которой код и данные счастливо живут вместе. (в отличие от моделей с сегментированной памятью или флэш-памяти для кода и ОЗУ для данных или других более сложных моделей)
Словарь обычно начинается в нижней части памяти и выделяется системой Forth вверх. Два стека в простой системе должны существовать в старшей памяти и обычно иметь два регистра ЦП, указывающие на них. (Очень зависит от системы)
На самом фундаментальном уровне память выделяется просто путем изменения значения переменной указателя словаря. (иногда называется DP)
Программист обычно не обращается к этой переменной напрямую, а использует некоторые слова более высокого уровня для управления ею.
Как уже упоминалось, слово Forth "ЗДЕСЬ" возвращает следующий доступный адрес в словаре. Что не было упомянуто, так это то, что ЗДЕСЬ определяется путем извлечения значения переменной DP. (системная зависимость здесь, но полезно для описания)
В Forth 'ЗДЕСЬ' может выглядеть так:
: ЗДЕСЬ ( - адрес) DP @;
Вот и все.
Чтобы выделить память, нам нужно переместиться ЗДЕСЬ вверх и сделать это словом "ALLOT".
Определение Forth для 'ALLOT' просто берет число из стека параметров и добавляет его к значению в DP. Так что это не более чем:
: ALLOT (n -) DP +!; \ '+!' добавляет n к переменной содержимого DP
ALLOT используется системой FORTH, когда мы создаем новое определение, чтобы то, что мы создали, было безопасно в "ALLOTed" памяти.
Что-то, что не сразу очевидно, это то, что ALLOT может принимать отрицательное число, поэтому можно перемещать указатель словаря вверх или вниз. Таким образом, вы можете выделить немного памяти и вернуть ее так:
HEX 100 ALLOT
И освободи это так:
HEX -100 ALLOT
Все это говорит о том, что это самая простая форма управления памятью в системе Forth. Пример того, как это используется, можно увидеть в определении слова "BUFFER:"
: BUFFER: ( n -) СОЗДАТЬ ALLOT;
'BUFFER:' 'создает' новое имя в словаре (кстати, create использует allot, чтобы освободить место для имени), затем ALLOTs n байтов памяти сразу после имени и любые связанные служебные байты, которые ваша система Forth может использовать
Так что теперь, чтобы выделить блок именованной памяти, мы просто набираем:
MARKER FOO \ отметьте, где заканчивается память
HEX 2000 BUFFER: IN_BUFFER
Теперь у нас есть 8-байтовый буфер под названием IN_BUFFER. Если бы мы захотели освободить это место в Standard Forth, мы могли бы напечатать 'FOO', и все, что выделено в Словаре после FOO, будет удалено из системы Forth.
Но если вам нужна временная память, ВСЕ, что выше "ЗДЕСЬ", можно использовать бесплатно!
Таким образом, вы можете просто указать адрес и использовать его, если вам это нравится
: MYMEMORY здесь 200 +; \ MYMEMORY указывает на нераспределенную память выше ЗДЕСЬ
\ MYMEMORY moves with HERE. be aware.
MYMEMORY HEX 1000 ERASE \ заполните его 2K байтами нуля
Forth обычно использовался для высокопроизводительных встроенных приложений, где динамическое выделение памяти может вызывать ненадежный код, поэтому предпочтительным было статическое распределение с использованием ALLOT. Однако большие системы имеют кучу и используют ALLOCATE, FREE и RESIZE так же, как мы используем malloc и т. Д. В C.
BF
Питер Мортенсен изложил это очень хорошо. Я добавлю несколько заметок, которые могут помочь программисту Си.
Стек наиболее близок к тому, что С называет "автоматическими" переменными, и что обычно называют локальными переменными. Вы можете дать имена стековых значений в несколько раз, но большинство программистов пытаются написать свой код так, чтобы называть значения не нужно.
Словарь лучше всего рассматривать как "статические данные" с точки зрения программирования на Си. Вы можете зарезервировать диапазоны адресов в словаре, но в целом вы будете использовать ALLOT и связанные слова для создания статических структур данных и пулов, которые не меняют размер после выделения. Если вы хотите реализовать связанный список, который может расти в реальном времени, вы можете выделить ВСЕГО достаточно места для ячеек ссылок, которые вам понадобятся, и написать слова, чтобы поддерживать свободный список ячеек, из которых вы можете извлечь. Существуют, естественно, реализации такого рода вещей, и написание собственного - хороший способ отточить навыки управления указателями.
Распределение кучи доступно во многих современных Forths, и стандарт определяет слова ALLOCATE, FREE и RESIZE, которые работают как malloc(), free() и realloc() в C. Возвращаемая ими память - из системной кучи ОС, и это как правило, хорошая идея хранить адрес в переменной или какой-либо другой более постоянной структуре, чем в стеке, чтобы вы случайно не потеряли указатель, прежде чем сможете его освободить. Как примечание, эти слова (вместе со словами ввода / вывода файла) возвращают состояние в стеке, которое ненулевое, если произошла ошибка. Это соглашение прекрасно согласуется с механизмом обработки исключений и позволяет вам писать код вроде:
variable PTR
1024 allocate throw PTR !
\ do some stuff with PTR
PTR @ free throw
0 PTR !
Или для более сложного, хотя и несколько искусственного, примера размещения / освобождения:
\ A simple 2-cell linked list implementation using allocate and free
: >link ( a -- a ) ;
: >data ( a -- a ) cell + ;
: newcons ( a -- a ) \ make a cons cell that links to the input
2 cells allocate throw tuck >link ! ;
: linkcons ( a -- a ) \ make a cons cell that gets linked by the input
0 newcons dup rot >link ! ;
: makelist ( n -- a ) \ returns the head of a list of the numbers from 0..n
0 newcons dup >r
over 0 ?do
i over >data ! linkcons ( a -- a )
loop >data ! r> ;
: walklist ( a -- )
begin dup >data ? >link @ dup 0= until drop ;
: freelist ( a -- )
begin dup >link @ swap free throw dup 0= until drop ;
: unittest 10 makelist dup walklist freelist ;
С Forth вы попадаете в другой мир.
В типичном Forth, таком как Ciforth на Linux (и предполагается, что 64-битный), вы можете настроить свой Forth, чтобы иметь линейное пространство памяти, равное вашему пространству подкачки (например, 128 ГБ). Это ваше, чтобы заполнить массивами, связанными списками, фотографиями, что угодно. Там нет никаких ограничений. Forth только предоставляет вам указатель ЗДЕСЬ, чтобы помочь вам отслеживать память, которую вы использовали. Даже то, что вы можете игнорировать, и в стандарте 1994 года есть даже слово, которое предоставляет пространство для царапин, которое плавает в свободной памяти (PAD).
Есть ли что-то вроде malloc() free()? Не обязательно в маленьком ядре пару десятков килобайт. Но вы можете просто включить файл с утилитой allocate и выделить пару Гбайт для использования в качестве динамической памяти.
В качестве примера я сейчас работаю с TIFF-файлами. Типичная 140-мегабайтная картинка вынимает небольшой кусок из словаря, продвигаясь ЗДЕСЬ Строки пикселей преобразуются, распаковываются и т. Д. Для этого я использую динамическую память, поэтому я выделяю пространство для результата распаковки строки. Я должен вручную освободить их снова, когда результаты были использованы для другого преобразования. Это совершенно не похоже на с. Здесь больше контроля и больше опасности.
Ваш вопрос о областях и т. Д. В Forth, если вы знаете адрес, вы можете получить доступ к структуре данных. Даже если вы набросали F7FFA1003 на листе бумаги. Попытка сделать программы более безопасными с помощью отдельных пространств имен не характерна для стиля Forth. Так называемый список слов (см. Также словарь) предоставляет средства в этом направлении.
Некоторые реализации Forth поддерживают локальные переменные в кадре стека возврата и выделения блоков памяти. Например, в SP-Forth:
lib/ext/locals.f
lib/ext/uppercase.f
100 CONSTANT /buf
: test ( c-addr u -- ) { \ len [ /buf 1 CHARS + ] buf }
buf SWAP /buf UMIN DUP TO len CMOVE
buf len UPPERCASE
0 buf len + C! \ just for illustration
buf len TYPE
;
S" abc" test \ --> "ABC"
В большой комнате управления памятью FORTH прячется слоненок, и я не видел, чтобы слишком много людей упоминали об этом.
Канонический FORTH имеет как минимум неадресируемый стек параметров. Так обстоит дело со всеми известными мне реализациями оборудования FORTH (обычно исходящими от Чака Мура), которые имеют стек аппаратных параметров: он не отображается в адресуемое пространство памяти.
Что означает "неадресный"? Это означает: у вас не может быть указателей на стек параметров , т.е. нет средств для получения адресов вещей в этом стеке. Стек представляет собой «черный ящик», к которому вы можете получить доступ только через API стека (коды операций, если это аппаратный стек), не обходя его - и только этот API будет изменять его содержимое.
Это подразумевает отсутствие псевдонимов между стеком параметров и обращениями к памяти с использованием указателей - через
Это, конечно, не работает, когда можно получить указатели на стек параметров. Хорошо спроектированная система, вероятно, защитила бы API для такого доступа, поскольку внутри этой защиты генератор кода должен переливать все, от регистров до стека, то есть при отсутствии полного анализа потока данных.
DFA и другие «дорогие» методы оптимизации, конечно, не являются невозможными в FORTH, просто они немного шире, чем многие практические системы FORTH. Несмотря на это, они могут быть выполнены очень чисто (я использую оптимизации CFA, DFA и SSA во внутренней реализации FORTH, и все это имеет меньше исходного кода, включая комментарии, чем служебные классы в LLVM... - классы, которые используются повсеместно, но на самом деле не делают ничего, связанного с компиляцией или анализом кода).
Практическая система FORTH также может накладывать ограничения на псевдонимы на содержимое стека возврата, а именно на то, что сами адреса возврата не имеют псевдонимов. Таким образом, поток управления может быть оптимистично проанализирован, только принимая во внимание явный доступ к стеку через
В C и C ++ создание псевдонимов между автоматическими «локальными» переменными и указателями представляет собой большую проблему, потому что только большие компиляторы с большими оптимизаторами могут позволить себе доказать отсутствие псевдонима и отказаться от перезагрузки / сброса регистров при промежуточном разыменовании указателя. Маленькие компиляторы, чтобы оставаться совместимыми и не генерировать неработающий код, должны пессимизировать и предполагать, что доступ через псевдоним все, а доступ через
Обычно принуждение
Моя идея опубликована на https://sites.google.com/a/wisc.edu/memorymanagement. Я надеюсь вскоре разместить код на github. Если у вас есть массив (или несколько), каждый из которых содержит определенное количество элементов определенного размера, вы можете связать одноцелевой стек с каждым массивом. Стек инициализируется адресом каждого элемента массива. Чтобы выделить элемент массива, извлеките адрес из стека. Чтобы освободить элемент массива, поместите его адрес в стек.