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

Chris Lattner via llvm-dev llvm-dev at lists.llvm.org
Sat Jun 23 10:14:04 PDT 2018

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


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

More information about the llvm-dev mailing list