BigInt -- a challenge for std.allocator

[Joseph Rushton Wakeling]

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