Premium
Garbage collection of strings and linked data structures in real time
Author(s) -
Nilsen K.
Publication year - 1988
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380180704
Subject(s) - garbage collection , pointer (user interface) , computer science , string (physics) , character (mathematics) , garbage , manual memory management , copying , memory leak , c dynamic memory allocation , heap (data structure) , data structure , linked list , programming language , database , theoretical computer science , arithmetic , memory management , mathematics , artificial intelligence , geometry , overlay , law , political science , mathematical physics
Modern high‐level languages frequently need to collect garbage not only from regions of linked structures similar to LISP's dotted pairs, but also from string regions where data is organized as an array of characters. Some characteristics of string regions that make garbage collection particularly difficult are as follows: multiple pointers to the same characters within the array are allowed and encouraged; all possible character values are legitimate as data, so it is not possible to ‘mark’ a string by overwriting with a reserved character; and a character is generally much smaller than a pointer, so it is not possible to overwrite a single character value with a forwarding pointer to a new location for a particular string. This paper describes the addition of certain information to a string descriptor and enhancements to existing copying garbage collection algorithms that permit linked data structures and strings to be allocated and garbage collected from a shared region of memory in real time. This algorithm is real‐time in the sense that the time required for allocation of each basic unit of memory is bounded by a constant. An analysis of performance is reported, and comparisons are made with traditional garbage collection.