Quels sont les avantages et les inconvénients de marquer les bits ensemble et séparément pour la collecte des déchets ?

Question

je regardais une vidéo Google IO 2008 - Composants internes de la machine virtuelle Dalvik pour comprendre comment fonctionne Dalvik VM et pourquoi ces personnes ont préféré Dalvik VM à JVM pour Android.J'ai trouvé qu'Android utilise une mémoire séparée pour les informations Garbage sur les objets, contrairement à la JVM où nous avons des bits de marque (bits indiquant si l'objet est capable ou non de collecter des déchets) avec les objets.

Quelqu'un peut-il me dire en détail quels sont les avantages et les inconvénients d'avoir une mémoire séparée pour les bits de marque et de ne pas avoir de mémoire séparée pour les bits de marque ?

Je n'ai pas pu obtenir cette différence en regardant une vidéo.

Answer 1

Quelques avantages d'un bitmap séparé:

• beaucoup plus dense. Un GC typique a peut-être besoin de huit bits de métadonnées GC, mais en raison de l'alignement, un en-tête d'objet peut arrondir cette mémoire jusqu'à 32 bits.
• Certaines opérations, en particulier autour du balayage, deviennent plus rapides. Ceci est en partie parce que le dense (voir ci-dessus) bitmap signifie moins de trafic mémoire et une meilleure utilisation de cache, mais aussi parce que certaines opérations (par exemple la mise à zéro, toutes les bits de marque) peuvent être vectorisées lors de ce format. (D'autres parties du GC doivent être conçues pour utiliser cette capacité.)
• Si vous généracodiCodeCode sur un système UNIX, une bitkark distincte utilise une meilleure utilisation de la copie-écriture: les pages contenant des objets peuvent rester partagées.

Quelques avantages des bits de marque d'objet:

• Selon le schéma utilisé pour associer des objets avec des bitmaps, obtenir le bit de marque pour un objet et inversement peut être assez compliqué et / ou lent. Un en-tête d'objet, d'autre part, est trivial à l'accès.
• faciliter la gestion de la mémoire: pas besoin de créer une allocation distincte de la taille de bonne taille et de la conserver en synchronisation.
• De nombreux régimes rapides pour trouver des bitmaps pour des objets et inversement sont assez restrictifs à d'autres égards. Par exemple, si vous créez un bitmap pour chaque page et stockez le pointeur Bitmap au début de la page, vous avez un problème de stockage d'objets plus gros qu'une page.

Answer 2

Les bits de marque séparés fonctionnent en ayant un tableau de bits où chaque bit représente une adresse dans le tas qui peut démarrer un objet.Par exemple, supposons que le tas fait 65 536 octets et que tous les objets sont alignés sur des limites de 16 octets, il y a alors 4 096 adresses dans le tas qui peuvent être le début d'un objet.Cela signifie que le tableau doit contenir 4 096 bits, qui peuvent être stockés efficacement sous forme de 512 octets ou 64 entiers non signés de 64 bits.

Les bits de marquage dans l'objet fonctionnent en définissant un bit de chaque en-tête de chaque objet sur 1 si l'objet est marqué et sur 0 sinon.Notez que cela nécessite que chaque objet ait une zone d'en-tête dédiée.Les environnements d'exécution tels que JVM et .NET ajoutent tous des en-têtes aux objets afin que vous obteniez essentiellement gratuitement l'espace pour le bit de marquage.

Mais cela ne fonctionne pas pour les collectionneurs conservateurs qui n'ont pas un contrôle total sur l'environnement dans lequel ils évoluent, comme le Boehm GC.Ils peuvent identifier à tort des entiers comme des pointeurs, donc pour eux, modifier quoi que ce soit dans le tas de données des mutateurs est risqué.

La collecte des déchets Mark & ​​Sweep est divisée en deux phases :marquage et balayage.Le marquage à l'aide de bits de marquage dans l'objet est simple (pseudo-code) :

if not obj.is_marked():
    obj.mark()
    mark_stack.append(obj)

En utilisant un tableau séparé pour stocker les bits de marque, nous devons convertir l'adresse et la taille des objets en indices dans le tableau de bits et définir les bits correspondants sur 1 :

obj_bits = obj.size_in_bytes() / 16
bit_idx = (obj - heap.start_address()) / 16
if not bitarr.bit_set(bit_idx):
    bitarr.set_range(bit_idx, obj_bits)
    mark_stack.append(obj)

Ainsi, dans notre exemple, si un objet fait 128 octets de long, 8 bits seront définis dans le tableau de bits.De toute évidence, utiliser des bits de marquage dans l'objet est beaucoup plus simple.

Mais les bits de marque séparés prennent un certain élan lors du balayage.Le balayage implique d'analyser l'ensemble du tas et de trouver des régions continues de mémoire qui ne sont pas marquées et peuvent donc être récupérées.En utilisant les bits de marquage dans l'objet, cela ressemblerait à ceci :

iter = heap.start_address()
while iter < heap.end_address():
    # Scan til the next unmarked object
    while iter.is_marked():
        iter.unmark()
        iter += iter.size()
        if iter == heap.end_address():
            return
    # At an unmarked block
    start = iter
    # Scan til the next marked object
    while iter < heap.end_address() and not iter.is_marked():
        iter += iter.size()
    size = iter - start
    # Reclaim the block
    heap.reclaim(start, size)

Notez comment l'itération passe d'un objet à l'autre dans le iter += iter.size() lignes.Cela signifie que la durée d'exécution de la phase de balayage est proportionnelle au nombre total d'objets actifs et indésirables.

En utilisant des bits de marque séparés, vous feriez à peu près la même boucle, sauf que de grandes bandes d'objets poubelles seraient survolées sans "s'arrêter" sur chacun d'eux.

Considérez à nouveau le tas 65536.Supposons qu’il contienne 4 096 objets qui sont tous des déchets.Itérer les 64 entiers de 64 bits dans le tableau de bits de marque et voir qu'ils sont tous 0 est évidemment très rapide.Par conséquent, la phase de balayage peut potentiellement être beaucoup plus rapide avec des bits de marquage séparés.

Mais il y a une autre ride !Dans tout collecteur de marquage et de balayage, le temps d'exécution est dominé par la phase de marquage et non par la phase de balayage qui est généralement très rapide.Le verdict est donc toujours tombé.Certains préfèrent les bits de marque séparés, d'autres préfèrent ceux intégrés à l'objet.À ma connaissance, personne n’a encore été en mesure de démontrer quelle approche est supérieure à l’autre.