From 6b17defc455a4b8fb0a57dd23ccdcc4edba91ac5 Mon Sep 17 00:00:00 2001 From: Nathan Bronson Date: Fri, 23 Oct 2015 19:48:25 -0700 Subject: [PATCH] fix AtomicUnorderedInsertMap load factor computation Summary: AtomicUnorderedInsertMap's constructor takes a maxLoadFactor argument, which is given its default argument of 0.8f in all of our code. The clipping function that was supposed to prevent load factors greater than one was inverted, resulting in all of our code using a maxLoadFactor of 1 instead of 0.8. This diff fixes the computation, as well as changing all of the use sites so that the actual memory allocated by existing clients does not change. Reviewed By: yfeldblum Differential Revision: D2575238 fb-gh-sync-id: bb9dd8de53114236b259631d175d62af098391cf --- folly/AtomicUnorderedMap.h | 2 +- folly/test/AtomicUnorderedMapTest.cpp | 20 ++++++++++++++++++++ 2 files changed, 21 insertions(+), 1 deletion(-) diff --git a/folly/AtomicUnorderedMap.h b/folly/AtomicUnorderedMap.h index 941905ef..4c0afb68 100644 --- a/folly/AtomicUnorderedMap.h +++ b/folly/AtomicUnorderedMap.h @@ -210,7 +210,7 @@ struct AtomicUnorderedInsertMap { const Allocator& alloc = Allocator()) : allocator_(alloc) { - size_t capacity = maxSize / std::max(1.0f, maxLoadFactor) + 128; + size_t capacity = maxSize / std::min(1.0f, maxLoadFactor) + 128; size_t avail = size_t{1} << (8 * sizeof(IndexType) - 2); if (capacity > avail && maxSize < avail) { // we'll do our best diff --git a/folly/test/AtomicUnorderedMapTest.cpp b/folly/test/AtomicUnorderedMapTest.cpp index 5d4e5a39..46a97b53 100644 --- a/folly/test/AtomicUnorderedMapTest.cpp +++ b/folly/test/AtomicUnorderedMapTest.cpp @@ -134,6 +134,26 @@ TYPED_TEST(AtomicUnorderedInsertMapTest, basic) { EXPECT_TRUE(a != b); } +TEST(AtomicUnorderedInsertMap, load_factor) { + AtomicUnorderedInsertMap m(5000, 0.5f); + + // we should be able to put in much more than 5000 things because of + // our load factor request + for (int i = 0; i < 10000; ++i) { + m.emplace(i, true); + } +} + +TEST(AtomicUnorderedInsertMap, capacity_exceeded) { + AtomicUnorderedInsertMap m(5000, 1.0f); + + EXPECT_THROW({ + for (int i = 0; i < 6000; ++i) { + m.emplace(i, false); + } + }, std::bad_alloc); +} + TYPED_TEST(AtomicUnorderedInsertMapTest, value_mutation) { UIM, TypeParam> m(100); -- 2.34.1