Skip to contentSkip to conversation

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

RFC PATCH Superseded Liew Rui Yan 2 participants 4 messages Mar 20 – Mar 21

Subsystems (2)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 mm/damon/ops-common: optimize damon_hot_score() using fls()

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 the fls().

In a simulated performance test with 10,000,000 iterations, this optimization showed a significant reduction in latency:
- Average Latency: Reduced from ~9ns to ~1ns.
- P99 Latency: Reduced from ~60ns to ~41ns.
- Throughput: The loop-based version mostly fell into the 40-50ns range, while the fls-based version shifted significantly towards the 20-39ns range in the test environment.

Although these results are based on a simulated kernel module test environment [1], they indicate a clear instruction-level optimization.

[1] https://github.com/aethernet65535/damon-hot-score-fls-optimize/blob/master/test-kernel-module/fls.c

---
Note on testing methodology:
I attempted to measure the performance directly within the kernel using bpftrace, perf, and ktime inside damon_hot_score(). However, the results were highly unstable (ktime), and in some cases (perf/bpftrace) the function was difficult to trace reliably (likely due to my own tracing limitations).

Despite the instability of in-kernel ktime measurements, one thing remained consistent: the fls-based version significantly improves the "long tail" latency compared to the for-loop.

Test results from the simulated module:
- fls-based:

    DAMON Perf Test: Starting 10000000 iterations
    =============================================
     Total Iterations : 10000000
     Average Latency  : 1 ns
     P95 Latency      : 40 ns
     P99 Latency      : 41 ns
    ---------------------------------------------
     Range (ns)      | Count    | Percent
    ---------------------------------------------
     20-39           | 3522000  |   35%
     40-59           | 6478000  |   64%
     60-79           | 0        |    0%
    =============================================

- for-loop:

    DAMON Perf Test: Starting 10000000 iterations
    =============================================
     Total Iterations : 10000000
     Average Latency  : 9 ns
     P95 Latency      : 51 ns
     P99 Latency      : 60 ns
    ---------------------------------------------
     Range (ns)      | Count    | Percent
    ---------------------------------------------
     20-39           | 0        |    0%
     40-59           | 9894000  |   98%
     60-79           | 98000    |    0%
    =============================================

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

If anyone could suggest a more robust way to profile this specific function within live DAMON context, I would greatly appreciate the guidance.

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

 mm/damon/ops-common.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)
mm/damon/ops-common.c +1 -3
index 8c6d613425c1..0294de61a23a 100644
@@ -117,9 +117,7 @@ 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)
-		;
+	age_in_log = min_t(int, fls(age_in_sec), DAMON_MAX_AGE_IN_LOG);
 
 	/* If frequency is 0, higher age means it's colder */
 	if (freq_subscore == 0)
Signature · 1 line
2.53.0
maintainer
#1 lore raw

Hello Liew,

Quoted 3 lines · On Fri, 20 Mar 2026 15:24:31 +0800 Liew Rui Yan <[email protected]>…

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 the fls().

This makes sense. But, it seems ilog2() looks more same to what the current code is trying to do. How about using ilog2() instead of fls()?

Quoted 9 lines

In a simulated performance test with 10,000,000 iterations, this optimization showed a significant reduction in latency:
- Average Latency: Reduced from ~9ns to ~1ns.
- P99 Latency: Reduced from ~60ns to ~41ns.
- Throughput: The loop-based version mostly fell into the 40-50ns range, while the fls-based version shifted significantly towards the 20-39ns range in the test environment.

Quoted 4 lines

Although these results are based on a simulated kernel module test environment [1], they indicate a clear instruction-level optimization.

[1] https://github.com/aethernet65535/damon-hot-score-fls-optimize/blob/master/test-kernel-module/fls.c

Makes sense!

Quoted 45 lines

---
Note on testing methodology:
I attempted to measure the performance directly within the kernel using bpftrace, perf, and ktime inside damon_hot_score(). However, the results were highly unstable (ktime), and in some cases (perf/bpftrace) the function was difficult to trace reliably (likely due to my own tracing limitations).

Despite the instability of in-kernel ktime measurements, one thing remained consistent: the fls-based version significantly improves the "long tail" latency compared to the for-loop.

Test results from the simulated module:
- fls-based:

    DAMON Perf Test: Starting 10000000 iterations
    =============================================
     Total Iterations : 10000000
     Average Latency  : 1 ns
     P95 Latency      : 40 ns
     P99 Latency      : 41 ns
    ---------------------------------------------
     Range (ns)      | Count    | Percent
    ---------------------------------------------
     20-39           | 3522000  |   35%
     40-59           | 6478000  |   64%
     60-79           | 0        |    0%
    =============================================

- for-loop:

    DAMON Perf Test: Starting 10000000 iterations
    =============================================
     Total Iterations : 10000000
     Average Latency  : 9 ns
     P95 Latency      : 51 ns
     P99 Latency      : 60 ns
    ---------------------------------------------
     Range (ns)      | Count    | Percent
    ---------------------------------------------
     20-39           | 0        |    0%
     40-59           | 9894000  |   98%
     60-79           | 98000    |    0%
    =============================================
Quoted 7 lines

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

If anyone could suggest a more robust way to profile this specific function within live DAMON context, I would greatly appreciate the guidance.

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

Nice test results! I think this deserves to be in the git history. Could you please add this on the commit message area, rather than this commentary area in the next version?

Quoted 21 lines
 mm/damon/ops-common.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)
mm/damon/ops-common.c +1 -3
index 8c6d613425c1..0294de61a23a 100644
@@ -117,9 +117,7 @@ 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)
-		;
+	age_in_log = min_t(int, fls(age_in_sec), DAMON_MAX_AGE_IN_LOG);
 
 	/* If frequency is 0, higher age means it's colder */
 	if (freq_subscore == 0)
Signature · 1 line
2.53.0

Thanks,
SJ

#2 lore raw

PATCH v2 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 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.

 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
maintainer Reviewed-by on v2 1/1
#3 lore raw

Re: [PATCH v2] mm/damon/ops-common: optimize damon_hot_score() using ilog2()

Hello Liew,

When you send a new version of patches, please send those as new thread, rather than as a reply to the previous version.

Quoted 29 lines · On Sat, 21 Mar 2026 03:20:20 +0800 Liew Rui Yan <[email protected]>…

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:

Quoted 16 lines
    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%
    =============================================

Nice!

Quoted 6 lines

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

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

Quoted 6 lines

---
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.

As I mentioned at the beginning, please send new versions as new thread from the next time. And, in the case, consider adding a link to the previous versions.

[1] https://docs.kernel.org/process/submitting-patches.html#commentary

Thanks,
SJ

[...]