[m-dev.] Rust backend?

[Zoltan Somogyi]

On Sat, 20 Sep 2025 00:47:39 +0200, Fabrice Nicol <fabrnicol at gmail.com> wrote:

> Thank you Zoltan for your clear reply, this is pretty much in line with
> what I thought.
> 
> Yes, I did check the PhD-related papers on RBMM before asking. As they
> looked promising, I wondered whether any progress had been made ever since.

Unfortunately, the answer is "no".

> Two points though:
> 
> 1. The original implementation of GNU Prolog did *not* resort to GC, this
> is made very clear in Diaz & al. 2010,  "On the Implementation of GNU
> Prolog", p. 29.   Clearly confirmed in a 2013 SO reply by Diaz. In a
> nutshell, they do not do dynamic heap allocation, they instead mmap all
> stacks in virtual memory and use swap. Stack sizes are controlled via env
> vars and generously set on startup. They may have been trying to fiddle
> with GC of late,  anyway it is not an essential part of the gprolog
> implementation.

I just had a look again at Diaz and Codognet: Design and implementation of
the GNU Prolog system, section 7 of which is about memory management.

It says they *do* do dynamic heap allocation. They even have a memory area
they call the heap, even though the standard name of this area in the WAM
is the extremely confusing "global stack".

Yes, they use virtual memory, but that is because *all* processes use virtual
memory on pretty much any operating system that is not intended for
hard-real-time systems. The use of mmap to deny access to the last page
of a given memory area is a stock-standard technique for detecting overflows
that are about to occur; Mercury has been using the same technique since
the beginning. It is NOT a technique for doing memory allocation; it is
simply a technique for detecting impending failure by memory exhaustion.
On some systems, this detection is what triggers a garbage collection.

I also direct your attention to the very last sentence of section 7, which says
that they *want* to use gc, even if they don't (didn't) have it yet. Note that
the WAM, which GNU Prolog is based on, requires a garbage collector for
any program that runs for more than a few seconds. (The actual limit is
available memory divided by allocation rate.)

The much later paper that you cite, does state on page 29 that they still
do not have a garbage collector, but they also effectively acknowledge that this is
a severe limitation. Since this paper came out when I was leaving academia,
it is not surprising I don't remember having read it at the time.

> It arose from my pro experiences with Rust over the past 2 years. I came to
> be aware of GC footprint both on RAM use and execution speed a bit more
> acutely than I used to be in younger years. A quick look at older Mercury
> benchmarks (in which GC is deactivated on command line or alternatively is
> not) confirms that GC footprints may be quite significant too.

If you are talking about the ten tiny benchmark programs we used in the original
JLP paper on Mercury, that was not a fair comparison between the gc and non-gc
versions of Mercury. The reason is that to get measurable run times, we had to
execute each microbenchmark many times. At the start of each iteration, the non-gc
versions simply reset their stack and heap pointers to the start of their respective areas,
which not only effectively collected all the memory allocated by the previous
iteration in two instructions, it also ensured that all iterations used the same
range of addresses, meaning that all iterations after the first could operate basically
out of the cache, not memory. (These benchmarks were so tiny, the memory they used
fit into the cache.) The Boehm collector's memory could not be recovered in this way,
so the performance difference between the non-gc and Boehm gc versions measures
not just the cost of gc, but also the difference between a hot cache and a cold cache,
i.e. the difference between cache speed and memory speed.

By the way, the reason why we used those microbenchmarks was that the Prolog
systems we were comparing Mercury to *could* reset all their memory areas
with a few instructions (that is one of the points of using a failure-driven loop in Prolog),
and the comparison was designed to be fair between the Prolog systems
and the non-gc version of Mercury.

Overall, I would say "yes, gc does impose a cost in runtime, but some such cost
has to be paid by *any* method of memory management you may choose,
and in a world dominated by interpreted languages such as Javascript and Python,
there are many much easier and more worthwhile performance wins available".

Zoltan.