Le coût du GC peut-il être négligé lors de l'analyse du temps d'exécution des structures de données les plus défavorables spécifiées dans un langage de programmation récupéré?

22

Je viens de réaliser que je supposais que la réponse à ma question était "oui" mais je n'ai pas de bonne raison. J'imagine qu'il y a peut-être un garbage collector qui n'introduit que le ralentissement pire des cas. Y a-t-il une référence définitive que je peux citer? Dans mon cas, je travaille sur une structure de données purement fonctionnelle et j'utilise Standard ML, si ces détails sont importants.O(1)

Et peut-être que cette question serait encore plus pertinente lorsqu'elle serait appliquée à des structures de données spécifiées, disons, en Java? Peut-être y a-t-il des discussions pertinentes sur les algorithmes / manuels de structure de données qui utilisent Java? (Je sais que Sedgewick a une version Java, mais j'ai uniquement accès à la version C.)

Maverick Woo
la source

Réponses:

17

Oui, gc est amorti à temps constant. Supposons que vous ayez un algorithme qui s'exécute pendant le temps avec un ensemble de travail maximal de taille k . Maintenant, notez que vous pouvez allouer au plus O ( n ) mots pendant l'exécution du programme, et que le coût en temps de l'exécution d'un ramasse-miettes de copie est O ( k ) (c'est-à-dire que le coût d'un GC est proportionnel au total quantité de données en direct). Donc, si vous exécutez le GC au plus O ( n / k ) fois, le coût total d'exécution est limité par O ( n )nkO(n)O(k)O(n/k)O(n)2kn/kkO(k)k

Cependant, un cas où la présence ou l'absence de gc n'est pas ignorable est lors de l'écriture de structures de données sans verrouillage. De nombreuses structures de données sans verrouillage modernes fuient délibérément la mémoire et s'appuient sur gc pour l'exactitude. En effet, à un niveau élevé, la façon dont ils fonctionnent consiste à copier des données, à y apporter des modifications et à essayer de les mettre à jour de manière atomique avec une instruction CAS, puis à exécuter cela en boucle jusqu'à ce que le CAS réussisse. L'ajout d'une désallocation déterministe à ces algorithmes les rend beaucoup plus complexes, et donc les gens ne s'en soucient pas souvent (d'autant plus qu'ils sont souvent ciblés sur des environnements de type Java).

EDIT: Si vous voulez des limites non amorties, le collecteur Cheney ne le fera pas - il scanne tout le live set à chaque fois qu'il est invoqué. Le mot clé pour google est "ramasser les ordures en temps réel", et Djikstra et al. et Steele a donné les premiers collecteurs de marquage et de balayage en temps réel, et Baker a donné le premier gc de compactage en temps réel.

@article {dijkstra1978fly,
  title = {{Collecte des ordures à la volée: un exercice de coopération}},
  auteur = {Dijkstra, EW et Lamport, L. et Martin, AJ et Scholten, CS et Steffens, EFM},
  journal = {Communications de l'ACM},
  volume = {21},
  nombre = {11},
  pages = {966--975},
  issn = {0001-0782},
  année = {1978},
  éditeur = {ACM}
}

@article {steele1975multiprocessing,
  title = {{Collecte des ordures de compactage multiprocessing}},
  auteur = {Steele Jr, GL},
  journal = {Communications de l'ACM},
  volume = {18},
  nombre = {9},
  pages = {495--508},
  issn = {0001-0782},
  année = {1975},
  éditeur = {ACM}
}

@article {baker1978list,
  title = {{Traitement des listes en temps réel sur un ordinateur série}},
  auteur = {Baker Jr, HG},
  journal = {Communications de l'ACM},
  volume = {21},
  nombre = {4},
  pages = {280--294},
  issn = {0001-0782},
  année = {1978},
  éditeur = {ACM}
}
Neel Krishnaswami
la source
unebuneb
1
"Oui, gc est amorti à temps constant". Ce n'est pas vrai en général. Vous pourriez faire valoir que le GC peut l' être, mais ils ne le sont pas nécessairement et les vrais ne le sont certainement pas. Par exemple, le naïf List.mapdans OCaml est en fait une complexité quadratique car la profondeur de la pile est linéaire et la pile est traversée chaque fois que la pépinière est évacuée. Il en va de même pour les tranches principales rencontrant de grands tableaux de pointeurs.
Jon Harrop
12

O(n)

O(1)

La référence définitive de collecte des ordures est:

  • Collecte des ordures par Richard Jones et Rafael Lin

Ben Zorn a fait un travail de mesure des coûts réels de différents algorithmes de collecte des ordures, bien que ce qui suit est un article plus récent qui présente une comparaison beaucoup plus complète:

Pour plus d'informations, voir:

Dave Clarke
la source