llvm dev - Jun 2018 - RFC: Should SmallVectors be smaller?

> On Jun 23, 2018, at 10:14, Chris Lattner <clattner at nondot.org>
wrote:
> 
> 
> 
>> On Jun 23, 2018, at 9:11 AM, Duncan P. N. Exon Smith <dexonsmith at
apple.com <mailto:dexonsmith at apple.com>> wrote:
>> 
>>> 
>>> I think we might be better off just reducing the pre-allocation
size of most of our SmallVectors across LLVM and Clang. They're all wild
guesses, never profiled. Especially for vectors of relatively "large"
elements, the pre-allocation optimization just doesn't make that much sense.
I'd go as far as to suggest providing a default SmallVector N value of
something like `sizeof(void*) * 3 / sizeof(T)`, i.e. by default, every
SmallVector is at most 6 pointers big.
>> 
>> Interesting idea... and then audit current instances to drop the size
argument.
>> 
>> Note that a SmallVector with N value of 0 takes the same storage as an
N value of 1, so very large sizeof(T) would still use more than 6 pointers.  The
cause is that SmallVectorTemplateCommon stores the first element so that it can
detect small mode by comparing BeginX against &FirstEl.  The fix would be to
shave a bit off of capacity (dropping max capacity to 2B)... likely reasonable.
> 
> The patch LGTM, but why would someone actually have a SmallVector with N =
0?  Isn’t that a vector?
It's a vector that can be passed as a SmallVectorImpl parameter.  But yeah,
mostly misguided.
> Also if you’re not familiar with it, TinyPtrVector is a very useful type
for vectors that are highly biased towards 0/1 element and whose elements are
pointer size.  It was added relatively late in LLVM’s evolution, so I wouldn’t
be surprised if there are still smallvectors that should be upgraded. 
TinyPtrVector is designed for use on the heap.
Yup, it's great for pointers.  Maybe we should make a TinyVector for
non-pointers and call it a day.
>> If we're going to audit anyway, I wonder if forking names would
make sense.  E.g., the current thing would be less tempting to use in data
structures if it were called StackVector.  But that wouldn't be a fun change
to roll out across sub-projects.
>> 
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180623/f1d6558d/attachment.html>

> On Jun 23, 2018, at 11:27, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
> 
>> The patch LGTM, but why would someone actually have a SmallVector with
N = 0?  Isn’t that a vector?
> 
> It's a vector that can be passed as a SmallVectorImpl parameter.  But
yeah, mostly misguided.
> 
There's another explanation given in llvm/include/llvm/ADT/IndexedMap.h:
```
template <typename T, typename ToIndexT = identity<unsigned>>
  class IndexedMap {
    using IndexT = typename ToIndexT::argument_type;
    // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps
    // can grow very large and SmallVector grows more efficiently as long as T
    // is trivially copyable.
    using StorageT = SmallVector<T, 0>;

```
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180623/16298af6/attachment.html>

> On Jun 23, 2018, at 11:35, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
> 
> 
> 
>> On Jun 23, 2018, at 11:27, Duncan P. N. Exon Smith <dexonsmith at
apple.com <mailto:dexonsmith at apple.com>> wrote:
>> 
>>> The patch LGTM, but why would someone actually have a SmallVector
with N = 0?  Isn’t that a vector?
>> 
>> It's a vector that can be passed as a SmallVectorImpl parameter. 
But yeah, mostly misguided.
>> 
> 
> There's another explanation given in
llvm/include/llvm/ADT/IndexedMap.h:
> ```
> template <typename T, typename ToIndexT = identity<unsigned>>
>   class IndexedMap {
>     using IndexT = typename ToIndexT::argument_type;
>     // Prefer SmallVector with zero inline storage over std::vector.
IndexedMaps
>     // can grow very large and SmallVector grows more efficiently as long
as T
>     // is trivially copyable.
>     using StorageT = SmallVector<T, 0>;
> 
> ```
And another explanation in r266909, along the same lines:

    IR: Use SmallVector instead of std::vector of TrackingMDRef
    
    Don't use std::vector<TrackingMDRef>, since (at least in some
versions
    of libc++) std::vector apparently copies values on grow operations
    instead of moving them.  Found this when I was temporarily deleting the
    copy constructor for TrackingMDRef to investigate a performance
    bottleneck.


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180623/25ec1d0b/attachment.html>

> On Jun 23, 2018, at 11:27 AM, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
> 
>> 
>> Also if you’re not familiar with it, TinyPtrVector is a very useful
type for vectors that are highly biased towards 0/1 element and whose elements
are pointer size.  It was added relatively late in LLVM’s evolution, so I
wouldn’t be surprised if there are still smallvectors that should be upgraded. 
TinyPtrVector is designed for use on the heap.
> 
> Yup, it's great for pointers.  Maybe we should make a TinyVector for
non-pointers and call it a day.
Sure.  The nice thing about TinyPtrVector is that sizeof(TinyPtrVector) is
sizeof(void*) through bitstealing, which you can’t achieve with an arbitrary T.

-Chris

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

(add back llvm-dev)
> On Jun 23, 2018, at 16:16, Duncan P. N. Exon Smith <dexonsmith at
apple.com> wrote:
> 
> 
> 
>> On Jun 23, 2018, at 16:13, Chris Lattner <clattner at nondot.org
<mailto:clattner at nondot.org>> wrote:
>> 
>> 
>> 
>>> On Jun 23, 2018, at 11:27 AM, Duncan P. N. Exon Smith
<dexonsmith at apple.com <mailto:dexonsmith at apple.com>> wrote:
>>> 
>>>> 
>>>> Also if you’re not familiar with it, TinyPtrVector is a very
useful type for vectors that are highly biased towards 0/1 element and whose
elements are pointer size.  It was added relatively late in LLVM’s evolution, so
I wouldn’t be surprised if there are still smallvectors that should be upgraded.
TinyPtrVector is designed for use on the heap.
>>> 
>>> Yup, it's great for pointers.  Maybe we should make a
TinyVector for non-pointers and call it a day.
>> 
>> Sure.  The nice thing about TinyPtrVector is that sizeof(TinyPtrVector)
is sizeof(void*) through bitstealing, which you can’t achieve with an arbitrary
T.
> 
> Right, it won't be as good the Ptr version for anything sizeof >= 8,
but we could fairly blindly move SmallVector with N=0 over to it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180623/00763efa/attachment.html>