nvanbenschoten
commented
2 years ago I think we can simplify this even further by creating a wrapper around big.Int and pushing the inline value optimization into that wrapper. Something along the lines of:
const inlineWords = 1 // or maybe 2
type BigInt struct {
inner big.Int
inline [inlineWords]big.Word
}
func (b *BigInt) lazyInit() {
if b.inner.Bits() == nil {
b.inline = [inlineWords]big.Word{}
b.inner.SetBits(b.inline[:0])
}
}
func (b *BigInt) Add(x, y *BigInt) *BigInt {
b.lazyInit()
b.inner.Add(&x.inner, &y.inner)
return b
}
...
type Decimal struct {
Form Form
Negative bool
Exponent int32
Coeff BigInt
}We could then re-implement the big.Int API on this wrapper and add calls to (*BigInt).lazyInit where appropriate. That would probably be more lines of code, but it would mostly be boilerplate and would keep the optimization confined to a small layer below Decimal and above big.Int.
This BigInt wrapper may then be useful in other contexts. For instance, it would provide the inline optimization to intermediate results in this library, which are currently allocation heavy (see benchmark results above). It may also be useful in CRDB code.
Replaces https://github.com/cockroachdb/cockroach/pull/74369.
This commit introduces a performance optimization that embeds small coefficient values directly in their
Decimalstruct, instead of storing these values in a separate heap allocation.Each
Decimalmaintains (throughbig.Int) an internal reference to a variable-length coefficient, which is represented by a[]big.Word. ThecoeffInlinefield and thelazyInitmethod combine to allow us to inline this coefficient within theDecimalstruct when its value is sufficiently small. InlazyInit, we point theCoefffield's backing slice at thecoeffInlinearray.big.Intwill avoid re-allocating this array until it is provided with a value that exceeds the initial capacity. We set this initial capacity to accommodate any coefficient that would fit in a 64-bit integer (i.e. values up to 2^64).This is an alternative to an optimization that many other arbitrary precision decimal libraries have where small coefficient values are stored as numeric fields in their data type's struct. Only when this coefficient value gets large enough do these libraries fall back to a variable-length coefficient with internal indirection. We can see the optimization in practice in the
ericlagergren/decimallibrary, where each struct contains acompact uint64and anunscaled big.Int. Prior concern from the authors ofcockroachdb/apdregarding this form of compact representation optimization was that it traded performance for complexity. The optimization fractured control flow, leaking out across the library and leading to more complex, error-prone code.The approach taken in this commit does not have the same issue. All arithmetic on the decimal's coefficient is still deferred to
bit.Int. In fact, the entire optimization is best-effort, and bugs that lead to missed calls tolazyInitare merely missed opportunities to avoid a heap allocation, and nothing more serious. The internal reference within Decimal is vulnerable to memory aliasing bugs when aDecimalis copied by value (and not through theDecimal.Setmethod), but this is not a new concern.Impact on benchmarks:
cc. @mjibson