После просмотра нескольких ответов о переполнении стека становится ясно, что некоторые скомпилированные в нативе языки имеют сборку мусора . Но мне неясно, как именно это будет работать.
Я понимаю, как сборка мусора может работать с интерпретированным языком. Сборщик мусора будет просто работать рядом с интерпретатором и удалять неиспользуемые и недоступные объекты из памяти программы. Они оба бегут вместе.
Как это будет работать со скомпилированными языками? Насколько я понимаю, как только компилятор скомпилировал исходный код в целевой код - в частности, машинный код - это делается. Его работа закончена. Так как же скомпилированная программа может быть собрана сборщиком мусора?
Работает ли компилятор с процессором каким-то образом во время выполнения программы для удаления «мусорных» объектов? Или компилятор включает минимальный сборщик мусора в исполняемый файл скомпилированной программы.
Я полагаю, что мое последнее утверждение будет более обоснованным, чем первое из-за этой выдержки из этого ответа о переполнении стека :
Одним из таких языков программирования является Eiffel. Большинство компиляторов Eiffel генерируют C-код по причинам переносимости. Этот C-код используется для создания машинного кода стандартным C-компилятором. Реализации Eiffel предоставляют GC (и иногда даже точный GC) для этого скомпилированного кода, и нет необходимости в VM. В частности, компилятор VisualEiffel генерировал собственный машинный код x86 напрямую с полной поддержкой GC .
Последнее утверждение, кажется, подразумевает, что компилятор включает некоторую программу в конечный исполняемый файл, который действует как сборщик мусора во время работы программы.
Страница на веб-сайте языка D о сборке мусора, которая скомпилирована нативно и имеет дополнительный сборщик мусора, также, похоже, намекает на то, что некоторая фоновая программа запускается вместе с исходной исполняемой программой для реализации сборки мусора.
D - язык системного программирования с поддержкой сборки мусора. Обычно нет необходимости явно освобождать память. Просто выделите по мере необходимости, и сборщик мусора будет периодически возвращать всю неиспользованную память в пул доступной памяти.
Если метод упомянутый выше будет использоваться, как именно он будет работать? Сохраняет ли компилятор копию какой-либо программы сборки мусора и вставляет ее в каждый исполняемый файл, который он генерирует?
Или я ошибаюсь в своих мыслях? Если да, какие методы используются для реализации сборки мусора для скомпилированных языков и как именно они будут работать?
источник
malloc().Ответы:
Сборка мусора на скомпилированном языке работает так же, как на интерпретируемом языке. В таких языках, как Go, используются трассирующие сборщики мусора, хотя их код обычно компилируется в машинный код заранее.
(Трассировка) сборка мусора обычно начинается с обхода стеков вызовов всех потоков, которые в данный момент работают. Объекты в этих стеках всегда живы. После этого сборщик мусора обходит все объекты, на которые указывают живые объекты, пока не будет обнаружен весь граф живых объектов.
Понятно, что для этого требуется дополнительная информация, которую такие языки, как C, не предоставляют. В частности, требуется карта фрейма стека каждой функции, которая содержит смещения всех указателей (и, вероятно, их типы данных), а также карты всех макетов объектов, которые содержат одинаковую информацию.
Однако легко увидеть, что языки, которые имеют строгие гарантии типов (например, если приведение указателей к различным типам данных запрещено) действительно могут вычислять эти карты во время компиляции. Они просто хранят связь между адресами команд и картами стековых кадров и связь между типами данных и картами размещения объектов внутри двоичного файла. Эта информация затем позволяет им выполнять обход объекта графа.
Сам сборщик мусора - это не что иное, как библиотека, связанная с программой, похожая на стандартную библиотеку C. Например, эта библиотека может предоставить функцию, аналогичную
malloc()той, которая запускает алгоритм сбора, если нагрузка на память высока.источник
Звучит некрасиво и странно, но да. Компилятор имеет целую библиотеку утилит, содержащую гораздо больше, чем просто код сборки мусора, и вызовы этой библиотеки будут вставляться в каждый исполняемый файл, который он создает. Это называется библиотека времени выполнения , и вы будете удивлены, как много разных задач она обычно выполняет.
источник
malloc()иfree()не встроены в язык, не являются частью операционной системы, но функции в этой библиотеке. C ++ также иногда компилируется с библиотекой сборки мусора, хотя язык не был разработан с учетом GC.dynamic_castработают такие вещи, как make и исключения, даже если вы не добавляете GC.main(), и вполне законно, скажем, запускать поток GC в этом коде. (Предполагая, что GC не выполняется внутри вызовов выделения памяти.) Во время выполнения GC действительно нужно знать, какие части объекта являются указателями или ссылками на объекты, и компилятору необходимо выдать код, чтобы перевести ссылку на объект на указатель. если ГХ перемещает объекты.crt0.o(что означает « С R ип T IME, самые основы»), который получает связанный с каждой программой (или , по крайней мере , каждой программы , которая не является свободно стоящая ).Это странный способ сказать «компилятор связывает программу с библиотекой, которая выполняет сборку мусора». Но да, это то, что происходит.
В этом нет ничего особенного: компиляторы обычно связывают тонны библиотек с программами, которые они компилируют; в противном случае скомпилированные программы не смогли бы ничего сделать без повторной реализации многих вещей с нуля: даже для записи текста на экран / в файл /… требуется библиотека.
Но может быть, GC отличается от этих других библиотек, которые предоставляют явные API, которые вызывает пользователь?
Нет: в большинстве языков библиотеки времени выполнения выполняют большую часть закулисной работы без общедоступного API, кроме GC. Рассмотрим эти три примера:
Таким образом, библиотека сборки мусора вовсе не является особенной, и априори не имеет ничего общего с тем, была ли программа скомпилирована заранее.
источник
Ваша формулировка неверна. Язык программирования является спецификацией написано в каком - то техническом отчете (для наглядного примера, см R5RS ). На самом деле вы имеете в виду какую-то конкретную языковую реализацию (которая является программным обеспечением).
(Некоторые языки программирования имеют плохие спецификации или даже отсутствуют, или просто соответствуют некоторому примеру реализации; тем не менее, язык программирования определяет поведение - например, он имеет синтаксис и семантику - он не является программным продуктом, но может быть реализуется некоторым программным продуктом; многие языки программирования имеют несколько реализаций, в частности, «скомпилированный» - это прилагательное, применяемое к реализациям, даже если некоторые языки программирования легче реализуются интерпретаторами, чем компиляторами.)
Обратите внимание, что интерпретаторы и компиляторы имеют слабое значение, и некоторые языковые реализации могут рассматриваться как оба. Другими словами, между ними существует континуум. Прочитайте последнюю книгу Dragon Book и подумайте о байт-коде , JIT-компиляции , динамически испускаемом C-коде, который компилируется в некоторый «плагин», а затем выполняется dlopen (3) тем же процессом (и на современных машинах это достаточно быстро, чтобы быть совместимым с интерактивный REPL , смотрите это )
Я настоятельно рекомендую прочитать руководство GC . Чтобы ответить, нужна целая книга . Перед этим прочтите вики-страницу « Сборка мусора» (которую, я полагаю, вы прочитали до прочтения ниже).
Система времени выполнения реализации скомпилированного языка содержит сборщик мусора, и компилятор генерирует код, который подходит для этой конкретной системы времени выполнения. В частности, примитивы распределения (скомпилированы в машинный код, который) будут (или могут) вызывать систему времени выполнения.
Просто путем выдачи машинного кода, который использует (и является «дружественным» и «совместимым с») систему времени выполнения.
Обратите внимание, что вы можете найти несколько библиотек для сборки мусора, в частности Boehm GC , MPS Рэйвенбрука или даже мою (необслуживаемую) Qish . И кодирование простого GC не очень сложно (однако отладка сложнее, а кодирование конкурентного GC затруднительно ).
В некоторых случаях компилятор будет использовать консервативный GC (например, Boehm GC ). Тогда не так много кода. Консервативный GC (когда компилятор вызывает свою процедуру выделения или всю процедуру GC) иногда сканирует весь стек вызовов и предполагает, что любая зона памяти (косвенно), достижимая из стека вызовов, является активной. Это называется консервативным GC, потому что информация о типе теряется: если целое число в стеке вызовов выглядит как какой-то адрес, за ним следуют и т. Д.
В других (более сложных) случаях среда выполнения обеспечивает сборку мусора при копировании поколений (типичным примером является компилятор Ocaml, который компилирует код Ocaml в машинный код с использованием такого GC). Тогда проблема заключается в том, чтобы точно найти в стеке вызовов все указатели, и некоторые из них перемещаются GC. Затем компилятор генерирует метаданные, описывающие кадры стека вызовов, которые использует среда выполнения. Таким образом, соглашения о вызовах и ABI становятся специфичными для этой реализации (то есть компилятора) и системы времени выполнения.
В некоторых случаях машинный код, сгенерированный компилятором (на самом деле даже замыкания, указывающие на него) , сам по себе является сборщиком мусора . Это особенно относится к SBCL (хорошая реализация Common Lisp), которая генерирует машинный код для каждого взаимодействия REPL . Это также требует некоторых метаданных, описывающих код и используемые в нем кадры вызова.
Вроде, как бы, что-то вроде. Однако система времени выполнения может быть общей библиотекой и т. Д. Иногда (в Linux и некоторых других системах POSIX) она может даже быть интерпретатором сценариев, например, передаваться в execve (2) с помощью shebang . Или переводчик ELF , см. Elf (5) и
PT_INTERPт. Д.Кстати, большинство компиляторов для языка со сборкой мусора (и их системой времени выполнения) сегодня являются свободным программным обеспечением . Поэтому скачайте исходный код и изучите его.
источник
Array#[], O (1) наихудший случай,Hash#[]O (1) амортизированный наихудший случай). И последнее, но не менее важное: мозг Матца.Уже есть несколько хороших ответов, но я хотел бы прояснить некоторые недоразумения, стоящие за этим вопросом.
Там нет такого понятия, как «нативно скомпилированный язык» как таковой. Например, тот же код Java был интерпретирован (а затем частично скомпилирован во время выполнения) на моем старом телефоне (Java Dalvik) и (заранее) скомпилирован на моем новом телефоне (ART).
Разница между выполнением кода и его интерпретацией гораздо менее строгая, чем кажется. Для работы обоих требуются библиотеки времени выполнения и операционная система (*). Интерпретируемый код нуждается в интерпретаторе, но интерпретатор - это только часть времени выполнения. Но даже это не является строгим, поскольку вы можете заменить интерпретатор компилятором (точно в срок). Для максимальной производительности вы можете захотеть и того и другого (среда выполнения Java для настольных компьютеров содержит интерпретатор и два компилятора).
Независимо от того, как запустить код, он должен вести себя одинаково. Выделение и освобождение памяти - это задача для среды выполнения (как открытие файлов, запуск потоков и т. Д.). На вашем языке вы просто пишете
new X()или похожи. Спецификация языка говорит, что должно произойти, и среда выполнения это делает.Выделяется некоторая свободная память, вызывается конструктор и т. Д. Когда памяти недостаточно, вызывается сборщик мусора. Поскольку вы уже находитесь во время выполнения, которое является нативным фрагментом кода, существование интерпретатора не имеет значения вообще.
Там действительно нет прямой связи между интерпретацией кода и сборкой мусора. Просто низкоуровневые языки, такие как C, предназначены для скорости и детального контроля всего, что не вписывается в идею неродного кода или сборщика мусора. Так что есть только корреляция.
Это было очень верно в старые времена, когда, например, интерпретатор Java был очень медленным, а сборщик мусора довольно неэффективным. В наше время все сильно отличается, и говорить о интерпретируемом языке уже не имеет смысла.
(*) По крайней мере, если говорить о коде общего назначения, оставляя в стороне загрузчики и тому подобное.
источник
java myprogявляется настолько же или менее родным, какgrep myname /etc/passwdилиld.so myprog: Это исполняемый файл (что бы это ни значило), который принимает аргумент и выполняет операции с данными.Детали варьируются между реализациями, но обычно это некоторая комбинация следующего:
В инкрементном и параллельном GC скомпилированный код и GC должны взаимодействовать для поддержки некоторых инвариантов. Например, в копирующем коллекторе GC работает, копируя текущие данные из пространства A в пространство B, оставляя позади мусор. Для следующего цикла он переворачивает A и B и повторяется. Таким образом, одно правило может заключаться в том, чтобы в любой момент, когда пользовательская программа пытается сослаться на объект в пространстве A, это обнаруживается, и объект немедленно копируется в пространство B, где программа может продолжать доступ к нему. Адрес пересылки остается в пространстве A, чтобы указать GC, что это произошло, так что любые другие ссылки на объект обновляются по мере их отслеживания. Это известно как «барьер для чтения».
Алгоритмы GC изучались с 60-х годов, и существует обширная литература по этому вопросу. Google, если вы хотите больше информации.
источник