From 591895bd28f3073dfeebf6bcfb0fc18491e54809 Mon Sep 17 00:00:00 2001 From: Yurii Zubrytskyi Date: Mon, 14 Nov 2022 22:06:30 -0800 Subject: [res] Split keys and values in Theme::Entry vector Having keys in a separate vector improves memory usage (because of a 4-byte padding in the original struct that's gone) and performance (much better cache utilization when searching only through the keys) Test: build + UTs + boot Bug: 237583012 Change-Id: I5ed3bada42fabfc30dfe5de39946ee5bbab22899 --- libs/androidfw/AssetManager2.cpp | 76 ++++++++++++++++++++-------------------- 1 file changed, 38 insertions(+), 38 deletions(-) (limited to 'libs/androidfw/AssetManager2.cpp') diff --git a/libs/androidfw/AssetManager2.cpp b/libs/androidfw/AssetManager2.cpp index c3d153d56b26..27b121b0cccc 100644 --- a/libs/androidfw/AssetManager2.cpp +++ b/libs/androidfw/AssetManager2.cpp @@ -1411,6 +1411,7 @@ uint8_t AssetManager2::GetAssignedPackageId(const LoadedPackage* package) const std::unique_ptr AssetManager2::NewTheme() { constexpr size_t kInitialReserveSize = 32; auto theme = std::unique_ptr(new Theme(this)); + theme->keys_.reserve(kInitialReserveSize); theme->entries_.reserve(kInitialReserveSize); return theme; } @@ -1421,20 +1422,11 @@ Theme::Theme(AssetManager2* asset_manager) : asset_manager_(asset_manager) { Theme::~Theme() = default; struct Theme::Entry { - uint32_t attr_res_id; ApkAssetsCookie cookie; uint32_t type_spec_flags; Res_value value; }; -namespace { -struct ThemeEntryKeyComparer { - bool operator() (const Theme::Entry& entry, uint32_t attr_res_id) const noexcept { - return entry.attr_res_id < attr_res_id; - } -}; -} // namespace - base::expected Theme::ApplyStyle(uint32_t resid, bool force) { ATRACE_NAME("Theme::ApplyStyle"); @@ -1463,18 +1455,20 @@ base::expected Theme::ApplyStyle(uint32_t resid, continue; } - auto entry_it = std::lower_bound(entries_.begin(), entries_.end(), attr_res_id, - ThemeEntryKeyComparer{}); - if (entry_it != entries_.end() && entry_it->attr_res_id == attr_res_id) { + 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. + // true. + keys_.erase(key_it); entries_.erase(entry_it); } else if (force) { - *entry_it = Entry{attr_res_id, it->cookie, (*bag)->type_spec_flags, it->value}; + *entry_it = Entry{it->cookie, (*bag)->type_spec_flags, it->value}; } } else { - entries_.insert(entry_it, Entry{attr_res_id, it->cookie, (*bag)->type_spec_flags, it->value}); + keys_.insert(key_it, attr_res_id); + entries_.insert(entry_it, Entry{it->cookie, (*bag)->type_spec_flags, it->value}); } } return {}; @@ -1485,6 +1479,7 @@ void Theme::Rebase(AssetManager2* am, const uint32_t* style_ids, const uint8_t* ATRACE_NAME("Theme::Rebase"); // Reset the entries without changing the vector capacity to prevent reallocations during // ApplyStyle. + keys_.clear(); entries_.clear(); asset_manager_ = am; for (size_t i = 0; i < style_count; i++) { @@ -1493,16 +1488,14 @@ void Theme::Rebase(AssetManager2* am, const uint32_t* style_ids, const uint8_t* } std::optional Theme::GetAttribute(uint32_t resid) const { - constexpr const uint32_t kMaxIterations = 20; uint32_t type_spec_flags = 0u; for (uint32_t i = 0; i <= kMaxIterations; i++) { - auto entry_it = std::lower_bound(entries_.begin(), entries_.end(), resid, - ThemeEntryKeyComparer{}); - if (entry_it == entries_.end() || entry_it->attr_res_id != resid) { + const auto key_it = std::lower_bound(keys_.begin(), keys_.end(), resid); + if (key_it == keys_.end() || *key_it != resid) { return std::nullopt; } - + const auto entry_it = entries_.begin() + (key_it - keys_.begin()); type_spec_flags |= entry_it->type_spec_flags; if (entry_it->value.dataType == Res_value::TYPE_ATTRIBUTE) { resid = entry_it->value.data; @@ -1536,6 +1529,7 @@ base::expected Theme::ResolveAttributeReference( } void Theme::Clear() { + keys_.clear(); entries_.clear(); } @@ -1547,11 +1541,12 @@ base::expected Theme::SetTo(const Theme& source) { type_spec_flags_ = source.type_spec_flags_; if (asset_manager_ == source.asset_manager_) { + keys_ = source.keys_; entries_ = source.entries_; } else { - std::map src_to_dest_asset_cookies; - typedef std::map SourceToDestinationRuntimePackageMap; - std::map src_asset_cookie_id_map; + std::unordered_map src_to_dest_asset_cookies; + using SourceToDestinationRuntimePackageMap = std::unordered_map; + std::unordered_map src_asset_cookie_id_map; // Determine which ApkAssets are loaded in both theme AssetManagers. const auto src_assets = source.asset_manager_->GetApkAssets(); @@ -1579,15 +1574,17 @@ base::expected Theme::SetTo(const Theme& source) { } src_to_dest_asset_cookies.insert(std::make_pair(i, j)); - src_asset_cookie_id_map.insert(std::make_pair(i, package_map)); + src_asset_cookie_id_map.insert(std::make_pair(i, std::move(package_map))); break; } } // Reset the data in the destination theme. + keys_.clear(); entries_.clear(); - for (const auto& entry : source.entries_) { + for (size_t i = 0, size = source.entries_.size(); i != size; ++i) { + const auto& entry = source.entries_[i]; bool is_reference = (entry.value.dataType == Res_value::TYPE_ATTRIBUTE || entry.value.dataType == Res_value::TYPE_REFERENCE || entry.value.dataType == Res_value::TYPE_DYNAMIC_ATTRIBUTE @@ -1627,13 +1624,15 @@ base::expected Theme::SetTo(const Theme& source) { } } + const auto source_res_id = source.keys_[i]; + // The package id of the attribute needs to be rewritten to the package id of the // attribute in the destination. - int attribute_dest_package_id = get_package_id(entry.attr_res_id); + int attribute_dest_package_id = get_package_id(source_res_id); if (attribute_dest_package_id != 0x01) { // Find the cookie of the attribute resource id in the source AssetManager base::expected attribute_entry_result = - source.asset_manager_->FindEntry(entry.attr_res_id, 0 /* density_override */ , + source.asset_manager_->FindEntry(source_res_id, 0 /* density_override */ , true /* stop_at_first_match */, true /* ignore_configuration */); if (UNLIKELY(IsIOError(attribute_entry_result))) { @@ -1657,16 +1656,15 @@ base::expected Theme::SetTo(const Theme& source) { attribute_dest_package_id = attribute_dest_package->second; } - auto dest_attr_id = make_resid(attribute_dest_package_id, get_type_id(entry.attr_res_id), - get_entry_id(entry.attr_res_id)); - Theme::Entry new_entry{dest_attr_id, data_dest_cookie, entry.type_spec_flags, - Res_value{.dataType = entry.value.dataType, - .data = attribute_data}}; - + auto dest_attr_id = make_resid(attribute_dest_package_id, get_type_id(source_res_id), + get_entry_id(source_res_id)); + const auto key_it = std::lower_bound(keys_.begin(), keys_.end(), dest_attr_id); + const auto entry_it = entries_.begin() + (key_it - keys_.begin()); // Since the entries were cleared, the attribute resource id has yet been mapped to any value. - auto entry_it = std::lower_bound(entries_.begin(), entries_.end(), dest_attr_id, - ThemeEntryKeyComparer{}); - entries_.insert(entry_it, new_entry); + keys_.insert(key_it, dest_attr_id); + entries_.insert(entry_it, Entry{data_dest_cookie, entry.type_spec_flags, + Res_value{.dataType = entry.value.dataType, + .data = attribute_data}}); } } return {}; @@ -1674,9 +1672,11 @@ base::expected Theme::SetTo(const Theme& source) { void Theme::Dump() const { LOG(INFO) << base::StringPrintf("Theme(this=%p, AssetManager2=%p)", this, asset_manager_); - for (auto& entry : entries_) { + for (size_t i = 0, size = keys_.size(); i != size; ++i) { + auto res_id = keys_[i]; + const auto& entry = entries_[i]; LOG(INFO) << base::StringPrintf(" entry(0x%08x)=(0x%08x) type=(0x%02x), cookie(%d)", - entry.attr_res_id, entry.value.data, entry.value.dataType, + res_id, entry.value.data, entry.value.dataType, entry.cookie); } } -- cgit v1.2.3-59-g8ed1b From dbce35604cdadfadc47492d7f75576365726d323 Mon Sep 17 00:00:00 2001 From: Yurii Zubrytskyi Date: Mon, 14 Nov 2022 22:26:10 -0800 Subject: [res] Reuse memory in RebuildFilterList() Original code deleted all allocated arrays to new' them back right away. Now, with new methods in ByteBucketArray the code only clears the vectors without releasing the capacity, and then proceeds to free the vectors that ended up not being used. This speeds up theme changes (accents / dark theme etc) by about 20% + small other improvements in ByteBucketArray Bug: 237583012 Test: build + UTs + boot Change-Id: I158af793e5476b4f3215dbe602daa872136d633f --- libs/androidfw/AssetManager2.cpp | 11 +++-- libs/androidfw/include/androidfw/ByteBucketArray.h | 50 ++++++++++++++++---- libs/androidfw/tests/ByteBucketArray_test.cpp | 53 ++++++++++++++++++++++ 3 files changed, 99 insertions(+), 15 deletions(-) (limited to 'libs/androidfw/AssetManager2.cpp') diff --git a/libs/androidfw/AssetManager2.cpp b/libs/androidfw/AssetManager2.cpp index 27b121b0cccc..2864c6843633 100644 --- a/libs/androidfw/AssetManager2.cpp +++ b/libs/androidfw/AssetManager2.cpp @@ -1356,21 +1356,22 @@ base::expected AssetManager2::GetResourceId( void AssetManager2::RebuildFilterList() { for (PackageGroup& group : package_groups_) { - for (ConfiguredPackage& impl : group.packages_) { - impl.filtered_configs_.clear(); - + for (ConfiguredPackage& package : group.packages_) { + package.filtered_configs_.forEachItem([](auto, auto& fcg) { fcg.type_entries.clear(); }); // Create the filters here. - impl.loaded_package_->ForEachTypeSpec([&](const TypeSpec& type_spec, uint8_t type_id) { + package.loaded_package_->ForEachTypeSpec([&](const TypeSpec& type_spec, uint8_t type_id) { FilteredConfigGroup* group = nullptr; for (const auto& type_entry : type_spec.type_entries) { if (type_entry.config.match(configuration_)) { if (!group) { - group = &impl.filtered_configs_.editItemAt(type_id - 1); + group = &package.filtered_configs_.editItemAt(type_id - 1); } group->type_entries.push_back(&type_entry); } } }); + package.filtered_configs_.trimBuckets( + [](const auto& fcg) { return fcg.type_entries.empty(); }); } } } diff --git a/libs/androidfw/include/androidfw/ByteBucketArray.h b/libs/androidfw/include/androidfw/ByteBucketArray.h index 05a2c4db8fe9..ca0a9eda9caa 100644 --- a/libs/androidfw/include/androidfw/ByteBucketArray.h +++ b/libs/androidfw/include/androidfw/ByteBucketArray.h @@ -17,6 +17,7 @@ #ifndef __BYTE_BUCKET_ARRAY_H #define __BYTE_BUCKET_ARRAY_H +#include #include #include @@ -36,15 +37,11 @@ class ByteBucketArray { } ~ByteBucketArray() { - clear(); + deleteBuckets(); } void clear() { - for (size_t i = 0; i < kNumBuckets; i++) { - if (buckets_[i] != NULL) { - delete[] buckets_[i]; - } - } + deleteBuckets(); memset(buckets_, 0, sizeof(buckets_)); } @@ -59,7 +56,7 @@ class ByteBucketArray { uint8_t bucket_index = static_cast(index) >> 4; T* bucket = buckets_[bucket_index]; - if (bucket == NULL) { + if (bucket == nullptr) { return default_; } return bucket[0x0f & static_cast(index)]; @@ -70,9 +67,9 @@ class ByteBucketArray { << ") with size=" << size(); uint8_t bucket_index = static_cast(index) >> 4; - T* bucket = buckets_[bucket_index]; - if (bucket == NULL) { - bucket = buckets_[bucket_index] = new T[kBucketSize](); + T*& bucket = buckets_[bucket_index]; + if (bucket == nullptr) { + bucket = new T[kBucketSize](); } return bucket[0x0f & static_cast(index)]; } @@ -86,9 +83,42 @@ class ByteBucketArray { return true; } + template + void forEachItem(Func f) { + for (size_t i = 0; i < kNumBuckets; i++) { + const auto bucket = buckets_[i]; + if (bucket != nullptr) { + for (size_t j = 0; j < kBucketSize; j++) { + f((i << 4) | j, bucket[j]); + } + } + } + } + + template + void trimBuckets(Func isEmptyFunc) { + for (size_t i = 0; i < kNumBuckets; i++) { + const auto bucket = buckets_[i]; + if (bucket != nullptr) { + if (std::all_of(bucket, bucket + kBucketSize, isEmptyFunc)) { + delete[] bucket; + buckets_[i] = nullptr; + } + } + } + } + private: enum { kNumBuckets = 16, kBucketSize = 16 }; + void deleteBuckets() { + for (size_t i = 0; i < kNumBuckets; i++) { + if (buckets_[i] != nullptr) { + delete[] buckets_[i]; + } + } + } + T* buckets_[kNumBuckets]; static inline const T default_ = {}; }; diff --git a/libs/androidfw/tests/ByteBucketArray_test.cpp b/libs/androidfw/tests/ByteBucketArray_test.cpp index 5d464c7dc0f7..9c36cfb212c5 100644 --- a/libs/androidfw/tests/ByteBucketArray_test.cpp +++ b/libs/androidfw/tests/ByteBucketArray_test.cpp @@ -52,4 +52,57 @@ TEST(ByteBucketArrayTest, TestSparseInsertion) { } } +TEST(ByteBucketArrayTest, TestForEach) { + ByteBucketArray bba; + ASSERT_TRUE(bba.set(0, 1)); + ASSERT_TRUE(bba.set(10, 2)); + ASSERT_TRUE(bba.set(26, 3)); + ASSERT_TRUE(bba.set(129, 4)); + ASSERT_TRUE(bba.set(234, 5)); + + int count = 0; + bba.forEachItem([&count](auto i, auto val) { + ++count; + switch (i) { + case 0: + EXPECT_EQ(1, val); + break; + case 10: + EXPECT_EQ(2, val); + break; + case 26: + EXPECT_EQ(3, val); + break; + case 129: + EXPECT_EQ(4, val); + break; + case 234: + EXPECT_EQ(5, val); + break; + default: + EXPECT_EQ(0, val); + break; + } + }); + ASSERT_EQ(4 * 16, count); +} + +TEST(ByteBucketArrayTest, TestTrimBuckets) { + ByteBucketArray bba; + ASSERT_TRUE(bba.set(0, 1)); + ASSERT_TRUE(bba.set(255, 2)); + { + bba.trimBuckets([](auto val) { return val < 2; }); + int count = 0; + bba.forEachItem([&count](auto, auto) { ++count; }); + ASSERT_EQ(1 * 16, count); + } + { + bba.trimBuckets([](auto val) { return val < 3; }); + int count = 0; + bba.forEachItem([&count](auto, auto) { ++count; }); + ASSERT_EQ(0, count); + } +} + } // namespace android -- cgit v1.2.3-59-g8ed1b From 9eb44c9727d83c9738819321b13d12a39cb10c55 Mon Sep 17 00:00:00 2001 From: Yurii Zubrytskyi Date: Mon, 14 Nov 2022 23:44:52 -0800 Subject: [res] Change callback from function to function_ref function_ref should be the default callback type if it's a function argument and won't get stored anywhere Bug: 237583012 Test: build + boot Change-Id: I1957665436f003f7a5e758b229640c9601c28faf --- libs/androidfw/AssetManager2.cpp | 12 ++++++++++++ libs/androidfw/include/androidfw/AssetManager2.h | 14 +++----------- 2 files changed, 15 insertions(+), 11 deletions(-) (limited to 'libs/androidfw/AssetManager2.cpp') diff --git a/libs/androidfw/AssetManager2.cpp b/libs/androidfw/AssetManager2.cpp index 2864c6843633..1b327018f681 100644 --- a/libs/androidfw/AssetManager2.cpp +++ b/libs/androidfw/AssetManager2.cpp @@ -1417,6 +1417,18 @@ std::unique_ptr AssetManager2::NewTheme() { return theme; } +void AssetManager2::ForEachPackage(base::function_ref func, + package_property_t excluded_property_flags) const { + for (const PackageGroup& package_group : package_groups_) { + const auto loaded_package = package_group.packages_.front().loaded_package_; + if ((loaded_package->GetPropertyFlags() & excluded_property_flags) == 0U + && !func(loaded_package->GetPackageName(), + package_group.dynamic_ref_table->mAssignedPackageId)) { + return; + } + } +} + Theme::Theme(AssetManager2* asset_manager) : asset_manager_(asset_manager) { } diff --git a/libs/androidfw/include/androidfw/AssetManager2.h b/libs/androidfw/include/androidfw/AssetManager2.h index c933fb38a22d..e4d1218debe6 100644 --- a/libs/androidfw/include/androidfw/AssetManager2.h +++ b/libs/androidfw/include/androidfw/AssetManager2.h @@ -17,6 +17,7 @@ #ifndef ANDROIDFW_ASSETMANAGER2_H_ #define ANDROIDFW_ASSETMANAGER2_H_ +#include "android-base/function_ref.h" #include "android-base/macros.h" #include @@ -320,17 +321,8 @@ class AssetManager2 { // Creates a new Theme from this AssetManager. std::unique_ptr NewTheme(); - void ForEachPackage(const std::function func, - package_property_t excluded_property_flags = 0U) const { - for (const PackageGroup& package_group : package_groups_) { - const auto loaded_package = package_group.packages_.front().loaded_package_; - if ((loaded_package->GetPropertyFlags() & excluded_property_flags) == 0U - && !func(loaded_package->GetPackageName(), - package_group.dynamic_ref_table->mAssignedPackageId)) { - return; - } - } - } + void ForEachPackage(base::function_ref func, + package_property_t excluded_property_flags = 0U) const; void DumpToLog() const; -- cgit v1.2.3-59-g8ed1b From 9d22537ee2ef820919e03cc1bf3024ae000194d9 Mon Sep 17 00:00:00 2001 From: Yurii Zubrytskyi Date: Tue, 29 Nov 2022 11:12:18 -0800 Subject: [res] Change OverlayableInfo to hold string views No need to copy the strings as we keep them in separate containers anyway, may just reference them Bug: 237583012 Test: build + boot + UTs Change-Id: I2853cd3c992ca482ed6988e0c52a4037b158d999 --- cmds/idmap2/libidmap2/ResourceMapping.cpp | 2 +- libs/androidfw/AssetManager2.cpp | 2 +- libs/androidfw/LoadedArsc.cpp | 12 ++++++------ libs/androidfw/include/androidfw/LoadedArsc.h | 4 ++-- 4 files changed, 10 insertions(+), 10 deletions(-) (limited to 'libs/androidfw/AssetManager2.cpp') diff --git a/cmds/idmap2/libidmap2/ResourceMapping.cpp b/cmds/idmap2/libidmap2/ResourceMapping.cpp index bb31c11d629c..b2300cea3a68 100644 --- a/cmds/idmap2/libidmap2/ResourceMapping.cpp +++ b/cmds/idmap2/libidmap2/ResourceMapping.cpp @@ -89,7 +89,7 @@ Result CheckOverlayable(const TargetResourceContainer& target, // If the overlay supplies a target overlayable name, the resource must belong to the // overlayable defined with the specified name to be overlaid. return Error(R"( android:targetName "%s" does not match overlayable name "%s")", - overlay_info.target_name.c_str(), (*overlayable_info)->name.c_str()); + overlay_info.target_name.c_str(), (*overlayable_info)->name.data()); } // Enforce policy restrictions if the resource is declared as overlayable. diff --git a/libs/androidfw/AssetManager2.cpp b/libs/androidfw/AssetManager2.cpp index 1b327018f681..cc7e8714c0ac 100644 --- a/libs/androidfw/AssetManager2.cpp +++ b/libs/androidfw/AssetManager2.cpp @@ -374,7 +374,7 @@ bool AssetManager2::GetOverlayablesToString(android::StringPiece package_name, const std::string name = ToFormattedResourceString(*res_name); output.append(base::StringPrintf( "resource='%s' overlayable='%s' actor='%s' policy='0x%08x'\n", - name.c_str(), info->name.c_str(), info->actor.c_str(), info->policy_flags)); + name.c_str(), info->name.data(), info->actor.data(), info->policy_flags)); } } } diff --git a/libs/androidfw/LoadedArsc.cpp b/libs/androidfw/LoadedArsc.cpp index 193c8650b2be..c0fdfe25da21 100644 --- a/libs/androidfw/LoadedArsc.cpp +++ b/libs/androidfw/LoadedArsc.cpp @@ -648,10 +648,11 @@ std::unique_ptr LoadedPackage::Load(const Chunk& chunk, util::ReadUtf16StringFromDevice(overlayable->name, std::size(overlayable->name), &name); std::string actor; util::ReadUtf16StringFromDevice(overlayable->actor, std::size(overlayable->actor), &actor); - auto [it, inserted] = - loaded_package->overlayable_map_.emplace(name, actor); + auto [name_to_actor_it, inserted] = + loaded_package->overlayable_map_.emplace(std::move(name), std::move(actor)); if (!inserted) { - LOG(ERROR) << "Multiple blocks with the same name '" << it->first << "'."; + LOG(ERROR) << "Multiple blocks with the same name '" + << name_to_actor_it->first << "'."; return {}; } @@ -668,7 +669,6 @@ std::unique_ptr LoadedPackage::Load(const Chunk& chunk, LOG(ERROR) << "RES_TABLE_OVERLAYABLE_POLICY_TYPE too small."; return {}; } - if ((overlayable_child_chunk.data_size() / sizeof(ResTable_ref)) < dtohl(policy_header->entry_count)) { LOG(ERROR) << "RES_TABLE_OVERLAYABLE_POLICY_TYPE too small to hold entries."; @@ -690,8 +690,8 @@ std::unique_ptr LoadedPackage::Load(const Chunk& chunk, // Add the pairing of overlayable properties and resource ids to the package OverlayableInfo overlayable_info { - .name = name, - .actor = actor, + .name = name_to_actor_it->first, + .actor = name_to_actor_it->second, .policy_flags = policy_header->policy_flags }; loaded_package->overlayable_infos_.emplace_back(std::move(overlayable_info), std::move(ids)); diff --git a/libs/androidfw/include/androidfw/LoadedArsc.h b/libs/androidfw/include/androidfw/LoadedArsc.h index 4ab004299500..4d12885ad291 100644 --- a/libs/androidfw/include/androidfw/LoadedArsc.h +++ b/libs/androidfw/include/androidfw/LoadedArsc.h @@ -99,8 +99,8 @@ enum : package_property_t { }; struct OverlayableInfo { - std::string name; - std::string actor; + std::string_view name; + std::string_view actor; uint32_t policy_flags; }; -- cgit v1.2.3-59-g8ed1b