0

I am looking for a bit-packing like schemed for compressing integers, then I came across the PinterIntPair part of the LLVM project, however I couldn't figure out exactly how this is done. Would anyone elaborate more about it!

They explain:

PointerIntPair - This class implements a pair of a pointer and small integer. It is designed to represent this in the space required by one pointer by bitmangling the integer into the low part of the pointer. This can only be done for small integers: typically up to 3 bits, but it depends on the number of bits available according to PointerLikeTypeTraits for the type.

mmain
  • 333
  • 3
  • 19
  • Asking for tutorials is off-topic for StackOverflow. – Remy Lebeau Oct 23 '19 at 18:45
  • _"...typically up to 3 bits..."_ possibly spare bits because of alignment requirements of the pointed to type. – Richard Critten Oct 23 '19 at 18:47
  • @RemyLebeau this question https://stackoverflow.com/questions/509211/understanding-slice-notation has 2969 votes and it is asking for explanation as my question – mmain Oct 23 '19 at 19:38
  • 1
    @RemyLebeau omar is just asking for an explanation of how PointerIntPair works, how is that off-topic?? – tjysdsg Jun 05 '21 at 05:48

1 Answers1

1

That particular class takes advantage of the fact that on many architectures, the low n bits of pointers are all zero. n is often 3 on today's 64-bit machines.

Therefore, it's possible to store a pointer and a small integer on top of each other, by checking that those bits are zero when the pointer is accepted during object initialisation and setting them to zero when returning the pointer for usage.

It would also be possible to store a few booleans, but what this class stored is an int.

arnt
  • 8,949
  • 5
  • 24
  • 32
  • I found out that this technique is called Tagged Pointer, I edited the question for more info about it. anyhow, I think that 3 bits is not so much, and maybe this would not be good during debugging (I may be incorrect) – mmain Oct 23 '19 at 20:28
  • 1
    No, this is not a tagged pointer. A tagged pointer is when the int is used to describe what the pointer points to, e.g. 'this is a pointer to an int', 'this is a pointer to a string'. Tagged pointers typically use much more than eight types, so need more than 3 bits. This class is used for other purposes, quite often for storing an enum and a pointer. – arnt Oct 24 '19 at 06:16
  • OK thanks for clearing that out, it seemed related to me, I removed my edit and the question is on hold anyway – mmain Oct 24 '19 at 08:08