Collecte des ordures et informations sur le type d'exécution

Question

La question du correctnum m'a amené à un autre avis. question que je me demandais depuis longtemps.

De nombreux documents en ligne sur la récupération de place n'indiquent pas comment les informations de type à l'exécution peuvent être implémentées. Par conséquent, je connais beaucoup de choses sur toutes sortes d'éboueurs, mais pas vraiment sur la manière de les mettre en œuvre.

La solution fixnum est en fait assez agréable, il est très clair que la valeur est un pointeur et celle qui ne l’est pas. Quelles sont les autres solutions couramment utilisées pour stocker les informations de type?

De plus, je m'interroge sur fixnum -thing. Cela ne signifie-t-il pas que vous êtes limité à des fixnums sur chaque index de tableau? Ou existe-t-il une solution de rechange pour obtenir des entiers complets sur 64 bits?

Answer 1

Pour obtenir un marquage précis, vous avez besoin de métadonnées indiquant les mots utilisés comme pointeurs et ceux qui ne le sont pas.

Ces métadonnées pourraient être stockées par référence, comme le fait emacs. Si, pour votre langage / implémentation, vous ne vous souciez pas de l'utilisation de la mémoire, vous pouvez même créer des références plus grandes que des mots (peut-être deux fois plus grandes), afin que chaque référence puisse contenir des informations de type ainsi que ses données d'un mot. De cette façon, vous pourriez obtenir un nombre fixe de points nuls d’un pointeur 32 bits, au prix de références 64 bits.

Alternativement, les métadonnées pourraient être stockées avec d'autres informations de type. Ainsi, par exemple, une classe peut contenir, ainsi que la table de pointeur de fonction habituelle, un bit par mot de la structure de données indiquant si le mot contient ou non une référence qui doit être suivie par le garbage collector. Si votre langue dispose d'appels virtuels, vous devez déjà disposer d'un moyen de déterminer, à partir d'un objet, les adresses de fonction à utiliser. Le même mécanisme vous permettra de déterminer les données de marquage à utiliser. En général, vous ajoutez un pointeur secret supplémentaire à le début de chaque objet, pointant vers la classe qui constitue son type d'exécution. De toute évidence, avec certains langages dynamiques, les données de type indiquées doivent être copiées sur écriture, car elles sont modifiables.

La pile peut faire la même chose - stocke les informations de marquage précises dans des sections de données du code lui-même et fait en sorte que le ramasse-miettes examine le compteur de programme enregistré et / ou les pointeurs de liens de la pile, et / ou d'autres informations placées sur le disque. pile par le code à cette fin, pour déterminer le code auquel chaque bit de pile se rapporte et donc quels mots sont des pointeurs. Les mécanismes d'exception légers ont tendance à faire la même chose pour stocker des informations sur l'endroit où le code essaye / attrape, et bien sûr, les débogueurs doivent aussi pouvoir interpréter la pile, de sorte que cela puisse très probablement être intégré à un tas d'autres choses. vous seriez déjà prêt à implémenter n’importe quel langage, y compris ceux avec un système de récupération de place intégré.

Notez que la récupération de place ne nécessite pas de marquage précis. Vous pouvez traiter chaque mot comme un pointeur, qu'il soit réellement ou non, recherchez-le dans la "grande liste de tout" du collecteur de mémoire. décider si elle peut faire référence de manière plausible à un objet qui n'a pas encore été marqué et, le cas échéant, la traiter comme une référence à cet objet. C’est simple, mais le coût est bien sûr qu’il se situe entre "assez lent" et et "très lent", en fonction des structures de données que votre gc utilise pour la recherche. De plus, il arrive parfois qu'un entier ait la même valeur que l'adresse d'un objet non référencé et vous oblige à conserver tout un tas d'objets qui auraient dû être collectés. Un tel ramasse-miettes ne peut donc pas offrir de garanties fortes quant à la collecte continue d'objets non référencés. Cela pourrait convenir à une implémentation de jouet ou à une première version de travail, mais il est peu probable qu'il soit populaire auprès des utilisateurs.

Une approche mixte pourrait, par exemple, effectuer un marquage précis des objets, mais pas des zones de la pile où les choses deviennent particulièrement poilues. Par exemple, si vous écrivez un JIT pouvant créer du code dans lequel une adresse d'objet référencée apparaît uniquement dans des registres, pas dans les emplacements de pile habituels, vous devrez peut-être ne pas suivre avec précision la région de la pile où le système d'exploitation stocke les registres lorsqu'il a déplacé le fil en question pour exécuter le ramasse-miettes. Ce qui est probablement assez fastidieux, donc une approche raisonnable (pouvant entraîner un code plus lent) consisterait à imposer au JIT de toujours conserver une copie de toutes les valeurs de pointeur utilisées sur la pile correctement marquée.

Answer 2

Dans Squeak (également Scheme et de nombreux autres langages dynamiques, je suppose), vous avez SmallInteger , la classe des entiers 31 bits signés et des classes pour les entiers arbitrairement grands, par exemple. LargePositiveInteger . Il pourrait très bien exister d’autres représentations, des nombres entiers de 64 bits, soit sous forme d’objets complets, soit avec quelques bits, sous la forme "Je ne suis pas un pointeur". drapeaux.

Mais les méthodes arithmétiques sont codées pour gérer les flux supérieurs / inférieurs. Ainsi, si vous en ajoutez un à SmallInteger maxVal , vous obtenez 2 ^ 30 + 1 en tant qu'instance de LargePositiveInteger et si vous en soustrayez un, vous récupérez 2 ^ 30 en tant que SmallInteger .