Memory Organization

The Jekejeke Prolog system is based on the notion of interpreter and knowledge base Java objects. We will explain how these objects are laid out in memory and how they basically interact. The Java virtual machine allocates to each thread its own stack. The stack size is a parameter during the creation of the thread. During their execution, the threads then share the heap where the Java objects reside.

Picture 1: Memory Organization

The Java virtual machine automatically reclaims used heap and stack space by means of a garbage collection. When a thread dies the stack space is returned. When a Java object is not anymore referenced by the stack of a living thread either directly or via other Java objects than its heap space is returned. The reclamation of Java objects is done periodically or when certain conditions meet. There is no means to explicitly return heap space.

The knowledge base consists basically of a set of clauses, which are in turn Java objects. These clauses can be referenced and manipulated during the execution of a Prolog program. We did not need to implement any special mechanism for the reclaim of clauses, since we delegated the process fully to the Java virtual machine. When a clause is removed it will not be any more referenced by the knowledge base. If an active thread does not anymore use the clause, it will then automatically be removed by the garbage collection sooner or later.

Whether an interpreter organization benefits from automatic garbage collection is less obvious. The interpreter will need a new frame whenever he performs a resolution step with another clause. The basic backtracking algorithm will create and release frames in high frequency and it could benefit from explicitly returned heap space. Also there are hardly any references between frames that could be used by an automatic garbage collector since it will not understand the indexing structure of Prolog variables into frames.

The Java virtual machine offers help here in the form of generation scavenging. This means that the Java virtual machine can distinguishes between young and old objects, and young objects are faster and more often reclaimed than old objects. For the tip of the backtracking algorithm the interpreter fames will qualify for young objects. As a result these frames will be automatically reclaimed by the garbage collection very quickly. The performance is even better compared to explicit returned space, since the garbage collector can work in bulk.

Nevertheless having frames as allocated entities is costly. This holds for any Prolog system implementation. Therefore various optimizations have been developed over the time. The Jekejeke Prolog system implements a couple of these optimizations. We will explain them in the following sections. In the context of garbage collection, these optimizations have all in common that they try to archive either of the following: