[Dlang-study] [rcstring] external reference counting

[Михаил Страшун]

On 02/07/2016 01:47 AM, Andrei Alexandrescu wrote:
> On 02/06/2016 04:51 PM, Михаил Страшун wrote:
>> Why do you completely discard external reference counting approach (i.e.
>> storing refcount in GC/allocator internal data structures bound to
>> allocated memory blocks)? Is there any paper explaining pitfalls of such
>> concept?

> Storing refcounts separately in the allocator is definitely possible but
> my understanding is it just moves the problem elsewhere. The "poison
> cast" that takes immutability away from the reference counter in order
> to manipulate it moves from rcstring's code to the allocator. I see an
> upside to that - we could move the allocator to "the language" and
> guarantee things about it (such as it can cast immutability away). What
> other advantages of the scheme do you see?

If reference count is stored inside allocator metadata, no cast becomes
necessary as relevant memory will never be allocated as immutable
(allocator is in full control on how its own metadata is stored).

Consider two simplified examples, with internal and external refcount:

struct RCInternal
{
    private size_t rc;
    private void[] data;

    ~this () { --this.rc; }
}

struct RCExternal
{
    alias allocator = theGlobalAllocator;

    private void[] data;

    ~this () { allocator.decRef(data.ptr); }
}

In the first case it is impossible for user code to create `immutable
RCInteral instance` because of violation of physical immutability. It
would if struct definition was somehow changed to `private immutable
void[]` and host kept being declared as plain mutable `RCInternal` but
that is not very generic.

In the second case, however, `immutable RCExternal instance` will be
able to satisfy language immutability requirements and thus work more or
less in the same style as immutable GC-collected data. To support that,
allocator could either reserve a mutable refcount block before request
block of immutable memory - or keep a separate refcount table which uses
allocated block pointer as lookup key.

Advantages:
- API remains very similar to existing GC-based data
- can keep physical immutability
- allows interesting designs for multi-threaded sharing with separate
thread-local and thread-global refcounts (i.e. thread-global refcount
gets decremented with a mutex only when thread-local one goes to 0, not
upon every inc/dec)

Disadvantages:
- for thread-local mutable data quite likely to have worse performance
because data locality is worse (need to load to CPU cache two different
memory pages to work with one reference-counted instance)
- puts extra complexity pressure on allocator implementations
- bad encapsulation, matching allocator API must be @system
- incompatbile with idiom of storing reference to allocator as runtime
interface inside data structures, requires some form of global allocator

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: OpenPGP digital signature
URL: <http://lists.puremagic.com/pipermail/dlang-study/attachments/20160207/33f8bbcb/attachment.sig>