mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
* [PATCH v2] cpuset: Optimize the number of iterations in the scheduling domain construction process
@ 2024-05-31  2:48 Xavier
  2024-05-31 21:13 ` Waiman Long
  2024-06-03 12:31 ` [PATCH v3] cpuset: use Union-Find to optimize the merging of cpumasks Xavier
  0 siblings, 2 replies; 53+ messages in thread
From: Xavier @ 2024-05-31  2:48 UTC (permalink / raw)
  To: longman, lizefan.x, tj, hannes; +Cc: cgroups, linux-kernel, Xavier

The process of constructing scheduling domains involves multiple loops
and repeated evaluations, leading to numerous redundant and ineffective
assessments that impact code efficiency.

Here, we use Union-Find to optimize the merging of cpumasks. By employing
path compression and union by rank, we effectively reduce the number of
lookups and merge comparisons.

Signed-off-by: Xavier <ghostxavier@sina.com>
---
 kernel/cgroup/cpuset.c | 117 +++++++++++++++++++++++------------------
 1 file changed, 66 insertions(+), 51 deletions(-)

diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index c12b9fdb2..4bea1c2db 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -891,6 +891,44 @@ static inline int nr_cpusets(void)
 	return static_key_count(&cpusets_enabled_key.key) + 1;
 }
 
+/*define a union find node struct*/
+struct uf_node {
+	int parent;
+	int rank;
+};
+
+static int find_root(struct uf_node *nodes, int x)
+{
+	int root = x;
+	int parent;
+
+	/*Find the root node and perform path compression at the same time*/
+	while (nodes[root].parent != root) {
+		parent = nodes[root].parent;
+		nodes[root].parent = nodes[parent].parent;
+		root = parent;
+	}
+	return root;
+}
+
+/*Function to merge two sets, using union by rank*/
+static void union_sets(struct uf_node *nodes, int a, int b)
+{
+	int root_a = find_root(nodes, a);
+	int root_b = find_root(nodes, b);
+
+	if (root_a != root_b) {
+		if (nodes[root_a].rank < nodes[root_b].rank) {
+			nodes[root_a].parent = root_b;
+		} else if (nodes[root_a].rank > nodes[root_b].rank) {
+			nodes[root_b].parent = root_a;
+		} else {
+			nodes[root_b].parent = root_a;
+			nodes[root_a].rank++;
+		}
+	}
+}
+
 /*
  * generate_sched_domains()
  *
@@ -950,13 +988,14 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	struct cpuset *cp;	/* top-down scan of cpusets */
 	struct cpuset **csa;	/* array of all cpuset ptrs */
 	int csn;		/* how many cpuset ptrs in csa so far */
-	int i, j, k;		/* indices for partition finding loops */
+	int i, j;		/* indices for partition finding loops */
 	cpumask_var_t *doms;	/* resulting partition; i.e. sched domains */
 	struct sched_domain_attr *dattr;  /* attributes for custom domains */
 	int ndoms = 0;		/* number of sched domains in result */
 	int nslot;		/* next empty doms[] struct cpumask slot */
 	struct cgroup_subsys_state *pos_css;
 	bool root_load_balance = is_sched_load_balance(&top_cpuset);
+	struct uf_node *nodes;
 
 	doms = NULL;
 	dattr = NULL;
@@ -1022,33 +1061,31 @@ static int generate_sched_domains(cpumask_var_t **domains,
 	}
 	rcu_read_unlock();
 
