Editing Garbage collection (computer science) (section)

=== BASIC ===
[[BASIC]] and [[Logo (programming language)|Logo]] have often used garbage collection for variable-length data types, such as strings and lists, so as not to burden programmers with memory management details. On the [[Altair 8800]], programs with many string variables and little string space could cause long pauses due to garbage collection.<ref name="MITS_1977"/> Similarly the [[Applesoft BASIC]] interpreter's garbage collection algorithm repeatedly scans the string descriptors for the string having the highest address in order to compact it toward high memory, resulting in [[Big O notation|<math>O(n^2)</math>]] performance<ref name="Hacker"/> and pauses anywhere from a few seconds to a few minutes.<ref name="Little_1985"/> A replacement garbage collector for Applesoft BASIC by [[Randy Wigginton]] identifies a group of strings in every pass over the heap, reducing collection time dramatically.<ref name="Fast_1981"/> BASIC.SYSTEM, released with [[ProDOS]] in 1983, provides a windowing garbage collector for BASIC that is many times faster.<ref name="Worth_1984"/>