Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Float Self-Tagging

arxiv.org

Post reply on HN
Print view View original

21–30 of 52 posts

Re: Float Self-Tagging

#21

Post by skybrian »

pavpanchekha wrote: post #6

I loved this clever, weird, awesome paper, so a short summary. In many dynamic languages some values are stored on the heap ("boxed") and represented as a pointer, while others are represented as an immediate value ("unboxed" or "immediate"). Pointer tagging is a common way to do that: the low bit of the value tells you the value's type, and some types are immediate while others are boxed. Naturally, the tag bits hav…

It’s clever, but not random chance. That would be too much of a coincidence. They rotate the floats to make it happen the way they want.

It’s hardly random that only 8 bits of exponent are needed for many calculations.

Re: Float Self-Tagging

#22

Post by phire »

rtpg wrote: post #9
pavpanchekha wrote: post #6

I loved this clever, weird, awesome paper, so a short summary. In many dynamic languages some values are stored on the heap ("boxed") and represented as a pointer, while others are represented as an immediate value ("unboxed" or "immediate"). Pointer tagging is a common way to do that: the low bit of the value tells you the value's type, and some types are immediate while others are boxed. Naturally, the tag bits hav…

Do all float operations need to reconfirm those bits afterwards though? I suppose if you have some sort of JIT you can end up with a bunch of unboxed floats and would only pay the cost on boundaries though

Yes, but there should be some optimisation opportunities.

Off the top of my head: Any multiply by a constant less than 1.0 will never overflow the unboxed range (but might underflow) and there should be times when it's provably better to check the inputs are inside a range, rather than checking the outputs.

It's worth pointing out that these overflow/underflow checks will be very cold (on typical code). They won't waste much in the way of branch-prediction resources.

I wonder if it's worth taking advantage of floating point overflow/underflow exceptions. I think a multiplication by 2^767 will trigger an exception if the value would overflow, and the corresponding multiply by 2^-765 will catch underflows.

It's tempting to allocate two more tags for floats (001 and 010), covering the entire range from -2^257 to +2^257. It will be rare to actually see those small floats near zero, but it could be worth eliminating the possibility of underflows.

Re: Float Self-Tagging

#23

Post by comex »

> For instance, NaN-tagging prevents (or largely complicates) optimizations relying on stack allocations. The stack uses high memory addresses that do not fit in 48 bits unless encoded relative to the location of the stack segment.

Er, what? The paper says they tested on a Xeon CPU, so x86-64, running Linux. On traditional x86-64, all pointers fit in 48 bits, period. Stack memory is no exception. More recently the architecture was extended to allow 56-bit pointers, but my impression is that Linux (like other OSes) keeps them disabled by default in userspace. According to the documentation [1]:

> Not all user space is ready to handle wide addresses. [..] To mitigate this, we are not going to allocate virtual address space above 47-bit by default.

So how would the stack end up above 47 bits? Is the documentation out of date?

[1] https://docs.kernel.org/arch/x86/x86_64/5level-paging.html

Re: Float Self-Tagging

#24

Post by AlotOfReading »

pansa2 wrote: post #11
rtpg wrote: post #9

Earlier quoted context omitted.

Do all float operations need to reconfirm those bits afterwards though? I suppose if you have some sort of JIT you can end up with a bunch of unboxed floats and would only pay the cost on boundaries though

> reconfirm those bits afterwards Thanks - I hadn't thought about that but it seems to be the main downside of this approach. The benefit of NaN-boxing is that it reassigns values that are otherwise unused - floating-point calculations will never generate NaNs with those bit patterns.

An additional wrinkle is that NaNs are a bit unstable and can have large performance penalties. You can't let the NaNs ever escape into arithmetic and you may even have issues even storing them in a register.

Re: Float Self-Tagging

#25

Post by lmm »

plagiarist wrote: post #17
wging wrote: post #16

Earlier quoted context omitted.

Another cool thing that seems related: exploiting alignment to free up N bits in a 'pointer' representation, because your values have to be aligned. The JVM does this to expand the set of possible addresses representable in 32 bits: https://shipilev.net/jvm/anatomy-quarks/23-compressed-refere... So, for example, with 3 bits of alignment required, the first valid address for a pointer to point to after 0x0 is 0x8, and…

It's interesting which runtimes exploit the extra space for what reasons! Definitely makes more sense to have the extra address space on 32 bits compared to 64. I wonder if the extra addresses are specific to JVM / not something that works well in the C family?

