Συλλογή απορριμμάτων (υπολογιστές)

Στην πληροφορική, η συλλογή απορριμμάτων (αγγλ. garbage collection ή GC) είναι μια μορφή αυτόματης διαχείρισης μνήμης η οποία λειτουργεί στο υπόβαθρο, κατά την εκτέλεση ενός προγράμματος. Ο συλλέκτης απορριμμάτων (garbage collector), η απλώς συλλέκτης, είναι συνήθως ένα νήμα του συστήματος (π.χ. του λειτουργικού συστήματος ή μιας εικονικής μηχανής επί της οποίας εκτελείται το βασικό πρόγραμμα) σχεδιασμένο κάθε φορά που ενεργοποιείται να απελευθερώνει τα τρέχοντα απορρίμματα: τη μνήμη την οποία καταναλώνουν τα αντικείμενα που το πρόγραμμα δεν χρησιμοποιεί πια. Η συλλογή απορριμμάτων εφευρέθηκε από τον Τζον Μακάρθι το 1959 για να λύσει προβλήματα της γλώσσας προγραμματισμού Lisp.
Η συλλογή απορριμμάτων συχνά εμφανίζεται σαν το αντίθετο της χειροκίνητης διαχείρισης μνήμης, η οποία απαιτεί από τον προγραμματιστή να ορίζει ποια αντικείμενα μπορούν να απομακρυνθούν από τη μνήμη. Πολλά συστήματα όμως συνδυάζουν τις δύο προσεγγίσεις, μαζί με άλλες τεχνικές όπως η δέσμευση μνήμης στη στοίβα και η εξαγωγή περιοχών (region inference).
Περιορισμένοι πόροι εκτός της μνήμης, όπως π.χ. οι δικτυακές υποδοχές, τα χειριστήρια βάσεων δεδομένων (database handles), τα παράθυρα για αλληλεπίδραση με τον χρήστη και οι περιγραφείς αρχείων και συσκευών, δεν επηρεάζονται από τη συλλογή απορριμμάτων. Υπάρχουν άλλες μέθοδοι για τη διαχείριση αυτών των πόρων, όπως οι καταστροφείς, που μπορούν να διαχειριστούν ακόμα και τη μνήμη, με αποτέλεσμα να μην χρειάζεται συλλογή απορριμμάτων. Κάποια συστήματα συλλογής απορριμμάτων επιτρέπουν σε αυτούς τους άλλους πόρους να σχετίζονται με μια περιοχή στη μνήμη, η οποία, όταν συλλεχθεί, να προκαλέσει την αποδέσμευση των πόρων, κάτι που ονομάζεται οριστικοποίηση (finalization). Αυτό όμως μπορεί να προκαλέσει περιπλοκές, όπως οι σημαντικές καθυστερήσεις μεταξύ της παύσης της χρήσης και της αποδέσμευσης σημαντικά περιορισμένων πόρων, ή η έλλειψη ελέγχου σχετικά με το ποιο νήμα θα κάνει την αποδέσμευση.

Ανιχνευτική συλλογή απορριμμάτων

Οι ανιχνευτικοί συλλέκτες απορριμμάτων (tracing garbage collectors) είναι ο συνηθέστερος τύπος συλλεκτών απορριμμάτων. Αρχικά εντοπίζουν τα αντικείμενα που είναι προσιτά (reachable) ή αυτά που θα μπορούσαν να είναι προσιτά, και στη συνέχεια αποδεσμεύουν όλα τα υπόλοιπα αντικείμενα.

Ισχυρές και ασθενείς αναφορές

