8 ms·

Storing data in pointers

118 points by luu 3y ago

dmt314159 3y ago
This will be a problem when trying this on Capability Hardware Enhanced RISC Instructions (CHERI) https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ systems. Currently the only CPU with this implemented is Arm's Morello prototype. Pointers are replaced by 128-bit capabilities containing what operations are valid, a 64-bit base address and a size. These capabilities are unforgeable, so trying to play with "unused" parts of 64-bit pointers simply won't work. FreeBSD & Gnome are running on hardware after minor source-code changes, along with a significant proportion of FreeBSD ports collection. As well as ARM, Microsoft is interested: https://www.microsoft.com/en-us/research/project/portmeirion/overview/ https://www.microsoft.com/en-us/research/project/portmeirion...
powera 3y ago
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.
- spacechild1 3y ago
  It is also very useful for some lockfree algorithms, e.g. to fit a pointer and a sequence number within a 64-bit value.
  - teh_matt 3y ago
    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.
    - ot 3y ago
      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.
      - ot 3y ago
        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 3y ago
        [deleted]
    - spacechild1 3y ago
      I don't really believe that it is easy to trigger. The thread would have to be preempted at a very specific point for a very specific duration, the other thread(s) would need to perform exactly 2^16 operations within that time window and the final operation would need to trigger the ABA problem. Possible, but extremely unlikely. (In some applications even impossible.) Do you happen to have some real world examples? But yes, it is definitely something to be aware of! BTW, if the pointers are always aligned, the sequence number may have a few bits more.
- deleted 3y ago
  [deleted]
- JonChesterfield 3y ago
  Dynamic language runtimes really like this. It gives you type information without dereferencing the pointer.
- KolmogorovComp 3y ago
  Any graph-heavy application constrained by memory potentially gain a lot from those kind of optimizations.
- UncleEntity 3y ago
  > 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.
jandrese 3y ago
Very old Macs used this trick to squeeze their ROM routines down a bit, operating with 24 bit addressing and using the top bits for flags and whatnot. Of course they ran into trouble when machines with 16MB of memory started appearing. If you do this you might be making more work for yourself in the future when you buy a new machine with 256EB of main memory.
- eschneider 3y ago
  Yeah, this was definitely a thing on old macs. Us olds also remember the pain and agony of cleaning this up for 32 bit addressing. Cool as these hacks are, do yourself a favor and avoid the (eventual) agony.
- Dylan16807 3y ago
  x86_64 (among others) specifically avoided that incompatibility, by the CPU forcing programs to mask those bits out instead of ignoring them. So programs are very compatible into the future, they just need to limit the range their memory allocator uses. Then it later added explicit automatic masking, which also avoids the problem. As long as your program can make do with smaller amounts of memory, there are no downsides.
  - masklinn 3y ago
    It does not actually make the software future proof: if the kernel returns a large address the software will either fault if it checks, or stomp over then mask out the wrong thing. Virtual memory is what mitigates the issue, as it lets the OS provide large virtual addresses on a per-process basis, and independent of physical addressing. This was already used on 32b x86: PAE decorrelated the physical address space from the virtual (giving the OS 36 bits physical address — with a theoretical upper bound of 64 — even as individual processes were still restricted to 32); and on windows the /LARGEADDRESSAWARE link switch allowed manipulating the virtual address space on a per-process granularity.
    - Dylan16807 3y ago
      > 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 (giving the OS 36 bits physical address — with a theoretical upper bound of 64 — even as individual processes were still restricted to 32); and on windows the /LARGEADDRESSAWARE link switch allowed manipulating the virtual address space on a per-process granularity. I wouldn't characterize this as very similar. Physical and virtual address space already had to be decorrelated to go above about 1GB, and PAE doesn't meaningfully extend how much memory a 32 bit processes can have. And LAA is based on software assumptions that were never particularly tied to hardware, and it can be relevant with or without PAE.
