Hello all,

First up -- please understand that this is written by someone whose practical experience of memory allocation is limited to either malloc/free or new/delete, and who is used to programming in scenarios where typically the amount of memory required can be allocated at the start of a program and freed at the end -- so, the rationale or use-cases of most of the content in std.allocator is not obvious to me.  So, in writing this, I'm looking to be educated ... :-)

As part of the work I've been doing towards getting David Simcha's std.rational module into Phobos, I've been looking inside std.bigint.  One aspect of how it works is its memory management: it has an internally-allocated data store (at its core, an array of words of some appropriate size, typically the same as the machine word size) which is stored by reference inside the user-facing object.

By default, when you copy a BigInt, this data is not duplicated -- the reference is copied instead, and BigInt copies only on write.  So:

    BigInt m = 100;
    BigInt n = m;       // just copies the reference
    m = 50;             // creates a new data store and writes to it

However, this has the unfortunate effect that it copies on write _regardless of whether multiple BigInts are pointing to the same data_.  So, you can do something like:

    BigInt n = 100;
    n += 10;
    ++n;

... and both the 2nd and 3rd lines will result in a reallocation even though there is no need for it, because only n is referencing the memory it wraps.

So, a better approach would be for BigInt write to ask,

    if (/* I'm the only person referencing this memory */)
    {
        // just write straight to the memory
    }
    else
    {
        // allocate new memory and write to it
    }

But, how would one go about implementing that using std.allocator?

Or ... am I overthinking this, and std.typecons.RefCounted would be a better approach?

Thanks & best wishes,

    -- Joe

Joseph Rushton Wakeling:

>     if (/* I'm the only person referencing this memory */)

It seems you refer to:

http://en.wikipedia.org/wiki/Uniqueness_typing

Bye,
bearophile

>     BigInt n = 100;
>     n += 10;
>     ++n;
>
> ... and both the 2nd and 3rd lines will result in a reallocation even though there is no need for it, because only n is referencing the memory it wraps.


 Does BigInt not have overloaded operators for adding normal integers? Is it converting 10 to a BigInt prior to adding it to n?

On Tuesday, 29 October 2013 at 11:26:45 UTC, Froglegs wrote:
>
>>    BigInt n = 100;
>>    n += 10;
>>    ++n;
>>
>> ... and both the 2nd and 3rd lines will result in a reallocation even though there is no need for it, because only n is referencing the memory it wraps.
>
>
>  Does BigInt not have overloaded operators for adding normal integers? Is it converting 10 to a BigInt prior to adding it to n?

Yes, it has overloaded operators, but that's not relevant. The issue is that
initially n points to an block of memory, containing [100].

Then, if you use COW, n+= 10 isn't in-place. It has to create a new array, containing [110].
Then ++n creates a third array. [111].

29-Oct-2013 16:22, Don пишет:
> On Tuesday, 29 October 2013 at 11:26:45 UTC, Froglegs wrote:
>>
>>>    BigInt n = 100;
>>>    n += 10;
>>>    ++n;
>>>
>>> ... and both the 2nd and 3rd lines will result in a reallocation even
>>> though there is no need for it, because only n is referencing the
>>> memory it wraps.
>>
>>
>>  Does BigInt not have overloaded operators for adding normal integers?
>> Is it converting 10 to a BigInt prior to adding it to n?
>
> Yes, it has overloaded operators, but that's not relevant. The issue is
> that
> initially n points to an block of memory, containing [100].
>
> Then, if you use COW, n+= 10 isn't in-place. It has to create a new
> array, containing [110].
> Then ++n creates a third array. [111].
>

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.

-- 
Dmitry Olshansky

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?

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?

This has almost nothing to do with an allocator.

On 30/10/13 01:38, inout wrote:
> This has almost nothing to do with an allocator.

My impression was that std.allocator as-is was designed to create a toolkit for developers to build different memory management strategies into their applications.  Is there any reason why that should exclude implementing ref-counting approaches?

As I said at the start, I'm looking to be educated, so I'd appreciate you explaining why something is wrong rather than just telling me.

On Wednesday, 30 October 2013 at 12:39:18 UTC, Joseph Rushton Wakeling wrote:
> On 30/10/13 01:38, inout wrote:
>> This has almost nothing to do with an allocator.
>
> My impression was that std.allocator as-is was designed to create a toolkit for developers to build different memory management strategies into their applications.  Is there any reason why that should exclude implementing ref-counting approaches?

"memory allocation strategy" != "memory management strategy", though those can be possibly coupled. Ref-counting can be done on top of any allocation strategy that support deterministic deallocattion.

On 10/30/13 5:39 AM, Joseph Rushton Wakeling wrote:
> On 30/10/13 01:38, inout wrote:
>> This has almost nothing to do with an allocator.
>
> My impression was that std.allocator as-is was designed to create a
> toolkit for developers to build different memory management strategies
> into their applications.  Is there any reason why that should exclude
> implementing ref-counting approaches?
>
> As I said at the start, I'm looking to be educated, so I'd appreciate
> you explaining why something is wrong rather than just telling me.

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.

Andrei