Ο συλλέκτης απορριμμάτων μπορεί να αποδεσμεύει μόνο αντικείμενα προς τα οποία δεν υπάρχουν αναφορές. Μπορούν όμως να υπάρχουν κάποιες αναφορές, οι οποίες δεν εμποδίζουν την αποδέσμευση, οι οποίες ονομάζονται ασθενείς αναφορές (weak references). Όταν οι ασθενείς αναφορές συγκρίνονται με τις συνηθισμένες αναφορές, οι τελευταίες τότε μπορεί να ονομάζονται και ισχυρές αναφορές (strong references). Ένα αντικείμενο τότε συλλέγεται όταν δεν υπάρχουν ισχυρές (δηλαδή κανονικές) αναφορές, ακόμα και αν υπάρχουν ασθενείς αναφορές σε αυτό.
Μια ασθενής αναφορά δεν είναι απλά ένας οποιοσδήποτε δείκτης σε ένα αντικείμενο για το οποίο δεν ενδιαφέρεται ο συλλέκτης απορριμμάτων. Ο όρος συνήθως χρησιμοποιείται για μια ειδικά διαχειριζόμενη κατηγορία ειδικών αναφορών, που είναι ασφαλείς στη χρήση, ακόμα και όταν το αντικείμενό τους εξαφανιστεί, γιατί τότε αποκτούν κάποια ειδική και ασφαλή τιμή. Μια αναφορά που δεν είναι ασφαλής και ο συλλέτης απορριμμάτων δεν γνωρίζει για αυτήν, θα μείνει «αιωρούμενη» (dangling) γιατί θα συνεχίσει να αναφέρεται σε μια διεύθυνση μνήμης, όπου το αντικείμενο ήταν στο παρελθόν. Αυτό δεν είναι ασθενής αναφορά.

Ασθενείς συλλογές

Υπάρχουν αντικείμενα που διατηρούν δείκτες προς συλλογές από άλλα αντικείμενα και τα παρακολουθούν με ασθενή τρόπο. Για παράδειγμα, υπάρχουν ασθενείς πίνακες κατακερματισμού (weak hash tables). Όπως και σε έναν κανονικό πίνακα κατακερματισμού, σε έναν ασθενή πίνακα κατακερματισμού διατηρείται μια σχέση μεταξύ αντικειμένων σε ζεύγη, με κάθε ζεύγος να είναι ένα κλειδί και μια τιμή. Ο πίνακας κατακερματισμού όμως δε διατηρεί κάποια ισχυρή αναφορά προς αυτά τα αντικείμενα. Όταν ένα κλειδί ή μια τιμή γίνει απόρριμμα η εγγραφή στον πίνακα διαγράφεται στιγμιαία. Υπάρχουν επίσης περιπτώσεις τέτοιων πινάκων που έχουν μόνο ασθενή κλειδιά και οι αναφορές κλειδιών είναι ισχυρές ή το αντίθετο (ισχυρά κλειδιά και ασθενείς τιμές).
Οι ασθενείς πίνακες κατακερματισμού είναι σημαντικοί γιατί δίνουν τη δυνατότητα αποθήκευσης σχέσεων μεταξύ αντικειμένων, αλλά με τρόπο που τα αντικείμενα της σχέσης να μπορούν να γίνουν απορρίμματα αν τίποτα στο πρόγραμμα δεν έχει αναφορές προς αυτά (εκτός από τον ίδιο τον πίνακα). Αντίθετα, η χρήση ενός απλού πίνακα κατακερματισμού για αυτόν τον σκοπό θα οδηγούσε σε διαρροή μνήμης.

Βασικός αλγόριθμος

Η ανιχνευτική συλλογή απορριμμάτων ονομάζεται έτσι γιατί ανιχνεύει όλον τον χώρο εργασίας στη μνήμη. Η συλλογή γίνεται σε κύκλους. Ένας κύκλος αρχίζει όταν ο συλλέκτης αποφασίζει (ή λάβει ειδοποίηση) ότι χρειάζεται να αποδεσμεύσει μνήμη, κάτι που συνήθως συμβαίνει όταν το σύστημα δεν έχει μνήμη ελεύθερη. Η αρχική μέθοδος περιλάμβανε ένα απλό «μαρκάρισμα-και-σκούπισμα» (mark-and-sweep), στο οποίο όλος ο χώρος εργασίας εξετάζεται μία ή περισσότερες φορές.

Απλό μαρκάρισμα-και-σκούπισμα

