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

41–50 of 52 posts

Re: Float Self-Tagging

#41

Post by jacobp100 »

omelancon wrote: post #4
vanderZwan wrote: post #2

Really cool solution! One question: maybe I missed it, but there's no technical reason the tag bits could not use the entire range of exponent bits, no? Other than the fact that having up to 2048 tags would be ridiculously branchy, I guess. Here's a variation I just thought of, which probably has a few footguns I'm overlooking right now: use the seven highest exponent bits instead of three. Then we can directly read…

Hi, I'm one of the authors of the paper. Thanks for your questions and comments! There are many reasons why 3-bit tags work well in practice. Importantly, it allows aligning heap objects on 64-bit machine words. Dereferencing a tagged pointer can then be done in a single machine instruction, a MOV offset by the tag. One of our goals is to make self-tagging as straightforward to implement in existing systems as possib…

Just to add some JS engine info - every engine stores numbers as 32 bit integers if possible, which is usually done by tagging a pointer. Also, JSC needs pointers to be represented exactly as-is, because it will scan the stack for anything that looks like a pointer, and retain it when running the GC

Re: Float Self-Tagging

#42

Post by SonOfLilit »

funny_falcon wrote: post #38
scottlamb wrote: post #34

Earlier quoted context omitted.

> CRuby uses this technique on 64bit platforms for years. What do you mean by "this technique"? The paper says that CRuby uses tagged objects but could benefit from the innovation being discussed here, a specific bit pattern used to tag floats. See the following quote: > Therefore, implementations that represent floats as tagged pointers could benefit from it with minimal implementation effort. Such popular implement…

In fact, CRuby successfully combined “Self Tagging” with pointer tagging. Here's the commit: https://github.com/ruby/ruby/commit/b3b5e626ad69bf22be3228f8...

Seems legit.

Linked commit contains code for rotating tagged floats so bits 60..62 go to the least significant positions, and a comment about a range of unboxed floats between 1.7...e-77 and 1.7...e77, plus special casing 0.0.

Re: Float Self-Tagging

#43

Post by SonOfLilit »

refulgentis wrote: post #39
funny_falcon wrote: post #32

Earlier quoted context omitted.

Just correction: CRuby uses “Float Self-Tagging” for years.

This is your 4th comment claiming this: it's not true. You're right that Ruby uses tags, ex. Objective-C does also and has for a while. The innovation here is its a tag without the tag bits . That's why its self-tagging, not tagging.

In another comment, this user links a CRuby commit that they claim adds it. It seems legit.

Linked commit contains code for rotating tagged floats so bits 60..62 go to the least significant positions, and a comment about a range of unboxed floats between 1.7...e-77 and 1.7...e77, plus special casing 0.0

e.g. this excerpt:

    #if USE_FLONUM
    #define RUBY_BIT_ROTL(v, n) (((v) > ((sizeof(v) * 8) - n)))
    #define RUBY_BIT_ROTR(v, n) (((v) >> (n)) | ((v) > 63);
     /* e: xx1... -> 011... */
     /*    xx0... -> 100... */
     /*      ^b63           */
     t.v = RUBY_BIT_ROTR(((b63 ^ 1) float_value;
      }
    }

Re: Float Self-Tagging

#44

Post by bee_rider »

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.

Got take, but a double with only 8 bits of exponent actually seems kind of nice, you get the extra precision but it can be cast down to a single and you only lose precision; you don’t have values that are outside the range of singles.

Re: Float Self-Tagging

#45

Post by vanderZwan »

omelancon wrote: post #31
vanderZwan wrote: post #5

Earlier quoted context omitted.

Thank you for the explanation! I was not aware of the context behind the choice of three-bit tags. > The trick is to rotate the tag to bits 2-3-4 of the exponent instead of 1-2-3 and add an offset to the exponent to "shift" the range of captured values. Maybe I misunderstand, but isn't that a similar idea to what I just described? Adding an offset to "rotate" the ranges of the exponent by a segment, putting the one w…

> Maybe I misunderstand, but isn't that a similar idea to what I just described? Adding an offset to "rotate" the ranges of the exponent by a segment... Yes it is similar. It seems to me that there really isn't that many useful operations that can be applied to the exponent beside adding an offset. But that's only a suspicion, do not take my word for it. > I suspect that ensuring NaN and Infinity are in there will be…

Yeah, this is one of those situations where speculating about behavior one thing, but well-designed benchmarks and tests may very well give some surprising results. I am very much looking forward to the follow-up paper where you'll share your results :). Good luck with the research to you and you colleagues!

Re: Float Self-Tagging

#46

Post by Leszek »

pizlonator wrote: post #36

I doubt this is actually faster than NaN or why they call NuN tagging. The code sequences they cite for encoding and decoding are worse than what I expect NuN tagging to give you. If they want to convince me that their thing is faster, they should do a comparison against a production implementation of NuN tagging. Note that the specifics of getting it right involve wacky register allocation tricks on x86 and super ca…

Agreed, NuN tagging is an awesome use of the NaN space, and it has the same benefits of being a no-op for pointers. I would only consider this for cases where NuN tagging is impossible, e.g. some system that needs more pointer bits than NuN tagging allows.

I'd add that the claim that this could be implemented in V8 doesn't take into account pointer compression, where on-heap V8 tagged pointers are 32-bit, not 64-bit.

Re: Float Self-Tagging

#47

Post by Joker_vD »

I imagine that in a "heavy numerical" part of the code one would ideally use identity-tagged floats, i.e., with no rotation applied. Instead, the (few) pointers that are used in this part would be stored in rotated state.

But thinking about how to mesh this scheme together with other, "normal" (that is, pointer-heavy) part of the code makes me slightly nauseous.

Re: Float Self-Tagging

#48

Post by dgreensp »

Leszek wrote: post #46
pizlonator wrote: post #36

I doubt this is actually faster than NaN or why they call NuN tagging. The code sequences they cite for encoding and decoding are worse than what I expect NuN tagging to give you. If they want to convince me that their thing is faster, they should do a comparison against a production implementation of NuN tagging. Note that the specifics of getting it right involve wacky register allocation tricks on x86 and super ca…

Agreed, NuN tagging is an awesome use of the NaN space, and it has the same benefits of being a no-op for pointers. I would only consider this for cases where NuN tagging is impossible, e.g. some system that needs more pointer bits than NuN tagging allows. I'd add that the claim that this could be implemented in V8 doesn't take into account pointer compression, where on-heap V8 tagged pointers are 32-bit, not 64-bit.

It’s also worth noting that engines with JIT, like V8, don’t box intermediate floating-point numbers in calculations after optimization has been performed. Arrays of (only) numbers also don’t box the numbers (though all numeric object property values that aren’t small integers are now boxed in V8). This means you can read floats from arrays, do math on them, and write them to arrays, without boxing or unboxing. This wouldn’t necessarily be true in a less sophisticated runtime that lacks an optimizing compiler (of which V8 has two or three IIRC).

Re: Float Self-Tagging

#50

Post by djwatson24 »

pizlonator wrote: post #36

I doubt this is actually faster than NaN or why they call NuN tagging. The code sequences they cite for encoding and decoding are worse than what I expect NuN tagging to give you. If they want to convince me that their thing is faster, they should do a comparison against a production implementation of NuN tagging. Note that the specifics of getting it right involve wacky register allocation tricks on x86 and super ca…

Can you go in to more detail on 'wacky register allocation tricks' or instruction selection needed to support nun-tagging? Or pointers to code somewhere? Would be nice to compare some of them to the paper.
Post reply on HN