mm/damon/ops-common: optimize damon_hot_score() using ilog2()
Subsystems (2)
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
@@ -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