Στο απλό μαρκάρισμα-και-σκούπισμα, κάθε αντικείμενο στη μνήμη έχει ένα πεδίο (συνήθως ένα bit) που προορίζεται για χρήση αποκλειστικά από τη συλλογή απορριμμάτων. Το πεδίο αυτό συνήθως είναι κενό, εκτός από τη διάρκεια του κύκλου συλλογής απορριμμάτων. Το πρώτο στάδιο της συλλογής διατρέχει ελεύθερα όλο το σύνολο των ριζών ('root set'), μαρκάροντας κάθε αντικείμενο προς το οποίο υπάρχει δείκτης, σαν σε χρήση ('in-use'). Επίσης μαρκάρονται και όλα τα αντικείμενα στα οποία δείχνουν τα αντικείμενα που ήδη μαρκαρίστηκαν, και ούτω καθεξής, μέχρι να μαρκαριστεί κάθε αντικείμενο στο οποίο μπορεί να φτάσει κανείς μέσω δεικτών από τις ρίζες. Στο τέλος, σκανάρεται όλη η μνήμη από την αρχή μέχρι το τέλος και εξετάζονται όλα τα ελεύθερα ή χρησιμοποιούμενα μέρη: όσα αντικείμενα εξακολουθούν να έχουν κενό το πεδίο 'σε χρήση', δεν είναι προσιτά από το πρόγραμμα ή τα δεδομένα του και η μνήμη που καταναλώνουν αποδεσμεύεται. (Στα αντικείμενα που έχουν μαρκαριστεί σαν 'σε χρήση', το πεδίο αυτό καθαρίζεται για τον επόμενο κύκλο συλλογής απορριμμάτων.)
Η μέθοδος αυτή έχει διάφορα μειονεκτήματα, με το κυριότερο να είναι ότι όλο το υπόλοιπο σύστημα πρέπει να σταματήσει κατά τη διάρκεια της συλλογής επειδή απαγορεύεται κάθε αλλαγή του χώρου της μνήμης. Αυτό έχει σαν αποτέλεσμα τα προγράμματα να 'παγώνουν' περιστασιακά (και απροειδοποίητα), αποκλείοντας έτσι τις εφαρμογές πραγματικού χρόνου. Επιπλέον, πρέπει να εξεταστεί όλη η μνήμη που χρησιμοποιείται, συχνά δύο φορές, κάτι που μπορεί να προκαλέσει προβλήματα σε συστήματα με μνήμη σε σελίδες (paged memory).

Στρατηγικές υλοποίησης

Για την υλοποίηση του βασικού αλγορίθμου τριών χρωμάτων πρέπει να ληφθούν κάποιες σημαντικές σχεδιαστικές αποφάσεις, οι οποίες επηρεάζουν σημαντικά την ταχύτητα της συλλογής απορριμμάτων.

Συλλογή απορριμμάτων σε γενεές

