From d3c5bebcb52a67cb06e7ab303eaf45f230c08b60 Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Fri, 11 Apr 2014 16:32:51 +0100 Subject: Avoid allocating OatFile::OatClass on the heap. Avoid allocating a BitVector for OatFile::OatClass::bitmap_ with kOatClassSomeCompiled methods. That makes the OatClass copy-constructible as it doesn't own any memory. We use that in OatFile::OatDexFile::GetOatClass() to return the result by value thus avoiding one or two heap allocations per call. Change-Id: Ic7098109028a5b49e39ef626f877de86e732ed18 --- runtime/base/bit_vector.cc | 47 +++++++++++++++++++++-------------------- runtime/base/bit_vector.h | 9 +++++++- runtime/base/bit_vector_test.cc | 28 ++++++++++++------------ 3 files changed, 46 insertions(+), 38 deletions(-) (limited to 'runtime/base') diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc index 590835e..d8ef962 100644 --- a/runtime/base/bit_vector.cc +++ b/runtime/base/bit_vector.cc @@ -65,8 +65,7 @@ bool BitVector::IsBitSet(uint32_t num) const { return false; } - uint32_t val = storage_[num >> 5] & check_masks[num & 0x1f]; - return (val != 0); + return IsBitSet(storage_, num); } // Mark all bits bit as "clear". @@ -213,27 +212,10 @@ uint32_t BitVector::NumSetBits() const { return count; } -// Count the number of bits that are set up through and including num. -uint32_t BitVector::NumSetBits(uint32_t num) const { - DCHECK_LT(num, storage_size_ * sizeof(*storage_) * 8); - uint32_t last_word = num >> 5; - uint32_t partial_word_bits = num & 0x1f; - - // partial_word_bits | # | | | partial_word_mask - // 00000 | 0 | 0xffffffff >> (31 - 0) | (1 << (0 + 1)) - 1 | 0x00000001 - // 00001 | 1 | 0xffffffff >> (31 - 1) | (1 << (1 + 1)) - 1 | 0x00000003 - // 00010 | 2 | 0xffffffff >> (31 - 2) | (1 << (2 + 1)) - 1 | 0x00000007 - // ..... | - // 11110 | 30 | 0xffffffff >> (31 - 30) | (1 << (30 + 1)) - 1 | 0x7fffffff - // 11111 | 31 | 0xffffffff >> (31 - 31) | last_full_word++ | 0xffffffff - uint32_t partial_word_mask = 0xffffffff >> (0x1f - partial_word_bits); - - uint32_t count = 0; - for (uint32_t word = 0; word < last_word; word++) { - count += __builtin_popcount(storage_[word]); - } - count += __builtin_popcount(storage_[last_word] & partial_word_mask); - return count; +// Count the number of bits that are set in range [0, end). +uint32_t BitVector::NumSetBits(uint32_t end) const { + DCHECK_LE(end, storage_size_ * sizeof(*storage_) * 8); + return NumSetBits(storage_, end); } BitVector::Iterator* BitVector::GetIterator() const { @@ -327,4 +309,23 @@ void BitVector::Copy(const BitVector *src) { } } +bool BitVector::IsBitSet(const uint32_t* storage, uint32_t num) { + uint32_t val = storage[num >> 5] & check_masks[num & 0x1f]; + return (val != 0); +} + +uint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) { + uint32_t word_end = end >> 5; + uint32_t partial_word_bits = end & 0x1f; + + uint32_t count = 0u; + for (uint32_t word = 0u; word < word_end; word++) { + count += __builtin_popcount(storage[word]); + } + if (partial_word_bits != 0u) { + count += __builtin_popcount(storage[word_end] & ~(0xffffffffu << partial_word_bits)); + } + return count; +} + } // namespace art diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h index c8f285e..a496dbd 100644 --- a/runtime/base/bit_vector.h +++ b/runtime/base/bit_vector.h @@ -119,7 +119,9 @@ class BitVector { bool SameBitsSet(const BitVector *src); uint32_t NumSetBits() const; - uint32_t NumSetBits(uint32_t num) const; + + // Number of bits set in range [0, end). + uint32_t NumSetBits(uint32_t end) const; Iterator* GetIterator() const; @@ -135,6 +137,11 @@ class BitVector { */ int GetHighestBitSet() const; + // Is bit set in storage. (No range check.) + static bool IsBitSet(const uint32_t* storage, uint32_t num); + // Number of bits set in range [0, end) in storage. (No range check.) + static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); + private: Allocator* const allocator_; const bool expandable_; // expand bitmap if we run out? diff --git a/runtime/base/bit_vector_test.cc b/runtime/base/bit_vector_test.cc index a67fb33..2ff55cb 100644 --- a/runtime/base/bit_vector_test.cc +++ b/runtime/base/bit_vector_test.cc @@ -29,8 +29,8 @@ TEST(BitVector, Test) { EXPECT_FALSE(bv.IsExpandable()); EXPECT_EQ(0U, bv.NumSetBits()); - EXPECT_EQ(0U, bv.NumSetBits(0)); - EXPECT_EQ(0U, bv.NumSetBits(kBits - 1)); + EXPECT_EQ(0U, bv.NumSetBits(1)); + EXPECT_EQ(0U, bv.NumSetBits(kBits)); for (size_t i = 0; i < kBits; i++) { EXPECT_FALSE(bv.IsBitSet(i)); } @@ -46,8 +46,8 @@ TEST(BitVector, Test) { bv.SetBit(0); bv.SetBit(kBits - 1); EXPECT_EQ(2U, bv.NumSetBits()); - EXPECT_EQ(1U, bv.NumSetBits(0)); - EXPECT_EQ(2U, bv.NumSetBits(kBits - 1)); + EXPECT_EQ(1U, bv.NumSetBits(1)); + EXPECT_EQ(2U, bv.NumSetBits(kBits)); EXPECT_TRUE(bv.IsBitSet(0)); for (size_t i = 1; i < kBits - 1; i++) { EXPECT_FALSE(bv.IsBitSet(i)); @@ -98,25 +98,25 @@ TEST(BitVector, NoopAllocator) { EXPECT_EQ(0x00010001U, bv.GetRawStorageWord(1)); EXPECT_EQ(4U, bv.NumSetBits()); - EXPECT_EQ(0U, bv.NumSetBits(0)); + EXPECT_EQ(0U, bv.NumSetBits(1)); - EXPECT_EQ(0U, bv.NumSetBits(7)); - EXPECT_EQ(1U, bv.NumSetBits(8)); + EXPECT_EQ(0U, bv.NumSetBits(8)); EXPECT_EQ(1U, bv.NumSetBits(9)); + EXPECT_EQ(1U, bv.NumSetBits(10)); - EXPECT_EQ(1U, bv.NumSetBits(15)); - EXPECT_EQ(2U, bv.NumSetBits(16)); + EXPECT_EQ(1U, bv.NumSetBits(16)); EXPECT_EQ(2U, bv.NumSetBits(17)); + EXPECT_EQ(2U, bv.NumSetBits(18)); - EXPECT_EQ(2U, bv.NumSetBits(31)); - EXPECT_EQ(3U, bv.NumSetBits(32)); + EXPECT_EQ(2U, bv.NumSetBits(32)); EXPECT_EQ(3U, bv.NumSetBits(33)); + EXPECT_EQ(3U, bv.NumSetBits(34)); - EXPECT_EQ(3U, bv.NumSetBits(47)); - EXPECT_EQ(4U, bv.NumSetBits(48)); + EXPECT_EQ(3U, bv.NumSetBits(48)); EXPECT_EQ(4U, bv.NumSetBits(49)); + EXPECT_EQ(4U, bv.NumSetBits(50)); - EXPECT_EQ(4U, bv.NumSetBits(63)); + EXPECT_EQ(4U, bv.NumSetBits(64)); } TEST(BitVector, SetInitialBits) { -- cgit v1.1