[PATCH] percpu: Reduce the number of cpu distance comparisions

[PATCH] percpu: Reduce the number of cpu distance comparisions

[Wonhuyk Yang]

From: Wonhyuk Yang <vvghjk1234@gmail.com>

To build group_map[] and group_cnt[], we find out which group
CPUs belong to by comparing the distance of the cpu. However,
this includes cases where comparisons are not required.

This patch uses a bitmap to record CPUs that is not classified in
the group. CPUs that we know which group they belong to should be
cleared from the bitmap. In result, we can reduce the number of
unnecessary comparisons.

Signed-off-by: Wonhyuk Yang <vvghjk1234@gmail.com>
---
 mm/percpu.c | 32 ++++++++++++++++++--------------
 1 file changed, 18 insertions(+), 14 deletions(-)

diff --git a/mm/percpu.c b/mm/percpu.c
index 66a93f096394..d19ca484eee4 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -2669,6 +2669,7 @@ static struct pcpu_alloc_info * __init pcpu_build_alloc_info(
 {
 	static int group_map[NR_CPUS] __initdata;
 	static int group_cnt[NR_CPUS] __initdata;
+	static struct cpumask mask __initdata;
 	const size_t static_size = __per_cpu_end - __per_cpu_start;
 	int nr_groups = 1, nr_units = 0;
 	size_t size_sum, min_unit_size, alloc_size;
@@ -2702,24 +2703,27 @@ static struct pcpu_alloc_info * __init pcpu_build_alloc_info(
 		upa--;
 	max_upa = upa;
 
+	cpumask_copy(&mask, cpu_possible_mask);
+
 	/* group cpus according to their proximity */
-	for_each_possible_cpu(cpu) {
-		group = 0;
-	next_group:
-		for_each_possible_cpu(tcpu) {
-			if (cpu == tcpu)
-				break;
-			if (group_map[tcpu] == group && cpu_distance_fn &&
-			    (cpu_distance_fn(cpu, tcpu) > LOCAL_DISTANCE ||
-			     cpu_distance_fn(tcpu, cpu) > LOCAL_DISTANCE)) {
-				group++;
-				nr_groups = max(nr_groups, group + 1);
-				goto next_group;
-			}
-		}
+	for (group = 0; !cpumask_empty(&mask); group++) {
+		/* pop the group's first cpu */
+		cpu = cpumask_first(&mask);
 		group_map[cpu] = group;
 		group_cnt[group]++;
+		cpumask_clear_cpu(cpu, &mask);
+
+		for_each_cpu(tcpu, &mask) {
+			if (!cpu_distance_fn ||
+			    (cpu_distance_fn(cpu, tcpu) == LOCAL_DISTANCE &&
+			     cpu_distance_fn(tcpu, cpu) == LOCAL_DISTANCE)) {
+				group_map[tcpu] = group;
+				group_cnt[group]++;
+				cpumask_clear_cpu(tcpu, &mask);
+			}
+		}
 	}
+	nr_groups = group;
 
 	/*
 	 * Wasted space is caused by a ratio imbalance of upa to group_cnt.
-- 
2.17.1

Re: [PATCH] percpu: Reduce the number of cpu distance comparisions

[Dennis Zhou]

Hello,

On Fri, Oct 30, 2020 at 10:38:20AM +0900, Wonhuyk Yang wrote:
> From: Wonhyuk Yang <vvghjk1234@gmail.com>
> 
> To build group_map[] and group_cnt[], we find out which group
> CPUs belong to by comparing the distance of the cpu. However,
> this includes cases where comparisons are not required.
> 
> This patch uses a bitmap to record CPUs that is not classified in
> the group. CPUs that we know which group they belong to should be
> cleared from the bitmap. In result, we can reduce the number of
> unnecessary comparisons.
> 
> Signed-off-by: Wonhyuk Yang <vvghjk1234@gmail.com>
> ---
>  mm/percpu.c | 32 ++++++++++++++++++--------------
>  1 file changed, 18 insertions(+), 14 deletions(-)
> 
> diff --git a/mm/percpu.c b/mm/percpu.c
> index 66a93f096394..d19ca484eee4 100644
> --- a/mm/percpu.c
> +++ b/mm/percpu.c
> @@ -2669,6 +2669,7 @@ static struct pcpu_alloc_info * __init pcpu_build_alloc_info(
>  {
>  	static int group_map[NR_CPUS] __initdata;
>  	static int group_cnt[NR_CPUS] __initdata;
> +	static struct cpumask mask __initdata;
>  	const size_t static_size = __per_cpu_end - __per_cpu_start;
>  	int nr_groups = 1, nr_units = 0;
>  	size_t size_sum, min_unit_size, alloc_size;
> @@ -2702,24 +2703,27 @@ static struct pcpu_alloc_info * __init pcpu_build_alloc_info(
>  		upa--;
>  	max_upa = upa;
>  
> +	cpumask_copy(&mask, cpu_possible_mask);
> +
>  	/* group cpus according to their proximity */
> -	for_each_possible_cpu(cpu) {
> -		group = 0;
> -	next_group:
> -		for_each_possible_cpu(tcpu) {
> -			if (cpu == tcpu)
> -				break;
> -			if (group_map[tcpu] == group && cpu_distance_fn &&
> -			    (cpu_distance_fn(cpu, tcpu) > LOCAL_DISTANCE ||
> -			     cpu_distance_fn(tcpu, cpu) > LOCAL_DISTANCE)) {
> -				group++;
> -				nr_groups = max(nr_groups, group + 1);
> -				goto next_group;
> -			}
> -		}
> +	for (group = 0; !cpumask_empty(&mask); group++) {
> +		/* pop the group's first cpu */
> +		cpu = cpumask_first(&mask);
>  		group_map[cpu] = group;
>  		group_cnt[group]++;
> +		cpumask_clear_cpu(cpu, &mask);
> +
> +		for_each_cpu(tcpu, &mask) {
> +			if (!cpu_distance_fn ||
> +			    (cpu_distance_fn(cpu, tcpu) == LOCAL_DISTANCE &&
> +			     cpu_distance_fn(tcpu, cpu) == LOCAL_DISTANCE)) {
> +				group_map[tcpu] = group;
> +				group_cnt[group]++;
> +				cpumask_clear_cpu(tcpu, &mask);
> +			}
> +		}
>  	}
> +	nr_groups = group;
>  
>  	/*
>  	 * Wasted space is caused by a ratio imbalance of upa to group_cnt.
> -- 
> 2.17.1
> 

Sorry for the delay. It's been a little bit of a busy week for me and it
always takes me a moment to wrap my head around this code.

I've applied this to percpu#for-5.11.

Thanks,
Dennis