Έχει παρατηρηθεί ότι σε πολλά προγράμματα, τα πρόσφατα δημιουργημένα αντικείμενα είναι και αυτά που είναι και πιο πιθανό να μην είναι προσιτά σύντομα, κάτι που είναι γνωστό και ως βρεφική θνησιμότητα (infant mortality) ή γενεαλογική υπόθεση (generational hypothesis). Η συλλογή απορριμμάτων σε γενεές (generational garbage collection ή ephemeral garbage collection) χωρίζει τα αντικείμενα σε γενεές και, στους περισσότερους κύκλους, θα τοποθετήσει μόνο τα αντικείμενα ενός υποσυνόλου των γενεών αυτών στο αρχικό άσπρο σύνολο. Επιπλέον, το σύστημα χρόνου εκτέλεσης διατηρεί πληροφορίες για τις αναφορές μεταξύ των γενεών, παρακολουθώντας τη δημιουργία και την ενημέρωση των αναφορών. Όταν εκτελείται ο συλλέκτης απορριμμάτων, μπορεί να χρησιμοποιήσει αυτήν την πληροφορία για να αποδείξει ότι κάποια αντικείμενα στο αρχικό άσπρο σύνολο δεν είναι προσιτά χωρίς να πρέπει να διατρέξει ολόκληρο το δέντρο των αναφορών. Αν η γενεαολογική υπόθεση ισχύει, αυτό έχει σαν αποτέλεσμα πιο γρήγορους κύκλους συλλογής, ενώ συλλέγονται τα πιο πολλά προσιτά αντικείμενα.
Για να υλοποιηθεί αυτή η ιδέα, πολλοί συλλέκτες απορριμμάτων αυτού του είδους χρησιμοποιούν διαφορετικές περιοχές μνήμης για αντικείμενα διαφορετικών ηλικιών. Όταν μια περιοχή γεμίσει, τα αντικείμενα στα οποία αναφέρονται περιοχές με μεγαλύτερη ηλικία αντιγράφονται στην επόμενη περιοχή, και ολόκληρη η περιοχή μπορεί τότε να χρησιμοποιηθεί για νέα αντικείμενα. Αυτή η τεχνική επιτρέπει πολύ γρήγορη σταδιακή (incremental) συλλογή απορριμμάτων, γιατί χρειάζεται μόνο συλλογή απορριμμάτων για μια περιοχή κάθε φορά.
Η συλλογή απορριμμάτων σε γενεές είναι μια ευριστική προσέγγιση και κάποια μη προσιτά αντικείμενα δε μπορούν να αποδεσμευτούν κατά τη διάρκεια κάθε κύκλου. Μπορεί επομένως σποραδικά να χρειάζεται να διενεργείται ένα πλήρες μαρκάρισμα και σκούπισμα ή μια συλλογή απορριμμάτων με αντιγραφή, για την αποδέσμευση όλου του διαθέσιμου χώρου. Τα συστήματα χρόνου εκτέλεσης των σύγχρονων γλωσσών προγραμματισμού (όπως η Java και το .NET Framework) συνήθως χρησιμοποιούν κάποια υβριδική στρατηγική που συνδυάζει τις στρατηγικές που ήδη αναφέρθηκαν. Για παράδειγμα, οι περισσότεροι κύκλοι συλλογής μπορεί να εξετάζουν μόνο κάποιες γενεές, ενώ κάποιες φορές συμβαίνει μαρκάρισμα και σκούπισμα, και ακόμα πιο σπάνια μια πλήρης αντιγραφή, ώστε να ελέγχεται ο κατακερματισμός (fragmentation). Οι όροι "minor cycle" και "major cycle" χρησιμοποιούνται κάποιες φορές για να περιγράψουν αυτά τα διαφορετικά επίπεδα συλλογής.

Stop-the-world, προσθετική και σύγχρονη συλλογή απορριμμάτων

Οι απλοί συλλέκτες απορριμμάτων σταματούν εντελώς την εκτέλεση του προγράμματος (stop-the-world) για να εκτελέσουν έναν κύκλο συλλογής, εξασφαλίζοντας ότι δεν θα δεσμευτούν νέα αντικείμενα, ούτε κάποια αντικείμενα πρόκειται να γίνουν απρόσιτα κατά τη συλλογή απορριμμάτων.
Το φανερό μειονέκτημα αυτής της τεχνικής είναι ότι το πρόγραμμα δεν μπορεί να συνεχίσει τις εργασίες του όταν γίνεται η συλλογή απορριμμάτων και προκύπτει μια παύση ("embarrassing pause"). Αυτό έχει σαν αποτέλεσμα η συλλογή απορριμμάτων τύπου stop-the-world να είναι κατάλληλη κυρίως για προγράμματα χωρίς αλληλεπίδραση με τον χρήστη. Το πλεονέκτημά της είναι ότι είναι πιο εύκολο να υλοποιηθεί και εκτελείται πιο γρήγορα σε σχέση με την προσθετική συλλογή απορριμμάτων.
Οι προσθετικοί (incremental) και οι σύγχρονοι (concurrent) συλλέκτες απορριμμάτων έχουν σχεδιαστεί έτσι ώστε να μειώνουν αυτήν την «αναστάτωση» κατά την εκτέλεση, παρεμβάλλοντας τις εργασίες τους στις δραστηριότητες του κύριου προγράμματος. Οι προσθετικοί συλλέκτες απορριμμάτων κάνουν συλλογή απορριμμάτων σε διακριτές φάσεις, επιτρέποντας την εκτέλεση του προγράμματος ανάμεσα στις φάσεις αυτές (και κάποιες φορές και κατά τη διάρκεια κάποιων από αυτές). Οι σύγχρονοι συλλέκτες απορριμμάτων δεν σταματούν καθόλου την εκτέλεση του προγράμματος, εκτός ίσως για το μικρό χρονικό διάστημα που σαρώνεται η στοίβα του προγράμματος. Όλες μαζί οι προσθετικές φάσεις όμως παίρνουν περισσότερο χρόνο για να εκτελεστούν, σε σύγκριση με ένα πέρασμα συνολικής συλλογής απορριμμάτων, επομένως οι συλλέκτες απορριμμάτων αυτού του είδους μπορεί να κάνουν λιγότερο έργο ανά μονάδα χρόνου.
Οι τεχνικές αυτές απαιτούν προσεκτική σχεδίαση ώστε να μην υπάρχουν ανεπιθύμητες αλληλεπιδράσεις μεταξύ του προγράμματος και του συλλέκτη απορριμμάτων. Για παράδειγμα, όταν το πρόγραμμα θελήσει να δεσμεύσει χώρο για κάποιο νέο αντικείμενο, το σύστημα χρόνου εκτέλεσης μπορεί να το σταματήσει μέχρι να ολοκληρωθεί η εκτέλεση, ή να ειδοποιήσει με κάποιον τρόπο τον συλλέκτη απορριμμάτων ότι υπάρχει ένα νέο, προσιτό αντικείμενο.

