From 1e5452a07694a6d4d2d6cede5594d42aca154fe2 Mon Sep 17 00:00:00 2001 From: Yurii Zubrytskyi Date: Thu, 13 Jun 2024 19:30:36 -0700 Subject: [res] Optimize Theme::ApplyStyle() This is the heaviest operation during the configuration change handling, as we recreate the asset manager object and rebase all existing themes on that object as soon as any assets change. The optimization here replaces the repeated binary search + insert in a middle of an array with a merge of two sorted arrays in place, achieving over 7x speedup: Before: #BM_ThemeApplyStyleFramework 9722.817566754931 ns After: #BM_ThemeApplyStyleFramework 1305.8760730843824 ns It also adds a detailed explanation of the algorithm and its assumptions to make it easier to optimize/debug it later. Flag: NONE A performance regression fix, flag check is too slow Bug: 345562237 Test: build, boot, atest + performance tests Change-Id: I979e17cf4837cc8853a8d54cb4cea2a9631c3136 --- libs/androidfw/AssetManager2.cpp | 86 +++++++++++++++++++++++++++++++--------- 1 file changed, 67 insertions(+), 19 deletions(-) (limited to 'libs/androidfw/AssetManager2.cpp') diff --git a/libs/androidfw/AssetManager2.cpp b/libs/androidfw/AssetManager2.cpp index 46f636e2ae7f..822a387351e3 100644 --- a/libs/androidfw/AssetManager2.cpp +++ b/libs/androidfw/AssetManager2.cpp @@ -23,9 +23,11 @@ #include #include #include +#include #include "android-base/logging.h" #include "android-base/stringprintf.h" +#include "androidfw/CombinedIterator.h" #include "androidfw/ResourceTypes.h" #include "androidfw/ResourceUtils.h" #include "androidfw/Util.h" @@ -1622,6 +1624,12 @@ Theme::Theme(AssetManager2* asset_manager) : asset_manager_(asset_manager) { Theme::~Theme() = default; +static bool IsUndefined(const Res_value& value) { + // DATA_NULL_EMPTY (@empty) is a valid resource value and DATA_NULL_UNDEFINED represents + // an absence of a valid value. + return value.dataType == Res_value::TYPE_NULL && value.data != Res_value::DATA_NULL_EMPTY; +} + base::expected Theme::ApplyStyle(uint32_t resid, bool force) { ATRACE_NAME("Theme::ApplyStyle"); @@ -1633,39 +1641,76 @@ base::expected Theme::ApplyStyle(uint32_t resid, // Merge the flags from this style. type_spec_flags_ |= (*bag)->type_spec_flags; + // + // This function is the most expensive part of applying an frro to the existing app resources, + // and needs to be as efficient as possible. + // The data structure we're working with is two parallel sorted arrays of keys (resource IDs) + // and entries (resource value + some attributes). + // The styles get applied in sequence, starting with an empty set of attributes. Each style + // contains its values for the theme attributes, and gets applied in either normal or forced way: + // - normal way never overrides the existing attribute, so only unique style attributes are added + // - forced way overrides anything for that attribute, and if it's undefined it removes the + // previous value completely + // + // Style attributes come in a Bag data type - a sorted array of attributes with their values. This + // means we don't need to re-sort the attributes ever, and instead: + // - for an already existing attribute just skip it or apply the forced value + // - if the forced value is undefined, mark it undefined as well to get rid of it later + // - for a new attribute append it to the array, forming a new sorted section of new attributes + // past the end of the original ones (ignore undefined ones here) + // - inplace merge two sorted sections to form a single sorted array again. + // - run the last pass to remove all undefined elements + // + // Using this algorithm performs better than a repeated binary search + insert in the middle, + // as that keeps shifting the tail end of the arrays and wasting CPU cycles in memcpy(). + // + const auto starting_size = keys_.size(); + if (starting_size == 0) { + keys_.reserve((*bag)->entry_count); + entries_.reserve((*bag)->entry_count); + } + bool wrote_undefined = false; for (auto it = begin(*bag); it != end(*bag); ++it) { const uint32_t attr_res_id = it->key; - // If the resource ID passed in is not a style, the key can be some other identifier that is not // a resource ID. We should fail fast instead of operating with strange resource IDs. if (!is_valid_resid(attr_res_id)) { return base::unexpected(std::nullopt); } - - // DATA_NULL_EMPTY (@empty) is a valid resource value and DATA_NULL_UNDEFINED represents - // an absence of a valid value. - bool is_undefined = it->value.dataType == Res_value::TYPE_NULL && - it->value.data != Res_value::DATA_NULL_EMPTY; + const bool is_undefined = IsUndefined(it->value); if (!force && is_undefined) { continue; } - - const auto key_it = std::lower_bound(keys_.begin(), keys_.end(), attr_res_id); - const auto entry_it = entries_.begin() + (key_it - keys_.begin()); - if (key_it != keys_.end() && *key_it == attr_res_id) { - if (is_undefined) { - // DATA_NULL_UNDEFINED clears the value of the attribute in the theme only when `force` is - // true. - keys_.erase(key_it); - entries_.erase(entry_it); - } else if (force) { + const auto key_it = std::lower_bound(keys_.begin(), keys_.begin() + starting_size, attr_res_id); + if (key_it != keys_.begin() + starting_size && *key_it == attr_res_id) { + const auto entry_it = entries_.begin() + (key_it - keys_.begin()); + if (force || IsUndefined(entry_it->value)) { *entry_it = Entry{it->cookie, (*bag)->type_spec_flags, it->value}; + wrote_undefined |= is_undefined; } - } else { - keys_.insert(key_it, attr_res_id); - entries_.insert(entry_it, Entry{it->cookie, (*bag)->type_spec_flags, it->value}); + } else if (!is_undefined) { + keys_.emplace_back(attr_res_id); + entries_.emplace_back(it->cookie, (*bag)->type_spec_flags, it->value); } } + + if (starting_size && keys_.size() != starting_size) { + std::inplace_merge( + CombinedIterator(keys_.begin(), entries_.begin()), + CombinedIterator(keys_.begin() + starting_size, entries_.begin() + starting_size), + CombinedIterator(keys_.end(), entries_.end())); + } + if (wrote_undefined) { + auto new_end = std::remove_if(CombinedIterator(keys_.begin(), entries_.begin()), + CombinedIterator(keys_.end(), entries_.end()), + [](const auto& pair) { return IsUndefined(pair.second.value); }); + keys_.erase(new_end.it1, keys_.end()); + entries_.erase(new_end.it2, entries_.end()); + } + if (android::base::kEnableDChecks && !std::is_sorted(keys_.begin(), keys_.end())) { + ALOGW("Bag %u was unsorted in the apk?", unsigned(resid)); + return base::unexpected(std::nullopt); + } return {}; } @@ -1691,6 +1736,9 @@ std::optional Theme::GetAttribute(uint32_t resid) return std::nullopt; } const auto entry_it = entries_.begin() + (key_it - keys_.begin()); + if (IsUndefined(entry_it->value)) { + return std::nullopt; + } type_spec_flags |= entry_it->type_spec_flags; if (entry_it->value.dataType == Res_value::TYPE_ATTRIBUTE) { resid = entry_it->value.data; -- cgit v1.2.3-59-g8ed1b From c4dadee12a57b3a75a2e8d570a0650617664e288 Mon Sep 17 00:00:00 2001 From: Yurii Zubrytskyi Date: Thu, 15 Aug 2024 12:08:47 -0700 Subject: [res] Start using ftl::SmallVector<> where it's most useful Test: build + boot Flag: EXEMPT minor change Change-Id: I21694756674169388407e2b3c7dce850ff19e354 --- libs/androidfw/AssetManager2.cpp | 12 +++++++----- libs/androidfw/include/androidfw/AssetManager2.h | 12 +++++++----- libs/androidfw/tests/AssetManager2_test.cpp | 20 ++++++++++---------- libs/androidfw/tests/BenchmarkHelpers.cpp | 2 +- libs/androidfw/tests/Theme_test.cpp | 2 +- 5 files changed, 26 insertions(+), 22 deletions(-) (limited to 'libs/androidfw/AssetManager2.cpp') diff --git a/libs/androidfw/AssetManager2.cpp b/libs/androidfw/AssetManager2.cpp index 822a387351e3..0fa31c7a832e 100644 --- a/libs/androidfw/AssetManager2.cpp +++ b/libs/androidfw/AssetManager2.cpp @@ -107,7 +107,7 @@ AssetManager2::AssetManager2(ApkAssetsList apk_assets, const ResTable_config& co } AssetManager2::AssetManager2() { - configurations_.resize(1); + configurations_.emplace_back(); } bool AssetManager2::SetApkAssets(ApkAssetsList apk_assets, bool invalidate_caches) { @@ -438,8 +438,8 @@ bool AssetManager2::ContainsAllocatedTable() const { return false; } -void AssetManager2::SetConfigurations(std::vector configurations, - bool force_refresh) { +void AssetManager2::SetConfigurations(std::span configurations, + bool force_refresh) { int diff = 0; if (force_refresh) { diff = -1; @@ -452,8 +452,10 @@ void AssetManager2::SetConfigurations(std::vector configuration } } } - configurations_ = std::move(configurations); - + configurations_.clear(); + for (auto&& config : configurations) { + configurations_.emplace_back(config); + } if (diff) { RebuildFilterList(); InvalidateCaches(static_cast(diff)); diff --git a/libs/androidfw/include/androidfw/AssetManager2.h b/libs/androidfw/include/androidfw/AssetManager2.h index ac46bc5c179f..0fdeefa09e26 100644 --- a/libs/androidfw/include/androidfw/AssetManager2.h +++ b/libs/androidfw/include/androidfw/AssetManager2.h @@ -32,6 +32,7 @@ #include "androidfw/AssetManager.h" #include "androidfw/ResourceTypes.h" #include "androidfw/Util.h" +#include "ftl/small_vector.h" namespace android { @@ -159,9 +160,10 @@ class AssetManager2 { // Sets/resets the configuration for this AssetManager. This will cause all // caches that are related to the configuration change to be invalidated. - void SetConfigurations(std::vector configurations, bool force_refresh = false); + void SetConfigurations(std::span configurations, + bool force_refresh = false); - inline const std::vector& GetConfigurations() const { + std::span GetConfigurations() const { return configurations_; } @@ -470,13 +472,13 @@ class AssetManager2 { // An array mapping package ID to index into package_groups. This keeps the lookup fast // without taking too much memory. - std::array::max() + 1> package_ids_; + std::array::max() + 1> package_ids_ = {}; - uint32_t default_locale_; + uint32_t default_locale_ = 0; // The current configurations set for this AssetManager. When this changes, cached resources // may need to be purged. - std::vector configurations_; + ftl::SmallVector configurations_; // Cached set of bags. These are cached because they can inherit keys from parent bags, // which involves some calculation. diff --git a/libs/androidfw/tests/AssetManager2_test.cpp b/libs/androidfw/tests/AssetManager2_test.cpp index c62f095e9dac..3f228841f6ba 100644 --- a/libs/androidfw/tests/AssetManager2_test.cpp +++ b/libs/androidfw/tests/AssetManager2_test.cpp @@ -113,7 +113,7 @@ TEST_F(AssetManager2Test, FindsResourceFromSingleApkAssets) { desired_config.language[1] = 'e'; AssetManager2 assetmanager; - assetmanager.SetConfigurations({desired_config}); + assetmanager.SetConfigurations({{desired_config}}); assetmanager.SetApkAssets({basic_assets_}); auto value = assetmanager.GetResource(basic::R::string::test1); @@ -137,7 +137,7 @@ TEST_F(AssetManager2Test, FindsResourceFromMultipleApkAssets) { desired_config.language[1] = 'e'; AssetManager2 assetmanager; - assetmanager.SetConfigurations({desired_config}); + assetmanager.SetConfigurations({{desired_config}}); assetmanager.SetApkAssets({basic_assets_, basic_de_fr_assets_}); auto value = assetmanager.GetResource(basic::R::string::test1); @@ -466,10 +466,10 @@ TEST_F(AssetManager2Test, ResolveDeepIdReference) { TEST_F(AssetManager2Test, DensityOverride) { AssetManager2 assetmanager; assetmanager.SetApkAssets({basic_assets_, basic_xhdpi_assets_, basic_xxhdpi_assets_}); - assetmanager.SetConfigurations({{ + assetmanager.SetConfigurations({{{ .density = ResTable_config::DENSITY_XHIGH, .sdkVersion = 21, - }}); + }}}); auto value = assetmanager.GetResource(basic::R::string::density, false /*may_be_bag*/); ASSERT_TRUE(value.has_value()); @@ -721,7 +721,7 @@ TEST_F(AssetManager2Test, GetLastPathWithoutEnablingReturnsEmpty) { ResTable_config desired_config; AssetManager2 assetmanager; - assetmanager.SetConfigurations({desired_config}); + assetmanager.SetConfigurations({{desired_config}}); assetmanager.SetApkAssets({basic_assets_}); assetmanager.SetResourceResolutionLoggingEnabled(false); @@ -736,7 +736,7 @@ TEST_F(AssetManager2Test, GetLastPathWithoutResolutionReturnsEmpty) { ResTable_config desired_config; AssetManager2 assetmanager; - assetmanager.SetConfigurations({desired_config}); + assetmanager.SetConfigurations({{desired_config}}); assetmanager.SetApkAssets({basic_assets_}); auto result = assetmanager.GetLastResourceResolution(); @@ -751,7 +751,7 @@ TEST_F(AssetManager2Test, GetLastPathWithSingleApkAssets) { AssetManager2 assetmanager; assetmanager.SetResourceResolutionLoggingEnabled(true); - assetmanager.SetConfigurations({desired_config}); + assetmanager.SetConfigurations({{desired_config}}); assetmanager.SetApkAssets({basic_assets_}); auto value = assetmanager.GetResource(basic::R::string::test1); @@ -774,7 +774,7 @@ TEST_F(AssetManager2Test, GetLastPathWithMultipleApkAssets) { AssetManager2 assetmanager; assetmanager.SetResourceResolutionLoggingEnabled(true); - assetmanager.SetConfigurations({desired_config}); + assetmanager.SetConfigurations({{desired_config}}); assetmanager.SetApkAssets({basic_assets_, basic_de_fr_assets_}); auto value = assetmanager.GetResource(basic::R::string::test1); @@ -796,7 +796,7 @@ TEST_F(AssetManager2Test, GetLastPathAfterDisablingReturnsEmpty) { AssetManager2 assetmanager; assetmanager.SetResourceResolutionLoggingEnabled(true); - assetmanager.SetConfigurations({desired_config}); + assetmanager.SetConfigurations({{desired_config}}); assetmanager.SetApkAssets({basic_assets_}); auto value = assetmanager.GetResource(basic::R::string::test1); @@ -817,7 +817,7 @@ TEST_F(AssetManager2Test, GetOverlayablesToString) { AssetManager2 assetmanager; assetmanager.SetResourceResolutionLoggingEnabled(true); - assetmanager.SetConfigurations({desired_config}); + assetmanager.SetConfigurations({{desired_config}}); assetmanager.SetApkAssets({overlayable_assets_}); const auto map = assetmanager.GetOverlayableMapForPackage(0x7f); diff --git a/libs/androidfw/tests/BenchmarkHelpers.cpp b/libs/androidfw/tests/BenchmarkHelpers.cpp index e3fc0a0a4e68..ec2abb84a5d5 100644 --- a/libs/androidfw/tests/BenchmarkHelpers.cpp +++ b/libs/androidfw/tests/BenchmarkHelpers.cpp @@ -66,7 +66,7 @@ void GetResourceBenchmark(const std::vector& paths, const ResTable_ AssetManager2 assetmanager; assetmanager.SetApkAssets(apk_assets); if (config != nullptr) { - assetmanager.SetConfigurations({*config}); + assetmanager.SetConfigurations({{{*config}}}); } while (state.KeepRunning()) { diff --git a/libs/androidfw/tests/Theme_test.cpp b/libs/androidfw/tests/Theme_test.cpp index 181d1411fb91..afcb0c1ad964 100644 --- a/libs/androidfw/tests/Theme_test.cpp +++ b/libs/androidfw/tests/Theme_test.cpp @@ -260,7 +260,7 @@ TEST_F(ThemeTest, ThemeRebase) { ResTable_config night{}; night.uiMode = ResTable_config::UI_MODE_NIGHT_YES; night.version = 8u; - am_night.SetConfigurations({night}); + am_night.SetConfigurations({{night}}); auto theme = am.NewTheme(); { -- cgit v1.2.3-59-g8ed1b