diff --git a/llvm/docs/ProgrammersManual.rst b/llvm/docs/ProgrammersManual.rst --- a/llvm/docs/ProgrammersManual.rst +++ b/llvm/docs/ProgrammersManual.rst @@ -1498,6 +1498,49 @@ Since this container is highly specialized, it is rarely used. +.. _dss_vec_svec: + +``Vec`` and ``SVec`` +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +``Vec`` and ``SVec`` are LLVM's preferred replacement for +``std::vector``. They are convenience wrappers around +:ref:`SmallVector `, and thus inherit all the benefits of that +type as compared to ``std::vector``. + +The recommended usage guidelines are simple: + +* ``SVec`` is recommended for vectors on the stack, where a "small" number + of elements is expected. (the "S" in the name stands for "Small"). +* ``Vec`` is recommended for vectors on the heap. This includes inside other + data structures, such as ``DenseMap>``. + +``SVec`` is just a ``SmallVector`` with ``N`` chosen automatically +using an internal heuristic that decides a reasonable number of +inline elements (which can be 0 if ``sizeof(T)`` is very big!). +If measurements show a need for more or fewer inline elements than +the ``SVec`` default, a ``SmallVector`` should be used. + +``Vec`` is just a ``SmallVector``. As described in the +:ref:`SmallVector ` section, this has advantages over +``std::vector``, even with 0 inline elements. + +There are exceptions to the recommendations above. Speaking generally, the +the additional storage space of the inline storage of ``SVec`` takes up more +memory and also makes move/copy more expensive. The lack of inline elements +in ``Vec`` will result in more malloc/free calls in usage scenarios where +the inline element storage would typically be large enough. + +.. note:: + + Historically, ``SmallVector`` has suffered from various misuses + due to the ``N`` parameter being chosen semi-arbitrarily (such + as described in `this thread + `_). + Making it easy to use ``Vec`` where appropriate, along with the principled + default number of inline elements for ``SVec`` is expected to mitigate + those issues. + .. _dss_smallvector: llvm/ADT/SmallVector.h @@ -1584,8 +1627,8 @@ ^^^^^^^^ -``std::vector`` is well loved and respected. However, ``SmallVector`` -is often a better option due to the advantages listed above. std::vector is +``std::vector`` is well loved and respected. However, ``Vec`` +is generally a better option due to the advantages listed above. std::vector is still useful when you need to store more than ``UINT32_MAX`` elements or when interfacing with code that expects vectors :). 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 @@ -978,6 +978,54 @@ return {std::begin(Range), std::end(Range)}; } +/// Parameter controlling the default number of inlined elements for SVec. +/// +/// We guarantee that `sizeof(SVec) <= kSVecMaxSizeof`. +constexpr size_t kSVecMaxSizeof = 64; +template constexpr size_t calculateSVecInlineElements() { + // Discount the size of the header itself when calculating the maximum inline + // bytes. + size_t MaxInlineBytes = kSVecMaxSizeof - sizeof(SmallVectorImpl); + return MaxInlineBytes / sizeof(ElementTy); +} + +/// SVec is a convenience wrapper around SmallVector with a default number of +/// inlined elements. +/// +/// One major reason to use SVec over SmallVector is convenience -- there is no +/// need to choose the number of inlined elements, or to write that number in +/// the type. Also, SVec is a shorter name than SmallVector which helps as well. +/// +/// SVec adjusts the number of inlined elements with a policy that bounds the +/// total `sizeof(SVec)` to never exceed a fixed size (currently 64 bytes). +/// This prevents a number of the most pathological cases of SmallVector usage. +/// For example, `SVec>>` works fine and doesn't result in an +/// excessive `sizeof`. +/// +/// For small types like `char`, the number of inlined elements will be larger. +/// For types like large structs, the number of inlined elements will be +/// smaller, including possibly having zero inlined elements in the extreme +/// case! +/// +/// Over time, we have found that most choices of the number of inlined elements +/// for SmallVector are chosen semi-arbitrarily or cargo-culted. It is expected +/// that by tuning SVec default sizes in aggregate by adjusting the policy here, +/// we can realize codebase-wide gains that would not be measurable if done +/// by tuning individual SmallVector sizes across the codebase. +template +using SVec = SmallVector()>; + +/// `Vec` is a convenience wrapper around SmallVector with 0 inlined +/// elements, and should generally be preferred over `std::vector`. +/// +/// As described in +/// https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h +/// `SmallVector` has a number of advantages over `std::vector`. +/// +/// See https://llvm.org/docs/ProgrammersManual.html#vector for situations +/// in which `std::vector` should be preferred over `Vec`. +template using Vec = SmallVector; + } // end namespace llvm namespace std { 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 @@ -999,4 +999,23 @@ EXPECT_TRUE(makeArrayRef(V2).equals({4, 5, 3, 2})); } +struct BigElementType { + char Arr[10000] = {0}; +}; +template struct TestSVecSizeof { + static_assert(sizeof(SVec) <= kSVecMaxSizeof, ""); +}; +using instantiateTestSVecSizeof = + ::testing::Types, TestSVecSizeof, + TestSVecSizeof, TestSVecSizeof, + TestSVecSizeof, TestSVecSizeof>; + +TEST(SmallVectorTest, SpotCheckOfVec) { + // Spot check that Vec works. + Vec V1; + EXPECT_TRUE(V1.empty()); + V1.push_back(1); + EXPECT_EQ(V1[0], 1); +} + } // end namespace