Implementation of fast lookup table to search class_def by descriptor
Lookup table is a hash table which built at compile time and stored
into oat file. At runtime the table is restored and used in the
method DexFile::FindClassDef(const char*) to perform fast search of
the class_def_idx by class descriptor. Advantages of the lookup table
over the HashSet (runtime/base/hash_set.h) are:
1. Lookup table is built at compile time and uses read-only memory at
runtime
2. Lookup table uses less memory then DexFile::Index (less by 80% for
/system/framework/framework.jar on Nexus5)
3. Lookup table does less string comparisons compared with HashSet
(less by 70% for zygote process on Nexus5)
The disadvantage of the lookup table is it increased boot.oat size by
0.2% on Nexus5 and application .oat file by 0.3% in average on Nexus5.
mathieuc changes:
Create lookup table in dex2oat to speed up compilation. Clean up code
to follow style guide and use less static functions. Added
performance measurements.
Compile ~100 APKs 5 times with filter interpret-only:
Before:
real 1m8.989s
user 0m59.318s
sys 0m7.773s
After:
real 1m1.493s
user 0m52.055s
sys 0m7.581s
App launch (AOSP N5 maps, average of 45 runs):
Before: 966.84ms
After: 923.733ms
Launch speedup is 4.7%
Memory usage compared to HashSet index on 50 various APK:
32 bit: HashSet ~625694b vs TypeLookupTable ~404268b
64 bit: HashSet ~1251390b vs TypeLookupTable ~404268b
Bug: 10921004
Bug: 20269715
Change-Id: I7246c1d9ad9fe81fe5c5907a4bf70396d8f9242a
diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc
index dcb23bf..c7b8884 100644
--- a/compiler/oat_writer.cc
+++ b/compiler/oat_writer.cc
@@ -33,6 +33,7 @@
#include "driver/compiler_options.h"
#include "gc/space/image_space.h"
#include "gc/space/space.h"
+#include "handle_scope-inl.h"
#include "image_writer.h"
#include "linker/relative_patcher.h"
#include "mirror/array.h"
@@ -44,7 +45,7 @@
#include "output_stream.h"
#include "safe_map.h"
#include "scoped_thread_state_change.h"
-#include "handle_scope-inl.h"
+#include "type_lookup_table.h"
#include "utils/dex_cache_arrays_layout-inl.h"
#include "verifier/method_verifier.h"
@@ -107,6 +108,9 @@
size_oat_class_status_(0),
size_oat_class_method_bitmaps_(0),
size_oat_class_method_offsets_(0),
+ size_oat_lookup_table_alignment_(0),
+ size_oat_lookup_table_offset_(0),
+ size_oat_lookup_table_(0),
method_offset_map_() {
CHECK(key_value_store != nullptr);
@@ -129,6 +133,10 @@
offset = InitDexFiles(offset);
}
{
+ TimingLogger::ScopedTiming split("InitLookupTables", timings);
+ offset = InitLookupTables(offset);
+ }
+ {
TimingLogger::ScopedTiming split("InitOatClasses", timings);
offset = InitOatClasses(offset);
}
@@ -322,7 +330,8 @@
return true;
}
- bool VisitMethod(size_t class_def_method_index ATTRIBUTE_UNUSED, const ClassDataItemIterator& it) {
+ bool VisitMethod(size_t class_def_method_index ATTRIBUTE_UNUSED,
+ const ClassDataItemIterator& it) {
// Fill in the compiled_methods_ array for methods that have a
// CompiledMethod. We track the number of non-null entries in
// num_non_null_compiled_methods_ since we only want to allocate
@@ -1043,11 +1052,29 @@
oat_dex_files_[i]->dex_file_offset_ = offset;
const DexFile* dex_file = (*dex_files_)[i];
+
+ // Initialize type lookup table
+ oat_dex_files_[i]->lookup_table_ = dex_file->GetTypeLookupTable();
+
offset += dex_file->GetHeader().file_size_;
}
return offset;
}
+size_t OatWriter::InitLookupTables(size_t offset) {
+ for (OatDexFile* oat_dex_file : oat_dex_files_) {
+ if (oat_dex_file->lookup_table_ != nullptr) {
+ uint32_t aligned_offset = RoundUp(offset, 4);
+ oat_dex_file->lookup_table_offset_ = aligned_offset;
+ size_oat_lookup_table_alignment_ += aligned_offset - offset;
+ offset = aligned_offset + oat_dex_file->lookup_table_->RawDataLength();
+ } else {
+ oat_dex_file->lookup_table_offset_ = 0;
+ }
+ }
+ return offset;
+}
+
size_t OatWriter::InitOatClasses(size_t offset) {
// calculate the offsets within OatDexFiles to OatClasses
InitOatClassesMethodVisitor visitor(this, offset);
@@ -1256,6 +1283,9 @@
DO_STAT(size_oat_class_status_);
DO_STAT(size_oat_class_method_bitmaps_);
DO_STAT(size_oat_class_method_offsets_);
+ DO_STAT(size_oat_lookup_table_alignment_);
+ DO_STAT(size_oat_lookup_table_offset_);
+ DO_STAT(size_oat_lookup_table_);
#undef DO_STAT
VLOG(compiler) << "size_total=" << PrettySize(size_total) << " (" << size_total << "B)"; \
@@ -1309,6 +1339,9 @@
}
size_dex_file_ += dex_file->GetHeader().file_size_;
}
+ if (!WriteLookupTables(out, file_offset)) {
+ return false;
+ }
for (size_t i = 0; i != oat_classes_.size(); ++i) {
if (!oat_classes_[i]->Write(this, out, file_offset)) {
PLOG(ERROR) << "Failed to write oat methods information to " << out->GetLocation();
@@ -1318,6 +1351,35 @@
return true;
}
+bool OatWriter::WriteLookupTables(OutputStream* out, const size_t file_offset) {
+ for (size_t i = 0; i < oat_dex_files_.size(); ++i) {
+ const uint32_t lookup_table_offset = oat_dex_files_[i]->lookup_table_offset_;
+ const TypeLookupTable* table = oat_dex_files_[i]->lookup_table_;
+ DCHECK_EQ(lookup_table_offset == 0, table == nullptr);
+ if (lookup_table_offset == 0) {
+ continue;
+ }
+ const uint32_t expected_offset = file_offset + lookup_table_offset;
+ off_t actual_offset = out->Seek(expected_offset, kSeekSet);
+ if (static_cast<uint32_t>(actual_offset) != expected_offset) {
+ const DexFile* dex_file = (*dex_files_)[i];
+ PLOG(ERROR) << "Failed to seek to lookup table section. Actual: " << actual_offset
+ << " Expected: " << expected_offset << " File: " << dex_file->GetLocation();
+ return false;
+ }
+ if (table != nullptr) {
+ if (!out->WriteFully(table->RawData(), table->RawDataLength())) {
+ const DexFile* dex_file = (*dex_files_)[i];
+ PLOG(ERROR) << "Failed to write lookup table for " << dex_file->GetLocation()
+ << " to " << out->GetLocation();
+ return false;
+ }
+ size_oat_lookup_table_ += table->RawDataLength();
+ }
+ }
+ return true;
+}
+
size_t OatWriter::WriteMaps(OutputStream* out, const size_t file_offset, size_t relative_offset) {
#define VISIT(VisitorType) \
do { \
@@ -1425,6 +1487,7 @@
dex_file_location_data_ = reinterpret_cast<const uint8_t*>(location.data());
dex_file_location_checksum_ = dex_file.GetLocationChecksum();
dex_file_offset_ = 0;
+ lookup_table_offset_ = 0;
methods_offsets_.resize(dex_file.NumClassDefs());
}
@@ -1433,6 +1496,7 @@
+ dex_file_location_size_
+ sizeof(dex_file_location_checksum_)
+ sizeof(dex_file_offset_)
+ + sizeof(lookup_table_offset_)
+ (sizeof(methods_offsets_[0]) * methods_offsets_.size());
}
@@ -1441,6 +1505,10 @@
oat_header->UpdateChecksum(dex_file_location_data_, dex_file_location_size_);
oat_header->UpdateChecksum(&dex_file_location_checksum_, sizeof(dex_file_location_checksum_));
oat_header->UpdateChecksum(&dex_file_offset_, sizeof(dex_file_offset_));
+ oat_header->UpdateChecksum(&lookup_table_offset_, sizeof(lookup_table_offset_));
+ if (lookup_table_ != nullptr) {
+ oat_header->UpdateChecksum(lookup_table_->RawData(), lookup_table_->RawDataLength());
+ }
oat_header->UpdateChecksum(&methods_offsets_[0],
sizeof(methods_offsets_[0]) * methods_offsets_.size());
}
@@ -1469,6 +1537,11 @@
return false;
}
oat_writer->size_oat_dex_file_offset_ += sizeof(dex_file_offset_);
+ if (!out->WriteFully(&lookup_table_offset_, sizeof(lookup_table_offset_))) {
+ PLOG(ERROR) << "Failed to write lookup table offset to " << out->GetLocation();
+ return false;
+ }
+ oat_writer->size_oat_lookup_table_offset_ += sizeof(lookup_table_offset_);
if (!out->WriteFully(&methods_offsets_[0],
sizeof(methods_offsets_[0]) * methods_offsets_.size())) {
PLOG(ERROR) << "Failed to write methods offsets to " << out->GetLocation();
diff --git a/compiler/oat_writer.h b/compiler/oat_writer.h
index d6cb65b..f2fe048 100644
--- a/compiler/oat_writer.h
+++ b/compiler/oat_writer.h
@@ -24,8 +24,8 @@
#include "linker/relative_patcher.h" // For linker::RelativePatcherTargetProvider.
#include "mem_map.h"
#include "method_reference.h"
-#include "oat.h"
#include "mirror/class.h"
+#include "oat.h"
#include "safe_map.h"
namespace art {
@@ -36,6 +36,7 @@
class ImageWriter;
class OutputStream;
class TimingLogger;
+class TypeLookupTable;
// OatHeader variable length with count of D OatDexFiles
//
@@ -49,6 +50,11 @@
// ...
// Dex[D]
//
+// TypeLookupTable[0] one descriptor to class def index hash table for each OatDexFile.
+// TypeLookupTable[1]
+// ...
+// TypeLookupTable[D]
+//
// OatClass[0] one variable sized OatClass for each of C DexFile::ClassDefs
// OatClass[1] contains OatClass entries with class status, offsets to code, etc.
// ...
@@ -168,6 +174,7 @@
size_t InitOatHeader();
size_t InitOatDexFiles(size_t offset);
+ size_t InitLookupTables(size_t offset);
size_t InitDexFiles(size_t offset);
size_t InitOatClasses(size_t offset);
size_t InitOatMaps(size_t offset);
@@ -177,6 +184,7 @@
SHARED_REQUIRES(Locks::mutator_lock_);
bool WriteTables(OutputStream* out, const size_t file_offset);
+ bool WriteLookupTables(OutputStream* out, const size_t file_offset);
size_t WriteMaps(OutputStream* out, const size_t file_offset, size_t relative_offset);
size_t WriteCode(OutputStream* out, const size_t file_offset, size_t relative_offset);
size_t WriteCodeDexFiles(OutputStream* out, const size_t file_offset, size_t relative_offset);
@@ -199,6 +207,8 @@
const uint8_t* dex_file_location_data_;
uint32_t dex_file_location_checksum_;
uint32_t dex_file_offset_;
+ uint32_t lookup_table_offset_;
+ TypeLookupTable* lookup_table_; // Owned by the dex file.
std::vector<uint32_t> methods_offsets_;
private:
@@ -333,6 +343,9 @@
uint32_t size_oat_class_status_;
uint32_t size_oat_class_method_bitmaps_;
uint32_t size_oat_class_method_offsets_;
+ uint32_t size_oat_lookup_table_alignment_;
+ uint32_t size_oat_lookup_table_offset_;
+ uint32_t size_oat_lookup_table_;
std::unique_ptr<linker::RelativePatcher> relative_patcher_;