On May 17, 2011, at 14:59, Mark H Weaver wrote: >> But the question I was after was, even if we want to use the full >> range of the values, do we need the entire set to be representable *in >> immediate form*? I doubt the very largest and smallest values are >> used often, so making just those values use heap storage probably >> wouldn't be too costly in space. > > In principle, I agree with you that it might be reasonable to cut the > exponent range of immediate doubles in half in order to gain an extra > bit of tagging information. Unfortunately, it seems to me that the > details of the IEEE 754 floating-point formats would make the required > checks rather expensive. > > The exponent field of an IEEE 754 binary floating-point number is not > stored in twos-complement format, but is instead "biased", meaning that > a constant is added to the true exponent of two, such that 1 represents > the smallest representable exponent, and 2^EXPBITS-2 represents the > largest representable exponent. The worse problem is that a 0 in the > exponent field means that the number is a (signed) zero, and 2^EXPBITS-1 > means that the number is either infinity of a NaN.
So the most interesting exponent values to keep expressible as immediates would include (hex) 000, 7ff, and values near 3ff and 400, right? One way of looking at that is, in the top 3 exponent bits, four of the eight possible patterns (000, 111, 011, 100) represent the most interesting floating point values, and the rest can be relegated to heap storage. If we leave it at that, actually, some of the really-small and really-large numbers could be encoded immediately, but values of medium magnitudes could not. Hmm... we'd want to map field values of 0, 7, 3, and 4 to one value, and 1, 2, 5, and 6 to another. How about: "(field+1) & 2"? I think that gives you 0 for 0/inf/nan and values with large positive or negative exponents, and for values closer to 1 in magnitude, and gives 2 for finite values with medium-range magnitudes. (I threw some code together testing some powers of 10; it looks like 1.0e-231 and smaller, 1.0e-76 through 1.0e77, and 1.0e232 and larger, along with 0/nan/inf, would get classified together that way.) Make the "field+1" part of the encoding, and all those values encode in a form that has that specific bit clear (or bits could be shuffled to put it elsewhere); then values with the bit set would indicate everything other than immediate doubles. A bit more arithmetic trickery might let you swap exponent 000 with 200 and 7ff with 5ff, giving you only 0x3ff exponent values you'd want to store immediately, same as above, but with only two of the exponent values "stolen" for 0/inf/nan. This is all still only somewhat IEEE-754 dependent, in that it doesn't require the existence of inf or nan values, it just twists things around a bit so that the IEEE-754 encodings of those values would be among those encoded as immediate values. If a machine like the Vax doesn't support them, no big deal; the basic idea still works. But, what's the case we should optimize for? I'm guessing that in cases where lots of floating point values are encoded and decoded, we're doing lots of math or lots of I/O, and I suspect that 0/inf/nan are not nearly as common as finite nonzero values in some truncated range. (And how big a range of exponents do most applications need?) So a variant encoding that uses magic values for 0/inf/nan that can be easily tested for collectively, much like we do for #t/#f/#nil now, and heap encoding for the largest-magnitude exponents, cuts in half the number of values we need to be able to encode in immediate form using lots of bits, at the cost of a few more magic constants, and a slightly slower classify/encode/decode process because of the use of three encodings. And we may be able to streamline usage slightly with a macro or inline function to express "tell me if this is a double and if it is also extract the value into this variable". I guess one important question is how important efficient use and encoding of the full range of floating point values is compared to other types. I think I'd rather have the wider space for integers and pointers, personally, but I'm sure other people's work may have different demands. And for that matter, I don't know if all that much of the 64-bit integer data I ever deal with really is outside the 48-bit range, though I could imagine issues coming up with bit masks. > Given this, I don't see an obvious way to steal a bit or two from the > exponent field without making the associated checks too expensive to be > worth the benefits. I think at least two conditional branches would be > required. Do you see a clever way around this? If so, can you please > post the details? Correctly predicted branches are generally cheap on most modern architectures, I believe. So I'm not sure how costly it would really be, compared to all the other stuff we do. It would cost a little more than in Andy's proposal, I think. If the test you care about is, "is this a double", then with the first form above I guess it would be implemented as "is bit X clear; if not, does the tag indicate that it's a double stored in the heap". So, looks like two tests to determine that it isn't a double, and they may or may not be easy to combine into one test. The second form preserves more of the value space for non-double values, but would probably take three tests (bit X; 0/nan/inf magic constants; heap-double tag) to determine that a value isn't a double. For a value that is a double, hopefully the first test would catch it, most of the time. Ken
