Replace vector usage in collect_vma with map
This change updates the collect_vma callback in showmap.cpp to use a map
to accumulate VMAs instead of a vector. This is done because the
insertion function used for the -a (address) and -v (verbose) options is
expensive, and is done in O(# of VMAs) time. This improves the runtime
complexity to O(log(# of VMAs)). collect_vma_merge_by_names has been
combined with collect_vma.
This drastically improves showmap's CPU usage. Over 3 trials each:
1) showmap -a: 37% reduction in CPU cycles spent in showmap
2) showmap -v: 67% reduction "
3) showmap -a -v: 35% reduction "
Test: Check that showmap still functions as expected (with various
options); measure CPU improvements.
Bug: 229147699
Change-Id: I6d9d40189883a98f4f434ac940967561d9cf26fb
diff --git a/tools/showmap.cpp b/tools/showmap.cpp
index 0377c22..51bbda1 100644
--- a/tools/showmap.cpp
+++ b/tools/showmap.cpp
@@ -34,15 +34,16 @@
#include <android-base/strings.h>
#include <meminfo/procmeminfo.h>
+using ::android::base::StringPrintf;
using ::android::meminfo::EscapeCsvString;
using ::android::meminfo::EscapeJsonString;
using ::android::meminfo::Format;
using ::android::meminfo::GetFormat;
+using ::android::meminfo::MemUsage;
using ::android::meminfo::Vma;
// Global options
static std::string g_filename;
-static bool g_merge_by_names = false;
static bool g_terse = false;
static bool g_verbose = false;
static bool g_show_addr = false;
@@ -199,9 +200,7 @@
output << ",\"object\":" << EscapeJsonString(get_vma_name(vma, total, is_bss)) << "}";
}
-static VmaInfo g_total;
-static std::vector<VmaInfo> g_vmas;
-static std::map<std::string, VmaInfo> g_vmas_name_map;
+static std::multimap<std::string, VmaInfo> g_vmas;
[[noreturn]] static void usage(const char* progname, int exit_status) {
std::cerr << progname << " [-aqtv] [-f FILE] PID\n"
@@ -220,14 +219,6 @@
return (name.size() > 4) && (name[0] == '/') && ::android::base::EndsWith(name, ".so");
}
-static bool insert_before(const VmaInfo& a, const VmaInfo& b) {
- if (g_show_addr) {
- return (a.vma.start < b.vma.start || (a.vma.start == b.vma.start && a.vma.end < b.vma.end));
- }
-
- return strcmp(a.vma.name.c_str(), b.vma.name.c_str()) < 0;
-}
-
static void infer_vma_name(VmaInfo& current, const VmaInfo& recent) {
if (current.vma.name.empty()) {
if (recent.vma.end == current.vma.start && is_library(recent.vma.name)) {
@@ -239,11 +230,40 @@
}
}
+static void add_mem_usage(MemUsage* to, const MemUsage& from) {
+ to->vss += from.vss;
+ to->rss += from.rss;
+ to->pss += from.pss;
+
+ to->swap += from.swap;
+ to->swap_pss += from.swap_pss;
+
+ to->private_clean += from.private_clean;
+ to->private_dirty += from.private_dirty;
+ to->shared_clean += from.shared_clean;
+ to->shared_dirty += from.shared_dirty;
+
+ to->anon_huge_pages += from.anon_huge_pages;
+ to->shmem_pmd_mapped += from.shmem_pmd_mapped;
+ to->file_pmd_mapped += from.file_pmd_mapped;
+ to->shared_hugetlb += from.shared_hugetlb;
+ to->private_hugetlb += from.private_hugetlb;
+}
+
static void collect_vma(const Vma& vma) {
static VmaInfo recent;
VmaInfo current(vma);
+
+ std::string key;
+ if (g_show_addr) {
+ // vma.end is included in case vma.start is identical for two VMAs.
+ key = StringPrintf("%16" PRIx64 "%16" PRIx64, vma.start, vma.end);
+ } else {
+ key = vma.name;
+ }
+
if (g_vmas.empty()) {
- g_vmas.emplace_back(current);
+ g_vmas.emplace(key, current);
recent = current;
return;
}
@@ -251,54 +271,29 @@
infer_vma_name(current, recent);
recent = current;
- std::vector<VmaInfo>::iterator it;
- for (it = g_vmas.begin(); it != g_vmas.end(); it++) {
- if (insert_before(current, *it)) {
- g_vmas.insert(it, current);
- break;
- }
- }
-
- if (it == g_vmas.end()) {
- g_vmas.emplace_back(current);
- }
-}
-
-static void collect_vma_merge_by_names(const Vma& vma) {
- static VmaInfo recent;
- VmaInfo current(vma);
- if (g_vmas_name_map.empty()) {
- g_vmas_name_map.emplace(vma.name, vma);
- recent = current;
+ // If sorting by address, the VMA can be placed into the map as-is.
+ if (g_show_addr) {
+ g_vmas.emplace(key, current);
return;
}
- infer_vma_name(current, recent);
- recent = current;
-
- auto iter = g_vmas_name_map.find(current.vma.name);
- if (iter == g_vmas_name_map.end()) {
- g_vmas_name_map.emplace(current.vma.name, current);
+ // infer_vma_name() may have changed current.vma.name, so this key needs to be set again before
+ // using it to sort by name. For verbose output, the VMA can immediately be placed into the map.
+ key = current.vma.name;
+ if (g_verbose) {
+ g_vmas.emplace(key, current);
return;
}
+
+ // Coalesces VMAs' usage by name, if !g_show_addr && !g_verbose.
+ auto iter = g_vmas.find(key);
+ if (iter == g_vmas.end()) {
+ g_vmas.emplace(key, current);
+ return;
+ }
+
VmaInfo& match = iter->second;
- match.vma.usage.vss += current.vma.usage.vss;
- match.vma.usage.rss += current.vma.usage.rss;
- match.vma.usage.pss += current.vma.usage.pss;
-
- match.vma.usage.shared_clean += current.vma.usage.shared_clean;
- match.vma.usage.shared_dirty += current.vma.usage.shared_dirty;
- match.vma.usage.private_clean += current.vma.usage.private_clean;
- match.vma.usage.private_dirty += current.vma.usage.private_dirty;
- match.vma.usage.swap += current.vma.usage.swap;
- match.vma.usage.swap_pss += current.vma.usage.swap_pss;
-
- match.vma.usage.anon_huge_pages += current.vma.usage.anon_huge_pages;
- match.vma.usage.shmem_pmd_mapped += current.vma.usage.shmem_pmd_mapped;
- match.vma.usage.file_pmd_mapped += current.vma.usage.file_pmd_mapped;
- match.vma.usage.shared_hugetlb += current.vma.usage.shared_hugetlb;
- match.vma.usage.private_hugetlb += current.vma.usage.shared_hugetlb;
-
+ add_mem_usage(&match.vma.usage, current.vma.usage);
match.is_bss &= current.is_bss;
}
@@ -339,19 +334,7 @@
}
static int showmap(Format format) {
- bool success;
- if (!g_merge_by_names) {
- success = ::android::meminfo::ForEachVmaFromFile(g_filename, collect_vma);
- } else {
- success = ::android::meminfo::ForEachVmaFromFile(g_filename, collect_vma_merge_by_names);
- g_vmas.reserve(g_vmas_name_map.size());
- // VMAs will be returned in lexicographical order of names.
- for (const auto& entry : g_vmas_name_map) {
- g_vmas.emplace_back(entry.second);
- }
- }
-
- if (!success) {
+ if (!::android::meminfo::ForEachVmaFromFile(g_filename, collect_vma)) {
if (!g_quiet) {
std::cerr << "Failed to parse file " << g_filename << "\n";
}
@@ -389,20 +372,10 @@
break;
}
- for (const auto& v : g_vmas) {
- g_total.vma.usage.vss += v.vma.usage.vss;
- g_total.vma.usage.rss += v.vma.usage.rss;
- g_total.vma.usage.pss += v.vma.usage.pss;
-
- g_total.vma.usage.private_clean += v.vma.usage.private_clean;
- g_total.vma.usage.private_dirty += v.vma.usage.private_dirty;
- g_total.vma.usage.shared_clean += v.vma.usage.shared_clean;
- g_total.vma.usage.shared_dirty += v.vma.usage.shared_dirty;
-
- g_total.vma.usage.swap += v.vma.usage.swap;
- g_total.vma.usage.swap_pss += v.vma.usage.swap_pss;
- g_total.count += v.count;
-
+ VmaInfo total_usage;
+ for (const auto& entry : g_vmas) {
+ const VmaInfo& v = entry.second;
+ add_mem_usage(&total_usage.vma.usage, v.vma.usage);
if (g_terse && !(v.vma.usage.private_dirty || v.vma.usage.private_clean)) {
continue;
}
@@ -429,13 +402,13 @@
print_divider(std::cout);
print_header(std::cout);
print_divider(std::cout);
- g_total.to_raw(std::cout, true);
+ total_usage.to_raw(std::cout, true);
break;
case Format::CSV:
- g_total.to_csv(std::cout, true);
+ total_usage.to_csv(std::cout, true);
break;
case Format::JSON:
- g_total.to_json(std::cout, true);
+ total_usage.to_json(std::cout, true);
std::cout << "]\n";
break;
default:
@@ -500,6 +473,5 @@
g_filename = ::android::base::StringPrintf("/proc/%d/smaps", g_pid);
}
- g_merge_by_names = !g_verbose && !g_show_addr;
return showmap(format);
}
