<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Jun 22, 2018, at 15:18, Reid Kleckner <<a href="mailto:rnk@google.com" class="">rnk@google.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><div class="gmail_quote"><div dir="ltr" class="">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" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div dir="auto" class=""><div class=""><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction: ltr;"><blockquote type="cite" class=""><div class=""><div class="">Out of curiosity, what brings this up?<br class=""></div></div></blockquote><div class="gmail-m_-6926382607035558243AppleOriginalContents" style="direction: ltr;"><br class=""></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 class=""></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 class=""></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 class=""><br class=""></div><div class="">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 class=""></div></div></div></div></blockquote><div><br class=""></div><div>Good point, there are two separable changes here and only the union part is likely to have compile-time slowdowns. I threw together <a href="https://reviews.llvm.org/D48518" class="">https://reviews.llvm.org/D48518</a> (currently building with ASan to run check-llvm) and the surely uncontroversial <a href="https://reviews.llvm.org/D48516" class="">https://reviews.llvm.org/D48516</a>.</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><div class="gmail_quote"><div class="">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></div></div></blockquote><div><br class=""></div><div>Interesting idea... and then audit current instances to drop the size argument.</div><div><br class=""></div><div>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.</div><div><br class=""></div><div>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.</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><div class="gmail_quote"><div class="">---</div><div class=""><br class=""></div><div class="">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></div></blockquote></div><br class=""></body></html>