_a_a_a_ 3y ago
The alpha only accessed 8-byte aligned mem addresses (originally anyway). The bottom 3 bits were ignored (masked out) on lookups, per the spec, to allow users to stuff juicy extra info into these.
- asb 3y ago
  Do you have a reference on that? This summary of the Alpha AXP <https://danluu.com/dick-sites-alpha-axp-architecture.pdf https://danluu.com/dick-sites-alpha-axp-architecture.pdf> states "Normal load or store instructions that specify an unaligned address take a precise data alignment trap to PALcode (which may do the access using two aligned accesses or report a fatal error, depending on the operating system design)"
  - _a_a_a_ 3y ago
    > Do you have a reference on that? Yeah, my totally infallible memory. Thanks for the PDF, nice when somebody provides more than the minimum information. Okay, from the same doc: The integer load and store quadword unaligned (LDQ_U, STQ_U) instructions ignore the low three bits of the byte address and always transfer an aligned quadword So sort of right, if you squint and don't look too closely :-) (edit: oh, you're the author? Didn't realise. Good stuff)
jandrewrogers 3y ago
This is a nice summary of the practical aspects and considerations. It isn’t something anyone should be doing explicitly on a regular basis but there are occasions, particularly in libraries, where it is the perfect tool for the job. There is also the inverse use case: smuggling pointers inside status codes, enums, and similar. For example, optionally encoding a pointer to additional error metadata for non-zero result codes. In C++ it isn’t that uncommon to also see Result types implemented similarly when the type allows it.
rr808 3y ago
My favorite hack back in MFC days was a combo box which I stored the pointer address in the text (to the right after a lot of spaces so was hidden). When a user chooses an item, parse the pointer and de-reference it back to an object.
- CoastalCoder 3y ago
  I predict that some day, you'll be beaten to death by an angry mob of screen-reader users :)
  - WJW 3y ago
    It should be easy to hide from them?
- userbinator 3y ago
  I guess you didn't come across CB_SETITEMDATA / CB_GETITEMDATA ?
  - rr808 3y ago
    Damn that brings back memories. There was a reason I didn't choose for that dialog, it was such a long time ago.
deleted 3y ago
[deleted]
marcus_holmes 3y ago
I looked at the Go implementation of this in "tagged pointers" [0] The amount of data that can be used for the tag is architecture-dependant, and the routine discards any tag bits that don't fit into the tagged pointer without telling the caller. To me, this seems ridiculous - why not just use a struct with a tag and a pointer, and not run the risk of your tag being destroyed without you knowing because the architecture can't fit that many bits? But the Go folks are smart, and must be doing this for a reason. Can anyone explain the thinking here? [0] https://github.com/golang/go/blob/master/src/runtime/tagptr_64bit.go https://github.com/golang/go/blob/master/src/runtime/tagptr_...
- yencabulator 3y ago
  It's up to the low-level code to stay within taggedPointerBits, and the value is arch-dependent. For netpoll, it looks to be just a cyclic epoch counter, so the size doesn't really matter: https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321f123d03731ddfc/src/runtime/netpoll.go#L299 https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321... For use in malloc, it's assumed to be >=10 and verified at init: https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321f123d03731ddfc/src/runtime/malloc.go#L449 https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321...
- deleted 3y ago
  [deleted]
- Splizard 3y ago
  Alignment, if you add a uint8 tag for example, you'll end up effectively doubling your pointer size.
- saagarjha 3y ago
  Auxiliary data is not free; by stuffing your data into a pointer you don’t need to pay the cost of extra storage.
- none_to_remain 3y ago
  One good use case is if you are doing atomic operations on pointers, you can atomically modify the tag as well.