-	for (i = 0; i < csn; i++)
-		csa[i]->pn = i;
-	ndoms = csn;
-
-restart:
-	/* Find the best partition (set of sched domains) */
-	for (i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		int apn = a->pn;
+	nodes = kmalloc_array(csn, sizeof(struct uf_node), GFP_KERNEL);
+	if (!nodes)
+		goto done;
 
-		for (j = 0; j < csn; j++) {
-			struct cpuset *b = csa[j];
-			int bpn = b->pn;
 
-			if (apn != bpn && cpusets_overlap(a, b)) {
-				for (k = 0; k < csn; k++) {
-					struct cpuset *c = csa[k];
+	/* Each node is initially its own parent */
+	for (i = 0; i < csn; i++) {
+		nodes[i].parent = i;
+		nodes[i].rank = 0;
+	}
 
-					if (c->pn == bpn)
-						c->pn = apn;
-				}
-				ndoms--;	/* one less element */
-				goto restart;
-			}
+	/* Merge overlapping cpusets */
+	for (i = 0; i < csn; i++) {
+		for (j = i + 1; j < csn; j++) {
+			if (cpusets_overlap(csa[i], csa[j]))
+				union_sets(nodes, i, j);
 		}
 	}
 
+	/* Calculate the number of domains after merging */
+	for (i = 0; i < csn; i++) {
+		if (nodes[i].parent == i)
+			ndoms++;
+	}
+
 	/*
 	 * Now we know how many domains to create.
 	 * Convert <csn, csa> to <ndoms, doms> and populate cpu masks.
@@ -1065,47 +1102,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
 			      GFP_KERNEL);
 
 	for (nslot = 0, i = 0; i < csn; i++) {
-		struct cpuset *a = csa[i];
-		struct cpumask *dp;
-		int apn = a->pn;
-
-		if (apn < 0) {
-			/* Skip completed partitions */
-			continue;
-		}
-
-		dp = doms[nslot];
-
-		if (nslot == ndoms) {
-			static int warnings = 10;
-			if (warnings) {
-				pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i %d, apn %d\n",
-					nslot, ndoms, csn, i, apn);
-				warnings--;
-			}
-			continue;
-		}
+		struct cpumask *dp = doms[nslot];
 
 		cpumask_clear(dp);
 		if (dattr)
 			*(dattr + nslot) = SD_ATTR_INIT;
 		for (j = i; j < csn; j++) {
-			struct cpuset *b = csa[j];
+			if (find_root(nodes, j) == i) {
+				if (i == j)
+					nslot++;
 
-			if (apn == b->pn) {
-				cpumask_or(dp, dp, b->effective_cpus);
+				cpumask_or(dp, dp, csa[j]->effective_cpus);
 				cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN));
 				if (dattr)
-					update_domain_attr_tree(dattr + nslot, b);
-
-				/* Done with this partition */
-				b->pn = -1;
+					update_domain_attr_tree(dattr + nslot, csa[j]);
 			}
 		}
-		nslot++;
 	}
 	BUG_ON(nslot != ndoms);
-
+	kfree(nodes);
 done:
 	kfree(csa);
 
-- 
2.34.1


^ permalink raw reply	[flat|nested] 53+ messages in thread
* Re: [PATCH v3] cpuset: use Union-Find to optimize the merging of cpumasks
@ 2024-06-05  2:32 ghostxavier
  0 siblings, 0 replies; 53+ messages in thread
From: ghostxavier @ 2024-06-05  2:32 UTC (permalink / raw)
  To: Waiman Long; +Cc: lizefan.x, tj, hannes, cgroups, linux-kernel

Hi Longman,

I am ready to prepare and send a v4 patch based on the new cpuset codebase. Thanks for your guidance and support.

Best regards,
Xavier

------------------------------------------------------------------------------------------

On 6/3/24 08:31, Xavier wrote:
> The process of constructing scheduling domains involves multiple loops
> and repeated evaluations, leading to numerous redundant and ineffective
> assessments that impact code efficiency.
>
> Here, we use Union-Find to optimize the merging of cpumasks. By employing
> path compression and union by rank, we effectively reduce the number of
> lookups and merge comparisons.
>
> Signed-off-by: Xavier <ghostxavier@sina.com>
>
> Hi Longman,
>
> Thank you for your feedback on the previous version of the patch.
>
> Now I will respond to the three questions you raised:
> 1) The function comment describes the algorithm to find the set of
> domains. If you change the algorithm, you have to update the comment as
> well.
>
> Reply: Sorry for not paying attention to the comments before. The new patch (v3) has updated the comment content.
>
> 2) generate_sched_domains() is not in a performance critical path, so
> its performance is not as important. Also the csn array is typically not
> that big. Changing the algorithm may introduce new bugs which leads to
> the next point.
>
> Reply: Indeed, this function is not a critical path impacting performance, but it's always good to optimize efficiency. The optimization is limited to the internals of this function and does not affect other modules, so fixing the internal bug should have manageable risks.
In term of efficiency, your patch does eliminate the third iteration (k) 
in the csn iteration loop. However the new union_sets() function may go 
up the node hierarchy which can considered a third iteration in some 
way. So there is some saving, but not as significant as it looks. It 
does simplify the code and make it a bit easier to read.
>
> 3) How do you test your code to ensure its correctness?
> I applied your patch and run the ./test_cpuset_prs.sh got the following...
>
> Reply: I'm very sorry, this is my first time submitting a kernel patch and I don't know which test cases need to be run. I just constructed some scenarios locally to test, so the testing scope is limited. Thank you for providing the test cases. I have reproduced and resolved the issue, and have passed several other test cases in CGroup. But currently, I only have QEMU simulation environment, so my testing ability is limited. I hope you can help me with some comprehensive testing of my new version patch. Thank you very much.
>
> I hope you can pay further attention to the new patch.
Also your patch eliminates all the use of the cpuset->pn variable. So 
you cab remove it as it is no longer needed.
After a harder look at the generate_sched_domains() code, I have found a 
bug in the code with respect to the support of remote partition. I will 
send another patch to fix it. I also realize that the function was 
originally designed to support v1 cpuset. v2 cpuset is quite different 
and the code can be simplified for the v2 use case.
You are welcome to send a v4 patch on top of the new cpuset code base.
Thanks,
Longman

