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 code unnecessarily.
- 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 implementation:
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 huge change.
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.
Comment #1 by jack — 2018-01-02T15:22:03Z
From my initial investigation into this, adding ref counting to BigInt is much more complicated than it first appears. Adding a size_t ref count on the heap for BigUint basically breaks the rest of BigInt because anytime BigInt is const/immutable it makes the pointer to the reference count const/immutable as well. Meaning, const(BigInt) is no longer implicitly convert-able to BigInt. I'm not sure this is doable without a large rewrite.
Comment #2 by hsteoh — 2018-01-02T17:42:23Z
If the BigInt is const, then the best we can do is to create a new BigInt to hold the result of the operation, i.e., what BigInt does now. For the optimization to have significant benefits, we pretty much require mutable BigInt. So one approach could be that if the BigInt is const/immutable, just do what we do today (allocate a new BigInt to hold the result), otherwise perform write-in-place optimization.
So the following approach *might* work:
- When performing an operation, if the operand is const or immutable, revert to current behaviour (i.e., make a new BigInt to hold the result).
- When assigning to/from a const(BigInt) or immutable(BigInt), always make a copy of the source. There's pretty much no choice when assigning from a const(BigInt), because you can't update the refcount through the const reference. Copying is also required when assigning to const(BigInt) because otherwise you could assign mutable x to const y, then mutate x through the mutable reference, which breaks by-value semantics when viewed through y.
- If assigning mutable BigInts to each other, update the reference count and copy by reference instead.
- When performing an operation on mutable BigInt, if the refcount > 1, revert to current behaviour (allocate a new BigInt to hold the result). If the refcount == 1, then mutate in-place where possible.
Comment #3 by jack — 2018-01-02T17:59:28Z
On the other hand, if the COW is to avoid issues in code like this
```
BigInt a = 10;
BigInt b = a;
++a;
assert(b == 10);
```
where b could end up equaling 11, can we just make opAssign and the this(T : BigInt) copy the data array, and have everything else just use the in-place data?
Comment #4 by robert.schadek — 2024-12-01T16:30:43Z