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/build/Android.gtest.mk b/build/Android.gtest.mk
index fdfd94c..ff41736 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -29,6 +29,7 @@
GetMethodSignature \
Instrumentation \
Interfaces \
+ Lookup \
Main \
MultiDex \
MultiDexModifiedSecondary \
@@ -78,6 +79,7 @@
ART_GTEST_reflection_test_DEX_DEPS := Main NonStaticLeafMethods StaticLeafMethods
ART_GTEST_stub_test_DEX_DEPS := AllFields
ART_GTEST_transaction_test_DEX_DEPS := Transaction
+ART_GTEST_type_lookup_table_test_DEX_DEPS := Lookup
# The elf writer test has dependencies on core.oat.
ART_GTEST_elf_writer_test_HOST_DEPS := $(HOST_CORE_IMAGE_default_no-pic_64) $(HOST_CORE_IMAGE_default_no-pic_32)
@@ -220,6 +222,7 @@
runtime/reference_table_test.cc \
runtime/thread_pool_test.cc \
runtime/transaction_test.cc \
+ runtime/type_lookup_table_test.cc \
runtime/utf_test.cc \
runtime/utils_test.cc \
runtime/verifier/method_verifier_test.cc \