Ακριβής/συντηρητική συλλογή απορριμμάτων και εσωτερικοί δείκτες

Οι συλλέκτες που μπορούν να αναγνωρίσουν σωστά όλους τους δείκτες (αναφορές) σε ένα αντικείμενο ονομάζονται ακριβείς (precise, exact ή accurate), ενώ το αντίθετο είναι οι συντηρητικοί (conservative) ή μερικώς συντηρητικοί (partly conservative) συλλέκτες. Οι συντηρητικοί συλλέκτες υποθέτουν ότι κάθε αλληλουχία bit στη μνήμη μπορεί να είναι δείκτης αν, ερμηνευόμενη σαν δείκτης, θα έδειχνε σε κάποιο αντικείμενο που έχει δεσμευτεί στη μνήμη. Οι συντηρητικοί συλλέκτες μπορεί να αναγνωρίσουν σαν δείκτες λάθος δεδομένα (false positives), με αποτέλεσμα να μην αποδεσμεύεται μνήμη λόγω λάθους αναγνώρισης. Αυτό στην πράξη δεν είναι πάντα πρόβλημα, εκτός και αν το πρόγραμμα χειρίζεται πολλά δεδομένα που μπορούν να αναγνωριστούν λανθασμένα σαν δείκτες. Οι περιπτώσεις λανθασμένης αναγνώρισης προκαλούν γενικά λιγότερα προβλήματα σε συστήματα 64-bit σε σχέση με τα συστήματα 32-bit επειδή το εύρος των έγκυρων διευθύνσεων μνήμης τείνει να είναι ένα πολύ μικρό υποσύνολο του εύρους των τιμών 64-bit. Για αυτόν τον λόγο, είναι σπάνιο κάποια αλληλουχία των 64 bit να μοιάζει με κάποιον έγκυρο δείκτη. Το αν ένας ακριβής συλλέκτης απορριμμάτων εξυπηρετεί στην πράξη εξαρτάται από τις ιδιότητες ασφάλειας τύπων (type safety) της εκάστοτε γλώσσας προγραμματισμού. Ένα παράδειγμα που χρειάζεται συντηρητικός συλλέκτης απορριμμάτων είναι η γλώσσα C, η οποία επιτρέπει την μετατροπή μεταξύ δεικτών με τύπο (όχι void) και δεικτών χωρίς τύπο (void).
Ένα σχετικό θέμα είναι αυτό των εσωτερικών δεικτών (internal pointers), που είναι οι δείκτες στα πεδία ενός αντικειμένου. Αν η σημασιολογία της γλώσσας επιτρέπει εσωτερικούς δείκτες, τότε μπορούν να υπάρχουν πολλές διαφορετικές διευθύνσεις που να αναφέρονται σε μέρη του ίδιου αντικειμένου, κάτι που περιπλέκει την απόφαση αν ένα αντικείμενο είναι απόρριμμα ή όχι. Ένα παράδειγμα είναι η γλώσσα C++, στην οποία η πολλαπλή κληρονομικότητα μπορεί να δημιουργήσει δείκτες προς αντικείμενα βάσης, οι οποίοι να έχουν διαφορετικές διευθύνσεις. Ακόμα και σε γλώσσες όπως η Java, μπορούν να εμφανίζονται εσωτερικοί δείκτες κατά τον υπολογισμό, για παράδειγμα, της διεύθυνσης ενός στοιχείου ενός πίνακα. Σε ένα πρόγραμμα που έχει υποστεί βελτιστοποίηση, ο αντίστοιχος δείκτης στο ίδιο το αντικείμενο μπορεί να έχει ενημερωθεί στον καταχωρητή στον οποίο βρίσκεται – αυτό σημαίνει ότι πρέπει να γίνεται σάρωση που να βρίσκει αυτούς τους δείκτες.

