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

> On Jun 22, 2018, at 15:18, Reid Kleckner <rnk at google.com> wrote:
> 
> On Thu, Jun 21, 2018 at 9:16 PM Duncan P. N. Exon Smith via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
wrote:
>> Out of curiosity, what brings this up?
> 
> I've noticed that Clang is using more stack recently (we're seeing
more crashes from template recursion; it seems the template recursion limit
needs to shrink), and somehow that train of thought led to this.
> 
> I share your skepticism that it will help stack usage much, but
SmallVector/SmallVectorImpl is so ubiquitous, it could help the heap a bit.  And
if it doesn’t hurt runtime performance in practice, there’s no reason to fork
the data structure.
> 
> If no one has measured before I might try it some time. 
> 
> I think it's important to keep begin(), end(), and indexing operations
branchless, so I'm not sure this pointer union is the best idea. I
haven't profiled, but that's my intuition. If you wanted to limit all
our vectors to 4 billion elements to save a pointer, I'd probably be fine
with that.
Good point, there are two separable changes here and only the union part is
likely to have compile-time slowdowns.  I threw together
https://reviews.llvm.org/D48518 <https://reviews.llvm.org/D48518>
(currently building with ASan to run check-llvm) and the surely uncontroversial
https://reviews.llvm.org/D48516 <https://reviews.llvm.org/D48516>.
> 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.

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.
> ---
> 
> Relatedly, there's a lot of work that can be done to tune DenseMap.
When the key and value pair is relatively large, we waste a lot of space on
empty table slots.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180623/6cbc7caf/attachment.html>

> On Jun 23, 2018, at 9:11 AM, Duncan P. N. Exon Smith <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?

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.

-Chris

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

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