Page MenuHomePhabricator

Fix DenseMap::reserve(): the formula was wrong

Authored by mehdi_amini on Mar 22 2016, 2:01 AM.



Just running the loop in the unittests for a few more iterations
(till 48) exhibit that the condition on the limit was not handled
properly in r263522.
Rewrite the test to use a class to count move/copies that happens
when inserting into the map.
Also take the opportunity to refactor the logic to compute the
number of buckets required for a given number of entries in the map.
Use this when constructing a DenseMap with a desired size given to
the constructor (and add a tests for this).

Diff Detail

Event Timeline

mehdi_amini retitled this revision from to Fix DenseMap::reserve(): the formula was wrong.
mehdi_amini updated this object.
mehdi_amini added a reviewer: dblaikie.
mehdi_amini added a subscriber: llvm-commits.
dblaikie added inline comments.Mar 22 2016, 8:36 AM

If both the ctor and reserve now use common code, might not be necessary to test all parts of that code through both access points.


Do we need to test it for all these values? Or could we be a bit more specific? (I worry about shotgun testing like this - hard to maintain (because it's not clear what cases it's testing) & can add time to our test runs, make them harder to debug (because they're doing so much unintended/unnecessary work), etc)


You could use '0u' for the unsigned 0 literal rather than a cast


Same question here

escha added a subscriber: escha.Mar 22 2016, 9:04 AM

Thanks for catching this off-by-one.

Try to improve tests. Also add one test for initializing with a pair of iterators.

dblaikie added inline comments.Mar 22 2016, 11:04 AM

I /think/ you can drop the ArrayRef<int>() here and just write:

for (auto Size : {1, 2, 48, 66})


Also, why 1 and 2? (maybe it's the right thing, just not clear to me - I take it your intent was that 1 is a boundary case, 2 is an "average" case below the minimum size, and 66 is an average case above the minimum size?)


It's not really random though. Perhaps "Ensure that when initializing with a range larger than the default minimum, reallocation doesn't occur"? (maybe that could be the test header comment? It's specifically not just about using an iterator range, but a range larger than the default number of buckets, right?)

Also, do we do this even when the iterators aren't random access? (I'd be suprrised if we paid the extra O(n) scan to find the size of the range first) Not to suggest you need to test that too - but maybe worth a comment that this test is only about random access iterators, where computing the delta between two iterators is O(1)

Though this isn't quite the test I had in mind/was suggesting (perhaps it wasn't your intent to implement the test I was suggesting - sorry for the confusion, if that's the case)

I was suggesting demonstrating that the default minimum size is what we're relying on in other tests: default construct a DenseMap, add up to the default minimum, check that nothing got reallocated/moved. Then add one more element and demonstrate that reallocation/moving did happen. That way, if someone changes the default minimum that test will fail - and we can include some breadcrumbs about how to update other tests. "WARNING: IF YOU UPDATE THIS TEST, UPDATE SOME OTHER TESTS TOO" or something

Improve tests

dblaikie accepted this revision.Mar 24 2016, 11:34 AM
dblaikie edited edge metadata.

I'm a bit turned around with all these related/similar reviews, but I think this is in a good state now.

Thanks for your patience.


I wouldn't expect to see this formula in the test case (since buckets are an implementation detail of the data structure) - maybe just hard code it to 47 as the max initial entries?

This revision is now accepted and ready to land.Mar 24 2016, 11:34 AM
mehdi_amini added inline comments.Mar 24 2016, 11:46 AM

I'm not sure hardcoding the number would be better: the formula would still be in the test, but hidden in the relationship between the 64 and 47. And I'd probably add a comment to explain where the 47 comes from, and to do so I'd expose the formula.
I may also remove the const int ExpectedInitialBucketCount, but then I would have to reintroduce it in the comment to explain where the 47 comes...

If you're okay with me removing the default allocation of 64, I'll totally remove this test anyway in the next patch.


1: boundary
2: small power of two
66: "random pick above 64 but not too big to not make the test too slow"

mehdi_amini closed this revision.Mar 25 2016, 5:38 PM