ForOldHack 3y ago
My first thought was to use the Address calculation logic for an additional ALU, then... my second thought was trying to justify this during a code review... and lastly, why Microsoft used the LDT upper byte to make Xenix 286 incompatible... and the headache that changing architectures made for poor programming.
JonChesterfield 3y ago
There's a trick here I hadn't noticed. Good times. If the plan is 8 byte aligned data and use the three low bits for other stuff, you mask them off before loads/stores. An alternative is to use the high three bits, store the pointer/8, and multiply by 8 to retrieve. That's appealing on x64 because memory operations can include a *8 in the encoding. Specifically, I've long wondered whether the pointer masking tricks mess up prefetch/speculation. It seems plausible that making the dereference look more like a normal memory operation is helpful for that. (It also means the low-alignment-bits and high-unused-bits can be considered contiguous modulo the *8 on decode which is probably less annoying when using both ranges)
jonasmerlin 3y ago
"I think it's quite well known that on a 64-bit system, the maximum bit-width of a virtual address is somewhat lower (commonly 48-bits)." might actually be a perfect example of the Average Framiliarity xkcd[0]. It's perfectly fine to write it that way and the article obviously knows its intended audience. But I'm wondering what percentage of readers here actually knew this beforehand. (I learned it only pretty recently myself. And yes, I should have known this sooner, but ... didn't.) [0] https://xkcd.com/2501/ https://xkcd.com/2501/
- asb 3y ago
  Article author here. Thanks for calling that out - the intent wasn't to make readers who might not have been aware feel bad. It really came from my worry about being seen to write about something that is trivial and everyone knows already! Perhaps I'd be better just dropping "I think it's quite well known that"?
  - amelius 3y ago
    There might be (future) 64 bit systems for which it doesn't hold. So maybe replace "well known" by "widely assumed".
  - jonasmerlin 3y ago
    Hey! First of all: don't worry, it didn't make me feel bad–don't know about others though, of course. And I really meant what I said: I think you knew your (originally) intended audience, and there, the percentage of people is almost certainly quite a lot higher than among general HN readership. I just really like that comic and immediately had to think of it when I read that sentence. (And it's only made funnier by your intention, it really shows how true to life the comic actually is!) But I think there is a good, general argument to be made against these kinds of sentences. I don't think anyone would ever blame you for writing about a well known thing, while at the same time there is a chance of needlessly making people feel bad. BUT I also think that with the right "mindset", these kinds of sentences can be a good indicator to readers about what is considered essential, common knowledge among a certain group of people. So ... I don't think you need to remove it, but wouldn't say it's bad if you did. Sorry for the long winded way of saying basically nothing. Cool article btw.!
alpaca128 3y ago
There's also the Rust library smartstring which allows creating short strings without heap allocations: a Rust string consists of three values (pointer, capacity, length), so 24B on a 64bit architecture. With one byte used as tag this leaves 23 bytes for storing the string in the same space.
- OskarS 3y ago
  C++'s std::string does some version of this as well (at least on all major standard libraries), it's known as the "small string optimization".
  - orlp 3y ago
    High-performance analytic databases also do this. A common representation is to store the length in 4 bytes from a total of 16. Then if the length is <= 12 the rest of the storage is used to store the string inline, otherwise only the first 4 bytes of the string are stored inline (this can drastically speed up sorts/comparisons by not having to do a non-local access), leaving the remaining 8 bytes for a pointer. This representation is also coming to arrow. But instead of 8 bytes for a pointer it will contain 4 bytes for a buffer index, and 4 bytes for an offset into that buffer. This allows reduced effort when concatenating/merging arrays (no need to copy the data section where the long strings are stored), while remaining a relocatable/serializable format (only offsets, no pointers).
    - xoranth 3y ago
      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.
      - orlp 3y ago
        I fail to see how that is better. Null-terminated strings are a terrible idea in the first place.
dkersten 3y ago
Note that Intels 5-level paging uses 57 bit addresses, so on these processors, you can only safely assume the top 7 bits are unused. https://en.m.wikipedia.org/wiki/Intel_5-level_paging https://en.m.wikipedia.org/wiki/Intel_5-level_paging I also believe that when masking the bits off before loads/stores, you need to set them to the same value of the highest used bit (bit 47 or bit 56), while this often is 0, it’s not necessarily the case. Something to be aware of. Finally, when using C++, you gotta be careful of strict aliasing. In C++20 you can use std::bit_cast https://en.cppreference.com/w/cpp/numeric/bit_cast https://en.cppreference.com/w/cpp/numeric/bit_cast
KMag 3y ago
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.

