diff --git a/llvm/docs/ProgrammersManual.rst b/llvm/docs/ProgrammersManual.rst --- a/llvm/docs/ProgrammersManual.rst +++ b/llvm/docs/ProgrammersManual.rst @@ -1521,6 +1521,12 @@ allocate lots of them (doing so will waste a lot of space). As such, SmallVectors are most useful when on the stack. +In the absence of a well-motivated choice for the number of +inlined elements ``N``, it is recommended to use ``SmallVector`` (that is, +omitting the ``N``). This will choose a default number of +inlined elements reasonable for allocation on the stack (for example, trying +to keep ``sizeof(SmallVector)`` around 64 bytes). + SmallVector also provides a nice portable and efficient replacement for ``alloca``. diff --git a/llvm/include/llvm/ADT/SmallVector.h b/llvm/include/llvm/ADT/SmallVector.h --- a/llvm/include/llvm/ADT/SmallVector.h +++ b/llvm/include/llvm/ADT/SmallVector.h @@ -948,6 +948,64 @@ /// well-defined. template struct alignas(T) SmallVectorStorage {}; +/// Forward declaration of SmallVector so that +/// calculateSmallVectorDefaultInlinedElements can reference +/// `sizeof(SmallVector)`. +template class LLVM_GSL_OWNER SmallVector; + +/// Helper class for calculating the default number of inline elements for +/// `SmallVector`. +/// +/// This should be migrated to a constexpr function when our minimum +/// compiler support is enough for multi-statement constexpr functions. +template struct CalculateSmallVectorDefaultInlinedElements { + // Parameter controlling the default number of inlined elements + // for `SmallVector`. + // + // The default number of inlined elements ensures that + // 1. There is at least one inlined element. + // 2. `sizeof(SmallVector) <= kPreferredSmallVectorSizeof` unless + // it contradicts 1. + static constexpr size_t kPreferredSmallVectorSizeof = 64; + + // static_assert that sizeof(T) is not "too big". + // + // Because our policy guarantees at least one inlined element, it is possible + // for an arbitrarily large inlined element to allocate an arbitrarily large + // amount of inline storage. We generally consider it an antipattern for a + // SmallVector to allocate an excessive amount of inline storage, so we want + // to call attention to these cases and make sure that users are making an + // intentional decision if they request a lot of inline storage. + // + // We want this assertion to trigger in pathological cases, but otherwise + // not be too easy to hit. To accomplish that, the cutoff is actually somewhat + // larger than kPreferredSmallVectorSizeof (otherwise, + // `SmallVector>` would be one easy way to trip it, and that + // pattern seems useful in practice). + // + // One wrinkle is that this assertion is in theory non-portable, since + // sizeof(T) is in general platform-dependent. However, we don't expect this + // to be much of an issue, because most LLVM development happens on 64-bit + // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for + // 32-bit hosts, dodging the issue. The reverse situation, where development + // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a + // 64-bit host, is expected to be very rare. + static_assert( + sizeof(T) <= 256, + "You are trying to use a default number of inlined elements for " + "`SmallVector` but `sizeof(T)` is really big! Please use an " + "explicit number of inlined elements with `SmallVector` to make " + "sure you really want that much inline storage."); + + // Discount the size of the header itself when calculating the maximum inline + // bytes. + static constexpr size_t PreferredInlineBytes = + kPreferredSmallVectorSizeof - sizeof(SmallVector); + static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T); + static constexpr size_t value = + NumElementsThatFit == 0 ? 1 : NumElementsThatFit; +}; + /// This is a 'vector' (really, a variable-sized array), optimized /// for the case when the array is small. It contains some number of elements /// in-place, which allows it to avoid heap allocation when the actual number of @@ -956,7 +1014,8 @@ /// /// Note that this does not attempt to be exception safe. /// -template +template ::value> class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl, SmallVectorStorage { public: diff --git a/llvm/unittests/ADT/SmallVectorTest.cpp b/llvm/unittests/ADT/SmallVectorTest.cpp --- a/llvm/unittests/ADT/SmallVectorTest.cpp +++ b/llvm/unittests/ADT/SmallVectorTest.cpp @@ -983,6 +983,22 @@ } } +TEST(SmallVectorTest, DefaultInlinedElements) { + SmallVector V; + EXPECT_TRUE(V.empty()); + V.push_back(7); + EXPECT_EQ(V[0], 7); + + // Check that at least a couple layers of nested SmallVector's are allowed + // by the default inline elements policy. This pattern happens in practice + // with some frequency, and it seems fairly harmless even though each layer of + // SmallVector's will grow the total sizeof by a vector header beyond the + // "preferred" maximum sizeof. + SmallVector>> NestedV; + NestedV.emplace_back().emplace_back().emplace_back(42); + EXPECT_EQ(NestedV[0][0][0], 42); +} + TEST(SmallVectorTest, InitializerList) { SmallVector V1 = {}; EXPECT_TRUE(V1.empty());