<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Thu, Jun 21, 2018 at 9:16 PM Duncan P. N. Exon Smith via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div><span></span></div><div><br><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr"><br><blockquote type="cite"><div>On Jun 21, 2018, at 18:38, Chris Lattner <<a href="mailto:clattner@nondot.org" target="_blank">clattner@nondot.org</a>> wrote:</div><br class="gmail-m_-6926382607035558243Apple-interchange-newline"><div><div><br><br><blockquote type="cite">On Jun 21, 2018, at 9:52 AM, Duncan P. N. Exon Smith via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br><br>I've been curious for a while whether SmallVectors have the right speed/memory tradeoff.  It would be straightforward to shave off a couple of pointers (1 pointer/4B on 32-bit; 2 pointers/16B on 64-bit) if users could afford to test for small-mode vs. large-mode.<br></blockquote><br>Something like this could definitely work, but most smallvectors are on the stack.  They are intentionally used when sizeof(smallvector) isn’t important, so I don’t think this optimization will pay off.<br></div></div></blockquote><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr"><br></div><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr">For better or worse (mostly worse), there are a ton of SmallVector fields in data structures, including some even nested inside other SmallVectors (e.g., see the cleanup in r235229).  Often these data structures are heap-allocated.</div></div></div></div></blockquote><div><br></div><div>Yes, this is a huge problem. We seriously overuse SmallVector. I think in CodeViewDebug.cpp we had a DenseMap of a struct which had a SmallVector of structs that contained SmallVectors. It was silly.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr"><blockquote type="cite"><div><div>Out of curiosity, what brings this up?<br></div></div></blockquote><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr"><br></div><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr">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.</div><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr"><br></div><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr">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.</div><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr"><br></div><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction:ltr">If no one has measured before I might try it some time. </div></div></div></div></blockquote><div><br></div><div>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.<br><br>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.</div><div><br></div><div>---</div><div><br></div><div>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.</div></div></div>