[llvm-dev] RFC: Should SmallVectors be smaller?

Duncan P. N. Exon Smith via llvm-dev llvm-dev at lists.llvm.org
Sat Jun 23 11:27:13 PDT 2018



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


More information about the llvm-dev mailing list