Subzero: Improve the behavior of resizing vectors.
In some cases, Subzero needs to insert into a std::vector at a particular index, resizing the vector as necessary. It appears that our vector implementation sets the capacity to exactly the size when growing the vector, without leaving any extra capacity. This causes lots of mallocs and recopies each time the vector size is increased. (Adding elements via push_back() or emplace_back() doesn't seem to have that behavior.)
We help this by reserving some extra space before resizing - bump to the next power of 2 up to some point, then bump to the next multiple of a chunk size beyond that point.
BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4360
R=kschimpf@google.com
Review URL: https://codereview.chromium.org/1783113002 .
diff --git a/src/IceAssemblerX86BaseImpl.h b/src/IceAssemblerX86BaseImpl.h
index 19cd99c..1bf1550 100644
--- a/src/IceAssemblerX86BaseImpl.h
+++ b/src/IceAssemblerX86BaseImpl.h
@@ -63,7 +63,7 @@
return L;
}
if (Number > Labels.size()) {
- Labels.resize(Number + 1);
+ Utils::reserveAndResize(Labels, Number + 1);
}
L = Labels[Number];
if (!L) {
diff --git a/src/IceGlobalContext.cpp b/src/IceGlobalContext.cpp
index 15cc40d..c96db74 100644
--- a/src/IceGlobalContext.cpp
+++ b/src/IceGlobalContext.cpp
@@ -375,7 +375,7 @@
// Ensure Pending is large enough that Pending[Index] is valid.
void resizePending(std::vector<EmitterWorkItem *> &Pending, uint32_t Index) {
if (Index >= Pending.size())
- Pending.resize(Index + 1);
+ Utils::reserveAndResize(Pending, Index + 1);
}
} // end of anonymous namespace
diff --git a/src/IceUtils.h b/src/IceUtils.h
index 83b3fe9..2c7c62b 100644
--- a/src/IceUtils.h
+++ b/src/IceUtils.h
@@ -36,14 +36,14 @@
}
/// Check whether an N-bit two's-complement representation can hold value.
-template <typename T> static inline bool IsInt(int N, T value) {
+template <typename T> inline bool IsInt(int N, T value) {
assert((0 < N) &&
(static_cast<unsigned int>(N) < (CHAR_BIT * sizeof(value))));
T limit = static_cast<T>(1) << (N - 1);
return (-limit <= value) && (value < limit);
}
-template <typename T> static inline bool IsUint(int N, T value) {
+template <typename T> inline bool IsUint(int N, T value) {
assert((0 < N) &&
(static_cast<unsigned int>(N) < (CHAR_BIT * sizeof(value))));
T limit = static_cast<T>(1) << N;
@@ -52,7 +52,7 @@
/// Check whether the magnitude of value fits in N bits, i.e., whether an
/// (N+1)-bit sign-magnitude representation can hold value.
-template <typename T> static inline bool IsAbsoluteUint(int N, T Value) {
+template <typename T> inline bool IsAbsoluteUint(int N, T Value) {
assert((0 < N) &&
(static_cast<unsigned int>(N) < (CHAR_BIT * sizeof(Value))));
if (Value < 0)
@@ -62,14 +62,14 @@
/// Return true if the addition X + Y will cause integer overflow for integers
/// of type T.
-template <typename T> static inline bool WouldOverflowAdd(T X, T Y) {
+template <typename T> inline bool WouldOverflowAdd(T X, T Y) {
return ((X > 0 && Y > 0 && (X > std::numeric_limits<T>::max() - Y)) ||
(X < 0 && Y < 0 && (X < std::numeric_limits<T>::min() - Y)));
}
/// Adds x to y and stores the result in sum. Returns true if the addition
/// overflowed.
-static inline bool add_overflow(uint32_t x, uint32_t y, uint32_t *sum) {
+inline bool add_overflow(uint32_t x, uint32_t y, uint32_t *sum) {
static_assert(std::is_same<uint32_t, unsigned>::value, "Must match type");
#if __has_builtin(__builtin_uadd_overflow)
return __builtin_uadd_overflow(x, y, sum);
@@ -80,20 +80,20 @@
}
/// Return true if X is already aligned by N, where N is a power of 2.
-template <typename T> static inline bool IsAligned(T X, intptr_t N) {
+template <typename T> inline bool IsAligned(T X, intptr_t N) {
assert(llvm::isPowerOf2_64(N));
return (X & (N - 1)) == 0;
}
/// Return Value adjusted to the next highest multiple of Alignment.
-static inline uint32_t applyAlignment(uint32_t Value, uint32_t Alignment) {
+inline uint32_t applyAlignment(uint32_t Value, uint32_t Alignment) {
assert(llvm::isPowerOf2_32(Alignment));
return (Value + Alignment - 1) & -Alignment;
}
/// Return amount which must be added to adjust Pos to the next highest
/// multiple of Align.
-static inline uint64_t OffsetToAlignment(uint64_t Pos, uint64_t Align) {
+inline uint64_t OffsetToAlignment(uint64_t Pos, uint64_t Align) {
assert(llvm::isPowerOf2_64(Align));
uint64_t Mod = Pos & (Align - 1);
if (Mod == 0)
@@ -103,26 +103,53 @@
/// Rotate the value bit pattern to the left by shift bits.
/// Precondition: 0 <= shift < 32
-static inline uint32_t rotateLeft32(uint32_t value, uint32_t shift) {
+inline uint32_t rotateLeft32(uint32_t value, uint32_t shift) {
if (shift == 0)
return value;
return (value << shift) | (value >> (32 - shift));
}
/// Rotate the value bit pattern to the right by shift bits.
-static inline uint32_t rotateRight32(uint32_t value, uint32_t shift) {
+inline uint32_t rotateRight32(uint32_t value, uint32_t shift) {
if (shift == 0)
return value;
return (value >> shift) | (value << (32 - shift));
}
/// Returns true if Val is +0.0. It requires T to be a floating point type.
-template <typename T> static bool isPositiveZero(T Val) {
+template <typename T> bool isPositiveZero(T Val) {
static_assert(std::is_floating_point<T>::value,
"Input type must be floating point");
return Val == 0 && !std::signbit(Val);
}
+/// Resize a vector (or other suitable container) to a particular size, and also
+/// reserve possibly a larger size to avoid repeatedly recopying as the
+/// container grows. It uses a strategy of doubling capacity up to a certain
+/// point, after which it bumps the capacity by a fixed amount.
+template <typename Container>
+inline void reserveAndResize(Container &V, uint32_t Size,
+ uint32_t ChunkSizeBits = 10) {
+#if __has_builtin(__builtin_clz)
+ // Don't call reserve() if Size==0.
+ if (Size > 0) {
+ uint32_t Mask;
+ if (Size <= (1 << ChunkSizeBits)) {
+ // For smaller sizes, reserve the smallest power of 2 greater than or
+ // equal to Size.
+ Mask =
+ ((1 << (CHAR_BIT * sizeof(uint32_t) - __builtin_clz(Size))) - 1) - 1;
+ } else {
+ // For larger sizes, round up to the smallest multiple of 1<<ChunkSizeBits
+ // greater than or equal to Size.
+ Mask = (1 << ChunkSizeBits) - 1;
+ }
+ V.reserve((Size + Mask) & ~Mask);
+ }
+#endif
+ V.resize(Size);
+}
+
/// An RAII class to ensure that a boolean flag is restored to its previous
/// value upon function exit.
///
diff --git a/src/PNaClTranslator.cpp b/src/PNaClTranslator.cpp
index 4f1c3a6..1b6cadd 100644
--- a/src/PNaClTranslator.cpp
+++ b/src/PNaClTranslator.cpp
@@ -275,7 +275,7 @@
// Recover by using existing type slot.
return &TypeIDValues[0];
}
- TypeIDValues.resize(ID + 1);
+ Ice::Utils::reserveAndResize(TypeIDValues, ID + 1);
}
return &TypeIDValues[ID];
}
@@ -1566,7 +1566,7 @@
// Recover by using index one beyond the maximal allowed.
LocalIndex = MaxRecordsInBlock;
}
- LocalOperands.resize(LocalIndex + 1);
+ Ice::Utils::reserveAndResize(LocalOperands, LocalIndex + 1);
}
// If element not defined, set it.
