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

[Duncan P. N. Exon Smith via llvm-dev]

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