[res] Stop using try_emplace for hash maps

1. Turns out libcxx's try_emplace() on unordered containers is
slower than even find + insert pair. Revert the 'optimization'
back to get the performance back

2. Fix the cache invalidation in AssetManager to keep the caches
coherent.

Bug: 282264161
Test: build + UTs + boot
Change-Id: I823215beb863c0ffaf703c70bb4358c331da8251

3 files changed, 183 insertions, 15 deletions

diff --git a/libs/androidfw/Android.bp b/libs/androidfw/Android.bp
index 28bda72bccdd..fa9447afbeab 100644
--- a/libs/androidfw/Android.bp
+++ b/libs/androidfw/Android.bp
@@ -232,6 +232,7 @@ cc_benchmark {
         "tests/AssetManager2_bench.cpp",
         "tests/AttributeResolution_bench.cpp",
         "tests/CursorWindow_bench.cpp",
+        "tests/Generic_bench.cpp",
         "tests/SparseEntry_bench.cpp",
         "tests/Theme_bench.cpp",
     ],
diff --git a/libs/androidfw/AssetManager2.cpp b/libs/androidfw/AssetManager2.cpp
index e3f0c8fcf3bf..4d434710589e 100644
--- a/libs/androidfw/AssetManager2.cpp
+++ b/libs/androidfw/AssetManager2.cpp
@@ -1094,14 +1094,16 @@ base::expected<std::monostate, NullOrIOError> AssetManager2::ResolveReference(
 
 base::expected<const std::vector<uint32_t>*, NullOrIOError> AssetManager2::GetBagResIdStack(
     uint32_t resid) const {
-  auto [it, inserted] = cached_bag_resid_stacks_.try_emplace(resid);
-  if (inserted) {
-    // This is a new entry in the cache, need to populate it.
-    if (auto maybe_bag = GetBag(resid, it->second); UNLIKELY(IsIOError(maybe_bag))) {
-      cached_bag_resid_stacks_.erase(it);
-      return base::unexpected(maybe_bag.error());
-    }
+  auto it = cached_bag_resid_stacks_.find(resid);
+  if (it != cached_bag_resid_stacks_.end()) {
+    return &it->second;
+  }
+  std::vector<uint32_t> stacks;
+  if (auto maybe_bag = GetBag(resid, stacks); UNLIKELY(IsIOError(maybe_bag))) {
+    return base::unexpected(maybe_bag.error());
   }
+
+  it = cached_bag_resid_stacks_.emplace(resid, std::move(stacks)).first;
   return &it->second;
 }
 
@@ -1119,8 +1121,12 @@ base::expected<const ResolvedBag*, NullOrIOError> AssetManager2::ResolveBag(
 }
 
 base::expected<const ResolvedBag*, NullOrIOError> AssetManager2::GetBag(uint32_t resid) const {
-  auto [resid_stacks_it, _] = cached_bag_resid_stacks_.try_emplace(resid);
-  resid_stacks_it->second.clear();
+  auto resid_stacks_it = cached_bag_resid_stacks_.find(resid);
+  if (resid_stacks_it != cached_bag_resid_stacks_.end()) {
+    resid_stacks_it->second.clear();
+  } else {
+    resid_stacks_it = cached_bag_resid_stacks_.emplace(resid, std::vector<uint32_t>{}).first;
+  }
   const auto bag = GetBag(resid, resid_stacks_it->second);
   if (UNLIKELY(IsIOError(bag))) {
     cached_bag_resid_stacks_.erase(resid_stacks_it);
@@ -1438,25 +1444,40 @@ void AssetManager2::RebuildFilterList() {
 }
 
 void AssetManager2::InvalidateCaches(uint32_t diff) {
-  cached_bag_resid_stacks_.clear();
+  cached_resolved_values_.clear();
 
   if (diff == 0xffffffffu) {
     // Everything must go.
     cached_bags_.clear();
+    cached_bag_resid_stacks_.clear();
     return;
   }
 
   // Be more conservative with what gets purged. Only if the bag has other possible
   // variations with respect to what changed (diff) should we remove it.
-  for (auto iter = cached_bags_.cbegin(); iter != cached_bags_.cend();) {
-    if (diff & iter->second->type_spec_flags) {
-      iter = cached_bags_.erase(iter);
+  for (auto stack_it = cached_bag_resid_stacks_.begin();
+       stack_it != cached_bag_resid_stacks_.end();) {
+    const auto it = cached_bags_.find(stack_it->first);
+    if (it == cached_bags_.end()) {
+      stack_it = cached_bag_resid_stacks_.erase(stack_it);
+    } else if ((diff & it->second->type_spec_flags) != 0) {
+      cached_bags_.erase(it);
+      stack_it = cached_bag_resid_stacks_.erase(stack_it);
     } else {
-      ++iter;
+      ++stack_it;  // Keep the item in both caches.
     }
   }
 
-  cached_resolved_values_.clear();
+  // Need to ensure that both bag caches are consistent, as we populate them in the same function.
+  // Iterate over the cached bags to erase the items without the corresponding resid_stack cache
+  // items.
+  for (auto it = cached_bags_.begin(); it != cached_bags_.end();) {
+    if ((diff & it->second->type_spec_flags) != 0) {
+      it = cached_bags_.erase(it);
+    } else {
+      ++it;
+    }
+  }
 }
 
 uint8_t AssetManager2::GetAssignedPackageId(const LoadedPackage* package) const {
diff --git a/libs/androidfw/tests/Generic_bench.cpp b/libs/androidfw/tests/Generic_bench.cpp
new file mode 100644
index 000000000000..4c978e889f83
--- /dev/null
+++ b/libs/androidfw/tests/Generic_bench.cpp
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+
+#include <stdint.h>
+
+#include <map>
+#include <unordered_map>
+
+#include "benchmark/benchmark.h"
+
+namespace android {
+
+template <class Map = std::unordered_map<uint32_t, std::vector<uint32_t>>>
+static Map prepare_map() {
+  Map map;
+  std::vector<uint32_t> vec;
+  for (int i = 0; i < 1000; ++i) {
+    map.emplace(i, vec);
+  }
+  return map;
+}
+
+static void BM_hashmap_emplace_same(benchmark::State& state) {
+  auto map = prepare_map<>();
+  auto val = map.size() - 1;
+  std::vector<uint32_t> vec;
+  for (auto&& _ : state) {
+    benchmark::DoNotOptimize(map.emplace(val, vec));
+  }
+}
+BENCHMARK(BM_hashmap_emplace_same);
+static void BM_hashmap_try_emplace_same(benchmark::State& state) {
+  auto map = prepare_map();
+  auto val = map.size() - 1;
+  for (auto&& _ : state) {
+    benchmark::DoNotOptimize(map.try_emplace(val));
+  }
+}
+BENCHMARK(BM_hashmap_try_emplace_same);
+static void BM_hashmap_find(benchmark::State& state) {
+  auto map = prepare_map<>();
+  auto val = map.size() - 1;
+  for (auto&& _ : state) {
+    benchmark::DoNotOptimize(map.find(val));
+  }
+}
+BENCHMARK(BM_hashmap_find);
+
+static void BM_hashmap_emplace_diff(benchmark::State& state) {
+  auto map = prepare_map<>();
+  std::vector<uint32_t> vec;
+  auto i = map.size();
+  for (auto&& _ : state) {
+    map.emplace(i++, vec);
+  }
+}
+BENCHMARK(BM_hashmap_emplace_diff);
+static void BM_hashmap_try_emplace_diff(benchmark::State& state) {
+  auto map = prepare_map();
+  auto i = map.size();
+  for (auto&& _ : state) {
+    map.try_emplace(i++);
+  }
+}
+BENCHMARK(BM_hashmap_try_emplace_diff);
+static void BM_hashmap_find_emplace_diff(benchmark::State& state) {
+  auto map = prepare_map<>();
+  std::vector<uint32_t> vec;
+  auto i = map.size();
+  for (auto&& _ : state) {
+    if (map.find(i++) == map.end()) {
+      map.emplace(i - 1, vec);
+    }
+  }
+}
+BENCHMARK(BM_hashmap_find_emplace_diff);
+
+static void BM_treemap_emplace_same(benchmark::State& state) {
+  auto map = prepare_map<std::map<uint32_t, std::vector<uint32_t>>>();
+  auto val = map.size() - 1;
+  std::vector<uint32_t> vec;
+  for (auto&& _ : state) {
+    benchmark::DoNotOptimize(map.emplace(val, vec));
+  }
+}
+BENCHMARK(BM_treemap_emplace_same);
+static void BM_treemap_try_emplace_same(benchmark::State& state) {
+  auto map = prepare_map<std::map<uint32_t, std::vector<uint32_t>>>();
+  auto val = map.size() - 1;
+  for (auto&& _ : state) {
+    benchmark::DoNotOptimize(map.try_emplace(val));
+  }
+}
+BENCHMARK(BM_treemap_try_emplace_same);
+static void BM_treemap_find(benchmark::State& state) {
+  auto map = prepare_map<std::map<uint32_t, std::vector<uint32_t>>>();
+  auto val = map.size() - 1;
+  for (auto&& _ : state) {
+    benchmark::DoNotOptimize(map.find(val));
+  }
+}
+BENCHMARK(BM_treemap_find);
+
+static void BM_treemap_emplace_diff(benchmark::State& state) {
+  auto map = prepare_map<std::map<uint32_t, std::vector<uint32_t>>>();
+  std::vector<uint32_t> vec;
+  auto i = map.size();
+  for (auto&& _ : state) {
+    map.emplace(i++, vec);
+  }
+}
+BENCHMARK(BM_treemap_emplace_diff);
+static void BM_treemap_try_emplace_diff(benchmark::State& state) {
+  auto map = prepare_map();
+  auto i = map.size();
+  for (auto&& _ : state) {
+    map.try_emplace(i++);
+  }
+}
+BENCHMARK(BM_treemap_try_emplace_diff);
+static void BM_treemap_find_emplace_diff(benchmark::State& state) {
+  auto map = prepare_map();
+  std::vector<uint32_t> vec;
+  auto i = map.size();
+  for (auto&& _ : state) {
+    if (map.find(i++) == map.end()) {
+      map.emplace(i - 1, vec);
+    }
+  }
+}
+BENCHMARK(BM_treemap_find_emplace_diff);
+
+}  // namespace android
\ No newline at end of file