Memory Management

EusLisp adopts a Fibonacci buddy memory management scheme in a single heap for every type of object. After running programs having different memory request characteristics, we have been convinced that Fibonacci buddy can allocate objects of various sizes equally fast, garbage-collects quickly without copying , and exhibits high memory utilization (the internal loss is 10 to 15% and the external loss is negligible). For multithreading, the second point, i.e., non-copying GC, is very important. If addresses of objects were changed by copying-GC, pointers in the stack and CPU registers of all thread contexts would have to be redirected to new locations, which is impossible or very difficult.

All memory allocation requests are handled by the alloc function at the lowest level. Alloc does mutex-locking because it manipulates the global database of free lists. Since we cannot predict when a garbage collection begins and which thread causes it, every thread must prepare for sporadic GCs. All pointers to living objects have to be arranged to be accessible by the GC anytime to prevent them from being reclaimed as garbage. This is done by storing the pointers to the most recently allocated objects in fixed slots of each context, instead of trusting they are maintained on the stacks.

Fig. 6 illustrates flow of threads requesting memory and forked inside GC to process marking and sweeping in parallel. Note that threads that do not request memory or manipulate pointers can run in parallel with the GC, improving real-time response of the low-level tasks such as signal processing and image acquisition.

Figure 6: Parallel threads requesting memory and GC running in parallel