On Friday, 12 February 2016 at 19:12:48 UTC, Andrei Alexandrescu wrote:
> https://github.com/D-Programming-Language/phobos/pull/3991
>
> A short while ago Dicebot discussed the notion of using the allocator to store the reference count of objects (and generally metadata). The allocator seems to be a good place because in a way it's a source of "ground truth" - no matter how data is qualified, it originated as untyped mutable bytes from the allocator.
> [...]
>
> Destroy!
>
> Andrei

So you can use metadata only with global allocators,
until you don't need to save ref to the allocator.

Why can't we use attribute @intransitive on ref fields to prevents
immutable being transitively applied on referred content?
Add some restrictions (only private, wrap using with trusted) and
it would be enough to implement RefCounting with immutable.

On 02/13/2016 01:50 PM, Mathias Lang via Digitalmars-d wrote:
> 2016-02-12 20:12 GMT+01:00 Andrei Alexandrescu via Digitalmars-d
> <digitalmars-d@puremagic.com <mailto:digitalmars-d@puremagic.com>>:
>
>     https://github.com/D-Programming-Language/phobos/pull/3991
>
>     The only difference between an approach based on an associative
>     array and AffixAllocator is that the latter is faster (the
>     association is fixed by layout).
>
>
> Could you point to your benchmark / paper about this ?

There's no need. I'll do the implementation with the prefix, and if you do it with a global hashtable within the same or better speed, my hat is off to you.

> The general idea sounds good, however I share deadalnix's concern over
> storing the metadata next to the user's data. I also fail to see how
> those are a "soup of generic considerations", given it only apply when
> using an affix.

It's really easy to throw hypotheticals out and speculate what's going to cause slowdown and what's not (and look awfully expert in the process). I'm very familiar with the concerns guarding storing metadata in jemalloc seeing I've worked in team with Jason Evans for months; most are quoted from rote and don't apply here.

But the entire matter of digging down into how efficient the layout is would be a massive missing of the point. AffixAllocator is one example, there are many other tactical possibilities for allocators to stash metadata, neither of which affects the point.

The point here was safely getting to modifiable metadata for modifiable data. Timon Gehr was the one person who figured the real problem (inadvertent sharing of data not meant to be shared). I think I'll remove the const overload for now. Would that leave any hole unplugged?


Andrei

On 02/13/2016 03:07 PM, Iakh wrote:
> So you can use metadata only with global allocators,
> until you don't need to save ref to the allocator.

Well you can use other allocators if you save them so you have them available for deallocation. -- Andrei

On Friday, 12 February 2016 at 19:12:48 UTC, Andrei Alexandrescu wrote:
> https://github.com/D-Programming-Language/phobos/pull/3991
>
> A short while ago Dicebot discussed the notion of using the allocator to store the reference count of objects (and generally metadata). The allocator seems to be a good place because in a way it's a source of "ground truth" - no matter how data is qualified, it originated as untyped mutable bytes from the allocator.

I agree. Your allocators framework is very flexible and AffixAllocator looks like the perfect tool for the job. The type system already relies on the allocators and putting more trust in them can indeed enable some interesting opportunities.

> So after thinking a bit I managed to convince myself that the affixes in an AffixAllocator can be accessed with removing immutable, but without actually breaking any guarantee made by the type system. (Affixes are extra bytes allocated before and after the actual allocation.) The logic goes as follows:
>
> * If the buffer is mutable, then the allocator assumes it hasn't been shared across threads, so it returns a reference to a mutable affix.

I agree that non-shared data implies that it's meta data can't be shared, but I don't exactly agree with you reasoning - see below.

> * If the buffer is const, then the allocator must conservatively assume it might have been immutable and subsequently shared among threads. Therefore, several threads may request the affix of the same buffer simultaneously. So it returns a reference to a shared affix.

Absolutely disagree. See below.

> * If the buffer is shared, then the allocator assumes again several threads may access the affix so it returns a reference to a shared affix.

Correct. Shared data implies shared access to the corresponding metadata.

> One simple way to look at this is: the allocator keeps an associative array mapping allocated buffers to metadata (e.g. reference counts). The allocated buffers may be immutable, which doesn't require the metadata to be immutable as well. The only difference between an approach based on an associative array and AffixAllocator is that the latter is faster (the association is fixed by layout).
>