Well in C you have non-aligned pointers, because you can have pointers to things that aren't objects and might not be aligned (e.g. individual chars or shorts). In Java everything is at least 8-byte-aligned, you can't store a loose char/short/int on the heap (it has to go in a boxed object that's 8-byte-aligned, though the compiler will do this semi-automatically) and you can't take a pointer to an individual element of an array.

If you applied the C standard strictly, you could use a JVM-style representation for pointers to longs, pointers, and structs that start with longs and pointers, so you could theoretically have an implementation where those pointers were shorter. But you'd have to convert back and forth when casting to and from void* (and char*), and in practice C people expect to be able to cast a long* to int, cast that to void*, and get the same result as casting long* to void*, even though doing that and using it is undefined behaviour according to the standard.

Re: Float Self-Tagging

#26

Post by ithkuil »

rtpg wrote: post #9
pavpanchekha wrote: post #6

I loved this clever, weird, awesome paper, so a short summary. In many dynamic languages some values are stored on the heap ("boxed") and represented as a pointer, while others are represented as an immediate value ("unboxed" or "immediate"). Pointer tagging is a common way to do that: the low bit of the value tells you the value's type, and some types are immediate while others are boxed. Naturally, the tag bits hav…

Do all float operations need to reconfirm those bits afterwards though? I suppose if you have some sort of JIT you can end up with a bunch of unboxed floats and would only pay the cost on boundaries though

You check the tag before doing float operations

Re: Float Self-Tagging

#27

Post by gus_massa »

pavpanchekha wrote: post #6

I loved this clever, weird, awesome paper, so a short summary. In many dynamic languages some values are stored on the heap ("boxed") and represented as a pointer, while others are represented as an immediate value ("unboxed" or "immediate"). Pointer tagging is a common way to do that: the low bit of the value tells you the value's type, and some types are immediate while others are boxed. Naturally, the tag bits hav…

Nice explanation but it took me a while to understand the trick. They are hidding the tag in the "exponent" of the float, not in the "mantisa"!

Re: Float Self-Tagging

#28

Post by pansa2 »

skybrian wrote: post #19
pansa2 wrote: post #8

Earlier quoted context omitted.

> This allows unboxing the vast majority of floats, which leads to big speedups on float-heavy benchmarks. NaN-boxing allows all floats to be unboxed though. The main benefit of the self-tagging approach seems to be that by boxing some floats, we can make space for 64-bit pointers which are too large for NaN-boxing. The surprising part of the paper is that " some floats" is only a small minority of values - not, say,…

A small minority, but apparently it includes all the floats you’re likely to use. It seems the insight is that you only need 8 bits of exponent in most cases. (And single-precision floating point only has 8 bits of exponent.) Most double-precision floats are never used because they have high exponents.

> A small minority, but apparently it includes all the floats you’re likely to use.

Sorry, I meant a small minority need to be boxed - all the floats you're likely to use can remain unboxed.

Re: Float Self-Tagging

#29

Post by pansa2 »

ithkuil wrote: post #26
rtpg wrote: post #9

Earlier quoted context omitted.

Do all float operations need to reconfirm those bits afterwards though? I suppose if you have some sort of JIT you can end up with a bunch of unboxed floats and would only pay the cost on boundaries though

You check the tag before doing float operations

And afterwards, because floating-point arithmetic can change the value of the tag. This isn't necessary with NaN-boxing, because it uses NaN bit patterns that the hardware never generates.

Re: Float Self-Tagging

#30

Post by dzaima »

pansa2 wrote: post #15
adgjlsfhk1 wrote: post #14

Earlier quoted context omitted.

50% means you only get 1 tag bit. also you totally can fit 64 bit pointers inside a NaN. 46 bit pointers are only 48 bits and you have 53 bits of NaN payload. (you also could get an extra 3 bits if you only allow storing 8 byte aligned pointers unboxed)

> 50% means you only get 1 tag bit. That's enough to distinguish between "unboxed float" and "something else", where the latter can have additional tag bits. > [64-bit] pointers are only 48 bits and you have 53 bits of NaN payload. The paper specifically talks about support for "high memory addresses that do not fit in 48 bits". If you don't have to handle those high addresses, I don't think this approach has any ben…

Of note is that even if you have some massive ≥2^48 data sources, you could still quite likely get away with having NaN-boxed pointers to within the low-size heap, with an extra indirection for massive data. This only would break apart if you managed to reach around 2^45 distinct referenceable objects, which you probably shouldn't ever have (esp. in a GCd language).
Post reply on HN