Issue ID: 17746
Summary: Improve BigInt memory usage
Currently, operations on BigInt always allocates a new BigInt instance to hold
the result, even if it is valid and possible to reuse the space of (one of) its
operand(s). For example, `BigInt x=...; x++;` will always allocate a new
BigInt in the course of evaluating `x++`, even though it could have more
efficiently updated x in-place.
As far as I can tell, the reason BigInt operations are implemented this way is
because it was intended to be a drop-in replacement for fixed-width ints, and
so it must replicate equivalent semantics, in particular by-value semantics.
Since BigInt.opAssign only copies by reference (probably for efficiency
reasons, since otherwise passing BigInt between functions could entail
expensive copying), the only way to ensure by-value semantics is to never
modify an existing BigInt instance, but always allocate a new instance for
holding the result of operations.
The current implementation has the following drawbacks:
- Excessive allocations: every operation on a BigInt involves an allocation,
including trivial operations like ++, that only rarely actually requires
allocating a new BigInt (i.e., only once every 2^n calls to opUnary!"++", where
n is the current size of the BigInt). This increases GC pressure in BigInt
- Suboptimal performance when the result of an operation fits within one of its
operations and said operand is not aliased. `x++`, for example, entails
allocating a new BigInt and copying the contents of x over, whereas updating
in-place would, most of the time, require updating only 1 word of BigInt data
or just a few words.
This enhancement request proposes the following change to BigInt's
1) Add a reference counting scheme to BigInt. Since BigInt is already a wrapper
around what's essentially a reference to the actual data, this would not be a
2) Implement in-place versions of the current BigInt operations, where
possible. (Certain operations like * may not make sense as an in-place
algorithm, since allocation of temporary working space will be needed anyway.)
3) In BigInt's overloaded operators, whenever the current reference count is 1,
and an in-place algorithm is available, use the in-place algorithm to update
the BigInt in-place rather than allocate a new BigInt to hold the result.
In addition to better memory usage and better efficiency for trivial operations
like ++, the proposed change also opens up the possibility of making BigInt
usable in a @nogc context.