llvm-cov export spends most of its time in skipOtherFiles

[jonhoo]

As part of digging into a performance issue in a tool built on top of llvm-cov (specifically, it calls llvm-cov export), I realized that llvm-cov export was taking upwards of 4s to run on a modestly-sized input. That is, it takes 4s to complete this invocation:

llvm-cov export some-binary --instr-profile some.profdata --format lcov > /dev/null

where some-binary is a Rust binary of about 370M and some.profdata is 4M. And, during this time, llvm-cov appears to be saturating a single core on my multi-core host.

I built llvm-cov from the source in main and ran it through perf and Valgrind, and an interesting picture emerged (Firefox profiler visualization). llvm-cov appears to be spending a majority of its time in

llvm-project/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

Lines 209 to 215 in 88b7e8e

	void FunctionRecordIterator::skipOtherFiles() {
	while (Current != Records.end() && !Filename.empty() &&
	Filename != Current->Filenames[0])
	++Current;
	if (Current == Records.end())
	*this = FunctionRecordIterator();
	}

The calls to that function appear to stem from this call in renderFile:

llvm-project/llvm/tools/llvm-cov/CoverageExporterLcov.cpp

Lines 179 to 181 in cae2a36

	if (!ExportSummaryOnly && !SkipFunctions) {
	renderFunctions(OS, Coverage.getCoveredFunctions(Filename));
	}

Which is ultimately called from CoverageExporterLcov::renderRoot via renderFiles.

Valgrind appears to struggle to follow the full call-graph, but from what I can see, it appears that skipOtherFiles is called upwards of 650k times. It also appears to be the case that renderRoot is itself called 300k times (possibly by itself — the call graph is unclear). In other words, it's not clear that skipOtherFiles itself is the problem (although it is doing a linear search as part of an iterator if I read it correctly?); the problem may be in the number of times it gets called. Perhaps some caching of its results are warranted?

My lack of LLVM knowledge is preventing me from digging much further into this, but I'd be happy to run additional commands/instrument llvm-cov in whatever ways may be helpful to surface more information to track down the underlying issue.

In case it matters, I'm running on an AArch64 host.

[jonhoo]

cc @bcardosolopes perhaps who has done some performance optimization work on llvm-cov in the past.

[jonhoo]

cc @tunz and @vedantk who also landed llvm-cov performance improvements previously

EDIT: Oh, and perhaps @mysterymath since you seem to be the person who's generally contributing to coverage work these days.

[glandium]

I have some work in progress that brings down a llvm-cov run on Firefox's libxul.so with a 2.5MB profile from 13 minutes down to 19 seconds. I'll open a PR when I'm 100% confident it doesn't break anything.