ART: Implement a fixed size string dex cache
Previously, the string dex cache was dex_file->NumStringIds() size, and
@ruhler found that only ~1% of that cache was ever getting filled. Since
many of these string dex caches were previously 100,000+ indices in
length, we're wasting a few hundred KB per app by storing null pointers.
The intent of this project was to reduce the space the string dex cache
is using, while not regressing on time that much. This is the first of a
few CLs, which implements the new fixed size array and disables the
compiled code so it always goes slow path. In four other CLs, I
implemented a "medium path" that regresses from the previous "fast path"
only a bit in assembly in the entrypoints. @vmarko will introduce new
compiled code in the future so that we ultimately won't be regressing on
time at all. Overall, space savings have been confirmed as on the order
of 100 KB per application.
A 4-5% slow down in art-opt on Golem, and no noticeable slow down in the
interpreter. The opt slow down should be diminished once the new
compiled code is introduced.
Test: m test-art-host
Bug: 20323084
Change-Id: Ic654a1fb9c1ae127dde59290bf36a23edb55ca8e
diff --git a/runtime/mirror/class-inl.h b/runtime/mirror/class-inl.h
index 8ad47eb..0f2aac2 100644
--- a/runtime/mirror/class-inl.h
+++ b/runtime/mirror/class-inl.h
@@ -26,7 +26,6 @@
#include "base/length_prefixed_array.h"
#include "class_loader.h"
#include "common_throws.h"
-#include "dex_cache.h"
#include "dex_file.h"
#include "gc/heap-inl.h"
#include "iftable.h"
@@ -899,12 +898,12 @@
}
}
-inline void Class::SetDexCacheStrings(GcRoot<String>* new_dex_cache_strings) {
+inline void Class::SetDexCacheStrings(StringDexCacheType* new_dex_cache_strings) {
SetFieldPtr<false>(DexCacheStringsOffset(), new_dex_cache_strings);
}
-inline GcRoot<String>* Class::GetDexCacheStrings() {
- return GetFieldPtr<GcRoot<String>*>(DexCacheStringsOffset());
+inline StringDexCacheType* Class::GetDexCacheStrings() {
+ return GetFieldPtr64<StringDexCacheType*>(DexCacheStringsOffset());
}
template<ReadBarrierOption kReadBarrierOption, class Visitor>
@@ -1058,8 +1057,8 @@
dest->SetMethodsPtrInternal(new_methods);
}
// Update dex cache strings.
- GcRoot<mirror::String>* strings = GetDexCacheStrings();
- GcRoot<mirror::String>* new_strings = visitor(strings);
+ StringDexCacheType* strings = GetDexCacheStrings();
+ StringDexCacheType* new_strings = visitor(strings);
if (strings != new_strings) {
dest->SetDexCacheStrings(new_strings);
}
diff --git a/runtime/mirror/class.h b/runtime/mirror/class.h
index 978fc4c..e2cd649 100644
--- a/runtime/mirror/class.h
+++ b/runtime/mirror/class.h
@@ -54,6 +54,9 @@
class DexCache;
class IfTable;
class Method;
+struct StringDexCachePair;
+
+using StringDexCacheType = std::atomic<mirror::StringDexCachePair>;
// C++ mirror of java.lang.Class
class MANAGED Class FINAL : public Object {
@@ -1219,8 +1222,8 @@
bool GetSlowPathEnabled() SHARED_REQUIRES(Locks::mutator_lock_);
void SetSlowPath(bool enabled) SHARED_REQUIRES(Locks::mutator_lock_);
- GcRoot<String>* GetDexCacheStrings() SHARED_REQUIRES(Locks::mutator_lock_);
- void SetDexCacheStrings(GcRoot<String>* new_dex_cache_strings)
+ StringDexCacheType* GetDexCacheStrings() SHARED_REQUIRES(Locks::mutator_lock_);
+ void SetDexCacheStrings(StringDexCacheType* new_dex_cache_strings)
SHARED_REQUIRES(Locks::mutator_lock_);
static MemberOffset DexCacheStringsOffset() {
return OFFSET_OF_OBJECT_MEMBER(Class, dex_cache_strings_);
diff --git a/runtime/mirror/dex_cache-inl.h b/runtime/mirror/dex_cache-inl.h
index 84469ea..a3071b7 100644
--- a/runtime/mirror/dex_cache-inl.h
+++ b/runtime/mirror/dex_cache-inl.h
@@ -27,6 +27,8 @@
#include "mirror/class.h"
#include "runtime.h"
+#include <atomic>
+
namespace art {
namespace mirror {
@@ -35,15 +37,18 @@
return Class::ComputeClassSize(true, vtable_entries, 0, 0, 0, 0, 0, pointer_size);
}
-inline String* DexCache::GetResolvedString(uint32_t string_idx) {
- DCHECK_LT(string_idx, NumStrings());
- return GetStrings()[string_idx].Read();
+inline mirror::String* DexCache::GetResolvedString(uint32_t string_idx) {
+ DCHECK_LT(string_idx, GetDexFile()->NumStringIds());
+ return StringDexCachePair::LookupString(GetStrings(), string_idx, NumStrings()).Read();
}
-inline void DexCache::SetResolvedString(uint32_t string_idx, String* resolved) {
- DCHECK_LT(string_idx, NumStrings());
+inline void DexCache::SetResolvedString(uint32_t string_idx, mirror::String* resolved) {
+ DCHECK_LT(string_idx % NumStrings(), NumStrings());
// TODO default transaction support.
- GetStrings()[string_idx] = GcRoot<String>(resolved);
+ StringDexCachePair idx_ptr;
+ idx_ptr.string_index = string_idx;
+ idx_ptr.string_pointer = GcRoot<String>(resolved);
+ GetStrings()[string_idx % NumStrings()].store(idx_ptr, std::memory_order_relaxed);
// TODO: Fine-grained marking, so that we don't need to go through all arrays in full.
Runtime::Current()->GetHeap()->WriteBarrierEveryFieldOf(this);
}
@@ -131,9 +136,16 @@
VisitInstanceFieldsReferences<kVerifyFlags, kReadBarrierOption>(klass, visitor);
// Visit arrays after.
if (kVisitNativeRoots) {
- GcRoot<mirror::String>* strings = GetStrings();
+ mirror::StringDexCacheType* strings = GetStrings();
for (size_t i = 0, num_strings = NumStrings(); i != num_strings; ++i) {
- visitor.VisitRootIfNonNull(strings[i].AddressWithoutBarrier());
+ StringDexCachePair source = strings[i].load(std::memory_order_relaxed);
+ mirror::String* before = source.string_pointer.Read<kReadBarrierOption>();
+ GcRoot<mirror::String> root(before);
+ visitor.VisitRootIfNonNull(root.AddressWithoutBarrier());
+ if (root.Read() != before) {
+ source.string_pointer = GcRoot<String>(root.Read());
+ strings[i].store(source, std::memory_order_relaxed);
+ }
}
GcRoot<mirror::Class>* resolved_types = GetResolvedTypes();
for (size_t i = 0, num_types = NumResolvedTypes(); i != num_types; ++i) {
@@ -143,12 +155,14 @@
}
template <ReadBarrierOption kReadBarrierOption, typename Visitor>
-inline void DexCache::FixupStrings(GcRoot<mirror::String>* dest, const Visitor& visitor) {
- GcRoot<mirror::String>* src = GetStrings();
+inline void DexCache::FixupStrings(mirror::StringDexCacheType* dest, const Visitor& visitor) {
+ mirror::StringDexCacheType* src = GetStrings();
for (size_t i = 0, count = NumStrings(); i < count; ++i) {
- mirror::String* source = src[i].Read<kReadBarrierOption>();
- mirror::String* new_source = visitor(source);
- dest[i] = GcRoot<mirror::String>(new_source);
+ StringDexCachePair source = src[i].load(std::memory_order_relaxed);
+ mirror::String* ptr = source.string_pointer.Read<kReadBarrierOption>();
+ mirror::String* new_source = visitor(ptr);
+ source.string_pointer = GcRoot<String>(new_source);
+ dest[i].store(source, std::memory_order_relaxed);
}
}
diff --git a/runtime/mirror/dex_cache.cc b/runtime/mirror/dex_cache.cc
index 57066d8..cfcec9c 100644
--- a/runtime/mirror/dex_cache.cc
+++ b/runtime/mirror/dex_cache.cc
@@ -33,7 +33,7 @@
void DexCache::Init(const DexFile* dex_file,
String* location,
- GcRoot<String>* strings,
+ StringDexCacheType* strings,
uint32_t num_strings,
GcRoot<Class>* resolved_types,
uint32_t num_resolved_types,
diff --git a/runtime/mirror/dex_cache.h b/runtime/mirror/dex_cache.h
index d02a0d8..e04bde0 100644
--- a/runtime/mirror/dex_cache.h
+++ b/runtime/mirror/dex_cache.h
@@ -35,12 +35,62 @@
class String;
+struct StringDexCachePair {
+ GcRoot<String> string_pointer;
+ uint32_t string_index;
+ // The array is initially [ {0,0}, {0,0}, {0,0} ... ]
+ // We maintain the invariant that once a dex cache entry is populated,
+ // the pointer is always non-0
+ // Any given entry would thus be:
+ // {non-0, non-0} OR {0,0}
+ //
+ // It's generally sufficiently enough then to check if the
+ // lookup string index matches the stored string index (for a >0 string index)
+ // because if it's true the pointer is also non-null.
+ //
+ // For the 0th entry which is a special case, the value is either
+ // {0,0} (initial state) or {non-0, 0} which indicates
+ // that a valid string is stored at that index for a dex string id of 0.
+ //
+ // As an optimization, we want to avoid branching on the string pointer since
+ // it's always non-null if the string id branch succeeds (except for the 0th string id).
+ // Set the initial state for the 0th entry to be {0,1} which is guaranteed to fail
+ // the lookup string id == stored id branch.
+ static void Initialize(StringDexCacheType* strings) {
+ DCHECK(StringDexCacheType().is_lock_free());
+ mirror::StringDexCachePair first_elem;
+ first_elem.string_pointer = GcRoot<String>(nullptr);
+ first_elem.string_index = 1;
+ strings[0].store(first_elem, std::memory_order_relaxed);
+ }
+ static GcRoot<String> LookupString(StringDexCacheType* dex_cache,
+ uint32_t string_idx,
+ uint32_t cache_size) {
+ StringDexCachePair index_string = dex_cache[string_idx % cache_size]
+ .load(std::memory_order_relaxed);
+ if (string_idx != index_string.string_index) return GcRoot<String>(nullptr);
+ DCHECK(!index_string.string_pointer.IsNull());
+ return index_string.string_pointer;
+ }
+};
+using StringDexCacheType = std::atomic<StringDexCachePair>;
+
+
// C++ mirror of java.lang.DexCache.
class MANAGED DexCache FINAL : public Object {
public:
// Size of java.lang.DexCache.class.
static uint32_t ClassSize(PointerSize pointer_size);
+ // Size of string dex cache. Needs to be a power of 2 for entrypoint assumptions to hold.
+ static constexpr size_t kDexCacheStringCacheSize = 1024;
+ static_assert(IsPowerOfTwo(kDexCacheStringCacheSize),
+ "String dex cache size is not a power of 2.");
+
+ static constexpr size_t StaticStringSize() {
+ return kDexCacheStringCacheSize;
+ }
+
// Size of an instance of java.lang.DexCache not including referenced values.
static constexpr uint32_t InstanceSize() {
return sizeof(DexCache);
@@ -48,7 +98,7 @@
void Init(const DexFile* dex_file,
String* location,
- GcRoot<String>* strings,
+ StringDexCacheType* strings,
uint32_t num_strings,
GcRoot<Class>* resolved_types,
uint32_t num_resolved_types,
@@ -62,7 +112,7 @@
SHARED_REQUIRES(Locks::mutator_lock_);
template <ReadBarrierOption kReadBarrierOption = kWithReadBarrier, typename Visitor>
- void FixupStrings(GcRoot<mirror::String>* dest, const Visitor& visitor)
+ void FixupStrings(StringDexCacheType* dest, const Visitor& visitor)
SHARED_REQUIRES(Locks::mutator_lock_);
template <ReadBarrierOption kReadBarrierOption = kWithReadBarrier, typename Visitor>
@@ -109,10 +159,10 @@
return OFFSET_OF_OBJECT_MEMBER(DexCache, num_resolved_methods_);
}
- String* GetResolvedString(uint32_t string_idx) ALWAYS_INLINE
+ mirror::String* GetResolvedString(uint32_t string_idx) ALWAYS_INLINE
SHARED_REQUIRES(Locks::mutator_lock_);
- void SetResolvedString(uint32_t string_idx, String* resolved) ALWAYS_INLINE
+ void SetResolvedString(uint32_t string_idx, mirror::String* resolved) ALWAYS_INLINE
SHARED_REQUIRES(Locks::mutator_lock_);
Class* GetResolvedType(uint32_t type_idx) SHARED_REQUIRES(Locks::mutator_lock_);
@@ -135,11 +185,11 @@
ALWAYS_INLINE void SetResolvedField(uint32_t idx, ArtField* field, PointerSize ptr_size)
SHARED_REQUIRES(Locks::mutator_lock_);
- GcRoot<String>* GetStrings() ALWAYS_INLINE SHARED_REQUIRES(Locks::mutator_lock_) {
- return GetFieldPtr<GcRoot<String>*>(StringsOffset());
+ StringDexCacheType* GetStrings() ALWAYS_INLINE SHARED_REQUIRES(Locks::mutator_lock_) {
+ return GetFieldPtr64<StringDexCacheType*>(StringsOffset());
}
- void SetStrings(GcRoot<String>* strings) ALWAYS_INLINE SHARED_REQUIRES(Locks::mutator_lock_) {
+ void SetStrings(StringDexCacheType* strings) ALWAYS_INLINE SHARED_REQUIRES(Locks::mutator_lock_) {
SetFieldPtr<false>(StringsOffset(), strings);
}
@@ -224,7 +274,8 @@
uint64_t resolved_fields_; // ArtField*, array with num_resolved_fields_ elements.
uint64_t resolved_methods_; // ArtMethod*, array with num_resolved_methods_ elements.
uint64_t resolved_types_; // GcRoot<Class>*, array with num_resolved_types_ elements.
- uint64_t strings_; // GcRoot<String>*, array with num_strings_ elements.
+ uint64_t strings_; // std::atomic<StringDexCachePair>*,
+ // array with num_strings_ elements.
uint32_t num_resolved_fields_; // Number of elements in the resolved_fields_ array.
uint32_t num_resolved_methods_; // Number of elements in the resolved_methods_ array.
uint32_t num_resolved_types_; // Number of elements in the resolved_types_ array.
diff --git a/runtime/mirror/dex_cache_test.cc b/runtime/mirror/dex_cache_test.cc
index 48f2ca5..175997c 100644
--- a/runtime/mirror/dex_cache_test.cc
+++ b/runtime/mirror/dex_cache_test.cc
@@ -22,6 +22,7 @@
#include "common_runtime_test.h"
#include "linear_alloc.h"
#include "mirror/class_loader-inl.h"
+#include "mirror/dex_cache-inl.h"
#include "handle_scope-inl.h"
#include "scoped_thread_state_change.h"
@@ -40,7 +41,8 @@
Runtime::Current()->GetLinearAlloc())));
ASSERT_TRUE(dex_cache.Get() != nullptr);
- EXPECT_EQ(java_lang_dex_file_->NumStringIds(), dex_cache->NumStrings());
+ EXPECT_TRUE(dex_cache->StaticStringSize() == dex_cache->NumStrings()
+ || java_lang_dex_file_->NumStringIds() == dex_cache->NumStrings());
EXPECT_EQ(java_lang_dex_file_->NumTypeIds(), dex_cache->NumResolvedTypes());
EXPECT_EQ(java_lang_dex_file_->NumMethodIds(), dex_cache->NumResolvedMethods());
EXPECT_EQ(java_lang_dex_file_->NumFieldIds(), dex_cache->NumResolvedFields());