Re: Proposal for a Guile binary file format

[Marius Vollmer <mvo at zagadka dot ping dot de>]

Mikael Djurfeldt <mdj@thalamus.nada.kth.se> writes:

> It is possible to introduce 4-word cells so that doubles can be
> stored on the heap instead.  I expect such a change to bring Guile
> floating point arithmetic up to approximately the same speed as its
> integer arithmetic.

Maybe it would be easier to just have a quicklist for doubles.  [ I
don't know if `quicklist' is the correct term or if that term is
established.  Errm.  It's just a the usual linked stack of memory
blocks that are all the same size ans where you allocate and free by
popping and pushing the stack. ]

> Here's a proposal for a Guile binary format which would speed up
> that part.
> 
> It can (I hope) be used at two levels:
> 
> 1. Storing the internal representation for Guile source.
> 2. Storing memoized source.

This reminds me of the freezer.  It tried to do something like that,
but used the dynamic linker to load the frozen heap segments.  That
is, it produced C code, compiled that code to an ELF shared library
for example, and then linked that at run-time.

A nice effect of using the linker could be that frozen heaps would be
shared among guile processes, if the heaps would be read only.  So I
think one design criterion of the binary format should also be to make
the loaded heaps as much constant as possible so that sharing can
occur.  I think this is difficult to achieve with the current
representation of executable code as cons cells.

If I remember right, the freezer only showed a significant speed up
when I went to the trouble of freezing only memoized source code.  For
that, the freezer contained its own very special version of the
evaluater that didn't really evaluate, it only memoized.  Reading and
consing the source into the heap is probably not very time-consuming,
but memoizing might be.

Given the legendary tightness of the evaluator, it might be too
involved to keep the memoizer in sync.  Maybe the evaluator can be
extended to be a memoizer, optionally.

Another, longer road would be to have some kind of bytecode format and
compile to that.  I know that Aubrey says his tree code evaluator is
actually faster thgan a bytecode one, and I think he might just be
right.  On the other hand, it might be that he is only saying that
treecodes are faster when you profile both the compilation *and*
execution phases.  I find it hard to believe that executing bytecodes
must be slower tham executing treecodes.  (Maybe we shouldn't really
be thinking "byte"codes here, but rather linearily arranged wordcodes
or something.)  This would also allow us to take the `constness
requirement' into account.

I would pay the price of slower loading of uncompiled Scheme source
when we would instead have a good compiler that produces binary code
that can be loaded fast and executes fast.  On the other hand, other
Schemes probably have such a thing already.  How fast are they?

The golden road would probably be to compile to native machine code,
but I don't think we have the resources to make that happen for enough
interesting platforms in a reasonable amount of time.

> A module chunk consists of 8 blocks:
> 
> 1. Header
> 2. Permanent heap block
> 3. Permanent malloc block
> 4. Standard heap block
> 5. Standard malloc block
> 6. Symbol table
> 7. Patch table

I could imagine that the number of patches would be quite large, on
the order of the number of cons cells in the heap blocks.  Would it be
possible to have `implicit' patches in the cons cells themselves?
That is the cells in the heap have their correct tags and thus
pointers could be identified just by looking at the cons cell.  No
need for a patch entry.

Ok, to summarize, my gut feeling is that a binary format for
unmemoized source code might not give us a significant speedup, but
I'm not sure.

- Marius

-- 
(let ((p #(78 91 29 77 90 51 71 91 86 24 54 55 119 16 104 62 42 58 121 80 10
124 48 102 79 22 12 116 27 34 37 100 16 83 115 40 126)))  (define (x n)  (do
((i 0 (1+ i))  (s 0 (+ s (* (vector-ref p i)  (expt n i)))))  ((= i 37) s)))
(do ((i 1 (1+ i))) ((= i 38)) (display (integer->char (modulo (x i) 127)))))