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.
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):
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.
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.
3. Pre-calculate an estimate as to the map size we need. For example, in
EarlyCSE, this is possibly gross overestimate of size needed:
unsigned InstCount = 0;
unsigned LoadCount = 0;
unsigned CallCount = 0;
for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE; ++FI) {
if (FI->mayReadOrWriteMemory())
++LoadCount;
else if (isa<CallInst>(*FI))
++CallCount;
else
++InstCount;
}
AvailableValues.resize(InstCount);
AvailableLoads.resize(LoadCount);
AvailableCalls.resize(CallCount);
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.
Any thoughts on this, or other less ugly alternatives? I estimate that, at least
in our pass pipeline, we’re losing at least ~1% of total time to avoidable
DenseMap::grow() operations, which feels a little bit… unnecessary.
—escha
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/311b9cf4/attachment.html>
----- Original Message -----> From: "via llvm-dev" <llvm-dev at lists.llvm.org> > To: "llvm-dev" <llvm-dev at lists.llvm.org> > Sent: Tuesday, March 15, 2016 5:07:29 PM > Subject: [llvm-dev] RFC: DenseMap grow() slowness> 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.> 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):> 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. > 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. > 3. Pre-calculate an estimate as to the map size we need. For example, > in EarlyCSE, this is possibly gross overestimate of size needed:> unsigned InstCount = 0 ; > unsigned LoadCount = 0 ; > unsigned CallCount = 0 ; > for ( inst_iterator FI = inst_begin ( F ), FE = inst_end ( F ); FI !> FE; ++FI) { > if (FI-> mayReadOrWriteMemory ()) > ++LoadCount; > else if ( isa < CallInst >(*FI)) > ++CallCount; > else > ++InstCount; > } > AvailableValues . resize (InstCount); > AvailableLoads . resize (LoadCount); > AvailableCalls . resize (CallCount);> 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.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. -Hal> Any thoughts on this, or other less ugly alternatives? I estimate > that, at least in our pass pipeline, we’re losing at least ~1% of > total time to avoidable DenseMap::grow() operations, which feels a > little bit… unnecessary.> —escha > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/f2e3fbde/attachment.html>
> On Mar 15, 2016, at 3:15 PM, Hal Finkel <hfinkel at anl.gov> wrote: > > > From: "via llvm-dev" <llvm-dev at lists.llvm.org> > To: "llvm-dev" <llvm-dev at lists.llvm.org> > Sent: Tuesday, March 15, 2016 5:07:29 PM > Subject: [llvm-dev] RFC: DenseMap grow() slowness > > 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. > > 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): > > 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. > 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. > 3. Pre-calculate an estimate as to the map size we need. For example, in EarlyCSE, this is possibly gross overestimate of size needed: > > unsigned InstCount = 0; > unsigned LoadCount = 0; > unsigned CallCount = 0; > for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE; ++FI) { > if (FI->mayReadOrWriteMemory()) > ++LoadCount; > else if (isa<CallInst>(*FI)) > ++CallCount; > else > ++InstCount; > } > AvailableValues.resize(InstCount); > AvailableLoads.resize(LoadCount); > AvailableCalls.resize(CallCount); > > 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. > > 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.Growing fewer times doesn’t actually help much from what I can tell, because the largest grow() always dominates the cost of the others. For example, if you start with 8 buckets, and you end up needing 512 buckets, and you grow 2x at a time: 8, 16, 32, 64, 128, 256, 512 The final grow() costs as much as all the others combined. So if you grow 4x at a time: 8, 32, 128, 512 you don’t actually save much; I think the gain is probably bounded at a factor of 2. —escha -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/b63d8a0c/attachment.html>
Xinliang David Li via llvm-dev
2016-Mar-15 22:30 UTC
[llvm-dev] RFC: DenseMap grow() slowness
yes it makes sense. Avoid using DenseMap when the size of the map is expected to be large but can not be pre-determined. David On Tue, Mar 15, 2016 at 3:07 PM, via llvm-dev <llvm-dev at lists.llvm.org> wrote:> 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. > > 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): > > 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. > 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. > 3. Pre-calculate an estimate as to the map size we need. For example, in > EarlyCSE, this is possibly gross overestimate of size needed: > > unsigned InstCount = 0; > unsigned LoadCount = 0; > unsigned CallCount = 0; > for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE; > ++FI) { > if (FI->mayReadOrWriteMemory()) > ++LoadCount; > else if (isa<CallInst>(*FI)) > ++CallCount; > else > ++InstCount; > } > AvailableValues.resize(InstCount); > AvailableLoads.resize(LoadCount); > AvailableCalls.resize(CallCount); > > 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. > > Any thoughts on this, or other less ugly alternatives? I estimate that, at > least in our pass pipeline, we’re losing at least ~1% of total time to > avoidable DenseMap::grow() operations, which feels a little bit… > unnecessary. > > —escha > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/fcf514a4/attachment.html>
What should we use instead of DenseMap? —escha> On Mar 15, 2016, at 3:30 PM, Xinliang David Li <xinliangli at gmail.com> wrote: > > yes it makes sense. Avoid using DenseMap when the size of the map is expected to be large but can not be pre-determined. > > David > > On Tue, Mar 15, 2016 at 3:07 PM, via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > 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. > > 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): > > 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. > 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. > 3. Pre-calculate an estimate as to the map size we need. For example, in EarlyCSE, this is possibly gross overestimate of size needed: > > unsigned InstCount = 0; > unsigned LoadCount = 0; > unsigned CallCount = 0; > for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE; ++FI) { > if (FI->mayReadOrWriteMemory()) > ++LoadCount; > else if (isa<CallInst>(*FI)) > ++CallCount; > else > ++InstCount; > } > AvailableValues.resize(InstCount); > AvailableLoads.resize(LoadCount); > AvailableCalls.resize(CallCount); > > 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. > > Any thoughts on this, or other less ugly alternatives? I estimate that, at least in our pass pipeline, we’re losing at least ~1% of total time to avoidable DenseMap::grow() operations, which feels a little bit… unnecessary. > > —escha > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/a5487bd4/attachment-0001.html>
On 03/15/2016 03:07 PM, via llvm-dev wrote:> 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. > > 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): > > 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. > 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. > 3. Pre-calculate an estimate as to the map size we need. For example, > in EarlyCSE, this is possibly gross overestimate of size needed: > > unsigned InstCount = 0; > unsigned LoadCount = 0; > unsigned CallCount = 0; > for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE; ++FI) { > if(FI->mayReadOrWriteMemory()) > ++LoadCount; > else if (isa<CallInst>(*FI)) > ++CallCount; > else > ++InstCount; > } > AvailableValues.resize(InstCount); > AvailableLoads.resize(LoadCount); > AvailableCalls.resize(CallCount); > > 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. > > Any thoughts on this, or other less ugly alternatives? I estimate > that, at least in our pass pipeline, we’re losing at least ~1% of > total time to avoidable DenseMap::grow() operations, which feels a > little bit… unnecessary.Slightly OT, but it looks like the LoadValue (value type of the AvailableLoads structure) is relatively memory inefficient. At minimum, we could get rid of the IsAtomic space by using a tagged pointer. That would at least bring us down to a 128 bits (a nice power of two). That might help speed up some of the copying. p.s. Good find! Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/8d77967a/attachment.html>
Xinliang David Li via llvm-dev
2016-Mar-15 23:21 UTC
[llvm-dev] RFC: DenseMap grow() slowness
On Tue, Mar 15, 2016 at 3:07 PM, via llvm-dev <llvm-dev at lists.llvm.org> wrote:> 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. > > 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): > > 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. > 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. >Another choice is to implement DenseMap using segmented array (of buckets) -- the segment size is fixed so finding a bucket using bucket number can be pretty cheap : segment number + segment offset. With this, there is no need for resizing. David> 3. Pre-calculate an estimate as to the map size we need. For example, in > EarlyCSE, this is possibly gross overestimate of size needed: > > unsigned InstCount = 0; > unsigned LoadCount = 0; > unsigned CallCount = 0; > for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE; > ++FI) { > if (FI->mayReadOrWriteMemory()) > ++LoadCount; > else if (isa<CallInst>(*FI)) > ++CallCount; > else > ++InstCount; > } > AvailableValues.resize(InstCount); > AvailableLoads.resize(LoadCount); > AvailableCalls.resize(CallCount); > > 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. > > Any thoughts on this, or other less ugly alternatives? I estimate that, at > least in our pass pipeline, we’re losing at least ~1% of total time to > avoidable DenseMap::grow() operations, which feels a little bit… > unnecessary. > > —escha > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/b30bc501/attachment.html>
> On Mar 15, 2016, at 4:09 PM, Philip Reames <listmail at philipreames.com> wrote: > > > > On 03/15/2016 03:07 PM, via llvm-dev wrote: >> 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. >> >> 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): >> >> 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. >> 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. >> 3. Pre-calculate an estimate as to the map size we need. For example, in EarlyCSE, this is possibly gross overestimate of size needed: >> >> unsigned InstCount = 0; >> unsigned LoadCount = 0; >> unsigned CallCount = 0; >> for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE; ++FI) { >> if (FI->mayReadOrWriteMemory()) >> ++LoadCount; >> else if (isa<CallInst>(*FI)) >> ++CallCount; >> else >> ++InstCount; >> } >> AvailableValues.resize(InstCount); >> AvailableLoads.resize(LoadCount); >> AvailableCalls.resize(CallCount); >> >> 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. >> >> Any thoughts on this, or other less ugly alternatives? I estimate that, at least in our pass pipeline, we’re losing at least ~1% of total time to avoidable DenseMap::grow() operations, which feels a little bit… unnecessary. > > Slightly OT, but it looks like the LoadValue (value type of the AvailableLoads structure) is relatively memory inefficient. At minimum, we could get rid of the IsAtomic space by using a tagged pointer. That would at least bring us down to a 128 bits (a nice power of two). That might help speed up some of the copying.Just to note, it looks like I was testing on a somewhat older LLVM version that didn’t have LoadValue at all, so my guess is this means it’s even -worse- in trunk. —escha -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/a5d95881/attachment.html>