From c742b72354a84958b6a061755249822eeef87d06 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 10 Jan 2018 11:46:09 -0800 Subject: Changes imported from Abseil "staging" branch: - f679f7de2957ac4dca0a862d04f1165d2f503525 Merge GitHub PR #78: Fix typo in thread_identity.h by Derek Mauro - 369cbefc9ebb8503e3c25b1516c856dab3bed7ac Minor refactor of operator-(uint128). by Alex Strelnikov - fba0f8c33b051d90936ad0fcaa4bea83f554bf8d Merge GitHub PR #75: Fix typo in per_thread_tls.h by Derek Mauro - 76d5d25a54ab93c1ea3bc74b5a28ba335b0f2bab Implement InlinedVector::shrink_to_fit() method. by Abseil Team GitOrigin-RevId: f679f7de2957ac4dca0a862d04f1165d2f503525 Change-Id: I03b39fdbd70c00a455d98d949d413dd7c8019578 --- absl/container/inlined_vector.h | 36 ++++++++++++++++ absl/container/inlined_vector_test.cc | 77 +++++++++++++++++++++++++++++++++++ absl/numeric/int128.h | 11 ++--- 3 files changed, 117 insertions(+), 7 deletions(-) (limited to 'absl') diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 4bf9c18adec4..feba87b58217 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -573,6 +573,42 @@ class InlinedVector { } } + // InlinedVector::shrink_to_fit() + // + // Reduces memory usage by freeing unused memory. + // After this call `capacity()` will be equal to `max(N, size())`. + // + // If `size() <= N` and the elements are currently stored on the heap, they + // will be moved to the inlined storage and the heap memory deallocated. + // If `size() > N` and `size() < capacity()` the elements will be moved to + // a reallocated storage on heap. + void shrink_to_fit() { + const auto s = size(); + if (!allocated() || s == capacity()) { + // There's nothing to deallocate. + return; + } + + if (s <= N) { + // Move the elements to the inlined storage. + // We have to do this using a temporary, because inlined_storage and + // allocation_storage are in a union field. + auto temp = std::move(*this); + assign(std::make_move_iterator(temp.begin()), + std::make_move_iterator(temp.end())); + return; + } + + // Reallocate storage and move elements. + // We can't simply use the same approach as above, because assign() would + // call into reserve() internally and reserve larger capacity than we need. + Allocation new_allocation(allocator(), s); + UninitializedCopy(std::make_move_iterator(allocated_space()), + std::make_move_iterator(allocated_space() + s), + new_allocation.buffer()); + ResetAllocation(new_allocation, s); + } + // InlinedVector::swap() // // Swaps the contents of this inlined vector with the contents of `other`. diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc index 8527ba1aa008..0e39855b3066 100644 --- a/absl/container/inlined_vector_test.cc +++ b/absl/container/inlined_vector_test.cc @@ -407,6 +407,69 @@ TEST(InlinedVectorTest, EmplaceBack) { EXPECT_EQ(allocated_element.second, 1729); } +TEST(InlinedVectorTest, ShrinkToFitGrowingVector) { + absl::InlinedVector, 1> v; + + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 1); + + v.emplace_back("answer", 42); + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 1); + + v.emplace_back("taxicab", 1729); + EXPECT_GE(v.capacity(), 2); + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 2); + + v.reserve(100); + EXPECT_GE(v.capacity(), 100); + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 2); +} + +TEST(InlinedVectorTest, ShrinkToFitEdgeCases) { + { + absl::InlinedVector, 1> v; + v.emplace_back("answer", 42); + v.emplace_back("taxicab", 1729); + EXPECT_GE(v.capacity(), 2); + v.pop_back(); + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 1); + EXPECT_EQ(v[0].first, "answer"); + EXPECT_EQ(v[0].second, 42); + } + + { + absl::InlinedVector v(100); + v.resize(0); + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 2); // inlined capacity + } + + { + absl::InlinedVector v(100); + v.resize(1); + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 2); // inlined capacity + } + + { + absl::InlinedVector v(100); + v.resize(2); + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 2); + } + + { + absl::InlinedVector v(100); + v.resize(3); + v.shrink_to_fit(); + EXPECT_EQ(v.capacity(), 3); + } +} + TEST(IntVec, Insert) { for (int len = 0; len < 20; len++) { for (int pos = 0; pos <= len; pos++) { @@ -1589,6 +1652,20 @@ TEST(AllocatorSupportTest, CountAllocations) { AllocVec v3(std::move(v), alloc3); EXPECT_THAT(allocated3, v3.size() * sizeof(int)); } + EXPECT_EQ(allocated, 0); + { + // Test shrink_to_fit deallocations. + AllocVec v(8, 2, alloc); + EXPECT_EQ(allocated, 8 * sizeof(int)); + v.resize(5); + EXPECT_EQ(allocated, 8 * sizeof(int)); + v.shrink_to_fit(); + EXPECT_EQ(allocated, 5 * sizeof(int)); + v.resize(4); + EXPECT_EQ(allocated, 5 * sizeof(int)); + v.shrink_to_fit(); + EXPECT_EQ(allocated, 0); + } } TEST(AllocatorSupportTest, SwapBothAllocated) { diff --git a/absl/numeric/int128.h b/absl/numeric/int128.h index f42a4aa3788e..a204ac4d9c3f 100644 --- a/absl/numeric/int128.h +++ b/absl/numeric/int128.h @@ -460,13 +460,10 @@ inline bool operator>=(uint128 lhs, uint128 rhs) { // Unary operators. inline uint128 operator-(uint128 val) { - const uint64_t hi_flip = ~Uint128High64(val); - const uint64_t lo_flip = ~Uint128Low64(val); - const uint64_t lo_add = lo_flip + 1; - if (lo_add < lo_flip) { - return MakeUint128(hi_flip + 1, lo_add); - } - return MakeUint128(hi_flip, lo_add); + uint64_t hi = ~Uint128High64(val); + uint64_t lo = ~Uint128Low64(val) + 1; + if (lo == 0) ++hi; // carry + return MakeUint128(hi, lo); } inline bool operator!(uint128 val) { -- cgit 1.4.1