Jump to page: 1 2
Thread overview
BigInt -- a challenge for std.allocator
Oct 29, 2013
bearophile
Oct 29, 2013
Froglegs
Oct 29, 2013
Don
Oct 29, 2013
Dmitry Olshansky
Oct 30, 2013
inout
Oct 30, 2013
Dicebot
Oct 30, 2013
Dmitry Olshansky
Oct 30, 2013
Dmitry Olshansky
Oct 30, 2013
Kagamin
October 29, 2013
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
October 29, 2013
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
October 29, 2013
>     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?
October 29, 2013
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].

October 29, 2013
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
October 29, 2013
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?

October 30, 2013
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.
October 30, 2013
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.
October 30, 2013
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.
October 30, 2013
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

« First   ‹ Prev
1 2