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


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