[SmallVector] Allow SmallVector<T>

[silvas]

Summary

This patch adds a capability to SmallVector to decide a number of inlined
elements automatically. The policy is:

• A minimum of 1 inlined elements, with more as long as sizeof(SmallVector<T>) <= 64.
• If sizeof(T) is "too big", then trigger a static_assert: this dodges the more pathological cases

This is expected to systematically improve SmallVector use in the
LLVM codebase, which has historically been plagued by semi-arbitrary /
cargo culted N parameters, often leading to bad outcomes due to
excessive sizeof(SmallVector<T, N>). This default also makes
programming more convenient by avoiding edit/rebuild cycles due to
forgetting to type the N parameter.

[dblaikie]

I'm generally good with this in terms of incremental forward progress. Still don't feel super great about the "at least 1" thing and the disparate storage limits (preferred size versus break-because-too-big size), but given the varied opinions, seems like the incremental progress is probably the best path forward for now. (perfect being the enemy of good and all that)

llvm/include/llvm/ADT/SmallVector.h

994

Could/should this be sizeof(SmallVector<T, 0>)? So that if we move members around for any reason (it's SmallVector, so it's not likely to get willy-nilly refactoring of this kind, but just on principle) this would still correctly capture the size of the SmallVector base footprint before inline buffer?

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

994

There could be difference, if it matters (not sure it does), since there's an alignas on SmallVector<T, 0> (IIRC, somehow used in isSmall).

[silvas]

Use SmallVector<T, 0> as the header size.

[silvas]

llvm/include/llvm/ADT/SmallVector.h

994

Good catch!

[silvas]

In D92522#2429795, @dblaikie wrote:

I'm generally good with this in terms of incremental forward progress. Still don't feel super great about the "at least 1" thing and the disparate storage limits (preferred size versus break-because-too-big size), but given the varied opinions, seems like the incremental progress is probably the best path forward for now. (perfect being the enemy of good and all that)

Thanks Dave. Totally agreed that this is a mismash of compromises but that even in this form it still helps push the discussion forward towards rationalizing our vector/smallvector usage. Once we rationalize it, we will hopefully be able to circle back and put this on a more principled foundation consistent with our overarching conclusions.

[lattner]

the patch looks good to me, I think the most important thing here is to nail down the programmer manual dox to be airtight :-)

llvm/docs/ProgrammersManual.rst

1527

I expand on what reasonable means here. I'd say "reasonable for inline allocation on the stack" or something like that, maybe even give the target number of inline bytes so people have a mental model.

llvm/include/llvm/ADT/SmallVector.h

990

Huh, interesting approach, I agree with the comment, I didn't think about it that way!

[silvas]

Address Chris's comments about the docs.

llvm/docs/ProgrammersManual.rst

1527

Good point. I incorporated your suggestions.

[dexonsmith]

This LGTM too. Thanks for working through all the discussion on this!

[lattner]

Thx Sean!

[silvas]

Replace constexpr function with old-school class with static members.

It looks like GCC5 does not support multi-statement constexpr functions.

[RKSimon]

FYI @silvas https://github.com/llvm/llvm-project/issues/54645 hits an issue where clang-cl /AVX builds crash if we use SmallVector<T> instead of SmallVector<T,N> - do you have any ideas?

[silvas]

Left a comment there.

llvm/docs/ProgrammersManual.rst

 fiddles around with the elements.
 
 This is good for vectors that are "usually small" (e.g. the number of
 predecessors/successors of a block is usually less than 8).  On the other hand,
 this makes the size of the SmallVector itself large, so you don't want to
 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<T>`` (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<T>)`` around 64 bytes).
+
 SmallVector also provides a nice portable and efficient replacement for
 ``alloca``.
 
 SmallVector has grown a few other minor advantages over std::vector, causing
 ``SmallVector<Type, 0>`` to be preferred over ``std::vector<Type>``.
 
 #. std::vector is exception-safe, and some implementations have pessimizations
    that copy elements when SmallVector would move them.

llvm/include/llvm/ADT/SmallVector.h

struct SmallVectorStorage {
   alignas(T) char InlineElts[N * sizeof(T)];
 };
 
 /// We need the storage to be properly aligned even for small-size of 0 so that
 /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
 /// well-defined.
 template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
 
+/// Forward declaration of SmallVector so that
+/// calculateSmallVectorDefaultInlinedElements can reference
+/// `sizeof(SmallVector<T, 0>)`.
+template <typename T, unsigned N> class LLVM_GSL_OWNER SmallVector;
+
+/// Helper class for calculating the default number of inline elements for
+/// `SmallVector<T>`.
+///
+/// This should be migrated to a constexpr function when our minimum
+/// compiler support is enough for multi-statement constexpr functions.
+template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
+  // Parameter controlling the default number of inlined elements
+  // for `SmallVector<T>`.
+  //
+  // The default number of inlined elements ensures that
+  // 1. There is at least one inlined element.
+  // 2. `sizeof(SmallVector<T>) <= 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<SmallVector<T>>` 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<T>` but `sizeof(T)` is really big! Please use an "
+      "explicit number of inlined elements with `SmallVector<T, N>` 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<T, 0>);
+  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
 /// elements is below that threshold.  This allows normal "small" cases to be
 /// fast without losing generality for large inputs.
 ///
 /// Note that this does not attempt to be exception safe.
 ///
-template <typename T, unsigned N>
+template <typename T,
+          unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
 class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>,
                                    SmallVectorStorage<T, N> {
 public:
   SmallVector() : SmallVectorImpl<T>(N) {}
 
   ~SmallVector() {
     // Destroy the constructed elements in the vector.
     this->destroy_range(this->begin(), this->end());

llvm/unittests/ADT/SmallVectorTest.cpp

EmplaceableArg<3> A3(true);
     V.emplace_back();
     V.emplace_back(42);
     EXPECT_EQ(2U, V.size());
     EXPECT_EQ(0, V[0]);
     EXPECT_EQ(42, V[1]);
   }
 }
 
+TEST(SmallVectorTest, DefaultInlinedElements) {
+  SmallVector<int> V;
+  EXPECT_TRUE(V.empty());
+  V.push_back(7);
+  EXPECT_EQ(V[0], 7);
+
+  // Check that at least a couple layers of nested SmallVector<T>'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<SmallVector<SmallVector<int>>> NestedV;
+  NestedV.emplace_back().emplace_back().emplace_back(42);
+  EXPECT_EQ(NestedV[0][0][0], 42);
+}
+
 TEST(SmallVectorTest, InitializerList) {
   SmallVector<int, 2> V1 = {};
   EXPECT_TRUE(V1.empty());
   V1 = {0, 0};
   EXPECT_TRUE(makeArrayRef(V1).equals({0, 0}));
   V1 = {-1, -1};
   EXPECT_TRUE(makeArrayRef(V1).equals({-1, -1}));