14 ms·

> It's a shame that tagged architectures have largely died out. Judging by benchmarks, it's a good thing they did. Byte-addressed but word-aligned pointers plu

by sedachv 14y ago

> It's a shame that tagged architectures have largely died out. Judging by benchmarks, it's a good thing they did. Byte-addressed but word-aligned pointers plus pipelining and superscalar processors (branch prediction probably helps too) give you almost the same performance as explicit instructions for tag support. The amount of flexibility and the simplification in the instruction set you get from it is well worth it IMO. SPARC had such instructions, and on benchmarks (see http://www.cs.ucsb.edu/~urs/oocsb/papers/oo-hardware.html http://www.cs.ucsb.edu/~urs/oocsb/papers/oo-hardware.html and http://www.cs.cmu.edu/~ram/pub/arch.ps http://www.cs.cmu.edu/~ram/pub/arch.ps) the difference in speed between using them and not was less than 5%. On a 64-bit machine, you have 30 different tags available (5 tag bits, since the smallest thing you'd want to point at is going to be two 64-bit words big, and two of the 5-bit patterns reserved for positive and negative fixnums, for 60-bit immediate integers). The problem is a lot of algorithms (especially crypto) are designed around 32 or 64 bit words, which typically means you have to make contortions and declarations to have your compiler operate on immediate representations. Typically, the compiler will set aside some registers on the CPU for dealing with these immediate values, so the garbage collector doesn't get confused. On x86 this might mean you don't have enough registers to run the algorithm efficiently, even if the compiler knows exactly what needs to be unboxed. Another problem is floating point values. On 64-bit systems there's a technique called NaN-boxing that can do something about this (http://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations http://wingolog.org/archives/2011/05/18/value-representation...), but I don't yet understand how it works. I do agree on one thing - slapping an extra byte onto word size would be awesome, as long as that extra byte is general purpose. Other things besides tagging that you could do with it would be error-correcting codes (the Symbolics Ivory actually had ECC for every word), and all kinds of metadata. Maybe it would even make sense to keep this extra byte out of the memory bus and just have it on registers; that's where most of the trouble with tagged values on modern machines seems to come from. This would make sense for load/store instruction sets.

tomp 14y ago
In IEEE 754 standard, floating point numbers are represented using 1 bit for the sign, 11 bits for the exponent, and the remaining 52 bits for the fraction (number between 0 and 1). The exponent 7FF (in binary: all ones) is reserved for special values: NaN and infinity. If the fraction is 0 (all zeroes), then the number is +/- inf, otherwise it is a NaN. NaN-tagging works by using the unused variations of NaN for pointers. The trick is that most processors only generate a single binary pattern for NaN, so all other binary patterns are never used to represent floating point numbers, and can thus be used to represent pointers. This works since the current x64 implementations only use 48 bits for the pointers, so all pointers can "fit" into the remaining 52 bits of NaN.
- lutusp 14y ago
  > In IEEE 754 standard, floating point numbers are represented using 1 bit for the sign, 11 bits for the exponent, and the remaining 52 bits for the fraction (number between 0 and 1). On reading this I immediately read the standard, hoping to discover that the word "fraction" wasn't used, only to find that "fraction" is defined as the part of the significand (mantissa) lying to the right of the implied binary point. In essence then (because the bit to the "left" of the binary point is only ever implied, never explicit), "fraction" stands as a synonym for significand. Unfortunate terminology. And why? Here's why: A fraction: 1/3 A significand, base ten: 0.3333333333333333 IEEE 754 can provide the second, but it cannot provide the first. IEEE 754: http://kfe.fjfi.cvut.cz/~klimo/nm/ieee754.pdf http://kfe.fjfi.cvut.cz/~klimo/nm/ieee754.pdf Significand: http://en.wikipedia.org/wiki/Significand http://en.wikipedia.org/wiki/Significand A quote: "The significand (also coefficient or mantissa) is part of a floating-point number, consisting of its significant digits." p.s. this is not a correction, it's a lament.
  - tomp 14y ago
    It's actually even more complicated... Remember, this is binary, so the only possible digits are 0 and 1. For example, 1/3 in binary is 0.01010101010101...; Encoding that in "floating point", we first get: 1.0101010101 * 2^-2; We can see that in this format, the first digit of the number is always 1; thus, the first digit of the significand, for any number, is ALWAYS 1 (in binary)! IEEE754 makes the optimization to not store this leading 1 as part of the fraction, so the the approximation to 1/3 is actually encoded as: 0 01111111101 0101010101010101010101010101010101010101010101010101 ^ ^ ^ | +-----+ | sign bit | fraction = 1.33333... = 1.01010101010101...0101010101010101b | |--- this part is included ---| | exponent = 01111111101b - 1023 = 1021 - 1023 = -2

by sedachv 14y ago

tomp 14y ago

In IEEE 754 standard, floating point numbers are represented using 1 bit for the sign, 11 bits for the exponent, and the remaining 52 bits for the fraction (number between 0 and 1). The exponent 7FF (in binary: all ones) is reserved for special values: NaN and infinity. If the fraction is 0 (all zeroes), then the number is +/- inf, otherwise it is a NaN. NaN-tagging works by using the unused variations of NaN for pointers. The trick is that most processors only generate a single binary pattern for NaN, so all other binary patterns are never used to represent floating point numbers, and can thus be used to represent pointers. This works since the current x64 implementations only use 48 bits for the pointers, so all pointers can "fit" into the remaining 52 bits of NaN.

lutusp 14y ago
> In IEEE 754 standard, floating point numbers are represented using 1 bit for the sign, 11 bits for the exponent, and the remaining 52 bits for the fraction (number between 0 and 1). On reading this I immediately read the standard, hoping to discover that the word "fraction" wasn't used, only to find that "fraction" is defined as the part of the significand (mantissa) lying to the right of the implied binary point. In essence then (because the bit to the "left" of the binary point is only ever implied, never explicit), "fraction" stands as a synonym for significand. Unfortunate terminology. And why? Here's why: A fraction: 1/3 A significand, base ten: 0.3333333333333333 IEEE 754 can provide the second, but it cannot provide the first. IEEE 754: http://kfe.fjfi.cvut.cz/~klimo/nm/ieee754.pdf http://kfe.fjfi.cvut.cz/~klimo/nm/ieee754.pdf Significand: http://en.wikipedia.org/wiki/Significand http://en.wikipedia.org/wiki/Significand A quote: "The significand (also coefficient or mantissa) is part of a floating-point number, consisting of its significant digits." p.s. this is not a correction, it's a lament.
- tomp 14y ago
  It's actually even more complicated... Remember, this is binary, so the only possible digits are 0 and 1. For example, 1/3 in binary is 0.01010101010101...; Encoding that in "floating point", we first get: 1.0101010101 * 2^-2; We can see that in this format, the first digit of the number is always 1; thus, the first digit of the significand, for any number, is ALWAYS 1 (in binary)! IEEE754 makes the optimization to not store this leading 1 as part of the fraction, so the the approximation to 1/3 is actually encoded as: 0 01111111101 0101010101010101010101010101010101010101010101010101 ^ ^ ^ | +-----+ | sign bit | fraction = 1.33333... = 1.01010101010101...0101010101010101b | |--- this part is included ---| | exponent = 01111111101b - 1023 = 1021 - 1023 = -2