[CodingStandards] Clarify the recommendation to use SmallVector

[gribozavr]

Summary

SmallVector is not unconditionally better than std::vector, it only
makes sense when the small size optimization is meaningful. In fact,
LLVM and Clang use std::vector a lot when the small size optimization is
not needed. Therefore, the wording "should usually be used" is
misleading.

[lebedev.ri]

What reasoning was used in the patch that added that wording?
IIRC llvm::SmallVector is better than std::vector also because
former doubles the allocation size instead of just increasing it.

[gribozavr2]

In D89544#2334494, @lebedev.ri wrote:

What reasoning was used in the patch that added that wording?

https://reviews.llvm.org/D74340

IIRC llvm::SmallVector is better than std::vector also because
former doubles the allocation size instead of just increasing it.

std::vector must also use a multiplicative strategy in order to provide O(1) push_back. The C++ standard does not guarantee the specific factor though.

As written, the wording can be read to suggest to use llvm::SmallVector<T, 0> instead of std::vector<T>. Is that the intent?

[jdoerfert]

Ratio in llvm-core, not that this method is actually accurate but I guess the ballpark is right:

ag SmallVector llvm/lib | wc
   9498   43412  970112

ag 'std::vector' llvm/lib | wc
   2296    9660  231768

[tschuett]

Maybe some examples?

Prefer llvm::SmallVector<T, 10> over std::vector<T> if you expect to store less than 10 elements.

Prefer std::vector<T> over llvm::SmallVector<T, 10> if expect to store way more than 10 elements.

[rjmccall]

llvm::SmallVector isn't, like, otherwise worse than std::vector, so that you should only consider it over std::vector when the inline-capacity optimization is highly valuable. It does have some specific drawbacks, but we go into this in more detail in the programmer's manual. I think "prefer llvm::SmallVector" is fine general advice for this paragraph.

[rjmccall]

Even if we decide to change that recommendation, this is not the place to elaborate on the advice. We have an entire section of the developer's manual dedicated to providing guidance on choosing data structures, and we should not duplicate it clumsily and in part out here.

[mehdi_amini]

SmallVector<T, 0> is documented here: https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h

llvm/docs/CodingStandards.rst

 implement specialized data structures or functionality missing in the standard
 library. Such libraries are usually implemented in the ``llvm`` namespace and
 follow the expected standard interface, when there is one.
 
 When both C++ and the LLVM support libraries provide similar functionality, and
 there isn't a specific reason to favor the C++ implementation, it is generally
 preferable to use the LLVM library. For example, ``llvm::DenseMap`` should
 almost always be used instead of ``std::map`` or ``std::unordered_map``, and
-``llvm::SmallVector`` should usually be used instead of ``std::vector``.
+``llvm::SmallVector`` should be used instead of ``std::vector`` when the small
+size optimization makes sense.
 
 We explicitly avoid some standard facilities, like the I/O streams, and instead
 use LLVM's streams library (raw_ostream_). More detailed information on these
 subjects is available in the :doc:`ProgrammersManual`.
 
 For more information about LLVM's data structures and the tradeoffs they make,
 please consult [that section of the programmer's
 manual](https://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task).