[mercury-users] a theoretical problem

[Fergus Henderson]

On 24-Apr-2003, Tom Wouters <tom.wouters1 at student.kuleuven.ac.be> wrote:
> We're working on our thesis -it's about using logic programming for 
> robot-control- and we would like some insights on why it would, or 
> wouldn't be possible to run Mercury on an embedded processor wich only 
> has about 16Kbyte of memory available.

Was that 16K RAM, 16K ROM, or 16K total?

I think it would most likely be possible to run some Mercury programs on
such a system, with a few caveats.  The first major caveat is that the
garbage collection is not likely to be usable in such an environment.
The second caveat is that getting it all working would probably require
a lot of effort.  The third caveat is that although you can probably
squeeze Mercury to fit in 16K, with a lot of effort, once you've done so I
think you won't have any space left over to do anything useful.  (If your
embedded processor had 32k or 64k, that would make it a lot easier.)

What size address space does this processor use?  With 16 Kb in a 16-bit
address space, half of the addressable memory is in use; conservative
GC techniques don't work so well in such situations, where a large
proportion of the addresses in the address space are valid.
But with the Boehm (et al) collector, that would be the least of
your worries, since the code for the Boehm collector probably won't fit
in 16Kb anyway; it weighs in at something closer to 64k.
I don't know how hard it would be to reduce that.

If you need garbage collection, you might have more luck with our new
accurate collector (the hlc.agc grade), but even that collector uses
about 9K of code space, and furthermore since it is currently just
a simple two-space collector, it doubles the heap space requirements.
So if you've only got 16 Kb, I'd recommend avoiding GC, and instead using
semi-manual techniques to reclaim memory, such as heap reclamation on
failure and/or io__gc_call.

> We first tought mayby a stripped-down version of the language might 
> produce a runtime small enough to fit in the memory, but we don't realy 
> have a good idea how small the runtime could get (since terminal-io libs 
> etc aren't nescesairy) without losing the power of backtracking etc.

The runtime itself can be very small.  We haven't focussed on optimizing
that, since we've placed a higher priority on other properties, such as
flexibility, maintainability, etc.  For example, the current Mercury runtime
contains code for converting argc/argv to a Mercury list, for parsing the
MERCURY_OPTIONS environment variable, and so forth, none of which would
be necessary or desirable in an embedded environment with only 16K available.
There are also a lot of places in the current runtime and standard
library which drag in unnecessary code.

With the `--high-level-code' back-end, there's almost no need for a
runtime system at all -- for example, I can run the N-queens program
from tests/benchmarks/queens.m in the "hlc.gc" grade using a 128-byte
runtime and standard library, plus the Boehm collector, plus the C
standard library.  See the attached "tiny_runtime.c" file.

128-bytes, fantastic!  That will fit in 16K no problem.  However, that's
only half the story.  Of course the problem is that the Boehm collector
and the C library are a lot bigger than 128 bytes.

Using the "hlc" grade, and a slightly more complicated runtime -- see
the attached "tiny_runtime2.c" file -- avoids the need to link in the
Boehm collector.  This runtime is still less than 300 bytes, but now
we need to also link in a few of the files from the original Mercury
runtime directory (mercury_engine.o, mercury_thread.o, mercury_memory.o,
mercury_memory_zones.o, mercury_memory_handlers.o, and mercury_context.o)
for initializing the Mercury heap.  These use about 8k of code space,
most of which could probably eliminated by only including the parts
which are really needed (I didn't try that) and about 5k of data space,
most of which is not actually used (it can be reduced to about 1k
by changing the setting of MR_MAX_VIRTUAL_REG).  If you want to have
all of that, plus the relevant parts of the C library, plus some space
for a Mercury heap, then more optimization is needed before this will
fit into 16k.  But it is not too far off.

Even with the older `--no-high-level-code' back-end, the runtime
system could be made pretty small; all it really needs to do is
initialize the memory areas (heap, stacks, etc.)
I've also attached another file "tiny_runtime3.c" which works
in grade "asm_fast".  This needs to link in the same Mercury
runtime files as above, plus mercury_dummy.o and mercury_reg_workarounds.o.
The sizes are similar to the "hlc" grade, although I think the "hlc"
grade has more scope for improvement here than the "asm_fast" grade.

> So the actual question is how would you guys tackle the problem,
> and why would(n't) it be possible to run Mercury directly on the 
> embedded processor?

Firstly, compile everything with -ffunctions-sections -fdata-sections
in CFLAGS (this requires a moderately recent version of GCC)
and link with -Wl,--gc-sections (this requires a moderately recent
version of GNU binutils).  This should avoid dragging in a lot of
unnecessary code.

Secondly, pick the right grade: either "hlc", "asm_fast", or "hlc.agc",
depending on your needs; "hlc" will keep things smallest.

Thirdly, don't link in the ordinary Mercury runtime and standard
library; instead, start with one of the attached "tiny_runtime*.c" files.
Then, if you need to fit things in 16k, you'll still need to remove a
lot of the unnecessary stuff in the Mercury runtime files that do need
to get linked in, and probably also make changes to avoid linking in
unnecessary parts of the C library, such as sprintf().

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tiny_runtime.c
Type: text/x-csrc
Size: 335 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20030425/b1616daf/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tiny_runtime2.c
Type: text/x-csrc
Size: 2690 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20030425/b1616daf/attachment-0001.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tiny_runtime3.c
Type: text/x-csrc
Size: 2899 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20030425/b1616daf/attachment-0002.c>