Optimize ResTable::getLocales() to improve bindApplication performance
Change from linear searching for uniqueness to binary search.
Bug:27198799
Change-Id: I1ccb6e93cc213810848f07d631d9d8de7c719803
diff --git a/libs/androidfw/AssetManager.cpp b/libs/androidfw/AssetManager.cpp
index 6913f43..715c875 100644
--- a/libs/androidfw/AssetManager.cpp
+++ b/libs/androidfw/AssetManager.cpp
@@ -34,9 +34,7 @@
#include <utils/String8.h>
#include <utils/threads.h>
#include <utils/Timers.h>
-#ifdef __ANDROID__
-#include <cutils/trace.h>
-#endif
+#include <utils/Trace.h>
#include <assert.h>
#include <dirent.h>
@@ -54,14 +52,6 @@
_rc; })
#endif
-#ifdef __ANDROID__
-#define MY_TRACE_BEGIN(x) ATRACE_BEGIN(x)
-#define MY_TRACE_END() ATRACE_END()
-#else
-#define MY_TRACE_BEGIN(x)
-#define MY_TRACE_END()
-#endif
-
using namespace android;
static const bool kIsDebug = false;
@@ -623,7 +613,7 @@
ResTable* sharedRes = NULL;
bool shared = true;
bool onlyEmptyResources = true;
- MY_TRACE_BEGIN(ap.path.string());
+ ATRACE_NAME(ap.path.string());
Asset* idmap = openIdmapLocked(ap);
size_t nextEntryIdx = mResources->getTableCount();
ALOGV("Looking for resource asset in '%s'\n", ap.path.string());
@@ -703,8 +693,6 @@
if (idmap != NULL) {
delete idmap;
}
- MY_TRACE_END();
-
return onlyEmptyResources;
}
@@ -752,6 +740,7 @@
void AssetManager::updateResourceParamsLocked() const
{
+ ATRACE_CALL();
ResTable* res = mResources;
if (!res) {
return;
diff --git a/libs/androidfw/ResourceTypes.cpp b/libs/androidfw/ResourceTypes.cpp
index 1ccc59a..15cb684 100644
--- a/libs/androidfw/ResourceTypes.cpp
+++ b/libs/androidfw/ResourceTypes.cpp
@@ -24,6 +24,7 @@
#include <stdlib.h>
#include <string.h>
+#include <algorithm>
#include <limits>
#include <memory>
#include <type_traits>
@@ -5810,6 +5811,10 @@
return NULL;
}
+static bool compareResTableConfig(const ResTable_config& a, const ResTable_config& b) {
+ return a.compare(b) < 0;
+}
+
void ResTable::getConfigurations(Vector<ResTable_config>* configs, bool ignoreMipmap,
bool ignoreAndroidPackage, bool includeSystemConfigs) const {
const size_t packageCount = mPackageGroups.size();
@@ -5840,17 +5845,11 @@
ResTable_config cfg;
memset(&cfg, 0, sizeof(ResTable_config));
cfg.copyFromDtoH(config->config);
- // only insert unique
- const size_t N = configs->size();
- size_t n;
- for (n = 0; n < N; n++) {
- if (0 == (*configs)[n].compare(cfg)) {
- break;
- }
- }
- // if we didn't find it
- if (n == N) {
- configs->add(cfg);
+
+ auto iter = std::lower_bound(configs->begin(), configs->end(), cfg,
+ compareResTableConfig);
+ if (iter == configs->end() || iter->compare(cfg) != 0) {
+ configs->insertAt(cfg, std::distance(configs->begin(), iter));
}
}
}
@@ -5858,6 +5857,10 @@
}
}
+static bool compareString8AndCString(const String8& str, const char* cStr) {
+ return strcmp(str.string(), cStr) < 0;
+}
+
void ResTable::getLocales(Vector<String8>* locales, bool includeSystemLocales) const
{
Vector<ResTable_config> configs;
@@ -5872,15 +5875,11 @@
char locale[RESTABLE_MAX_LOCALE_LEN];
for (size_t i=0; i<I; i++) {
configs[i].getBcp47Locale(locale);
- const size_t J = locales->size();
- size_t j;
- for (j=0; j<J; j++) {
- if (0 == strcmp(locale, (*locales)[j].string())) {
- break;
- }
- }
- if (j == J) {
- locales->add(String8(locale));
+
+ auto iter = std::lower_bound(locales->begin(), locales->end(), locale,
+ compareString8AndCString);
+ if (iter == locales->end() || strcmp(iter->string(), locale) != 0) {
+ locales->insertAt(String8(locale), std::distance(locales->begin(), iter));
}
}
}
diff --git a/libs/androidfw/tests/ResTable_test.cpp b/libs/androidfw/tests/ResTable_test.cpp
index 7cd7fb5..b8b4625 100644
--- a/libs/androidfw/tests/ResTable_test.cpp
+++ b/libs/androidfw/tests/ResTable_test.cpp
@@ -39,8 +39,20 @@
*/
#include "data/basic/basic_arsc.h"
+/**
+ * Include a binary library resource table.
+ *
+ * Package: com.android.test.basic
+ */
#include "data/lib/lib_arsc.h"
+/**
+ * Include a system resource table.
+ *
+ * Package: android
+ */
+#include "data/system/system_arsc.h"
+
TEST(ResTableTest, shouldLoadSuccessfully) {
ResTable table;
ASSERT_EQ(NO_ERROR, table.add(basic_arsc, basic_arsc_len));
@@ -324,4 +336,25 @@
ASSERT_EQ(uint32_t(600), val.data);
}
+TEST(ResTableTest, GetConfigurationsReturnsUniqueList) {
+ ResTable table;
+ ASSERT_EQ(NO_ERROR, table.add(system_arsc, system_arsc_len));
+ ASSERT_EQ(NO_ERROR, table.add(basic_arsc, basic_arsc_len));
+
+ ResTable_config configSv;
+ memset(&configSv, 0, sizeof(configSv));
+ configSv.language[0] = 's';
+ configSv.language[1] = 'v';
+
+ Vector<ResTable_config> configs;
+ table.getConfigurations(&configs);
+
+ EXPECT_EQ(1, std::count(configs.begin(), configs.end(), configSv));
+
+ Vector<String8> locales;
+ table.getLocales(&locales);
+
+ EXPECT_EQ(1, std::count(locales.begin(), locales.end(), String8("sv")));
+}
+
} // namespace
diff --git a/libs/androidfw/tests/TestHelpers.h b/libs/androidfw/tests/TestHelpers.h
index ac80d88..ff9be16 100644
--- a/libs/androidfw/tests/TestHelpers.h
+++ b/libs/androidfw/tests/TestHelpers.h
@@ -21,7 +21,7 @@
enum { MAY_NOT_BE_BAG = false };
static inline bool operator==(const android::ResTable_config& a, const android::ResTable_config& b) {
- return memcmp(&a, &b, sizeof(a)) == 0;
+ return a.compare(b) == 0;
}
static inline ::std::ostream& operator<<(::std::ostream& out, const android::ResTable_config& c) {
diff --git a/libs/androidfw/tests/data/system/R.h b/libs/androidfw/tests/data/system/R.h
index 27f25fe..6a31fb8 100644
--- a/libs/androidfw/tests/data/system/R.h
+++ b/libs/androidfw/tests/data/system/R.h
@@ -33,6 +33,12 @@
};
}
+namespace integer {
+ enum {
+ number = 0x01030000, // sv
+ };
+}
+
} // namespace R
} // namespace android
diff --git a/libs/androidfw/tests/data/system/res/values-sv/values.xml b/libs/androidfw/tests/data/system/res/values-sv/values.xml
new file mode 100644
index 0000000..b97bdb6
--- /dev/null
+++ b/libs/androidfw/tests/data/system/res/values-sv/values.xml
@@ -0,0 +1,20 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2016 The Android Open Source Project
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+-->
+
+<resources>
+ <public type="integer" name="number" id="0x01030000" />
+ <integer name="number">1</integer>
+</resources>
diff --git a/libs/androidfw/tests/data/system/system_arsc.h b/libs/androidfw/tests/data/system/system_arsc.h
index 215ecae..b0dab6b 100644
--- a/libs/androidfw/tests/data/system/system_arsc.h
+++ b/libs/androidfw/tests/data/system/system_arsc.h
@@ -1,8 +1,8 @@
unsigned char system_arsc[] = {
- 0x02, 0x00, 0x0c, 0x00, 0x18, 0x03, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
+ 0x02, 0x00, 0x0c, 0x00, 0xf8, 0x03, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
0x01, 0x00, 0x1c, 0x00, 0x1c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1c, 0x00, 0x00, 0x00,
- 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x20, 0x01, 0xf0, 0x02, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x20, 0x01, 0xd0, 0x03, 0x00, 0x00,
0x01, 0x00, 0x00, 0x00, 0x61, 0x00, 0x6e, 0x00, 0x64, 0x00, 0x72, 0x00,
0x6f, 0x00, 0x69, 0x00, 0x64, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
@@ -25,26 +25,33 @@
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x20, 0x01, 0x00, 0x00,
- 0x02, 0x00, 0x00, 0x00, 0x60, 0x01, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00,
- 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1c, 0x00, 0x40, 0x00, 0x00, 0x00,
- 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
- 0x24, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
- 0x0c, 0x00, 0x00, 0x00, 0x04, 0x00, 0x61, 0x00, 0x74, 0x00, 0x74, 0x00,
- 0x72, 0x00, 0x00, 0x00, 0x05, 0x00, 0x73, 0x00, 0x74, 0x00, 0x79, 0x00,
- 0x6c, 0x00, 0x65, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1c, 0x00,
- 0x70, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
- 0x00, 0x00, 0x00, 0x00, 0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
- 0x00, 0x00, 0x00, 0x00, 0x18, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00,
+ 0x04, 0x00, 0x00, 0x00, 0x98, 0x01, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1c, 0x00, 0x78, 0x00, 0x00, 0x00,
+ 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x2c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x0c, 0x00, 0x00, 0x00, 0x1a, 0x00, 0x00, 0x00, 0x2c, 0x00, 0x00, 0x00,
+ 0x04, 0x00, 0x61, 0x00, 0x74, 0x00, 0x74, 0x00, 0x72, 0x00, 0x00, 0x00,
+ 0x05, 0x00, 0x73, 0x00, 0x74, 0x00, 0x79, 0x00, 0x6c, 0x00, 0x65, 0x00,
+ 0x00, 0x00, 0x07, 0x00, 0x69, 0x00, 0x6e, 0x00, 0x74, 0x00, 0x65, 0x00,
+ 0x67, 0x00, 0x65, 0x00, 0x72, 0x00, 0x00, 0x00, 0x0d, 0x00, 0x5e, 0x00,
+ 0x61, 0x00, 0x74, 0x00, 0x74, 0x00, 0x72, 0x00, 0x2d, 0x00, 0x70, 0x00,
+ 0x72, 0x00, 0x69, 0x00, 0x76, 0x00, 0x61, 0x00, 0x74, 0x00, 0x65, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1c, 0x00, 0x84, 0x00, 0x00, 0x00,
+ 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x2c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x18, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00, 0x46, 0x00, 0x00, 0x00,
0x0a, 0x00, 0x62, 0x00, 0x61, 0x00, 0x63, 0x00, 0x6b, 0x00, 0x67, 0x00,
0x72, 0x00, 0x6f, 0x00, 0x75, 0x00, 0x6e, 0x00, 0x64, 0x00, 0x00, 0x00,
0x0a, 0x00, 0x66, 0x00, 0x6f, 0x00, 0x72, 0x00, 0x65, 0x00, 0x67, 0x00,
0x72, 0x00, 0x6f, 0x00, 0x75, 0x00, 0x6e, 0x00, 0x64, 0x00, 0x00, 0x00,
0x09, 0x00, 0x54, 0x00, 0x68, 0x00, 0x65, 0x00, 0x6d, 0x00, 0x65, 0x00,
- 0x2e, 0x00, 0x4f, 0x00, 0x6e, 0x00, 0x65, 0x00, 0x00, 0x00, 0x00, 0x00,
- 0x02, 0x02, 0x10, 0x00, 0x18, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
- 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x40,
- 0x01, 0x02, 0x44, 0x00, 0x84, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
- 0x02, 0x00, 0x00, 0x00, 0x4c, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00,
+ 0x2e, 0x00, 0x4f, 0x00, 0x6e, 0x00, 0x65, 0x00, 0x00, 0x00, 0x06, 0x00,
+ 0x6e, 0x00, 0x75, 0x00, 0x6d, 0x00, 0x62, 0x00, 0x65, 0x00, 0x72, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x02, 0x02, 0x10, 0x00, 0x18, 0x00, 0x00, 0x00,
+ 0x01, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40,
+ 0x00, 0x00, 0x00, 0x40, 0x01, 0x02, 0x4c, 0x00, 0x8c, 0x00, 0x00, 0x00,
+ 0x01, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x54, 0x00, 0x00, 0x00,
+ 0x38, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
@@ -55,15 +62,27 @@
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x01, 0x08, 0x00, 0x00, 0x10, 0x11, 0x00, 0x00, 0x00,
0x02, 0x02, 0x10, 0x00, 0x14, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00,
- 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x01, 0x02, 0x44, 0x00,
- 0x70, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
- 0x48, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x01, 0x02, 0x4c, 0x00,
+ 0x78, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
+ 0x50, 0x00, 0x00, 0x00, 0x38, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
- 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x03, 0x00,
- 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00,
- 0x00, 0x00, 0x01, 0x01, 0x08, 0x00, 0x00, 0x1d, 0x00, 0x00, 0xff, 0xff,
- 0x01, 0x00, 0x01, 0x01, 0x08, 0x00, 0x00, 0x1d, 0x00, 0x00, 0x00, 0xff
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x03, 0x00, 0x02, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01,
+ 0x08, 0x00, 0x00, 0x1d, 0x00, 0x00, 0xff, 0xff, 0x01, 0x00, 0x01, 0x01,
+ 0x08, 0x00, 0x00, 0x1d, 0x00, 0x00, 0x00, 0xff, 0x02, 0x02, 0x10, 0x00,
+ 0x14, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x40, 0x01, 0x02, 0x4c, 0x00, 0x60, 0x00, 0x00, 0x00,
+ 0x03, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x50, 0x00, 0x00, 0x00,
+ 0x38, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x73, 0x76, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ 0x08, 0x00, 0x02, 0x00, 0x03, 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x10,
+ 0x01, 0x00, 0x00, 0x00, 0x02, 0x02, 0x10, 0x00, 0x10, 0x00, 0x00, 0x00,
+ 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};
-unsigned int system_arsc_len = 792;
+unsigned int system_arsc_len = 1016;