[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.
-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>
More information about the llvm-dev
mailing list