Hacker News Reader

Comment by unlinked_dll | Hacker News Reader

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.

View on HN

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-Representat...

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

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. Their compiler backend went places, but I'm not sure if the optimization described in the paper ever made it into production.

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)

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.

> 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!

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

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.

What's in those slots? (Full pointers)

https://itanium-cxx-abi.github.io/cxx-abi/cxx-vtable-ex.html

https://bugs.llvm.org/show_bug.cgi?id=26723

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.

Is Itanium still around??

Its ABI is.

https://stackoverflow.com/q/53455855

Why are you talking about the itanium API instead of the x86-64 API?

The Itanium ABI lives on in x86_64.

https://stackoverflow.com/q/53455855

Reply on news.ycombinator.com