[PATCH] perf/x86/amd/lbr: Compress branch stack in a single pass

[Sandipan Das <sandipan.das@amd.com>]

Software filtering removes rejected branch records by shifting the
entire tail of the array down by one for each dropped entry. With k
invalid entries out of n, this costs O(k*n) copies. Switch to a two
pointer compaction that walks the array once and packs the remaining
entries towards the front, moving each entry at most once, for O(n)
total. No functional change intended.

Signed-off-by: Sandipan Das <sandipan.das@amd.com>
---
 arch/x86/events/amd/lbr.c | 17 +++++++----------
 1 file changed, 7 insertions(+), 10 deletions(-)

diff --git a/arch/x86/events/amd/lbr.c b/arch/x86/events/amd/lbr.c
index a55646fcb846..1e1b2f08cb51 100644
--- a/arch/x86/events/amd/lbr.c
+++ b/arch/x86/events/amd/lbr.c
@@ -141,17 +141,14 @@ static void amd_pmu_lbr_filter(void)
 		return;
 
 	/* Remove all invalid entries */
-	for (i = 0; i < cpuc->lbr_stack.nr; ) {
-		if (!cpuc->lbr_entries[i].from) {
-			j = i;
-			while (++j < cpuc->lbr_stack.nr)
-				cpuc->lbr_entries[j - 1] = cpuc->lbr_entries[j];
-			cpuc->lbr_stack.nr--;
-			if (!cpuc->lbr_entries[i].from)
-				continue;
-		}
-		i++;
+	for (i = 0, j = 0; i < cpuc->lbr_stack.nr; i++) {
+		if (!cpuc->lbr_entries[i].from)
+			continue;
+		if (j != i)
+			cpuc->lbr_entries[j] = cpuc->lbr_entries[i];
+		j++;
 	}
+	cpuc->lbr_stack.nr = j;
 }
 
 static const int lbr_spec_map[PERF_BR_SPEC_MAX] = {
-- 
2.53.0