118 points by luu 3y ago

This will be a problem when trying this on Capability Hardware Enhanced RISC Instructions (CHERI) https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ systems. Currently the only CPU with this implemented is Arm's Morello prototype. Pointers are replaced by 128-bit capabilities containing what operations are valid, a 64-bit base address and a size. These capabilities are unforgeable, so trying to play with "unused" parts of 64-bit pointers simply won't work. FreeBSD & Gnome are running on hardware after minor source-code changes, along with a significant proportion of FreeBSD ports collection. As well as ARM, Microsoft is interested: https://www.microsoft.com/en-us/research/project/portmeirion/overview/ https://www.microsoft.com/en-us/research/project/portmeirion...

powera 3y ago

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.

spacechild1 3y ago
It is also very useful for some lockfree algorithms, e.g. to fit a pointer and a sequence number within a 64-bit value.
- teh_matt 3y ago
  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.
  - ot 3y ago
    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.
    - ot 3y ago
      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 3y ago
        [deleted]
  - spacechild1 3y ago
    I don't really believe that it is easy to trigger. The thread would have to be preempted at a very specific point for a very specific duration, the other thread(s) would need to perform exactly 2^16 operations within that time window and the final operation would need to trigger the ABA problem. Possible, but extremely unlikely. (In some applications even impossible.) Do you happen to have some real world examples? But yes, it is definitely something to be aware of! BTW, if the pointers are always aligned, the sequence number may have a few bits more.
deleted 3y ago
[deleted]
JonChesterfield 3y ago
Dynamic language runtimes really like this. It gives you type information without dereferencing the pointer.
KolmogorovComp 3y ago
Any graph-heavy application constrained by memory potentially gain a lot from those kind of optimizations.
UncleEntity 3y ago
> 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.

jandrese 3y ago

Very old Macs used this trick to squeeze their ROM routines down a bit, operating with 24 bit addressing and using the top bits for flags and whatnot. Of course they ran into trouble when machines with 16MB of memory started appearing. If you do this you might be making more work for yourself in the future when you buy a new machine with 256EB of main memory.

eschneider 3y ago
Yeah, this was definitely a thing on old macs. Us olds also remember the pain and agony of cleaning this up for 32 bit addressing. Cool as these hacks are, do yourself a favor and avoid the (eventual) agony.
Dylan16807 3y ago
x86_64 (among others) specifically avoided that incompatibility, by the CPU forcing programs to mask those bits out instead of ignoring them. So programs are very compatible into the future, they just need to limit the range their memory allocator uses. Then it later added explicit automatic masking, which also avoids the problem. As long as your program can make do with smaller amounts of memory, there are no downsides.
- masklinn 3y ago
  It does not actually make the software future proof: if the kernel returns a large address the software will either fault if it checks, or stomp over then mask out the wrong thing. Virtual memory is what mitigates the issue, as it lets the OS provide large virtual addresses on a per-process basis, and independent of physical addressing. This was already used on 32b x86: PAE decorrelated the physical address space from the virtual (giving the OS 36 bits physical address — with a theoretical upper bound of 64 — even as individual processes were still restricted to 32); and on windows the /LARGEADDRESSAWARE link switch allowed manipulating the virtual address space on a per-process granularity.
  - Dylan16807 3y ago
    > 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 (giving the OS 36 bits physical address — with a theoretical upper bound of 64 — even as individual processes were still restricted to 32); and on windows the /LARGEADDRESSAWARE link switch allowed manipulating the virtual address space on a per-process granularity. I wouldn't characterize this as very similar. Physical and virtual address space already had to be decorrelated to go above about 1GB, and PAE doesn't meaningfully extend how much memory a 32 bit processes can have. And LAA is based on software assumptions that were never particularly tied to hardware, and it can be relevant with or without PAE.

_a_a_a_ 3y ago

The alpha only accessed 8-byte aligned mem addresses (originally anyway). The bottom 3 bits were ignored (masked out) on lookups, per the spec, to allow users to stuff juicy extra info into these.

