30-Oct-2013 01:59, Joseph Rushton Wakeling пишет:
> On 29/10/13 15:58, Dmitry Olshansky wrote:
>> Can't it use ref-counted COW? Then since there is only 1 reference to the
>> original block it may mutate it in-place else it creates new chunk
>> with refs=1
>> and decrements the original count. Maybe I'm missing something but it
>> shouldn't
>> be that hard.
>
> Yes, that's pretty much what I was thinking of.  The question is how to
> implement it in terms of std.allocator -- or is that the wrong base to
> build ref=counted memory upon?
>

Like others said - just use allocator.alloc/allocator.free instead of malloc/free nothing stellar.

-- 
Dmitry Olshansky

On Tuesday, 29 October 2013 at 21:59:38 UTC, Joseph Rushton Wakeling wrote:
> On 29/10/13 15:58, Dmitry Olshansky wrote:
>> Can't it use ref-counted COW? Then since there is only 1 reference to the
>> original block it may mutate it in-place else it creates new chunk with refs=1
>> and decrements the original count. Maybe I'm missing something but it shouldn't
>> be that hard.
>
> Yes, that's pretty much what I was thinking of.  The question is how to implement it in terms of std.allocator -- or is that the wrong base to build ref=counted memory upon?

Implement a pool of bigints as an allocator: when refcount reaches zero, return the bigint buffer to the pool - a simple bump the pointer algorithm, when you need a new buffer, request it from the pool. A pool is a stack with fixed capacity, and buffers go in and out.

On 30/10/13 16:21, Andrei Alexandrescu wrote:
> Reference counting comes somewhere on top of allocators. (For a long time I
> thought they should be fused; now I think they can be neatly separated.)
> Allocators know how to manage void[] and that's about it.

Ahh, OK.  That makes more sense.  It rather baffled me to hear people saying, "This has nothing to do with an allocator."

My impression is that std.typecons.RefCounted has some issues, and that we might expect better reference counting solutions to be built on top of std.allocator -- otherwise I'd just have used the existing RefCounted.

On 10/30/13 9:35 AM, Dmitry Olshansky wrote:
> 30-Oct-2013 01:59, Joseph Rushton Wakeling пишет:
>> On 29/10/13 15:58, Dmitry Olshansky wrote:
>>> Can't it use ref-counted COW? Then since there is only 1 reference to
>>> the
>>> original block it may mutate it in-place else it creates new chunk
>>> with refs=1
>>> and decrements the original count. Maybe I'm missing something but it
>>> shouldn't
>>> be that hard.
>>
>> Yes, that's pretty much what I was thinking of.  The question is how to
>> implement it in terms of std.allocator -- or is that the wrong base to
>> build ref=counted memory upon?
>>
>
> Like others said - just use allocator.alloc/allocator.free instead of
> malloc/free nothing stellar.

Well actually there are things that can be done at the allocator level to explicitly help reference counting:

1. The refcount could be an affix to the allocated block.

2. Small refcounts can be kept together in a compact block a la HeapBlock.

3. Or refcounts can be kept in a freelist.

So refounting can be helped by an allocator built especially for it.


Andrei

30-Oct-2013 22:02, Andrei Alexandrescu пишет:
> Well actually there are things that can be done at the allocator level
> to explicitly help reference counting:
> 1. The refcount could be an affix to the allocated block.

Yup. I seriously underappreciated this one.

>
> 2. Small refcounts can be kept together in a compact block a la HeapBlock.

That would entail some work to tie-up refcounts and bigint internal array, but it sounds interesting.

> 3. Or refcounts can be kept in a freelist.

Doubtful. That would amount to extra pointer stored per BigInt AND extra indirection to get at ref-count unless I'm missing the details completely.

> So refounting can be helped by an allocator built especially for it.
>

Agreed.
BTW AffixAllocator is quite a feat, I think I wanted it countless times while working on std.regex/std.uni. I expect massive code performance and clarity improvements when {core,std}.allocator comes in.

>
> Andrei
>


-- 
Dmitry Olshansky