Skip to contentSkip to conversation

mm/damon/ops-common: optimize damon_hot_score() using ilog2()

PATCH New Liew Rui Yan 1 participant 1 message Mar 21

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH v3 1/1 mm/damon/ops-common: optimize damon_hot_score() using ilog2()

The current implementation of damon_hot_score() uses a manual for-loop to calculate the value of 'age_in_log'. This can be efficiently replaced by ilog2(), which is semantically more appropriate for calculating the logarithmic value of age.

In a simulated-kernel-module performance test with 10,000,000 iterations, this optimization showed a significant reduction in latency (average latency reduced from ~12ns to ~1ns).

Test results from the simulated-kernel-module:
- ilog2:
DAMON Perf Test: Starting 10000000 iterations
=============================================
Total Iterations : 10000000
Average Latency : 1 ns
P95 Latency : 41 ns
P99 Latency : 41 ns
---------------------------------------------
Range (ns) | Count | Percent
---------------------------------------------
0-19 | 0 | 0%
20-39 | 2625000 | 26%
40-59 | 7374000 | 73%
60-79 | 0 | 0%
80-99 | 0 | 0%
100+ | 1000 | 0%
=============================================

- for-loop:

    DAMON Perf Test: Starting 10000000 iterations
    =============================================
     Total Iterations : 10000000
     Average Latency  : 12 ns
     P95 Latency      : 51 ns
     P99 Latency      : 60 ns
    ---------------------------------------------
     Range (ns)      | Count        | Percent
    ---------------------------------------------
     0-19            | 0            |      0%
     20-39           | 0            |      0%
     40-59           | 9862000      |     98%
     60-79           | 135000       |      1%
     80-99           | 1000         |      0%
     100+            | 2000         |      0%
    =============================================

Full raw benchmark results can be found at [1].

[1] https://github.com/aethernet65535/damon-hot-score-fls-optimize/tree/master/result-raw

---
Changes from v2:
- Send as a new thread instead of a reply to previous version.
- Add SeongJae Park's Reviewed-by tag.
- Link to v2: https://lore.kernel.org/[email protected]

Changes from v1:
- Replace fls() with ilog2() per SeongJae Park's suggestion for better semantic clarity.
- Move performance benchmark results into the commit message and add comparison between for-loop and ilog2.
- Link to v1: https://lore.kernel.org/[email protected]/

 mm/damon/ops-common.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)
mm/damon/ops-common.c +6 -3
index a218d9922234..ac604fb7b409 100644
@@ -117,9 +117,12 @@ int damon_hot_score(struct damon_ctx *c, struct damon_region *r,
 		damon_max_nr_accesses(&c->attrs);
 
 	age_in_sec = (unsigned long)r->age * c->attrs.aggr_interval / 1000000;
-	for (age_in_log = 0; age_in_log < DAMON_MAX_AGE_IN_LOG && age_in_sec;
-			age_in_log++, age_in_sec >>= 1)
-		;
+	if (age_in_sec)
+		age_in_log = min_t(int, ilog2(age_in_sec) + 1,
+				DAMON_MAX_AGE_IN_LOG);
+	else
+		age_in_log = 0;
+
 
 	/* If frequency is 0, higher age means it's colder */
 	if (freq_subscore == 0)
Signature · 1 line
2.53.0