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

31–40 of 52 posts

Re: Float Self-Tagging

#31

Post by omelancon »

vanderZwan wrote: post #5
omelancon wrote: post #4

Earlier quoted context omitted.

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…

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 crucial to avoid performance cliffs...

This is a reasonable assumption. There are in fact ways to rotate and add an offset such that the exponent can overflows/underflows to capture exponents 0 and 0x7ff (for inf and nan) with a single well-positioned tag. Making it work in practice is not as simple, but we are working on it.

Re: Float Self-Tagging

#32

Post by funny_falcon »

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 correction: CRuby uses “Float Self-Tagging” for years.

Re: Float Self-Tagging

#34

Post by scottlamb »

funny_falcon wrote: post #33

CRuby uses this technique on 64bit platforms for years. Edit: the commit https://github.com/ruby/ruby/commit/b3b5e626ad69bf22be3228f8...

> 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 implementations include CPython [11], CRuby [32] and Google’s V8 [33].

Re: Float Self-Tagging

#35

Post by pizlonator »

comex wrote: post #23

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

Yeah I think they’re just wrong about this.

Re: Float Self-Tagging

#36

Post by pizlonator »

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 careful instruction selection on arm.

It seems that they use some very nonstandard JS implementation of NaN tagging as a strawman comparison.

(Source: I wrote a lot of the NuN tagging optimizations in JavaScriptCore, but I didn’t invent the technique.)

Re: Float Self-Tagging

#37

Post by funny_falcon »

scottlamb wrote: post #34
funny_falcon wrote: post #33

CRuby uses this technique on 64bit platforms for years. Edit: the commit https://github.com/ruby/ruby/commit/b3b5e626ad69bf22be3228f8...

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

I mean, CRuby does “Float Self Tagging” for years. Paper just has the mistake about CRuby.

Re: Float Self-Tagging

#38

Post by funny_falcon »

scottlamb wrote: post #34
funny_falcon wrote: post #33

CRuby uses this technique on 64bit platforms for years. Edit: the commit https://github.com/ruby/ruby/commit/b3b5e626ad69bf22be3228f8...

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

Re: Float Self-Tagging

#39

Post by refulgentis »

funny_falcon wrote: post #32
omelancon wrote: post #4

Earlier quoted context omitted.

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

Re: Float Self-Tagging

#40

Post by 4ad »

comex wrote: post #23

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

The address space size limitations doesn't mean that only the least significants bits are used, the memory hole is in the middle of the address space[1].

I don't know what Linux does specifically (or under what configurations), but one some other operating systems the user space stack is in the higher half[2].

[1] https://en.wikipedia.org/wiki/X86-64#Canonical_form_addresse...

[2] https://github.com/illumos/illumos-gate/blob/master/usr/src/...

Post reply on HN