1

I'm writing my own dynamic programming language. So far I've been using a tagged union for all values. Since this boxes primitive types needlessly, I've begun researching tagged pointers which seem to be a common solution.

It works by taking advantage of pointer alignment requirements which result in a certain number of bits always being zero in valid pointers. Those can be used to mark other primitive types and fold the value into the pointer itself. A 16 byte aligned pointer provides 4 tag bits.

if (pointer & 1) {
    // upper 63 bits hold an integer
    long integer = ((uintptr_t) pointer) >> 1;
}

However, according to this paper, this has costs. In particular, it can interact badly with processor branch prediction. So I decided to consider alternatives as well.

In my research, I found that people also use so called fat pointers. Instead of one tagged pointer, two words are used: one for the polymorphic value and another for the metadata.

struct value {
    union {
        long integer;
        double decimal;
        union heap_value {
            /* list,
               vector,
               table,
               string
               ...
             */
        } *pointer;

    } value;  /* first word/register */

    struct {
        enum type {
            /* -fshort-enums
               list,
               vector,
               table,
               string
               ...
             */
        } type;
        struct {
            bool marked: 1;
            bool live: 1;
            /* ... */
        } flags;

    } metadata; /* second word/register */
};

I find this to be a very elegant solution. It would avoid boxing while being really simple and easy to use and understand.

Tradeoffs include the fact it would occupy two registers, reducing the effectiveness of processor caching. I've also seen people claim that it's a "non-starter" because two words can't be accessed atomically. It doesn't seem like a big deal to me but I'm not sure.

I couldn't find any literature comparing these two techniques. Most language implementations I've looked at use tagged pointers. Is it known if the tradeoff is worth it? Has the performance been benchmarked?

5
  • 3
    Fat pointers have the benefit that the type can always point to metadata (e.g. a vtable) and the data can be completely opaque, as long as it fits within 1 word. This is highly flexible and reduces the need to always special-case a handfull of primitive types. Also plays reasonably nice with debuggers and is highly portable, unlike tagged pointers. Fat pointers don't need their metadata if the type is already known, e.g. in a homogeneous array where you can store one copy for all items. Tags are less portable, but you have ~20 bits available in practice (I think x86 uses 46 of 64 bits).
    – amon
    Nov 29, 2023 at 15:44
  • @amon Excellent points, thank you. Nov 29, 2023 at 16:15
  • 2
    Are you aware of the new Programming Language Design and Implementation (BETA) SE? Note: your question is perfectly on-topic here and there is no need to delete it. It is perfectly fine for a question to be on-topic on multiple stacks, in which case you can choose the stack which most closely fits the answers you are looking for. You can even ask the question on multiple stacks, but PLEASE make sure you tailor the question specifically to each stack so that the answers have as little overlap as possible. Nov 29, 2023 at 18:02
  • @JörgWMittag I was not aware. I will register right now. Thank you. Nov 29, 2023 at 18:55
  • 1
    This question was also posted in reddit.com/r/ProgrammingLanguages/comments/186nai0/…
    – amon
    Nov 29, 2023 at 23:15

1 Answer 1

4

Right now many OSes start using cryptographically tagged pointers to prevent attacks. Today I would look into that before using pointers in a way that might make them unusable in the future.

On the other hand, if you are for example sure that pointers to instances are always say 16 byte aligned, then a non-zero value in the lowest four bits would distinguish clearly between pointer and non-pointer.

It means you can use the lowest 4 bits as an enum with 16 values - one “pointer to instance” and 15 for anything else. So you could store 60 bit integers, double with a reduced exponent range, timestamps with nanoseconds for +/- 15 years, strings with up to six characters, and whatever else you can think of.

1
  • That's true... There are already smartphones in the market with support for ARM memory tagging extensions. I'll definitely take that into account. Nov 29, 2023 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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