llvm dev - Dec 2020 - RFC: [SmallVector] Adding SVec<T> and Vec<T> convenience wrappers.

+richard
> On 2020 Dec  1, at 14:19, Chris Lattner <clattner at nondot.org>
wrote:
> 
>>>> On Nov 17, 2020, at 1:42 PM, David Blaikie <dblaikie at
gmail.com <mailto:dblaikie at gmail.com>> wrote:
>>>>>> Thoughts/suggestions:
>>>>>> - Adding the default seems very reasonable to me, and I
think that 64 bytes is a good default.  I think you should change the behavior
so that SmallVector<LargeThing> defaults to a single inline element
instead of zero though.  Perhaps generate a static_assert when it is crazy
large.
>>>>> 
>>>>> Out of curiosity: Why a single rather than zero?
>>>> 
>>>> My rationale for this is basically that SmallVector is
typically used for the case when you want to avoid an out-of-line allocation for
a small number of elements, this was the reason it was created.  While there is
some performance benefits of SmallVector<T,0> over std::vector<>
they are almost trivial.
>>> 
>>> The performance benefits aren't trivial.
>>> 
>>> std::vector grow operations will refuse to use std::move for some
T, a pessimization required by its exception guarantees, even if you're
building with `-fno-exceptions`. We had a massive compile-time problem in 2016
related to this that I fixed with 3c406c2da52302eb5cced431373f240b9c037841 by
switching to SmallVector<T,0>. You can see the history in r338071 /
0f81faed05c3c7c1fbaf6af402411c99d715cf56.
>>> 
>>> That issue, at least, is fixable without switching from std::vector
just by adding noexcept to the appropriate user-defined move constructors.
>> 
>> Sure, once we’ve added noexcept to all types in LLVM/Clang/etc. That’s
a pretty long tail though; a lot of work for relatively little gain given that
we don’t care about exceptions anyway and we have an optimized vector
implementation in tree.
> 
> Can you spell this out for me?  Why do we need noexcept if we’re building
with -fno-exceptions?  What is going on here?
Sure. It's a bit convoluted. Here's my understanding:

First, here's why std::vector has this behaviour:
- std::vector grow operations need to transfer their existing elements over to
the new storage.
- The grow operations are usually required to meet the "strong exception
guarantee": if something throws, this function has no effect.
- If move operations throw, you can't provide this guarantee unless you copy
(you can't move back the elements that have been half-moved over, in case
another exception is thrown; but if it was just a copy, the original storage
still has the elements safely unmodified).
- There's a caveat / carve out, that if T cannot be copy-constructed AND
T's move constructor is not noexcept, then the guarantee is waived (since
there's no way to implement it).
- Implementation is to call std::move_if_noexcept
(https://en.cppreference.com/w/cpp/utility/move_if_noexcept), which moves if
it's a noexcept operation, or if T is not copy-constructible.

Second, here's why the behaviour doesn't change when -fno-exceptions:
- -fno-exceptions does NOT imply `noexcept` (maybe it should?, but it
doesn't).
- This is implemented by detecting via SFINAE whether something is `noexcept`
(maybe std::vector::resize/push_back/etc should have a special case? but
that's controversial).

IMO, until all the C++ standard libraries and host compilers that we support
being built with will consistently use std::move on grow operations in
std::vector in -fno-exceptions mode, we should only use std::vector when we
absolutely have to. It's not designed for -fno-exceptions codebases.

(
There's some discussion in this thread:
http://lists.llvm.org/pipermail/libcxx-dev/2019-April/000344.html

And Richard had a proposal that made sense to me:
http://lists.llvm.org/pipermail/libcxx-dev/2019-April/000343.html
> I'm wondering if we should have an experimental
> option to specify that functions are noexcept by default (overridable
> by an explicit exception specification)

But that only fixes it in host compilers that implemented this experimental
mode.
)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201201/f1ab91d5/attachment.html>

> On Dec 1, 2020, at 4:07 PM, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
>> 
>> Can you spell this out for me?  Why do we need noexcept if we’re
building with -fno-exceptions?  What is going on here?
> 
> Sure. It's a bit convoluted. Here's my understanding:
> 
> First, here's why std::vector has this behaviour:
> - std::vector grow operations need to transfer their existing elements over
to the new storage.
> - The grow operations are usually required to meet the "strong
exception guarantee": if something throws, this function has no effect.
> - If move operations throw, you can't provide this guarantee unless you
copy (you can't move back the elements that have been half-moved over, in
case another exception is thrown; but if it was just a copy, the original
storage still has the elements safely unmodified).
> - There's a caveat / carve out, that if T cannot be copy-constructed
AND T's move constructor is not noexcept, then the guarantee is waived
(since there's no way to implement it).
> - Implementation is to call std::move_if_noexcept
(https://en.cppreference.com/w/cpp/utility/move_if_noexcept
<https://en.cppreference.com/w/cpp/utility/move_if_noexcept>), which moves
if it's a noexcept operation, or if T is not copy-constructible.
> 
> Second, here's why the behaviour doesn't change when
-fno-exceptions:
> - -fno-exceptions does NOT imply `noexcept` (maybe it should?, but it
doesn't).
> - This is implemented by detecting via SFINAE whether something is
`noexcept` (maybe std::vector::resize/push_back/etc should have a special case?
but that's controversial).
> 
> IMO, until all the C++ standard libraries and host compilers that we
support being built with will consistently use std::move on grow operations in
std::vector in -fno-exceptions mode, we should only use std::vector when we
absolutely have to. It's not designed for -fno-exceptions codebases
Wow, thank you for the great explanation.  I agree with you that this seems like
a pretty credible reason why we can’t depend on every host std::vector to do
what we need, so we should use something like an llvm::Vector.

Two thoughts:

1) are you, or anyone else, interested in driving an llvm::Vector proposal +
coding standard change to get us going in the right direction?  I don’t think we
need a mass migration of the code base, just get the policy aligned right plus
the new type name to exist.

2) I think we should pursue Richard’s proposal or something like it to make
Clang provide better C++ performance out of the box.  I assume that all the STL
containers will have similar issues (not to mention user defined ones), and
noexcept isn’t widely used.  Some flag that turns noexcept on by default (or for
everything even with an exception spec?) in -fno-exceptions mode seems like a
great thing to do.

-Chris

> .
> 
> (
> There's some discussion in this thread:
> http://lists.llvm.org/pipermail/libcxx-dev/2019-April/000344.html
<http://lists.llvm.org/pipermail/libcxx-dev/2019-April/000344.html>
> 
> And Richard had a proposal that made sense to me:
> http://lists.llvm.org/pipermail/libcxx-dev/2019-April/000343.html
<http://lists.llvm.org/pipermail/libcxx-dev/2019-April/000343.html>
>> I'm wondering if we should have an experimental
>> option to specify that functions are noexcept by default (overridable
>> by an explicit exception specification)
> 
> 
> But that only fixes it in host compilers that implemented this experimental
mode.
> )
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201201/453ae8c6/attachment.html>