5 ms·

I think pointer compression is worthy of a masters/PhD thesis in compiler design if it hasn't been done already. Should be ubiquitous, if you don't have a progr

I think pointer compression is worthy of a masters/PhD thesis in compiler design if it hasn't been done already. Should be ubiquitous, if you don't have a program that will ever require the amount of memory needed for more than a 2^N bit number the pointers should probably be compressed and arithmetic optimized. There's a lot of edge cases to look for there however.

Taniwha 7y ago
It's pretty trivial, from a compiler point of view - not being able to take real pointers is going to make code slower in some cases - the hard part is things like partially computed pointers that get spilled onto the stack (esp if you are doing GC)
- unlinked_dll 7y ago
  GC is interesting, because often times the concept of a reference is a concept of identity, whereas a pointer is a concept of location in the heap. Things like reallocating GC that shuffle around location on the fly make this a bit easier since your references only pertain to identity, and the compression can be applied to estimating or validating the total number of identities won't exceed some maximum for a valid set of inputs to the program.
bdash 7y ago
A student from University of Illinois at Urbana-Champaign wrote a paper on transparent pointer compression in their custom GCC backend back in 2005: https://llvm.org/pubs/2005-06-12-MSP-PointerComp.pdf https://llvm.org/pubs/2005-06-12-MSP-PointerComp.pdf. Their compiler backend went places, but I'm not sure if the optimization described in the paper ever made it into production.
chubot 7y ago
There's been a bunch of work on it in the last 10-20 years... Here are some (disorganized) links, including the one by Chris Lattner mentioned in a sibling comment: https://github.com/oilshell/oil/wiki/Compact-AST-Representation https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
- joe_the_user 7y ago
  This is a really cool reference that actually appears to be just what I'm seeking, cheers.
chrisseaton 7y ago
> worthy of a masters/PhD thesis in compiler design if it hasn't been done already You can’t just write a thesis about someone else’s existing idea! You’re supposed to come up with a new idea!
ndesaulniers 7y ago
Or if vtables had relative offsets, rather than absolute addresses? Fuchsia is designing their ABI with that change to the Itanium ABI.
- vidarh 7y ago
  It's unclear what you mean here. Lots of uses of vtables will use offsets to look up a specific slot in a vtable, but the total space used by vtables in most systems will be a tiny proportion of the heap, so storing the pointers in the vtables as offsets doesn't seem likely to make much difference.
  - ndesaulniers 7y ago
    What's in those slots? (Full pointers) https://itanium-cxx-abi.github.io/cxx-abi/cxx-vtable-ex.html https://itanium-cxx-abi.github.io/cxx-abi/cxx-vtable-ex.html https://bugs.llvm.org/show_bug.cgi?id=26723 https://bugs.llvm.org/show_bug.cgi?id=26723
    - vidarh 7y ago
      Yes, but there's only 1 vtable per class. While the latter shows a shockingly high reduction in code size, which seems to imply a ludicrous number of tiny classes with few call sites per method in use in the Chromium code base, relative to what I've seen when doing compiler development, it shouldn't translate into much of a change in heap usage. From reading those, my main takeaway is that the Chromium codebase sounds awful.
- iainmerrick 7y ago
  Is Itanium still around??
  - ndesaulniers 7y ago
    Its ABI is. https://stackoverflow.com/q/53455855 https://stackoverflow.com/q/53455855
- 7y ago

Taniwha 7y ago

It's pretty trivial, from a compiler point of view - not being able to take real pointers is going to make code slower in some cases - the hard part is things like partially computed pointers that get spilled onto the stack (esp if you are doing GC)

unlinked_dll 7y ago
GC is interesting, because often times the concept of a reference is a concept of identity, whereas a pointer is a concept of location in the heap. Things like reallocating GC that shuffle around location on the fly make this a bit easier since your references only pertain to identity, and the compression can be applied to estimating or validating the total number of identities won't exceed some maximum for a valid set of inputs to the program.

bdash 7y ago

A student from University of Illinois at Urbana-Champaign wrote a paper on transparent pointer compression in their custom GCC backend back in 2005: https://llvm.org/pubs/2005-06-12-MSP-PointerComp.pdf https://llvm.org/pubs/2005-06-12-MSP-PointerComp.pdf. Their compiler backend went places, but I'm not sure if the optimization described in the paper ever made it into production.

chubot 7y ago

There's been a bunch of work on it in the last 10-20 years... Here are some (disorganized) links, including the one by Chris Lattner mentioned in a sibling comment: https://github.com/oilshell/oil/wiki/Compact-AST-Representation https://github.com/oilshell/oil/wiki/Compact-AST-Representat...

joe_the_user 7y ago
This is a really cool reference that actually appears to be just what I'm seeking, cheers.

chrisseaton 7y ago

> worthy of a masters/PhD thesis in compiler design if it hasn't been done already You can’t just write a thesis about someone else’s existing idea! You’re supposed to come up with a new idea!

ndesaulniers 7y ago

Or if vtables had relative offsets, rather than absolute addresses? Fuchsia is designing their ABI with that change to the Itanium ABI.

vidarh 7y ago
It's unclear what you mean here. Lots of uses of vtables will use offsets to look up a specific slot in a vtable, but the total space used by vtables in most systems will be a tiny proportion of the heap, so storing the pointers in the vtables as offsets doesn't seem likely to make much difference.
- ndesaulniers 7y ago
  What's in those slots? (Full pointers) https://itanium-cxx-abi.github.io/cxx-abi/cxx-vtable-ex.html https://itanium-cxx-abi.github.io/cxx-abi/cxx-vtable-ex.html https://bugs.llvm.org/show_bug.cgi?id=26723 https://bugs.llvm.org/show_bug.cgi?id=26723
  - vidarh 7y ago
    Yes, but there's only 1 vtable per class. While the latter shows a shockingly high reduction in code size, which seems to imply a ludicrous number of tiny classes with few call sites per method in use in the Chromium code base, relative to what I've seen when doing compiler development, it shouldn't translate into much of a change in heap usage. From reading those, my main takeaway is that the Chromium codebase sounds awful.
iainmerrick 7y ago
Is Itanium still around??
- ndesaulniers 7y ago
  Its ABI is. https://stackoverflow.com/q/53455855 https://stackoverflow.com/q/53455855
7y ago