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