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

Tue Nov 17 17:29:31 PST 2020

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/20201117/e352562c/attachment.html>