asb 3y ago
Do you have a reference on that? This summary of the Alpha AXP <https://danluu.com/dick-sites-alpha-axp-architecture.pdf https://danluu.com/dick-sites-alpha-axp-architecture.pdf> states "Normal load or store instructions that specify an unaligned address take a precise data alignment trap to PALcode (which may do the access using two aligned accesses or report a fatal error, depending on the operating system design)"
- _a_a_a_ 3y ago
  > Do you have a reference on that? Yeah, my totally infallible memory. Thanks for the PDF, nice when somebody provides more than the minimum information. Okay, from the same doc: The integer load and store quadword unaligned (LDQ_U, STQ_U) instructions ignore the low three bits of the byte address and always transfer an aligned quadword So sort of right, if you squint and don't look too closely :-) (edit: oh, you're the author? Didn't realise. Good stuff)

jandrewrogers 3y ago

This is a nice summary of the practical aspects and considerations. It isn’t something anyone should be doing explicitly on a regular basis but there are occasions, particularly in libraries, where it is the perfect tool for the job. There is also the inverse use case: smuggling pointers inside status codes, enums, and similar. For example, optionally encoding a pointer to additional error metadata for non-zero result codes. In C++ it isn’t that uncommon to also see Result types implemented similarly when the type allows it.

rr808 3y ago

My favorite hack back in MFC days was a combo box which I stored the pointer address in the text (to the right after a lot of spaces so was hidden). When a user chooses an item, parse the pointer and de-reference it back to an object.

CoastalCoder 3y ago
I predict that some day, you'll be beaten to death by an angry mob of screen-reader users :)
- WJW 3y ago
  It should be easy to hide from them?
userbinator 3y ago
I guess you didn't come across CB_SETITEMDATA / CB_GETITEMDATA ?
- rr808 3y ago
  Damn that brings back memories. There was a reason I didn't choose for that dialog, it was such a long time ago.

deleted 3y ago

[deleted]

marcus_holmes 3y ago

I looked at the Go implementation of this in "tagged pointers" [0] The amount of data that can be used for the tag is architecture-dependant, and the routine discards any tag bits that don't fit into the tagged pointer without telling the caller. To me, this seems ridiculous - why not just use a struct with a tag and a pointer, and not run the risk of your tag being destroyed without you knowing because the architecture can't fit that many bits? But the Go folks are smart, and must be doing this for a reason. Can anyone explain the thinking here? [0] https://github.com/golang/go/blob/master/src/runtime/tagptr_64bit.go https://github.com/golang/go/blob/master/src/runtime/tagptr_...

yencabulator 3y ago
It's up to the low-level code to stay within taggedPointerBits, and the value is arch-dependent. For netpoll, it looks to be just a cyclic epoch counter, so the size doesn't really matter: https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321f123d03731ddfc/src/runtime/netpoll.go#L299 https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321... For use in malloc, it's assumed to be >=10 and verified at init: https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321f123d03731ddfc/src/runtime/malloc.go#L449 https://github.com/golang/go/blob/4956c3437bd2f4448bcec51321...
deleted 3y ago
[deleted]
Splizard 3y ago
Alignment, if you add a uint8 tag for example, you'll end up effectively doubling your pointer size.
saagarjha 3y ago
Auxiliary data is not free; by stuffing your data into a pointer you don’t need to pay the cost of extra storage.
none_to_remain 3y ago
One good use case is if you are doing atomic operations on pointers, you can atomically modify the tag as well.

ForOldHack 3y ago

My first thought was to use the Address calculation logic for an additional ALU, then... my second thought was trying to justify this during a code review... and lastly, why Microsoft used the LDT upper byte to make Xenix 286 incompatible... and the headache that changing architectures made for poor programming.

JonChesterfield 3y ago

