6 ms·
Stealing bits from pointers makes sense sometimes, but in most cases an easier and less error-prone way to increase memory efficiency is to just use indices or
by gizmo 2y ago
Stealing bits from pointers makes sense sometimes, but in most cases an easier and less error-prone way to increase memory efficiency is to just use indices or relative pointers. Instead of shaving individual bits of a pointer take advantage of the fact that most pointers in a program are almost exactly alike.
Instead of storing a 64 bit prev and next pointer for an item in a linked list just store e.g. two 16 bit offsets. Then the next_ptr = (this_ptr & base_mask) + offset * alignment.
Most of the time wasting memory by storing full 64bit pointers is no big deal. But when it is, you can go a lot further than just shaving off a few bits.
If you want to be extra clever you can encode values in the base address of your pointers by taking advantage of how virtual memory is allocated. Every process has its own virtual memory pages and you can request memory pages at specific address ranges. For instance if you align all your memory at a 32gb boundary then you can use 32bit pointers + a base pointer without even having to mask. You can also use virtual memory allocation tricks to convey information about alignment, typing, whether a pointer is allowed to be shared between threads and so on. And again, without having to butcher the pointer itself.
- jsheard 2y agoConsidering how common it is to use indices in lieu of pointers in Rust, it would be nice if it had native NonMax integer types similar to the NonZero types it already has. NonZero gives you the niche-filling optimization (e.g. Option<NonZero> and NonZero are the same size) but with indices you want zero to be a valid value, so it would be natural to use the maximum as the illegal value instead. You can kind of do it by offsetting the index by 1 or inverting the bits then putting it in a NonZero but that's a small extra runtime cost on every use.
- joseluis 2y agoYou can do a handy struct wrapper over a private Nonzero that xors the given value with the prohibited value (max in this case) at the new constructor. And like so for the get method. Xoring is very cheap. That's my favorite way of storing indices/links for nodes, since you can wrap them in Option for free.
- o11c 2y agoAddition/subtraction are more likely to optimize well I think, since pointer arithmetic already uses those.
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]
- jsheard 2y agoGood point, on x86 at least the mov instruction can add/subtract a constant from the address by itself since that pattern is so common.
- zozbot234 2y agoThis requires using arenas extensively in your program or perhaps playing tricks with virtual memory, because your system allocator will give you arbitrary pointers by default and you'll often want to point to an object from a different allocation.
- gizmo 2y agoRight. Which is why I favor doing your own memory management entirely (which has some huge advantages) or not worrying about memory at all and trusting a garbage collector. I don't think there are many situations left where memory management is too important to leave to a gc but not important enough to do from scratch.
- adql 2y agoPlenty of niche ways that are limited enough to not require program wide architecture change https://muxup.com/2023q4/storing-data-in-pointers#some-real-world-examples https://muxup.com/2023q4/storing-data-in-pointers#some-real-...
- gpderetta 2y agoDefinitely indices are a great option, but then you need a base pointer and a way to allocate off of it. That can add significant complexity. So it is all a tradeoff.
- dkjaudyeqooe 2y agoThat's really not the application for this, it's tags, which are endlessly useful or characterizing the pointer. For instance you can use the MSBs to establish the type of whats pointed to, or for reference counting. I use the LSB to indicate if the value is a pointer or an unsigned integer, whereby you can store both an (integer) key to a record in a database, or a pointer to the record data in memory. You could use another bit in the pointer to indicate that the record is dirty. Using unused bits in pointers can make you code more efficient and simpler.
- westurner 2y agoCan unused bits be used for signed pointers or CRCs?
- aetherspawn 2y agoI would argue that we shouldn’t bother to build CRC checking of memory into programs and that ECC RAM should just become the norm eventually. 99.9999% of memory operations aren’t CRC-d so trying to fight against flaky hardware is a bit of an uphill battle.
- westurner 2y agoPointer authentication: https://llvm.org/docs/PointerAuth.html https://llvm.org/docs/PointerAuth.html : > Pointer Authentication is a mechanism by which certain pointers are signed. When a pointer gets signed, a cryptographic hash of its value and other values (pepper and salt) is stored in unused bits of that pointer. > Before the pointer is used, it needs to be authenticated, i.e., have its signature checked. This prevents pointer values of unknown origin from being used to replace the signed pointer value. ECC can't solve for that because it would only have one key for all processes. Given a presumption of side channel writes, pointer auth is another layer of defense that may or may not be worth the loss in performance. https://news.ycombinator.com/item?id=21791269#21800181 https://news.ycombinator.com/item?id=21791269#21800181