[swift-dev] [Discussion] New refcount representation

[Greg Parker]

> On Mar 16, 2016, at 1:42 PM, Brent Royal-Gordon <brent at architechies.com> wrote:
> 
> This is damned clever.
> 
>> * Allows inexpensive per-object storage for future features like associated references or class extensions with instance variables.
> 
> It sounds like you wouldn't be able to resize an out-of-band refcount allocation once it's been created, though, right? There are pointers to it all over memory; you can't track them all unless you save back references to all of them. So if you added, say, a refcount allocation-based feature for extension ivars, every refcount allocation would need to have the extra pointers to accommodate them in case you dynamically loaded code later that added an ivar in an extension. You couldn't go "whoops, need space for ivars, let's replace this recount allocation with one that has room for another pointer".

Yes, every side allocation would need to include all of the storage needed for any side allocation feature. That size is sufficiently small, I think; perhaps something like this:

struct {
    void* object;
    uint32_t strongRefCount;
    uint32_t unownedRefCount;
    uint32_t weakRefCount;
    void* associatedReferenceDictionary;
    void* extensionIvarDictionary;
}


>> The MSB bit also becomes set if you increment or decrement a retain count too far. That means we can implement the RR fast path with a single conditional branch after the increment or decrement:
> 
> You don't talk much about it, but I think you're suggesting that the strong and unowned refcounts would still be packed into the same fields. It's worth noting that your clever high-bit-indicates-slow-path trick would *not* work on the unowned refcount, though that matters less since it doesn't get checked as often.

Right. Unowned refcount would be slower than strong refcount. Strong refcount is by far the most common, so we're willing to tilt pretty much any scale in its favor. Unowned refcount would still be in the object, though, so it's still faster than a weak reference. 

Alternatively we could reduce the implementation distinction between unowned references and weak references. Only the strong refcount would be in the object. (That in turn would help Joe's dream of a pointer-size object header.) That might make sense if (1) unowned references are sufficiently rare that they don't provoke too many side allocations, and (2) side table weak references are sufficiently fast that they can be used for unowned references too. My fear is that #1 is not true enough.

Anyone want to hack up a custom runtime that counts some object statistics, and run some non-trivial non-benchmark app with it? Something like these:
1. count of objects allocated
2. count of objects that were ever referenced unowned, but never referenced weakly
3. count of objects that were ever referenced weakly


>>       // out-of-object refcount     (MSB bits 0b10x)
>>       // or refcount has overflowed (MSB bits 0b111)
>>       // or refcount is constant    (MSB bits 0b110)
> 
> Is this going to work on 32-bit? Even if we assume that valid pointers don't start with 0b1, can we assume that they don't start with 1b01?

The *low* two bits of the side allocation address are clear (assuming that the side allocation is 4-byte aligned). We can store 0b10 in the high two bits and (side allocation >> 2) in the low 30 bits. 

(Bonus: using a shift instead of a mask to recover the pointer is one instruction shorter on armv7, I think.)

(And no, we cannot assume that the MSB of all 32-bit pointers is clear. On 32-bit we can only cheat with the low bits.)


>> The side allocation would store a pointer to the object and a strong refcount and a weak refcount. (This weak refcount would be distinct from the unowned refcount.)  The weak refcount would be incremented once for every weak variable holding this object. 
>> 
>> The advantage of using a side allocation for weak references is that the storage for a weakly-referenced object could be freed synchronously when deinit completes. Only the small side allocation would remain, backing the weak variables until they are cleared on their next access. This is a memory improvement over today's scheme, which keeps the object's entire storage alive for a potentially long time.
>> 
>> The hierarchy:
>> Strong refcount goes to zero: deinit
>> Unowned refcount goes to zero: free the object
>> Weak refcount goes to zero: free the side allocation
> 
> I take it the refcount field's pointer is itself considered a weak reference, so the weak refcount starts +1 like the unowned refcount does?

You need to do something to make sure the side allocation is not freed if the object is live with no weak references to it. Biasing the weak refcount might work. 

It might be more robust to do something else, though. Ideally an incorrect weak reference decrement would deliberately log an underflow error and halt, instead of quietly freeing the side allocation out from under a live object.


-- 
Greg Parker     gparker at apple.com     Runtime Wrangler