Storage management for an implementation of SNOBOL4
David R. Hanson · Software Practice and Experience · 1977
Abstract The implementation of the SNOBOL4 programming language requires some scheme for dynamic allocation and reclamation of storage. This paper describes the method used in a machine‐dependent implementation of SNOBOL4 called SITBOL. Available storage is divided into two regions: one for the allocation of storage for permanent or immovable objects and one for objects that are subject to reclamation. Reclamation is accomplished by a four‐phase algorithm, which includes marking, address adjustment and compaction. The reclamation process is supplemented by several heuristics that reduce the cost of reclamation and increase the amount of storage reclaimed. The storage overhead of the technique is analysed and compared with an alternate method. Some empirical measurements of actual SNOBOL4 programs are given that substantiate the results of the analysis.