41–50 of 71 posts
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.
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.
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".
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
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.
Earlier quoted context omitted.
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".
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 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…
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.
Earlier quoted context omitted.
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 downsi…
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 fro…
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.
Earlier quoted context omitted.
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 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…
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.
Earlier quoted context omitted.
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 fro…
> 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…
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 meaningfully extend how much memory a 32 bit processes can have.
Of course not. What it does is show that there is no correlation between the physical and virtual address spaces, so you can have a 64 bits physical address space and only provide a 48 bits virtual address space to applications.
> And LAA is based on software assumptions that were never particularly tied to hardware, and it can be relevant with or without PAE.
Missing the point, the example of LAA shows that the OS can provide different virtual address spaces to different processes. So the OS can provide 48 bit virtual address spaces by default, and a full 64 bits virtual address space to applications which request it. The former can then keep using tagged pointers just fine.
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.
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.
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)