Re: Immediate doubles (up to 2^256) and rationals coming to Guile 3

[Arne Babenhauserheide <arne_bab@web.de>]

[-- Attachment #1: Type: text/plain, Size: 2609 bytes --]


Mark H Weaver <mhw@netris.org> writes:
> I have a working draft implementation that roughly doubles the speed of
> a simple "substract 1.0 until negative" loop for inexact reals less than
> 2^256, compared with current 'master' (near 2.9.2).  The same loop for
> exact rationals runs in ~70% of the time compared with current master.
> More importantly, no heap allocation is required when working with these
> immediate values.

> More precisely, large finite doubles with magnitude >= 2^256
> (1.157920892373162e77) must be heap allocated.  All other doubles,
> including all Inf/NaNs, are immediate floats, or "iflos".
>
> I call this approach "high-exponent boxing", because instead of using
> the space of ~2^53 NaNs for non-flonum purposes, I use the space of
> finite doubles with binary exponent larger than 255.  That's 3/8ths of
> the total space of IEEE doubles.  This gives us a total of (3 * 2^61)
> SCM values to use for other things.
…
> I've also implemented immediate exact rationals, or "fixrats".  The
> precise rule is that on a 64-bit system, an exact non-integer rational
> is immediate if and only if it can be written with 54 binary digits or
> less.  In terms of decimal digits, any rational that can be written with
> 16 decimal digits is immediate, and some that require 17 or 18 decimal
> digits are immediate.

Wow, that’s awesome!

> I should also mention that although the current patch set adds about 4
> bits to the size of all heap tags, e.g. changing most tc7 tags to tc11,
> I can see a way to avoid this: we could tag pairs in the low bits of
> their pointers, instead of in their CARs.
>
> More concretely, 1110 would become the "pair pointer" tag, thus
> eliminating the need for the 1110 "NOT_SCM" tag (a.k.a. the non-pair
> heap object tag).  This would eliminate the need to change the heap tags
> at all, and dramatically reduce the size of my patch set.  Moreover, the
> low bit would no longer need to be 1, so we would have many more tc7
> tags to work with.

I don’t understand the implications of this, but I realized that I would
love to have info about the sizes of different datastructures in Guile.

I recently started measuring how much memory is required for a record
compared to a list, so I could give people concrete guidelines which
datastructures to use for which algorithm, and for that such low-level
details would be great to have! (or just to know where to read them up —
or which keywords to look for)

Best wishes,
Arne
--
Unpolitisch sein
heißt politisch sein
ohne es zu merken

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 1076 bytes --]