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

Storing data in pointers

muxup.com

Post reply on HN
Print view View original

51–60 of 71 posts

Re: Storing data in pointers

#51

Post by KMag »

It's really unfortunate that all of the mainstream OSes run userspace in the lower portions of the address space.

Setting the most-significant 13 bits (really, setting the second to 12th bits and at least one of the following bits) of an IEEE-754 float will result in a NaN bit pattern. That means that any pointer to the top 2 petabytes of a 64-bit address space, if cast to an IEEE-754 double will be NaN. This means the NaN-boxing used in Safari and Firefox's JavaScript engines, LuaJIT, etc. would be no-ops. (Safari and Firefox use different mechanisms, but they'd become the same if moved to the top of the address space.)

It's not enough of a performance difference to re-jigger everything in mainstream OSes, but I imagine if someone were to come up with a unikernel/exokernel OS specifically for JITing some dynamic language, there's some performance to be had by having all of the dynamic language objects in the upper 2 petabytes of the address space.

Re: Storing data in pointers

#52

Post by Dylan16807 »

masklinn wrote: post #48
Dylan16807 wrote: post #46

Earlier quoted context omitted.

> if the kernel returns a large address That's why I said you need to control your allocator. It's so much easier than rewriting everything that deals with pointers. And of course everything has virtual memory. But even without it, you're not really worse off when you upgrade the CPU if masking was already enforced. > This was already used on 32b x86: PAE decorrelated the physical address space from the virtual (givi…

> That's why I said you need to control your allocator. The allocator does not matter unless by "control your allocator" you mean "the OS provides an API which can restrict the virtual memory system", which has nothign to do with the allocator. If you're using 19 bits for tagging and the OS returns a 52 bit pointer, you don't have the space for your tagging scheme, no matter what your allocator is. > PAE doesn't mean…

> The allocator does not matter

The allocator gets address space. The OS doesn't just shove things into your process in general. It can't return a 52 bit pointer out of nowhere. My first draft mentioned OS explicitly but it's not really the OS that's making the decisions.

> What it does is show that there is no correlation between the physical and virtual address spaces

It does show that, but that decorrelation is neither necessary nor sufficient to solve this problem.

> Missing the point, the example of LAA shows that the OS can provide different virtual address spaces to different processes.

I agree with that. In the context of your overall post it wasn't clear to me that that was why you mentioned it.

Re: Storing data in pointers

#53

Post by masklinn »

Dylan16807 wrote: post #52
masklinn wrote: post #48

Earlier quoted context omitted.

> That's why I said you need to control your allocator. The allocator does not matter unless by "control your allocator" you mean "the OS provides an API which can restrict the virtual memory system", which has nothign to do with the allocator. If you're using 19 bits for tagging and the OS returns a 52 bit pointer, you don't have the space for your tagging scheme, no matter what your allocator is. > PAE doesn't mean…

> The allocator does not matter The allocator gets address space. The OS doesn't just shove things into your process in general. It can't return a 52 bit pointer out of nowhere. My first draft mentioned OS explicitly but it's not really the OS that's making the decisions. > What it does is show that there is no correlation between the physical and virtual address spaces It does show that, but that decorrelation is ne…

> The allocator gets address space.

The allocator gets address space from the OS.

> The OS doesn't just shove things into your process in general. It can't return a 52 bit pointer out of nowhere. My first draft mentioned OS explicitly but it's not really the OS that's making the decisions.

Of course it’s the OS making the decision. You ask the OS for memory and it returns whatever it wants.

The allocators acts as bridge between the application and OS and can do cool stuff but if the OS returns a 52 bits pointer there isn’t a thing the allocator can do about it that would result in a working 48 bits pointer.

> It does show that, but that decorrelation is neither necessary nor sufficient to solve this problem.

It absolutely is necessary, since the entire subject is to not break applications requiring a smaller address space for their tagging scheme to work even as the system and other applications migrate to larger ones.

Re: Storing data in pointers

#54

Post by Dylan16807 »

masklinn wrote: post #53
Dylan16807 wrote: post #52

Earlier quoted context omitted.

> The allocator does not matter The allocator gets address space. The OS doesn't just shove things into your process in general. It can't return a 52 bit pointer out of nowhere. My first draft mentioned OS explicitly but it's not really the OS that's making the decisions. > What it does is show that there is no correlation between the physical and virtual address spaces It does show that, but that decorrelation is ne…

> The allocator gets address space. The allocator gets address space from the OS . > The OS doesn't just shove things into your process in general. It can't return a 52 bit pointer out of nowhere. My first draft mentioned OS explicitly but it's not really the OS that's making the decisions. Of course it’s the OS making the decision. You ask the OS for memory and it returns whatever it wants. The allocators acts as br…

The allocator can choose which part of the address space to fill. It does not have to deal with "whatever the OS wants".

> It absolutely is necessary, since the entire subject is to not break applications requiring a smaller address space for their tagging scheme to work even as the system and other applications migrate to larger ones.

Even if you have a 1:1 memory mapping, you can leave the applications that want small addresses at the start of memory. You don't need to decorrelate virtual and physical addresses to do that.

Re: Storing data in pointers

