<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div><span></span></div><div><br><div class="AppleOriginalContents" style="direction: ltr;"><br><blockquote type="cite"><div>On Jun 21, 2018, at 18:38, Chris Lattner <<a href="mailto:clattner@nondot.org">clattner@nondot.org</a>> wrote:</div><br class="Apple-interchange-newline"><div><div><br class=""><br class=""><blockquote type="cite" class="">On Jun 21, 2018, at 9:52 AM, Duncan P. N. Exon Smith via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br class=""><br class="">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 class=""></blockquote><br class="">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 class=""></div></div></blockquote><div class="AppleOriginalContents" style="direction: ltr;"><br></div><div class="AppleOriginalContents" 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><br><blockquote type="cite"><div><div>Out of curiosity, what brings this up?<br class=""></div></div></blockquote><div class="AppleOriginalContents" style="direction: ltr;"><br></div><div class="AppleOriginalContents" 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="AppleOriginalContents" style="direction: ltr;"><br></div><div class="AppleOriginalContents" 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="AppleOriginalContents" style="direction: ltr;"><br></div><div class="AppleOriginalContents" style="direction: ltr;">If no one has measured before I might try it some time. </div><br><blockquote type="cite"><div><div>-Chris<br class=""><br class=""><br class=""><blockquote type="cite" class=""><br class="">The current scheme works out to something like this:<br class="">```<br class="">template <class T, size_t SmallCapacity><br class="">struct SmallVector {<br class=""> T *BeginX, *EndX, *CapacityX;<br class=""> T Small[SmallCapacity];<br class=""><br class=""> bool isSmall() const { return BeginX == Small; }<br class=""> T *begin() { return BeginX; }<br class=""> T *end() { return EndX; }<br class=""> size_t size() const { return EndX - BeginX; }<br class=""> size_t capacity() const { return CapacityX - BeginX; }<br class="">};<br class="">```<br class=""><br class="">In the past I used something more like:<br class="">```<br class="">template <class T, size_t SmallCapacity><br class="">struct SmallVector2 {<br class=""> unsigned Size;<br class=""> unsigned Capacity;<br class=""> union {<br class=""> T Small[SmallCapacity];<br class=""> T *Large;<br class=""> };<br class=""><br class=""> bool isSmall() const { return Capacity == SmallCapacity; } // Or a bit shaved off of Capacity.<br class=""> T *begin() { return isSmall() ? Small : Large; }<br class=""> T *end() { return begin() + Size; }<br class=""> size_t size() const { return Size; }<br class=""> size_t capacity() const { return Capacity; }<br class="">};<br class="">```<br class=""><br class="">I'm curious whether this scheme would be really be slower in practice (as a complete replacement for `SmallVector` in ADT). I wonder, has anyone profiled something like this before? If so, in what context? on what workloads?<br class=""><br class="">Duncan<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""></blockquote><br class=""></div></div></blockquote></div><br></div></body></html>