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

[Sean Silva via llvm-dev]

Ping.

It sounds like we left off with consensus around just making SmallVector<T>
have a default N.

We were converging to a default N policy of:
- at least 1 inlined element
- sizeof(SmallVector<T>) <= 64 when it doesn't contradict the "at least 1
inlined element".

Any objections to moving forward with that?

-- Sean Silva

On Tue, Nov 17, 2020 at 5:29 PM Sean Silva <chisophugis at gmail.com> wrote:

>
>
> On Tue, Nov 17, 2020 at 2:16 PM Duncan P. N. Exon Smith <
> dexonsmith at apple.com> wrote:
>
>>
>>
>> On 2020 Nov  17, at 13:40, Sean Silva <chisophugis at gmail.com> wrote:
>>
>>
>>
>> On Tue, Nov 17, 2020 at 7:26 AM Chris Lattner <clattner at nondot.org>
>> wrote:
>>
>>> On Nov 13, 2020, at 2:06 PM, Sean Silva via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>> We've pretty happy now with a patch that adds two wrappers around
>>> SmallVector that make it 1) more convenient to use and 2) will tend to
>>> mitigate misuse of SmallVector. We think it's ready for wider discussion:
>>> https://reviews.llvm.org/D90884
>>>
>>> SVec<T> is a convenience alias for SmallVector<T, N> with N chosen
>>> automatically to keep its size under 64 Bytes (that heuristic is easy to
>>> change though). The recommendation in the patch is to use this "on the
>>> stack, where a "small" number of elements are expected".
>>>
>>>
>>> Hey Sean,
>>>
>>> I agree with other comments that his approach unnecessarily fragments
>>> the API surface area for a core class.  You’re doing two things here: 1)
>>> adding a new name for an existing thing, and 2) adding a default.
>>>
>>> My major concern and objection is about #1, since the codebase will get
>>> to be a mishmash of the two.  I’d rather keep the world consistent here and
>>> have an opinionated “one way to do it”.
>>>
>>
>> Thanks Chris. That was my original proposal when I first drafted the
>> patch, and I'm happy to just add the default.
>>
>>
>>>
>>> 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.
>>>
>>
>> That would work for me.
>>
>> Mehdi, would SmallVector<T>, defaulting to a minimum single inline
>> element with static_assert(sizeof(T) < 512) address your concerns?
>>
>>
>> I'd be a bit concerned about this for two reasons:
>>
>> - Adding a large inlined element by-default may reinforce one of the
>> problems with SmallVector, that people accidentally put big vectors in
>> places that shouldn't have them. If we're going to make accidentally large
>> inlined vectors more ergonomic, I think we ought to make 0-element versions
>> more ergonomic too.
>>
>
> I would prefer 0, but I'm ok with 1 because SmallVector<SmallVector<T>>
> avoids the "exponential" effect of SmallVector<SmallVector<T, 4>, 2> == 8
> inlined T's (+ headers and stuff).
>
> As an experiment, I added in a static_assert(sizeof(T) < 512) into
> SmallVector. Almost all the errors were due to nested
> SmallVector<SmallVector<T, 4 or 8>, 4 or 8> and such. The only case I could
> see in the error log that was *not* due to nested SmallVector's was this
> legitimately enormous struct in llvm-objcopy:
> https://github.com/llvm/llvm-project/blob/67e0f791c93a23d0a523f3f05082c020f7c9109f/llvm/tools/llvm-objcopy/CopyConfig.h#L149
> (which, btw, is used only in a SmallVector<T, 1>)
>
> So I feel pretty confident that 1 inline element from
> SmallVector<LargeType> is probably less or equal to what users would
> choose. Thus, I still think 1 inline element minimum is net positive if
> Chris won't budge on lowering that to 0.
>
> Chris, thoughts?
>
>
>
>>
>> - The `static_assert` is going to fail differently on different
>> platforms, since `T`'s size will tend to be platform-dependent for large
>> `T`. I'm not sure it'll be predictable enough.
>>
>
> Agreed.
>
>
>>
>> -- Sean Silva
>>
>>
>>>
>>>  - The name SmallVector has always been confusing, InlinedVector is more
>>> principled, but is even more verbose for such a common type.  If you think
>>> it is worth shrinkifying the name SmallVector, then I think the best thing
>>> to do is *rename* SmallVector (perhaps to IVector?) everywhere in the
>>> codebase.  I don’t think that introducing a redundant name is a good thing
>>> (except to smooth the transition).
>>>
>>
>> I like the idea of a minor rename, although a bit different:
>> - SmallVectorBase => VectorBase
>> - SmallVectorImpl => VectorImpl (we could keep both around for a
>> transition period)
>> - (etc.)
>> - SmallVector => Vector, but give `Vector` a default small size of 0
>> - Add SmallVector as a wrapper around Vector that has a nice default for
>> the small size:
>> ```
>> template <class T>
>> using SmallVector = Vector<T, DefaultInlinedElementSize<T>>;
>> ```
>>
>
> I'm generally +1 on making SmallVector<T, 0> be easier to use, but it
> seems that the discussion of default N is already complex enough, so for
> now let's focus only on the default N situation.
>
> -- Sean Silva
>
>
>>  - If people are concerned about the default being bad, then you could
>>> choose to make “SmallVector<T, -1>” be the thing that autosizes.  I tend to
>>> agree with your viewpoint that the N chosen is arbitrary in almost all
>>> cases anyway though, so I wouldn’t go this way.
>>>
>>>
>>> Vec<T> is a convenience alias for SmallVector<T, 0>. It lets us get the
>>> (little-known?) benefits of SmallVector even when it has no inline elements
>>> (see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h).
>>> The recommendation in the patch is to use this when the SmallVector is on
>>> the heap.
>>>
>>>
>>> These benefits are tiny, I really don’t think it is worth introducing a
>>> new name for this.  I think this is better handled with a change to
>>> CodingStandards (saying “don’t use std::vector”) and the programmers manual.
>>>
>>> -Chris
>>>
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201125/349ad833/attachment.html>