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

11–20 of 52 posts

Re: Float Self-Tagging

#11

Post by pansa2 »

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

> 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.

Re: Float Self-Tagging

#12

Post by daanx »

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…

> This idea is so simple, so crazy, so stupid, and works so well, but I never thought of it. Bravo to the authors.

Thanks for the nice summary -- looking forward to read the paper!

The same idea of self-tagging is actually also used in Koka language [1] runtime system where by default the Koka compiler only heap allocates float64's when their absolute value is outside the range [2e-511,2e512) and not 0, infinity, or NaN (see [2]). This saves indeed many (many!) heap allocations for float intensive programs.

Since Koka only uses 1 bit to distinguish pointers from values, another slightly faster option is to only box negative float64's but of course, negative numbers are still quite common so it saves less allocations in general.

[1] https://koka-lang.github.io/koka/doc/book.html#sec-value-typ...

[2] https://github.com/koka-lang/koka/blob/dev/kklib/src/box.c#L...

ps. If you enjoy reading about tagging, I recently wrote a note on efficiently supporting seamless large integer arithmetic (as used in Koka as well) and discuss how certain hardware instructions could really help to speed this up [3]:

[3] https://www.microsoft.com/en-us/research/uploads/prod/2022/0... (ML workshop 2022)

Re: Float Self-Tagging

#13

Post by plagiarist »

The idea in the paper is really cool.

People who enjoyed this might also like to read how Apple used tagged pointers for short strings in Objective-C [0]. I think that's when I first learned about tagged pointers. NaN-boxing was mindblowing for me. I love this kind of stuff.

[0] https://mikeash.com/pyblog/friday-qa-2015-07-31-tagged-point...

Re: Float Self-Tagging

#14

Post by adgjlsfhk1 »

pansa2 wrote: post #8
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…

> 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,…

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)

Re: Float Self-Tagging

#15

Post by pansa2 »

adgjlsfhk1 wrote: post #14
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,…

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 benefits compared to NaN-boxing.

Re: Float Self-Tagging

#16

Post by wging »

plagiarist wrote: post #13

The idea in the paper is really cool. People who enjoyed this might also like to read how Apple used tagged pointers for short strings in Objective-C [0]. I think that's when I first learned about tagged pointers. NaN-boxing was mindblowing for me. I love this kind of stuff. [0] https://mikeash.com/pyblog/friday-qa-2015-07-31-tagged-point...

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 after that is 0x10, but you represent those as 0x1 and 0x2 respectively, and use a shift to get back the actual address (0x1 > Aligning all heap-allocated values to 64-bit machine words conveniently frees the low bits of pointers to store a 3-bit tag.

Re: Float Self-Tagging

#17

Post by plagiarist »

wging wrote: post #16
plagiarist wrote: post #13

The idea in the paper is really cool. People who enjoyed this might also like to read how Apple used tagged pointers for short strings in Objective-C [0]. I think that's when I first learned about tagged pointers. NaN-boxing was mindblowing for me. I love this kind of stuff. [0] https://mikeash.com/pyblog/friday-qa-2015-07-31-tagged-point...

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?

Re: Float Self-Tagging

#18

Post by [deleted] »

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…

[deleted]

Re: Float Self-Tagging

#19

Post by skybrian »

pansa2 wrote: post #8
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…

> 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.

Re: Float Self-Tagging

#20

Post by ndjdjddjsjj »

lifthrasiir wrote: post #10
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

Only when they have to be boxed, but yes if you are talking about that.

You need to check after the floating point operation though just in case. Or after the boundary where you pass the float to something else expecting this scheme.
Post reply on HN