[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Immediate doubles (up to 2^256) and rationals coming to Guile 3
From: |
Arne Babenhauserheide |
Subject: |
Re: Immediate doubles (up to 2^256) and rationals coming to Guile 3 |
Date: |
Thu, 06 Jun 2019 21:37:22 +0200 |
User-agent: |
mu4e 1.2.0; emacs 26.1 |
Mark H Weaver <address@hidden> 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
signature.asc
Description: PGP signature
Re: Immediate doubles (up to 2^256) and rationals coming to Guile 3, Mark H Weaver, 2019/06/07