Ownership tag pointers

Development Compiler
1

Hi, I would like to share a concept that I implemented and works, maybe could work in swift since it is about ref-counting objects.

The idea is every ref object pointer carries a one‑bit tag in its lowest bit:

  • Own_Ref (bit = 1) – owns the object; responsible for decrementing the reference count on release.

  • Borrow_Ref (bit = 0) – a non‑owning view; release is a no‑op, meaning after checking the bit.

The api is

Operation Meaning Input → Output RC Change
borrow(x) Create a borrowed view. Any → Borrow_Ref None
transfer(x) Move a reference unchanged. Own → Own, Borrow → Borrow None
own(x) Promote to Own_Ref if needed,
ex. when the pointer is returned.		 Borrow → Own (RC++)
Own → Own (no‑op)		 Only if Borrowed
share(x) Create an independent owner. Any → Own_Ref Always RC++
release(x) Drop this reference. Own → RC-- (free if 0)
Borrow → nothing		 Only if Owned

Here using liveness for insertion on a single thread

Function call

x liveness Operation Release x?
Live after call callee(borrow(x)) -
Dead after call callee(transfer(x)) No, responsibility moved

v = get(obj, f) operartion

v liveness Operation
Live after v = share(raw_get(obj, f))
Dead after v = borrow(raw_get(obj, f))

set(obj, f, val) operation

  1. release(transfer(raw_get(obj, f))) – always release the old field value.
  2. Then:
val liveness Operation Release val ?
Dead after raw_set(obj, f, own(val)) No,responsability moved
Live after raw_set(obj, f, share(val)) -

Example of optimization:

  1. share -> borrow when the pointer is does not escape
  2. own -> transfer when the previous pointer is dead.

More optimization could be done, whenever it is safe to do.

This is not a complete description, it is about summarizing the idea.

1 Like
2

It's a neat idea for some language, but it would be an ABI break for Swift.

2 Likes
3

Someone on the team at Apple was actually exploring this idea years ago (or, well, something similar). We came to the conclusion that…it doesn't actually do anything if everybody is following the ARC rules:

  • if you statically know someone else is holding on to a value for you, you only need to do your own retaining if it's (possibly) going to outlive the current borrow, such as assigning to a property or calling a function that accepts an owned value
  • if you statically know that someone else has given you an owned value, the same thing is true, except you're responsible for doing one release at the end

Swift today says "you are always in one of these two scenarios". Adding this kind of run-time tracking would allow for a third one: "the value you're given might be owned or it might be borrowed". This turns out to be the worst of both cases from a complexity perspective! Now you only have the guarantees of a borrowed value, but you still have to try to release it when you're done with it.

Now, the optimizer has fallen short of those two bullet points in Swift's history, doing more retains and releases than are strictly necessary. Separate compilation makes this tricky too: if a function takes an argument as owned but only benefits from that on one branch, the caller still has to do a retain even if they wouldn't end up on that branch. And most of the time Swift developers don't manually choose owned and borrowed, because it's still relatively new and the defaults are usually good enough (but not always!). So I can't say a scheme like this is never beneficial—it'd be good for some programs and less good for others. But it is less transformative than it seems at first glance.

8 Likes
4

Agree, It would break the ABI.

5

That's the point of the optimization here, trying to release becomes releasing and that is just a bit check, instead of receiving an owned value which will involve an RC when releasing. A bit check is cheaper than the RC.

All the insertions is done by the compiler, none would be seen by the programmer.

Since it would break the ABI, on that case it is irrelevant since all value should follow the tag convention in order to work.

Thanks.