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

>>> 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?

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201201/fbb568d8/attachment.html>

On Tue, Dec 1, 2020 at 2:19 PM Chris Lattner via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> On Nov 17, 2020, at 1:42 PM, David Blaikie <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?
>
It isn't clear to me that -fno-exceptions can get the same benefit as
noexcept for code that is written with exceptions in mind (I think
https://stackoverflow.com/questions/61417534/can-stdvectort-use-ts-move-constructor-if-exceptions-are-disabled
explains some of it).

While it is possible to write a library that optimizes for -fno-exceptions,
I am not sure it would be standard-compliant for the STL to do so (and it'd
be anyway another code path that the one written in term of
`std::move_if_noexcept`).

Does it make sense or did you see it differently with your question?

-- 
Mehdi
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201201/ebcfc472/attachment.html>

+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>