Optimise Bignum layout. (#107)
* Use memset to clear bignum.
* Improve data locality.
* Reduce size of bignum.
diff --git a/double-conversion/bignum.cc b/double-conversion/bignum.cc
index 7e504fe..f089715 100644
--- a/double-conversion/bignum.cc
+++ b/double-conversion/bignum.cc
@@ -26,6 +26,7 @@
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include <algorithm>
+#include <cstring>
#include "bignum.h"
#include "utils.h"
@@ -33,10 +34,20 @@
namespace double_conversion {
Bignum::Bignum()
- : bigits_buffer_(), bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
- for (int i = 0; i < kBigitCapacity; ++i) {
- bigits_[i] = 0;
- }
+ : used_digits_(0), exponent_(0) {
+ std::memset(bigits_buffer_, 0, sizeof(Chunk) * kBigitCapacity);
+}
+
+
+Bignum::Chunk& Bignum::RawBigit(int index) {
+ DOUBLE_CONVERSION_ASSERT(static_cast<unsigned>(index) < kBigitCapacity);
+ return bigits_buffer_[index];
+}
+
+
+const Bignum::Chunk& Bignum::RawBigit(int index) const {
+ DOUBLE_CONVERSION_ASSERT(static_cast<unsigned>(index) < kBigitCapacity);
+ return bigits_buffer_[index];
}
@@ -50,10 +61,11 @@
void Bignum::AssignUInt16(uint16_t value) {
DOUBLE_CONVERSION_ASSERT(kBigitSize >= BitSize(value));
Zero();
- if (value == 0) return;
-
+ if (value == 0) {
+ return;
+ }
EnsureCapacity(1);
- bigits_[0] = value;
+ RawBigit(0) = value;
used_digits_ = 1;
}
@@ -62,12 +74,13 @@
const int kUInt64Size = 64;
Zero();
- if (value == 0) return;
-
+ if (value == 0) {
+ return;
+ }
int needed_bigits = kUInt64Size / kBigitSize + 1;
EnsureCapacity(needed_bigits);
for (int i = 0; i < needed_bigits; ++i) {
- bigits_[i] = value & kBigitMask;
+ RawBigit(i) = value & kBigitMask;
value = value >> kBigitSize;
}
used_digits_ = needed_bigits;
@@ -78,11 +91,11 @@
void Bignum::AssignBignum(const Bignum& other) {
exponent_ = other.exponent_;
for (int i = 0; i < other.used_digits_; ++i) {
- bigits_[i] = other.bigits_[i];
+ RawBigit(i) = other.RawBigit(i);
}
// Clear the excess digits (if there were any).
for (int i = other.used_digits_; i < used_digits_; ++i) {
- bigits_[i] = 0;
+ RawBigit(i) = 0;
}
used_digits_ = other.used_digits_;
}
@@ -143,7 +156,7 @@
for (int j = 0; j < kBigitSize / 4; j++) {
current_bigit += HexCharValue(value[string_index--]) << (j * 4);
}
- bigits_[i] = current_bigit;
+ RawBigit(i) = current_bigit;
}
used_digits_ = needed_bigits - 1;
@@ -153,7 +166,7 @@
most_significant_bigit += HexCharValue(value[j]);
}
if (most_significant_bigit != 0) {
- bigits_[used_digits_] = most_significant_bigit;
+ RawBigit(used_digits_) = most_significant_bigit;
used_digits_++;
}
Clamp();
@@ -193,15 +206,15 @@
int bigit_pos = other.exponent_ - exponent_;
DOUBLE_CONVERSION_ASSERT(bigit_pos >= 0);
for (int i = 0; i < other.used_digits_; ++i) {
- Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
- bigits_[bigit_pos] = sum & kBigitMask;
+ Chunk sum = RawBigit(bigit_pos) + other.RawBigit(i) + carry;
+ RawBigit(bigit_pos) = sum & kBigitMask;
carry = sum >> kBigitSize;
bigit_pos++;
}
while (carry != 0) {
- Chunk sum = bigits_[bigit_pos] + carry;
- bigits_[bigit_pos] = sum & kBigitMask;
+ Chunk sum = RawBigit(bigit_pos) + carry;
+ RawBigit(bigit_pos) = sum & kBigitMask;
carry = sum >> kBigitSize;
bigit_pos++;
}
@@ -223,13 +236,13 @@
int i;
for (i = 0; i < other.used_digits_; ++i) {
DOUBLE_CONVERSION_ASSERT((borrow == 0) || (borrow == 1));
- Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
- bigits_[i + offset] = difference & kBigitMask;
+ Chunk difference = RawBigit(i + offset) - other.RawBigit(i) - borrow;
+ RawBigit(i + offset) = difference & kBigitMask;
borrow = difference >> (kChunkSize - 1);
}
while (borrow != 0) {
- Chunk difference = bigits_[i + offset] - borrow;
- bigits_[i + offset] = difference & kBigitMask;
+ Chunk difference = RawBigit(i + offset) - borrow;
+ RawBigit(i + offset) = difference & kBigitMask;
borrow = difference >> (kChunkSize - 1);
++i;
}
@@ -259,13 +272,13 @@
DOUBLE_CONVERSION_ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1);
DoubleChunk carry = 0;
for (int i = 0; i < used_digits_; ++i) {
- DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
- bigits_[i] = static_cast<Chunk>(product & kBigitMask);
+ DoubleChunk product = static_cast<DoubleChunk>(factor) * RawBigit(i) + carry;
+ RawBigit(i) = static_cast<Chunk>(product & kBigitMask);
carry = (product >> kBigitSize);
}
while (carry != 0) {
EnsureCapacity(used_digits_ + 1);
- bigits_[used_digits_] = carry & kBigitMask;
+ RawBigit(used_digits_) = carry & kBigitMask;
used_digits_++;
carry >>= kBigitSize;
}
@@ -283,16 +296,16 @@
uint64_t low = factor & 0xFFFFFFFF;
uint64_t high = factor >> 32;
for (int i = 0; i < used_digits_; ++i) {
- uint64_t product_low = low * bigits_[i];
- uint64_t product_high = high * bigits_[i];
+ uint64_t product_low = low * RawBigit(i);
+ uint64_t product_high = high * RawBigit(i);
uint64_t tmp = (carry & kBigitMask) + product_low;
- bigits_[i] = tmp & kBigitMask;
+ RawBigit(i) = tmp & kBigitMask;
carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
(product_high << (32 - kBigitSize));
}
while (carry != 0) {
EnsureCapacity(used_digits_ + 1);
- bigits_[used_digits_] = carry & kBigitMask;
+ RawBigit(used_digits_) = carry & kBigitMask;
used_digits_++;
carry >>= kBigitSize;
}
@@ -363,7 +376,7 @@
// First shift the digits so we don't overwrite them.
int copy_offset = used_digits_;
for (int i = 0; i < used_digits_; ++i) {
- bigits_[copy_offset + i] = bigits_[i];
+ RawBigit(copy_offset + i) = RawBigit(i);
}
// We have two loops to avoid some 'if's in the loop.
for (int i = 0; i < used_digits_; ++i) {
@@ -373,13 +386,13 @@
int bigit_index2 = 0;
// Sum all of the sub-products.
while (bigit_index1 >= 0) {
- Chunk chunk1 = bigits_[copy_offset + bigit_index1];
- Chunk chunk2 = bigits_[copy_offset + bigit_index2];
+ Chunk chunk1 = RawBigit(copy_offset + bigit_index1);
+ Chunk chunk2 = RawBigit(copy_offset + bigit_index2);
accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
bigit_index1--;
bigit_index2++;
}
- bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
+ RawBigit(i) = static_cast<Chunk>(accumulator) & kBigitMask;
accumulator >>= kBigitSize;
}
for (int i = used_digits_; i < product_length; ++i) {
@@ -388,16 +401,16 @@
// Invariant: sum of both indices is again equal to i.
// Inner loop runs 0 times on last iteration, emptying accumulator.
while (bigit_index2 < used_digits_) {
- Chunk chunk1 = bigits_[copy_offset + bigit_index1];
- Chunk chunk2 = bigits_[copy_offset + bigit_index2];
+ Chunk chunk1 = RawBigit(copy_offset + bigit_index1);
+ Chunk chunk2 = RawBigit(copy_offset + bigit_index2);
accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
bigit_index1--;
bigit_index2++;
}
- // The overwritten bigits_[i] will never be read in further loop iterations,
+ // The overwritten RawBigit(i) will never be read in further loop iterations,
// because bigit_index1 and bigit_index2 are always greater
// than i - used_digits_.
- bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
+ RawBigit(i) = static_cast<Chunk>(accumulator) & kBigitMask;
accumulator >>= kBigitSize;
}
// Since the result was guaranteed to lie inside the number the
@@ -507,26 +520,26 @@
// This naive approach is extremely inefficient if `this` divided by other
// is big. This function is implemented for doubleToString where
// the result should be small (less than 10).
- DOUBLE_CONVERSION_ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
- DOUBLE_CONVERSION_ASSERT(bigits_[used_digits_ - 1] < 0x10000);
+ DOUBLE_CONVERSION_ASSERT(other.RawBigit(other.used_digits_ - 1) >= ((1 << kBigitSize) / 16));
+ DOUBLE_CONVERSION_ASSERT(RawBigit(used_digits_ - 1) < 0x10000);
// Remove the multiples of the first digit.
// Example this = 23 and other equals 9. -> Remove 2 multiples.
- result += static_cast<uint16_t>(bigits_[used_digits_ - 1]);
- SubtractTimes(other, bigits_[used_digits_ - 1]);
+ result += static_cast<uint16_t>(RawBigit(used_digits_ - 1));
+ SubtractTimes(other, RawBigit(used_digits_ - 1));
}
DOUBLE_CONVERSION_ASSERT(BigitLength() == other.BigitLength());
// Both bignums are at the same length now.
// Since other has more than 0 digits we know that the access to
- // bigits_[used_digits_ - 1] is safe.
- Chunk this_bigit = bigits_[used_digits_ - 1];
- Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
+ // RawBigit(used_digits_ - 1) is safe.
+ Chunk this_bigit = RawBigit(used_digits_ - 1);
+ Chunk other_bigit = other.RawBigit(other.used_digits_ - 1);
if (other.used_digits_ == 1) {
// Shortcut for easy (and common) case.
int quotient = this_bigit / other_bigit;
- bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
+ RawBigit(used_digits_ - 1) = this_bigit - other_bigit * quotient;
DOUBLE_CONVERSION_ASSERT(quotient < 0x10000);
result += static_cast<uint16_t>(quotient);
Clamp();
@@ -585,7 +598,7 @@
}
// We add 1 for the terminating '\0' character.
int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
- SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
+ SizeInHexChars(RawBigit(used_digits_ - 1)) + 1;
if (needed_chars > buffer_size) return false;
int string_index = needed_chars - 1;
buffer[string_index--] = '\0';
@@ -595,14 +608,14 @@
}
}
for (int i = 0; i < used_digits_ - 1; ++i) {
- Chunk current_bigit = bigits_[i];
+ Chunk current_bigit = RawBigit(i);
for (int j = 0; j < kHexCharsPerBigit; ++j) {
buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
current_bigit >>= 4;
}
}
// And finally the last bigit.
- Chunk most_significant_bigit = bigits_[used_digits_ - 1];
+ Chunk most_significant_bigit = RawBigit(used_digits_ - 1);
while (most_significant_bigit != 0) {
buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
most_significant_bigit >>= 4;
@@ -611,10 +624,10 @@
}
-Bignum::Chunk Bignum::BigitAt(int index) const {
+Bignum::Chunk Bignum::BigitOrZero(int index) const {
if (index >= BigitLength()) return 0;
if (index < exponent_) return 0;
- return bigits_[index - exponent_];
+ return RawBigit(index - exponent_);
}
@@ -626,8 +639,8 @@
if (bigit_length_a < bigit_length_b) return -1;
if (bigit_length_a > bigit_length_b) return +1;
for (int i = bigit_length_a - 1; i >= (std::min)(a.exponent_, b.exponent_); --i) {
- Chunk bigit_a = a.BigitAt(i);
- Chunk bigit_b = b.BigitAt(i);
+ Chunk bigit_a = a.BigitOrZero(i);
+ Chunk bigit_b = b.BigitOrZero(i);
if (bigit_a < bigit_b) return -1;
if (bigit_a > bigit_b) return +1;
// Otherwise they are equal up to this digit. Try the next digit.
@@ -656,9 +669,9 @@
// Starting at min_exponent all digits are == 0. So no need to compare them.
int min_exponent = (std::min)((std::min)(a.exponent_, b.exponent_), c.exponent_);
for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
- Chunk chunk_a = a.BigitAt(i);
- Chunk chunk_b = b.BigitAt(i);
- Chunk chunk_c = c.BigitAt(i);
+ Chunk chunk_a = a.BigitOrZero(i);
+ Chunk chunk_b = b.BigitOrZero(i);
+ Chunk chunk_c = c.BigitOrZero(i);
Chunk sum = chunk_a + chunk_b;
if (sum > chunk_c + borrow) {
return +1;
@@ -674,7 +687,7 @@
void Bignum::Clamp() {
- while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
+ while (used_digits_ > 0 && RawBigit(used_digits_ - 1) == 0) {
used_digits_--;
}
if (used_digits_ == 0) {
@@ -685,14 +698,12 @@
bool Bignum::IsClamped() const {
- return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
+ return used_digits_ == 0 || RawBigit(used_digits_ - 1) != 0;
}
void Bignum::Zero() {
- for (int i = 0; i < used_digits_; ++i) {
- bigits_[i] = 0;
- }
+ std::memset(bigits_buffer_, 0, sizeof(Chunk) * used_digits_);
used_digits_ = 0;
exponent_ = 0;
}
@@ -709,10 +720,10 @@
int zero_digits = exponent_ - other.exponent_;
EnsureCapacity(used_digits_ + zero_digits);
for (int i = used_digits_ - 1; i >= 0; --i) {
- bigits_[i + zero_digits] = bigits_[i];
+ RawBigit(i + zero_digits) = RawBigit(i);
}
for (int i = 0; i < zero_digits; ++i) {
- bigits_[i] = 0;
+ RawBigit(i) = 0;
}
used_digits_ += zero_digits;
exponent_ -= zero_digits;
@@ -727,12 +738,12 @@
DOUBLE_CONVERSION_ASSERT(shift_amount >= 0);
Chunk carry = 0;
for (int i = 0; i < used_digits_; ++i) {
- Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
- bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
+ Chunk new_carry = RawBigit(i) >> (kBigitSize - shift_amount);
+ RawBigit(i) = ((RawBigit(i) << shift_amount) + carry) & kBigitMask;
carry = new_carry;
}
if (carry != 0) {
- bigits_[used_digits_] = carry;
+ RawBigit(used_digits_) = carry;
used_digits_++;
}
}
@@ -749,17 +760,17 @@
Chunk borrow = 0;
int exponent_diff = other.exponent_ - exponent_;
for (int i = 0; i < other.used_digits_; ++i) {
- DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
+ DoubleChunk product = static_cast<DoubleChunk>(factor) * other.RawBigit(i);
DoubleChunk remove = borrow + product;
- Chunk difference = bigits_[i + exponent_diff] - (remove & kBigitMask);
- bigits_[i + exponent_diff] = difference & kBigitMask;
+ Chunk difference = RawBigit(i + exponent_diff) - (remove & kBigitMask);
+ RawBigit(i + exponent_diff) = difference & kBigitMask;
borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
(remove >> kBigitSize));
}
for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
if (borrow == 0) return;
- Chunk difference = bigits_[i] - borrow;
- bigits_[i] = difference & kBigitMask;
+ Chunk difference = RawBigit(i) - borrow;
+ RawBigit(i) = difference & kBigitMask;
borrow = difference >> (kChunkSize - 1);
}
Clamp();
diff --git a/double-conversion/bignum.h b/double-conversion/bignum.h
index ec2991a..d42532f 100644
--- a/double-conversion/bignum.h
+++ b/double-conversion/bignum.h
@@ -125,16 +125,15 @@
void BigitsShiftLeft(int shift_amount);
// BigitLength includes the "hidden" digits encoded in the exponent.
int BigitLength() const { return used_digits_ + exponent_; }
- Chunk BigitAt(int index) const;
+ Chunk& RawBigit(int index);
+ const Chunk& RawBigit(int index) const;
+ Chunk BigitOrZero(int index) const;
void SubtractTimes(const Bignum& other, int factor);
- Chunk bigits_buffer_[kBigitCapacity];
- // A vector backed by bigits_buffer_. This way accesses to the array are
- // checked for out-of-bounds errors.
- Vector<Chunk> bigits_;
int used_digits_;
// The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
int exponent_;
+ Chunk bigits_buffer_[kBigitCapacity];
DOUBLE_CONVERSION_DISALLOW_COPY_AND_ASSIGN(Bignum);
};
