Efficient Memory Management in a Single Stack Prolog Machine
Xining Li
To appear at the 2nd International Conference on Principles and Practice of
Declarative Programming (PPDP 2000), Montreal, Canada, September 20-22, 2000
Abstract
Traditional Prolog implementations are based on the stack/heap memory
architecture: the stack holds local variables and control information,
whereas the heap stores data objects which outlive procedure activations.
A stack frame can be deallocated when an activation ends while heap space
can only be reclaimed on backtracking or by garbage collection. Conventional
garbage collection methods may yield poor performance. In this paper, I
present a novel memory management approach used in the implementation of
Logic Virtual Machine (LVM). The LVM is a simple Prolog abstract machine
with a small, clean instruction set. It combines the stack and the heap into
a single memory block for all dynamical memory requirements, supports
coarse-grain two-stream unification, and embeds an efficient garbage
collection algorithm, the Chronological Garbage Collection (CGC), to
reclaim useless memory cells. An experimental LVM emulator has been
implemented. Our experimental results show that the proposed approach
has low runtime overhead, good virtual memory and cache performance, and
very short, evenly distributed pause times during garbage collection.
Some benchmarks even revealed that the CGC not only improves the program's
cache performance by more than enough to pay its own cost, but also improves
the program execution performance which is competitive with the SICStus
fast-code.
Keywords: logic virtual machine, garbage collection, high performance