Συλλογή απορριμμάτων σε πραγματικό χρόνο

Αν και η συλλογή απορριμμάτων είναι γενικά μη ντετερμινιστική, μπορεί να χρησιμοποιηθεί σε συστήματα αυστηρά πραγματικού χρόνου (hard real-time). Ένας συλλέκτης πραγματικού χρόνου μπορεί να εγγυηθεί ότι, στη χειρότερη περίπτωση, θα παραχωρήσει έναν συγκεκριμένο αριθμό υπολογιστικών πόρων στο τμήμα του προγράμματος που χρειάζεται τη μνήμη. Οι περιορισμοί που ακολουθεί ένας συλλέκτης πραγματικού χρόνου βασίζονται συνήθως είτε στον φόρτο εργασίας (work based), είτε στον χρόνο (time based). Ένας περιορισμός στον χρόνο θα μπορούσε να είναι ο εξής: σε κάθε χρονικό παράθυρο διάρκειας T, το πρόγραμμα θα πρέπει να εκτελείται τουλάχιστον για χρόνο Tm. Στην περίπτωση της ανάλυσης του φόρτου εργασίας, χρησιμοποιείται συνήθως το μέγεθος MMU (minimal mutator utilization).
Μια από τις πρώτες υλοποιήσεις συλλογής απορριμμάτων πραγματικού χρόνου για την JVM αφορούσε τον αλγόριθμο Metronome. Υπάρχουν επίσης άλλες εμπορικές υλοποιήσεις.

Escape analysis

Η ανάλυση διαφυγής (escape analysis) μπορεί να χρησιμοποιηθεί για να μετατρέψει τη δέσμευση χώρου στον σωρό σε δέσμευση στη στοίβα, μειώνοντας το έργο του συλλέκτη απορριμμάτων.

Συλλογή απορριμμάτων κατά τη μεταγλώττιση

Η συλλογή απορριμμάτων κατά τη μεταγλώττιση (compile-time garbage collection) είναι μια μορφή στατικής ανάλυσης που επιτρέπει στη μνήμη να επαναχρησιμοποιείται και να απελευθερώνεται με βάση αναλλοίωτες συνθήκες που είναι γνωστές από τη φάση της μεταγλώττισης. Αυτή η μορφή συλλογής απορριμμάτων μελετήθηκε στη γλώσσα προγραμματισμού Mercury.

Διαθεσιμότητα

