ADT: Document advantages of SmallVector<T,0> over std::vector

[dexonsmith]

Summary

In light of the recent changes to SmallVector in r335421, r337514, and r337820, document its advantages over std::vector (see r175906 and r266909).

Also add a release note.

[rnk]

lgtm

Thanks for writing down things that were previously just "known".

[dexonsmith]

Committed in r338071.

llvm/docs/ProgrammersManual.rst

 ^^^^^^^^^^^^^^^^^^^^^^
 
 ``SmallVector<Type, N>`` is a simple class that looks and smells just like
 ``vector<Type>``: it supports efficient iteration, lays out elements in memory
 order (so you can do pointer arithmetic between elements), supports efficient
 push_back/pop_back operations, supports efficient random access to its elements,
 etc.
 
-The advantage of SmallVector is that it allocates space for some number of
+The main advantage of SmallVector is that it allocates space for some number of
 elements (N) **in the object itself**.  Because of this, if the SmallVector is
 dynamically smaller than N, no malloc is performed.  This can be a big win in
 cases where the malloc/free call is far more expensive than the code that
 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.
 
 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.
+
+#. SmallVector understands ``isPodLike<Type>`` and uses realloc aggressively.
+
+#. Many LLVM APIs take a SmallVectorImpl as an out parameter (see the note
+   below).
+
+#. SmallVector with N equal to 0 is smaller than std::vector on 64-bit
+   platforms, since it uses ``unsigned`` (instead of ``void*``) for its size
+   and capacity.
+
 .. note::
 
    Prefer to use ``SmallVectorImpl<T>`` as a parameter type.
 
    In APIs that don't care about the "small size" (most?), prefer to use
    the ``SmallVectorImpl<T>`` class, which is basically just the "vector
    header" (and methods) without the elements allocated after it. Note that
    ``SmallVector<T, N>`` inherits from ``SmallVectorImpl<T>`` so the
.. note::
    it really isn't "private to the implementation" anymore. A name like
    ``SmallVectorHeader`` would be more appropriate.
 
 .. _dss_vector:
 
 <vector>
 ^^^^^^^^
 
-``std::vector`` is well loved and respected.  It is useful when SmallVector
-isn't: when the size of the vector is often large (thus the small optimization
-will rarely be a benefit) or if you will be allocating many instances of the
-vector itself (which would waste space for elements that aren't in the
-container).  vector is also useful when interfacing with code that expects
-vectors :).
+``std::vector<T>`` is well loved and respected.  However, ``SmallVector<T, 0>``
+is often 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 :).
 
 One worthwhile note about std::vector: avoid code like this:
 
 .. code-block:: c++
 
   for ( ... ) {
      std::vector<foo> V;
      // make use of V.

llvm/docs/ReleaseNotes.rst

 .. code-block:: bash
 
     git grep -l 'DEBUG' | xargs perl -pi -e 's/\bDEBUG\s?\(/LLVM_DEBUG(/g'
     git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM
 
 * Early support for UBsan, X-Ray instrumentation and libFuzzer (x86 and x86_64) for OpenBSD. Support for MSan
   (x86_64), X-Ray instrumentation and libFuzzer (x86 and x86_64) for FreeBSD.
 
+* ``SmallVector<T, 0>`` shrank from ``sizeof(void*) * 4 + sizeof(T)`` to
+  ``sizeof(void*) + sizeof(unsigned) * 2``, smaller than ``std::vector<T>`` on
+  64-bit platforms.  The maximum capacity is now restricted to ``UINT32_MAX``.
+  Since SmallVector doesn't have the exception-safety pessimizations some
+  implementations saddle std::vector with and is better at using ``realloc``,
+  it's now a better choice even on the heap (although when TinyPtrVector works,
+  it's even smaller).
+
 * Note..
 
 .. NOTE
    If you would like to document a larger change, then you can add a
    subsection about it right here. You can copy the following boilerplate
    and un-indent it (the indentation causes it to be inside this comment).
 
    Special New Feature