^ permalink raw reply	[flat|nested] 53+ messages in thread
end of thread, other threads:[~2024-07-30 23:06 UTC | newest]

Thread overview: 53+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-05-31  2:48 [PATCH v2] cpuset: Optimize the number of iterations in the scheduling domain construction process Xavier
2024-05-31 21:13 ` Waiman Long
2024-06-03 12:31 ` [PATCH v3] cpuset: use Union-Find to optimize the merging of cpumasks Xavier
2024-06-04 15:02   ` Waiman Long
2024-06-10 17:18   ` Michal Koutný
2024-06-20  8:52   ` [PATCH v4 v4 0/2] cpuset: use Union-Find to optimize Xavier
2024-06-20  8:52     ` [PATCH v4 v4 1/2] Union-Find: add a new module in kernel library Xavier
2024-06-20 14:54       ` Waiman Long
2024-06-21  8:49         ` [PATCH-cpuset v5 0/2] cpuset: use Union-Find to optimize Xavier
2024-06-21  8:49           ` [PATCH-cpuset v5 1/2] Union-Find: add a new module in kernel library Xavier
2024-06-21 21:10             ` Tejun Heo
2024-06-22  7:14               ` [PATCH-cpuset v6 0/2] Add Union-Find and use it to optimize cpuset Xavier
2024-06-22  7:14                 ` [PATCH-cpuset v6 1/2] Union-Find: add a new module in kernel library Xavier
2024-06-22  7:14                 ` [PATCH-cpuset v6 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Xavier
2024-06-22 16:13                 ` [PATCH-cpuset v6 0/2] Add Union-Find and use it to optimize cpuset Tejun Heo
2024-06-23  2:38                   ` [PATCH-cpuset v7 " Xavier
2024-06-23  2:39                     ` [PATCH-cpuset v7 1/2] Union-Find: add a new module in kernel library Xavier
2024-06-23  2:39                     ` [PATCH-cpuset v7 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Xavier
2024-06-27 21:06                     ` [PATCH-cpuset v7 0/2] Add Union-Find and use it to optimize cpuset Tejun Heo
2024-06-28 16:13                       ` [PATCH-cpuset v8 " Xavier
2024-06-28 16:13                         ` [PATCH-cpuset v8 1/2] Union-Find: add a new module in kernel library Xavier
2024-07-01 20:53                           ` Tejun Heo
2024-07-02 10:50                             ` [PATCH-cpuset v9 0/2] Add Union-Find and use it to optimize cpuset Xavier
2024-07-02 10:50                               ` [PATCH-cpuset v9 1/2] Union-Find: add a new module in kernel library Xavier
2024-07-02 10:50                               ` [PATCH-cpuset v9 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Xavier
2024-07-03  3:05                                 ` Waiman Long
2024-07-02 19:22                               ` [PATCH-cpuset v9 0/2] Add Union-Find and use it to optimize cpuset Tejun Heo
2024-07-03  0:31                                 ` Andrew Morton
2024-07-03 17:34                                   ` Tejun Heo
2024-07-03  6:37                                 ` [PATCH-cpuset v10 " Xavier
2024-07-03  6:37                                   ` [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel library Xavier
2024-07-03  9:40                                     ` Michal Koutný
2024-07-03 11:20                                       ` Xavier
2024-07-04 12:12                                         ` Michal Koutný
2024-07-03  6:37                                   ` [PATCH-cpuset v10 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Xavier
2024-07-03  9:40                                     ` Michal Koutný
2024-07-03 10:49                                       ` Xavier
2024-07-03 16:43                                         ` Waiman Long
2024-07-04  6:24                                           ` [PATCH-cpuset v11 0/2] Add Union-Find and use it to optimize cpuset Xavier
2024-07-04  6:24                                             ` [PATCH-cpuset v11 1/2] Union-Find: add a new module in kernel library Xavier
2024-07-30 23:05                                               ` Tejun Heo
2024-07-04  6:24                                             ` [PATCH-cpuset v11 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Xavier
2024-07-30 23:05                                               ` Tejun Heo
2024-07-08  1:59                                             ` [PATCH-cpuset v11 0/2] Add Union-Find and use it to optimize cpuset Waiman Long
2024-07-08 18:38                                               ` Tejun Heo
2024-07-09  2:45                                                 ` Xavier
2024-07-29  2:44                                                 ` Xavier
2024-07-30 23:06                                                   ` Tejun Heo
2024-06-28 16:13                         ` [PATCH-cpuset v8 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Xavier
2024-07-01 20:53                           ` Tejun Heo
2024-06-21  8:49           ` [PATCH-cpuset v5 " Xavier
2024-06-20  8:52     ` [PATCH v4 v4 " Xavier
2024-06-05  2:32 [PATCH v3] " ghostxavier

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®