[PATCH] percpu: optimize group assignment when cpu_distance_fn isNULL

[Wei Yang]

When cpu_distance_fn is NULL, all CPUs belongs to group 0. The original logic
will continue to go through each CPU and its predecessor. cpu_distance_fn is
always NULL when pcpu_build_alloc_info() is called from pcpu_page_first_chunk().

By applying this patch, the time complexity will drop to O(n) form O(n^2) in
case cpu_distance_fn is NULL.

Signed-off-by: Wei Yang <weiyang@xxxxxxxxxxxxxxxxxx>
---
 mm/percpu.c |   23 ++++++++++++-----------
 1 files changed, 12 insertions(+), 11 deletions(-)

diff --git a/mm/percpu.c b/mm/percpu.c
index f79c807..8e6034f 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -1481,20 +1481,21 @@ static struct pcpu_alloc_info * __init pcpu_build_alloc_info(
 	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++;
-				if (group == nr_groups) {
-					nr_groups++;
+		if (cpu_distance_fn)
+			for_each_possible_cpu(tcpu) {
+				if (cpu == tcpu)
 					break;
+				if (group_map[tcpu] == group &&
+				    (cpu_distance_fn(cpu, tcpu) > LOCAL_DISTANCE ||
+				     cpu_distance_fn(tcpu, cpu) > LOCAL_DISTANCE)) {
+					group++;
+					if (group == nr_groups) {
+						nr_groups++;
+						break;
+					}
+					goto next_group;
 				}
-				goto next_group;
 			}
-		}
 		group_map[cpu] = group;
 		group_cnt[group]++;
 	}
-- 
1.7.5.4

BTW, this one is based on my previous patch.

>
>Thanks a lot!
>
>-- 
>tejun

-- 
Richard Yang
Help you, Help me

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/