Yes, mutable metadata in front of immutable data is OK, as long as the users of the immutable data can't directly access the metadata (e.g. it is well encapsulated and those who do access it, must see is typed as `shared`).

> Destroy!
>
> Andrei

Overall it's an interesting and strong propsal, except for the part about prefix(const) magically returning shared.
Shared is transitive and unless you take special care to remove it - e.g.
http://dpaste.dzfl.pl/4294b9c2653e, you shouldn't be able to get non-shared references in to it (and vice-versa - you should have shared references in a non-shared objects).
That's why I believe that unless the allocator is explicitly shared, you shouldn't be allowed to share the bytes allocated from it.

So in order to get shareable immutable data, we should use shared Allocator and not try to subvert the type system, even though allocators are low-level infrastructure code.

On Saturday, 13 February 2016 at 21:38:30 UTC, ZombineDev wrote:
> ...
> get non-shared references in to it (and vice-versa - you should have shared references in a non-shared objects).
> ...
you should ***not be able to*** have shared references in a non-shared objects

On Saturday, 13 February 2016 at 02:35:43 UTC, Andrei Alexandrescu wrote:
> On 02/12/2016 09:21 PM, Timon Gehr wrote:
>> Const could also mean mutable. This can hence reference the same data as
>> both shared and unshared, which violates the type system.
>
> If const comes from mutable, then shared is superfluous leading to extra synchronization. That's suboptimal, but how does it violate the type system? -- Andrei

It violates the expectations that if an object is not shared, it could not possibly be modified from another thread.

On Saturday, 13 February 2016 at 21:49:48 UTC, ZombineDev wrote:
> On Saturday, 13 February 2016 at 02:35:43 UTC, Andrei Alexandrescu wrote:
>> On 02/12/2016 09:21 PM, Timon Gehr wrote:
>>> Const could also mean mutable. This can hence reference the same data as
>>> both shared and unshared, which violates the type system.
>>
>> If const comes from mutable, then shared is superfluous leading to extra synchronization. That's suboptimal, but how does it violate the type system? -- Andrei
>
> It violates the expectations that if an object is not shared, it could not possibly be modified from another thread.

All threads must agree on a protocol in order for synchronization to work correctly.
Say thread A has a non-shared ref to an object and thread B has a shared ref to it. What good is this shared qualifier for B when A doesn't honor it?

On Saturday, 13 February 2016 at 13:10:19 UTC, Andrei Alexandrescu wrote:
> On 2/13/16 7:40 AM, John Colvin wrote:
>> On Saturday, 13 February 2016 at 00:30:58 UTC, Andrei Alexandrescu wrote:
>>> On 02/12/2016 06:52 PM, deadalnix wrote:
>>>> [...]
>>>
>>> I think we're good there. -- Andrei
>>
>> Is there somewhere where I / others can see an explanation of how "we're
>> good"? Those sound like genuine problems.
>
> Those are just a soup of generic considerations that could be brought about any code. -- andrei

Indeed, I just explained why some major moved away from it, it is not like it is relevant. I mean, it is not like this is proposed as a way to handle memory management in the language down the road.

On Saturday, 13 February 2016 at 21:10:50 UTC, Andrei Alexandrescu wrote:
> There's no need. I'll do the implementation with the prefix, and if you do it with a global hashtable within the same or better speed, my hat is off to you.
>

That is false dichotomy. What about storing the metadata at an address that is computable from from the object's address, while not being contiguous with the object allocated ? Is substracting a constant really the only option here ? (hint, it is not)

On Saturday, 13 February 2016 at 21:10:50 UTC, Andrei Alexandrescu wrote:
> On 02/13/2016 01:50 PM, Mathias Lang via Digitalmars-d wrote:
>> 2016-02-12 20:12 GMT+01:00 Andrei Alexandrescu via Digitalmars-d
>> <digitalmars-d@puremagic.com <mailto:digitalmars-d@puremagic.com>>:
>>
>>     https://github.com/D-Programming-Language/phobos/pull/3991
>>
>>     The only difference between an approach based on an associative
>>     array and AffixAllocator is that the latter is faster (the
>>     association is fixed by layout).
>>
>>
>> Could you point to your benchmark / paper about this ?
>
> There's no need. I'll do the implementation with the prefix, and if you do it with a global hashtable within the same or better speed, my hat is off to you.

I believe he was referring to BiBoP.