What are the real life use cases for tagged pointers?

This is mostly coming from reading about small 64-bit systems and possible uses of 64-bit word pointers.

To my understanding tagged pointers are addresses which can containing extra information in bits due to possible address space on that particular architecture is much smaller.

But then, is it possible to use tagged pointers beyond trivial cases? Any cool ideas / examples?

Are there popular libraries, frameworks taking advantage of 64-bit pointers via tagged pointers? Is that possible on every hardware?

closed as off-topic by gnat, user40980, ozz, GlenH7, Michael Kohne Oct 3 '13 at 20:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to recommend a tool, library or favorite off-site resource are off-topic for Programmers as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – gnat, Community, ozz
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    Lisps frequently use tagged pointers to seamlessly switch between integers and bignums. With one tag the adress is interpreted as int and with another tag it is interpreted as pointer to a bignum. – Patrick Oct 2 '13 at 14:38
  • 2
    Some real uses of tagged pointers: * The Objective-C runtime in Mac OS X 10.7 - mikeash.com/pyblog/… * The Objective-C runtime in iOS 7 on ARM64 - mikeash.com/pyblog/friday-qa-2013-09-27-arm64-and-you.html – Andrew Medico Oct 2 '13 at 17:23
  • of course a down vote... again... without any comment. – auselen Oct 2 '13 at 18:10
  • 1
    This question appears to be off-topic because it is a polling based question. No criteria have been provided to make any particular answer stand out more than any other answer. – GlenH7 Oct 3 '13 at 13:28
  • So this is not about "data structure concepts"? (programmers.stackexchange.com/help/on-topic) hmm... – auselen Oct 4 '13 at 18:33

The critbit trie library uses tagged pointers to differentiate between internal and external nodes in the trie. By ensuring that new nodes are allocated aligned to a certain value you are guaranteed that some of the lower bits of the address are zero, the number of which depends on the alignment you require. You can then store other info in these bits... in the case of critbit nodes the LSB is set if the node is external (a leaf). Just remember to untag the address if you intend to use it.

It saves having an extra member variable in the node structure.

  • The same trick is used in kd trees used for ray tracing - Wald et al. align nodes such that the lower two bits of the child pointer are always zero and use those bits to store the splitting plane. – user7043 Oct 2 '13 at 16:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.