Οι γλώσσες προγραμματισμού υψηλού επιπέδου είναι πιο πιθανό να έχουν σαν βασικό χαρακτηριστικό τη συλλογή απορριμμάτων. Οι γλώσσες που δεν περιλαμβάνουν συλλογή απορριμμάτων, μπορούν να την αποκτήσουν με τη βοήθεια εξωτερικών βιβλιοθηκών (όπως ο συλλέκτης απορριμμάτων του Boehm για τη C και τη C++). Αυτό δεν είναι πάντα χωρίς προβλήματα, αφού αλλάζουν οι μηχανισμοί δημιουργίας και καταστροφής των αντικειμένων.
Οι περισσότερες συναρτησιακές γλώσσες προγραμματισμού, όπως η ML, η Haskell και η APL, περιλαμβάνουν συλλογή απορριμμάτων. Ο ίδιος ο μηχανισμός εμφανίστηκε για πρώτη φορά στη Lisp, η οποία και εισήγαγε τον συναρτησιακό προγραμματισμό.
Άλλες δυναμικές γλώσσες, όπως η Ruby (αλλά όχι η Perl 5, ή η PHP, που χρησιμοποιούν καταμέτρηση αναφορών), τείνουν επίσης να χρησιμοποιούν συλλογή απορριμμάτων. Οι αντικειμενοστρεφείς γλώσσες όπως η Smalltalk, η Java και η ECMAScript συχνά ενσωματώνουν συλλογή απορριμμάτων. Εξαιρέσεις αποτελούν η C++ και η Delphi, οι οποίες έχουν συναρτήσεις καταστροφής (destructors). Η Objective-C στο παρελθόν δεν είχε συλλογή απορριμμάτων, αλλά η ObjC 2.0 που υλοποιήθηκε από την Apple για το Mac OS X χρησιμοποιεί έναν δικό της συλλέκτη στο χρόνο εκτέλεσης, ενώ το εγχείρημα GNUstep χρησιμοποιεί έναν συλλέκτη Boehm.
Ιστορικά, οι γλώσσες που απευθύνονταν σε αρχάριους, όπως η BASIC και η Logo, συχνά χρησιμοποιούσαν συλλογή απορριμμάτων για τύπους δεδομένων μεταβλητού μήκους που αποθηκεύονταν στον σωρό, όπως οι συμβολοσειρές και οι λίστες, ώστε να μην δυσκολεύουν τον προγραμματιστή με λεπτομέρειες διαχείρισης μνήμης. Στους πρώτους μικροϋπολογιστές, που είχαν μικρές μνήμες και αργούς επεξεργαστές, η συλλογή απορριμμάτων της BASIC συχνά προκαλούσε τυχαίες και (για τον χρήστη) ανεξήγητες παύσεις κατά την εκτέλεση του προγράμματος. Κάποιοι διερμηνείς της BASIC όπως ο Applesoft BASIC της οικογένειας των Apple II, είχαν πολύ αργούς συλλέκτες απορριμμάτων για τις συμβολοσειρές, που σάρωναν συνέχεια τις συμβολοσειρές για να τοποθετήσουν αυτές με την υψηλότερη διεύθυνση, στις υψηλότερες θέσεις μνήμης (high memory). Αυτή η επανάληψη για μια συμβολοσειρά κάθε φορά είχα σαν αποτέλεσμα πολυπλοκότητα χρόνου O(N*N) όσον αφορά τον αριθμό των συμβολοσειρών, που μπορούσε να διακόψει προσωρινά την εκτέλεση προγραμμάτων που έκαναν συχνή χρήση συμβολοσειρών, ακόμα και για ένα λεπτό. Ένας άλλος συλλέκτης απορριμμάτων για την Applesoft BASIC που δημοσιεύτηκε στο Call-A.P.P.L.E. (Ιανουάριος 1981, σελ. 40–45, Randy Wiggington) έβρισκε μια ομάδα συμβολοσειρών σε κάθε πέρασμα στον σωρό, με αποτέλεσμα μια παύση των δύο λεπτών να γίνεται ενός δευτερολέπτου, ανάλογα και με το μέγεθος της ομάδας. Δημοσιεύτηκαν και άλλες προσεγγίσεις, αλλά καμία δεν έφτασε να μπει σε κάποια νεότερη έκδοση του διερμηνέα της BASIC.

Περιορισμένα περιβάλλοντα

Η συλλογή απορριμμάτων σπάνια χρησιμοποιείται σε ενσωματωμένα συστήματα ή σε συστήματα πραγματικού χρόνου, όπου απαιτείται πολύ αυστηρός έλεγχος της χρήσης των περιορισμένων διαθέσιμων πόρων. Παρόλα αυτά, έχουν αναπτυχθεί συλλέκτες για τέτοια περιορισμένα περιβάλλοντα. Το .NET Micro Framework της Microsoft και η Java Platform, Micro Edition είναι ενσωματωμένες πλατφόρμες λογισμικού, οι οποίες, όπως και οι μεγαλύτερες εκδόσεις τους, περιλαμβάνουν συλλογή απορριμμάτων.