<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>escha@apple.com<br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Tuesday, March 15, 2016 5:17:46 PM<br><b>Subject: </b>Re: [llvm-dev] RFC: DenseMap grow() slowness<br><br>
<br class=""><div><blockquote class=""><div class="">On Mar 15, 2016, at 3:15 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="" target="_blank">hfinkel@anl.gov</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><br class="Apple-interchange-newline"><hr id="zwchr" style="font-family: arial,helvetica,sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;" class=""><b class="">From:<span class="Apple-converted-space"> </span></b>"via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class=""><b class="">To:<span class="Apple-converted-space"> </span></b>"llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class=""><b class="">Sent:<span class="Apple-converted-space"> </span></b>Tuesday, March 15, 2016 5:07:29 PM<br class=""><b class="">Subject:<span class="Apple-converted-space"> </span></b>[llvm-dev] RFC: DenseMap grow() slowness<br class=""><br class="">There’s a few passes in LLVM that make heavy use of a big DenseMap, one that potentially gets filled with up to 1 entry for each instruction in the function. EarlyCSE is the best example, but Reassociate and MachineCSE have this to some degree as well (there might be others?). To put it simply: at least in my profile, EarlyCSE spends ~1/5 of its time growing DenseMaps. This is kind of… bad.<div class=""><br class=""></div><div class="">grow() is inherently slow because it needs to rehash and reinsert everything. This means growing a DenseMap costs much, much more than growing, for example, a vector. I talked about this with a few people and here are some possibilities we’ve come up with to improve this (some of which probably aren’t what we want):</div><div class=""><br class=""></div><div class="">1. Use a map that doesn’t require rehashing and reinsertion to grow. Chaining lets you do this, but std::unordered_map is probably so much slower than DenseMap we’d lose more than we gain.</div><div class="">2. Include the hash code in the map so that we don’t have to rehash. 32 bits more per entry (or whatever), and it might not help that much, since we still have to do the whole reinsertion routine.</div><div class="">3. Pre-calculate an estimate as to the map size we need. For example, in EarlyCSE, this is possibly gross overestimate of size needed:</div><div class=""><br class=""></div><div class=""><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="" style="color: rgb(187, 44, 162);">unsigned</span><span class="Apple-converted-space"> </span>InstCount =<span class="Apple-converted-space"> </span><span class="" style="color: rgb(39, 42, 216);">0</span>;</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="Apple-converted-space"> </span><span class="" style="color: rgb(187, 44, 162);">unsigned</span><span class="Apple-converted-space"> </span>LoadCount =<span class="Apple-converted-space"> </span><span class="" style="color: rgb(39, 42, 216);">0</span>;</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="Apple-converted-space"> </span><span class="" style="color: rgb(187, 44, 162);">unsigned</span><span class="Apple-converted-space"> </span>CallCount =<span class="Apple-converted-space"> </span><span class="" style="color: rgb(39, 42, 216);">0</span>;</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="Apple-converted-space"> </span><span class="" style="color: rgb(187, 44, 162);">for</span><span class="Apple-converted-space"> </span>(<span class="" style="color: rgb(79, 129, 135);">inst_iterator</span><span class="Apple-converted-space"> </span>FI =<span class="Apple-converted-space"> </span><span class="" style="color: rgb(49, 89, 93);">inst_begin</span>(<span class="" style="color: rgb(79, 129, 135);">F</span>), FE =<span class="Apple-converted-space"> </span><span class="" style="color: rgb(49, 89, 93);">inst_end</span>(<span class="" style="color: rgb(79, 129, 135);">F</span>); FI != FE; ++FI) {</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(49, 89, 93);"><span class="" style=""> <span class="Apple-converted-space"> </span></span><span class="" style="color: rgb(187, 44, 162);">if</span><span class="" style=""><span class="Apple-converted-space"> </span>(FI-></span>mayReadOrWriteMemory<span class="" style="">())</span></div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> ++LoadCount;</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="Apple-converted-space"> </span><span class="" style="color: rgb(187, 44, 162);">else</span><span class="Apple-converted-space"> </span><span class="" style="color: rgb(187, 44, 162);">if</span><span class="Apple-converted-space"> </span>(<span class="" style="color: rgb(49, 89, 93);">isa</span><<span class="" style="color: rgb(79, 129, 135);">CallInst</span>>(*FI))</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> ++CallCount;</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="Apple-converted-space"> </span><span class="" style="color: rgb(187, 44, 162);">else</span></div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> ++InstCount;</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> }</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="Apple-converted-space"> </span><span class="" style="color: rgb(79, 129, 135);">AvailableValues</span>.<span class="" style="color: rgb(61, 29, 129);">resize</span>(InstCount);</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="Apple-converted-space"> </span><span class="" style="color: rgb(79, 129, 135);">AvailableLoads</span>.<span class="" style="color: rgb(61, 29, 129);">resize</span>(LoadCount);</div><div class="" style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;"> <span class="Apple-converted-space"> </span><span class="" style="color: rgb(79, 129, 135);">AvailableCalls</span>.<span class="" style="color: rgb(61, 29, 129);">resize</span>(CallCount);</div></div><div class=""><br class=""></div><div id="DWT7802" class="">But it does the job, and saves ~20% of time in EarlyCSE on my profiles. Yes, iterating over the entire function is way cheaper than grow(). Downsides are that while it’s still bounded by function size, it could end up allocating a good bit more depending on — in EarlyCSE’s case — the control flow/dominator structure.</div></blockquote><br style="font-family: arial,helvetica,sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: arial,helvetica,sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">This last option makes perfect sense to me. One thing we might be able to do regarding the extra memory overhead is, instead of actually resizing up front, to start with a relatively small map, but use the function size to set the growth factor so that we grow only a small number of times (say once) in the worst case.</span></div></blockquote><br class=""></div><div>Growing fewer times doesn’t actually help much from what I can tell, because the largest grow() always dominates the cost of the others.</div><div><br class=""></div><div>For example, if you start with 8 buckets, and you end up needing 512 buckets, and you grow 2x at a time:</div><div><br class=""></div><div>8, 16, 32, 64, 128, 256, 512</div><div><br class=""></div><div>The final grow() costs as much as all the others combined. So if you grow 4x at a time:</div><div><br class=""></div><div>8, 32, 128, 512</div><div><br class=""></div><div id="DWT7881">you don’t actually save much; I think the gain is probably bounded at a factor of 2.</div></blockquote><br>Understood; but that wasn't what I had in mind exactly. What about if we added a threshold and a target size (set as above), so that the growth factors would do this:<br><br>8, 16, 32, 64, 128, ..., threshold (I suppose this will be big), target size<br><br>i.e. once you hit some threshold, we assume the map will be large, and we jump right to your precalculated target size? Would that bring the benefits while mitigating much of the extra memory overhead?<br><br> -Hal<br><br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div></div><div><br class=""></div><div>—escha</div><div><br class=""></div></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>