• Joseph Rushton Wakeling (39/39) Oct 29 2013 Hello all,
• bearophile (5/6) Oct 29 2013 It seems you refer to:
• Froglegs (2/8) Oct 29 2013 Does BigInt not have overloaded operators for adding normal
• Don (7/17) Oct 29 2013 Yes, it has overloaded operators, but that's not relevant. The
• Dmitry Olshansky (7/26) Oct 29 2013 Can't it use ref-counted COW? Then since there is only 1 reference to
• Joseph Rushton Wakeling (4/8) Oct 29 2013 Yes, that's pretty much what I was thinking of. The question is how to
• inout (3/14) Oct 29 2013 This has almost nothing to do with an allocator.
• Joseph Rushton Wakeling (7/8) Oct 30 2013 My impression was that std.allocator as-is was designed to create a tool...
• Dicebot (6/13) Oct 30 2013 "memory allocation strategy" != "memory management strategy",
• Andrei Alexandrescu (5/13) Oct 30 2013 Reference counting comes somewhere on top of allocators. (For a long
• Joseph Rushton Wakeling (6/9) Oct 30 2013 Ahh, OK. That makes more sense. It rather baffled me to hear people sa...
• Dmitry Olshansky (5/15) Oct 30 2013 Like others said - just use allocator.alloc/allocator.free instead of
• Andrei Alexandrescu (8/24) Oct 30 2013 Well actually there are things that can be done at the allocator level
• Dmitry Olshansky (12/19) Oct 30 2013 That would entail some work to tie-up refcounts and bigint internal
• Kagamin (7/18) Oct 30 2013 Implement a pool of bigints as an allocator: when refcount

Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:

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

"bearophile" <bearophileHUGS lycos.com> writes:

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

"Froglegs" <barf barf.com> writes:

     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?

"Don" <x nospam.com> writes:

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].

Dmitry Olshansky <dmitry.olsh gmail.com> writes:

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

Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:

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?