4 ms·

AFAICT, x32 is basically dead. I'm gonna go out on very thin ice and disagree with a Donald Knuth quote: > It is absolutely idiotic to have 64-bit pointers wh

AFAICT, x32 is basically dead. I'm gonna go out on very thin ice and disagree with a Donald Knuth quote: > It is absolutely idiotic to have 64-bit pointers when I compile a program that uses less than 4 gigabytes of RAM. When such pointer values appear inside a struct, they not only waste half the memory, they effectively throw away half of the cache. In general if shrinking the pointer size is a huge optimization, your data structures have too many pointers in them. Learning Rust was a turning point for me here. The borrow checker encouraged me to get rid of references to parents or siblings. In general, I ended up passing parent references on the program stack and having sibling references (e.g. in graph structures) via indices into a slab, which can be u32 rather than pointer-sized. You could also write a SmallVec/SmallString that uses u32 for len/capacity rather than usize, which would be a nice savings if you have lots of them. And/or move the len/capacity inside the heap allocation, so empty/unallocated vecs/strings don't have those fields at all. Or do what Rust's smallvec crate does and C++'s std::string's "small string optimization" does: carve out the space for them but use it for actual object storage until it overflows and you need to move to the heap. If you're working in a language that doesn't have value objects (that is, all user-defined structures are implicitly boxed), my sympathy, you will just end up with a bunch of extra pointers, which is why this kind of optimization is important for Java and JS. I consider lack of value objects to be a significant design flaw in a language.

dist1ll 4y ago
I'm not sure I understand your point. First you say: > In general if shrinking the pointer size is a huge optimization, your data structures have too many pointers in them. And then you go on to say > having sibling references (e.g. in graph structures) via indices into a slab, which can be u32 rather than pointer-sized. What you're describing is literally pointer compression. You're using offset indices that point to a compressed/sufficiently small address space.
- scottlamb 4y ago
  > What you're describing is literally pointer compression. You're using offset indices that point to a compressed/sufficiently small address space. True, but it's finer-grained than a global switch. I can decide that I will have at most 2^32-1 objects in this particular graph/slab without giving up the ability for my program to address more than 4 GiB of RAM in total as it would with the x32 ABI. Also, this trick is only a small part of reducing pointer storage. I mentioned passing stuff in via the stack vs keeping it in the data structure. I forgot to mention: use vecs rather than e.g. linked lists, open addressing hash maps rather than chaining, btrees rather than red/black trees, etc. This is also stuff that Rust's std library encourages. btw: of course none of the techniques I mention are unknown to Donald Knuth. He's likely either wanting to get programs written by others to run more quickly or trying to optimize well beyond what I'd care to do. I'd rather split the difference, basically: decrease pointer density a fair bit and keep the pointers at 64-bit.
  - dist1ll 4y ago
    Fair enough, I agree that a global x32 switch seems misguided, especially since efficient data structures are already written in cache-aware ways.
speed_spread 4y ago
You can still build a Gentoo system using the 'abi_x86_x32' flag.
cryptonector 4y ago
You're basically screaming "don't use so many pointers!", but this much much easier said than done. You can only really do this if you write the entire stack -all the dependencies- yourself, just so you can optimize like this. This approach doesn't scale or compose well at all.
- scottlamb 4y ago
  That's just like saying you can only optimize CPU usage if you've written the world perfectly from scratch. In reality, profiles aren't flat. A little effort in the right spot can go a long way for any optimization goal.

dist1ll 4y ago

I'm not sure I understand your point. First you say: > In general if shrinking the pointer size is a huge optimization, your data structures have too many pointers in them. And then you go on to say > having sibling references (e.g. in graph structures) via indices into a slab, which can be u32 rather than pointer-sized. What you're describing is literally pointer compression. You're using offset indices that point to a compressed/sufficiently small address space.

scottlamb 4y ago
> What you're describing is literally pointer compression. You're using offset indices that point to a compressed/sufficiently small address space. True, but it's finer-grained than a global switch. I can decide that I will have at most 2^32-1 objects in this particular graph/slab without giving up the ability for my program to address more than 4 GiB of RAM in total as it would with the x32 ABI. Also, this trick is only a small part of reducing pointer storage. I mentioned passing stuff in via the stack vs keeping it in the data structure. I forgot to mention: use vecs rather than e.g. linked lists, open addressing hash maps rather than chaining, btrees rather than red/black trees, etc. This is also stuff that Rust's std library encourages. btw: of course none of the techniques I mention are unknown to Donald Knuth. He's likely either wanting to get programs written by others to run more quickly or trying to optimize well beyond what I'd care to do. I'd rather split the difference, basically: decrease pointer density a fair bit and keep the pointers at 64-bit.
- dist1ll 4y ago
  Fair enough, I agree that a global x32 switch seems misguided, especially since efficient data structures are already written in cache-aware ways.

speed_spread 4y ago

You can still build a Gentoo system using the 'abi_x86_x32' flag.

cryptonector 4y ago

You're basically screaming "don't use so many pointers!", but this much much easier said than done. You can only really do this if you write the entire stack -all the dependencies- yourself, just so you can optimize like this. This approach doesn't scale or compose well at all.

scottlamb 4y ago
That's just like saying you can only optimize CPU usage if you've written the world perfectly from scratch. In reality, profiles aren't flat. A little effort in the right spot can go a long way for any optimization goal.