chicken-hackers
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Chicken-hackers] [PATCH] More efficient numbers integration through


From: Felix Winkelmann
Subject: Re: [Chicken-hackers] [PATCH] More efficient numbers integration through "scratchspace"
Date: Tue, 21 Apr 2015 12:11:18 +0200 (CEST)

> The scratch area is seen as an extension of the nursery: the
> C_demand() and C_stack_probe() checks will add the size of the scratch
> space to the stack's size, and trigger a minor GC when the sum of the
> two exceeds the maximum nursery size.

So this is just a heuristic, as the data in scratch-space never makes
it into the nursery, but will end up in the heap, right?

> This has been solved by adding a level of indirection: bignums are now
> represented exactly like in the "numbers" egg, as a record that contains
> two slots: the type (##sys#bignum) and a string that holds the binary
> representation of the bignum's digit words.  When a bignum is allocated,
> the record itself is _always_ allocated on the stack, and the string is
> allocated in the scratch space.  The memory location of the slot
> containing the string is recorded in scratch space, in a machine word
> just preceding the string.  This "back pointer" functions in a way that
> looks a lot like the mutation stack: it remembers what slots need to be
> looked at when reallocating.  Because numbers are "atomic" in Scheme, we
> can also assume that nothing else is going to mutate this slot.

Ingenious.

> To visualise this, the memory layout of the scratch space looks like this:
> 
>     ------------------------------------------------------------------- 
> LO | size_0 | slot_0 | ..digits.. | ... | size_n | slot_n | ..digits.. | HI
>     ------------------------------------------------------------------- 
> 
> If we take "LO" to be the starting address of the scratch space and look at
> the first word that's stored there, we first see a "size_0" which indicates
> how many words the first object uses.  If we calculate (LO + size_0 + 2),
> we reach the location of size_1, and so on, until we reach the address of
> size_n.  If we add size_n + 2 to the address of size_n, we go beyond "HI",
> which is the scratch space's upper bound (stored in C_scratchspace_limit).

Are the "..digits.." parts full data-objects, including header?

> 
> When bignum X must be "freed" (which is done manually in the algorithms
> written in C), we can simply update slot_X to NULL.  This way, when the
> next reallocation of the scratch space occurs, we can simply move over
> this object and skip copying it to the new scratch space.

Sp the scratchspace for this particular object ("X") is then lost,
until the next GC occurs, which will clear the scratch-space
completely?

> 
> We also need to do some bookkeeping so that when a function returns,
> it will transfer all its "live" objects to buffers allocated by the
> caller, and "free" any objects that are no longer needed, even if the
> next function's local data would overwrite the stack anyway.  My initial
> implementation didn't do that, but I quickly ran into trouble, because
> sometimes another machine word may end up exactly on the place where a
> bignum lived in the previous function, and the object had the same bit
> pattern as the bignum, so on realloc the system thought it could replace
> the machine word with the new location of the stale bignum.

What functions do you mean here? All functions in general, or only
numerical primitives?

> 
> So, to move objects around, there's a "C_migrate_buffer_object" function
> which receives the boundaries of the local buffer and an allocation
> pointer.  It scans for objects still living in the local buffer and
> moves those to the allocation pointer.  Any slots pointing to objects
> in the scratch area are detected, and the "slot_N" word immediately
> preceding the object in the scratch area is updated to point to the
> moved object's slot.  This is done recursively, so that for example
> a cplxnums containing two ratnums, which both contain two bignums will
> be correctly updated, regardless of where any of the 7 objects lives.
> To keep things manageable, C_migrate_buffer_object also accepts a NULL
> allocation pointer to indicate that any objects in scratch space must
> be freed.

I thought wrappers exist in the stack and only immutable (raw) data is
located in the scratch-space, or is that assumption wrong? Can "obj"
in C_migrate_buffer_object refer to any kind of object, or only to
data-blocks (i.e. bignum digit strings)? As only bignum-digits can be
of unknown size, wouldn't it be sufficient to restrict the use of
scratchspace for these?

The performance impact looks acceptable. That runtime.c has grown to
12000 lines is unfortunate and I just hope you'll never get run over
by a bus, because a) you are a fine chap, and b) nobody will want to
maintain the horrible mess of code that is required for all this to
work (I understand that there isn't much one can do, but I just wanted
to mention it.) I do take a certain pride in the fact that we have a
function called "bignum_divide_burnikel_ziegler" in our codebase,
though.

So merging this into chicken-5 is fine for me, even if it's just for
the work you put into that stuff. But I would really like to
understand the scratchspace thing better.


felix



reply via email to

[Prev in Thread] Current Thread [Next in Thread]