Page MenuHomePhabricator

DenseMap: make .resize() do the intuitive thing

Authored by escha on Mar 14 2016, 11:42 AM.



In some places, like InstCombine, we resize a DenseMap to fit the elements we intend to put in it, then insert those elements (to avoid continual reallocations as it grows). But .resize(foo) doesn't actually do what people think; it resizes to foo buckets (which is really an implementation detail the user of DenseMap probably shouldn't care about), not the space required to fit foo elements. DenseMap grows if 3/4 of its buckets are full, so this actually causes one forced reallocation every time instead of avoiding a reallocation.

This patch makes .resize(foo) do the intuitive thing: it grows to the size necessary to fit foo elements without new allocations.

Diff Detail


Event Timeline

escha updated this revision to Diff 50619.Mar 14 2016, 11:42 AM
escha retitled this revision from to DenseMap: make .resize() do the intuitive thing.
escha updated this object.
escha added reviewers: bogner, resistor.
escha set the repository for this revision to rL LLVM.
escha added a subscriber: llvm-commits.
escha updated this revision to Diff 50637.Mar 14 2016, 1:31 PM

Added a test to make sure that resizing is enough to insert N elements without reallocation for a variety of sizes.

I also looked quickly over the uses and none of the uses seem to be already-compensating for this.

grimar added a subscriber: grimar.Mar 15 2016, 1:15 AM
escha accepted this revision.Mar 15 2016, 11:42 AM
escha added a reviewer: escha.
This revision is now accepted and ready to land.Mar 15 2016, 11:42 AM
escha closed this revision.Mar 15 2016, 11:42 AM