There's a trick here I hadn't noticed. Good times. If the plan is 8 byte aligned data and use the three low bits for other stuff, you mask them off before loads/stores. An alternative is to use the high three bits, store the pointer/8, and multiply by 8 to retrieve. That's appealing on x64 because memory operations can include a *8 in the encoding. Specifically, I've long wondered whether the pointer masking tricks mess up prefetch/speculation. It seems plausible that making the dereference look more like a normal memory operation is helpful for that. (It also means the low-alignment-bits and high-unused-bits can be considered contiguous modulo the *8 on decode which is probably less annoying when using both ranges)

jonasmerlin 3y ago

"I think it's quite well known that on a 64-bit system, the maximum bit-width of a virtual address is somewhat lower (commonly 48-bits)." might actually be a perfect example of the Average Framiliarity xkcd[0]. It's perfectly fine to write it that way and the article obviously knows its intended audience. But I'm wondering what percentage of readers here actually knew this beforehand. (I learned it only pretty recently myself. And yes, I should have known this sooner, but ... didn't.) [0] https://xkcd.com/2501/ https://xkcd.com/2501/

asb 3y ago
Article author here. Thanks for calling that out - the intent wasn't to make readers who might not have been aware feel bad. It really came from my worry about being seen to write about something that is trivial and everyone knows already! Perhaps I'd be better just dropping "I think it's quite well known that"?
- amelius 3y ago
  There might be (future) 64 bit systems for which it doesn't hold. So maybe replace "well known" by "widely assumed".
- jonasmerlin 3y ago
  Hey! First of all: don't worry, it didn't make me feel bad–don't know about others though, of course. And I really meant what I said: I think you knew your (originally) intended audience, and there, the percentage of people is almost certainly quite a lot higher than among general HN readership. I just really like that comic and immediately had to think of it when I read that sentence. (And it's only made funnier by your intention, it really shows how true to life the comic actually is!) But I think there is a good, general argument to be made against these kinds of sentences. I don't think anyone would ever blame you for writing about a well known thing, while at the same time there is a chance of needlessly making people feel bad. BUT I also think that with the right "mindset", these kinds of sentences can be a good indicator to readers about what is considered essential, common knowledge among a certain group of people. So ... I don't think you need to remove it, but wouldn't say it's bad if you did. Sorry for the long winded way of saying basically nothing. Cool article btw.!

alpaca128 3y ago

There's also the Rust library smartstring which allows creating short strings without heap allocations: a Rust string consists of three values (pointer, capacity, length), so 24B on a 64bit architecture. With one byte used as tag this leaves 23 bytes for storing the string in the same space.

OskarS 3y ago
C++'s std::string does some version of this as well (at least on all major standard libraries), it's known as the "small string optimization".
- orlp 3y ago
  High-performance analytic databases also do this. A common representation is to store the length in 4 bytes from a total of 16. Then if the length is <= 12 the rest of the storage is used to store the string inline, otherwise only the first 4 bytes of the string are stored inline (this can drastically speed up sorts/comparisons by not having to do a non-local access), leaving the remaining 8 bytes for a pointer. This representation is also coming to arrow. But instead of 8 bytes for a pointer it will contain 4 bytes for a buffer index, and 4 bytes for an offset into that buffer. This allows reduced effort when concatenating/merging arrays (no need to copy the data section where the long strings are stored), while remaining a relocatable/serializable format (only offsets, no pointers).
  - xoranth 3y ago
    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.
    - orlp 3y ago
      I fail to see how that is better. Null-terminated strings are a terrible idea in the first place.

dkersten 3y ago

Note that Intels 5-level paging uses 57 bit addresses, so on these processors, you can only safely assume the top 7 bits are unused. https://en.m.wikipedia.org/wiki/Intel_5-level_paging https://en.m.wikipedia.org/wiki/Intel_5-level_paging I also believe that when masking the bits off before loads/stores, you need to set them to the same value of the highest used bit (bit 47 or bit 56), while this often is 0, it’s not necessarily the case. Something to be aware of. Finally, when using C++, you gotta be careful of strict aliasing. In C++20 you can use std::bit_cast https://en.cppreference.com/w/cpp/numeric/bit_cast https://en.cppreference.com/w/cpp/numeric/bit_cast

KMag 3y ago

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.