SCBM-Prolog v1.60: Proof-Sequence Garbage Collection Boosts Performance to 14 MLIPS
I've just released SCBM-Prolog v1.60, which introduces garbage collection for proof sequences.
SCBM (Sasagawa Continuation Backtracking Model) is an alternative Prolog execution model I've been developing, based on doubly linked proof sequences rather than the traditional WAM architecture.
Until now, SCBM-Prolog had garbage collection for working memory, but not for the proof sequences themselves.
The new mechanism takes advantage of Prolog's backtracking semantics. When execution returns to a FIRST node and the corresponding proof sequence is restored, the proof objects created after that point can be reclaimed by restoring the saved allocation pointers.
Interestingly, adding this garbage collection mechanism actually improved execution speed!
On my 9-Queens benchmark, repeated 16 times, SCBM-Prolog achieved approximately 14.36 MLIPS.
My hypothesis is that reusing the proof-sequence memory improves CPU cache locality, possibly reducing L3 cache misses. This has not yet been confirmed through hardware performance counters.
I find this particularly interesting because garbage collection is usually associated with additional overhead, rather than improved performance.
SCBM-Prolog is still an experimental implementation, but the results suggest that this alternative execution model has considerable potential.
I've written a more detailed explanation, including the benchmark and implementation, on Medium:
Medium article: SCBM-Prolog Now Has Garbage Collection — Achieving 14 MLIPS on 9 Queens | by Kenichi Sasagawa | Nov, 2026 | Medium
Feedback, criticism, and technical discussion are very welcome!