#55

Post by UncleEntity »

orlp wrote: post #47
xoranth wrote: post #45

Earlier quoted context omitted.

An even better representation is the one from `folly::FBString`. There, the tag that indicates small string mode is not a particular bound on capacity, but the last byte of the struct that is set to zero. That way, the tag also acts as a null terminator for the stored string.

I fail to see how that is better. Null-terminated strings are a terrible idea in the first place.

If null-terminated strings are already a thing in your language and you can just pass an inlined string to whatever function without any bit manipulation I fail to see the downside.

Re: Storing data in pointers

#56

Post by xoranth »

orlp wrote: post #47
xoranth wrote: post #45

Earlier quoted context omitted.

An even better representation is the one from `folly::FBString`. There, the tag that indicates small string mode is not a particular bound on capacity, but the last byte of the struct that is set to zero. That way, the tag also acts as a null terminator for the stored string.

I fail to see how that is better. Null-terminated strings are a terrible idea in the first place.

> I fail to see how that is better. Null-terminated strings are a terrible idea in the first place.

TLDR: you get extra bytes in your small strings

Long version: Copying from FBString code:

    struct MediumLarge {
     Char* data_;
     size_t size_;
     size_t capacity_;
    };
    // sizeof(MediumLarge) == 24

    struct FBString {
        union {
            // For accessing the last byte.
         uint8_t bytes_[sizeof(MediumLarge)]; 
         Char small_[sizeof(MediumLarge) / sizeof(Char)];
         MediumLarge ml_;
        };
    };
Then `bytes_[23]` is set to `24 - size of small string` for a small string. You also "steal" a couple of bits from `capacity_` as a tag to see if a string is small or large.

This has two advantages:

- You get to reuse seven of the eight bytes of `capacity_` in your small string (i.e. your max small string size is 23, not 16 as it would be with a simpler scheme). - You get a null terminator "for free" (though, of course, you still have size and capacity). This is on top of size/capacity.

This could be reduced to 16 bytes by making `size_` and `capacity_` uint32_t instead of size_t.

Re: Storing data in pointers

#57

Post by UncleEntity »

powera wrote: post #2

I don't want to say you should never do this. But if you aren't writing a compiler or an embedded system, you should never do this.

> But if you aren't writing a compiler or an embedded system, you should never do this.

I have this hex trie library that uses this to differentiate between a leaf and a node that will soon be optimizing single-value nodes as tagged pointers. __edit__ umm... single-value nodes are leaves!?! Yeah, not enough coffee apparently.

Not to mention the tinyscheme interpreter I occasionally poke at that TFA gave me a bunch of ideas to try out.

Re: Storing data in pointers

#58

Post by vidarh »

KMag wrote: post #50
vidarh wrote: post #24

Earlier quoted context omitted.

I'm guessing the problem occurred specifically with CPUs newer than the 68000 irrespective of amount of RAM? (Microsoft's) Amiga Basic also did this and stopped working on newer CPUs, as the 68000 only has 24 address lines and ignores the top 8 bits of a 32 bit address, but 68020 and up uses all 32 (I don't remember about the 68010, but that was pin compatible with the 68000 so I'm guessing not)

There was hardware (not sure if it was CPU state or state in the memory controller) to zero-out all of the address bits above the 24th, allowing backward compatibility. I forget the shortcut (option-I? option-M?), but if you selected an executable in Finder, you could go in and change the hardware compatibility mode used to run it.

That's interesting. I don't think the address hack was widely used on the Amiga, so we didn't get anything like that. Amiga Basic was the main one and that was ditched for Arexx for the newer OS versions (a shame, because as much as I liked to mock Microsoft at the time, Amiga Basic was quite decent). I don't think the incompatibility had anything to do with ditching it - people have patched it and it wasn't a big deal; I'm assuming it didn't get an official patch because Commodore had already decided to replace it.

Re: Storing data in pointers

#59

Post by ot »

ot wrote: post #39
teh_matt wrote: post #4

Earlier quoted context omitted.

You should be very careful when doing that. It may be rare in practice, but it's surprisingly easy to trigger ABA issues with only a 16-bit sequence number.

Don't you need 65k threads all contending on the same state for that to happen? Even if your process does have 65k threads, you'd need a pretty large critical section for all of them to be preempted in an unlucky point. That said, it's better to rely on RCU/hazptr to solve ABA issues, but the extra bits are still useful to store state that can be CAS'd together with the pointer.

Cannot edit anymore but I realized that my comment was wrong :) You just need 2 threads, as long as one is suspended long enough.

Re: Storing data in pointers

#60

Post by [deleted] »

ot wrote: post #59
ot wrote: post #39

Earlier quoted context omitted.

Don't you need 65k threads all contending on the same state for that to happen? Even if your process does have 65k threads, you'd need a pretty large critical section for all of them to be preempted in an unlucky point. That said, it's better to rely on RCU/hazptr to solve ABA issues, but the extra bits are still useful to store state that can be CAS'd together with the pointer.

Cannot edit anymore but I realized that my comment was wrong :) You just need 2 threads, as long as one is suspended long enough.

[deleted]
Post reply on HN