Skip to contentSkip to conversation

Fix Kconfig performance bug

PATCH In review David Gibson 2 participants 4 messages Oct 20, 2005 – Oct 31, 2005 Kconfig

lore
Share & tools
lore

David Gibson

author
#0 lore raw

PATCH 1/1 Fix Kconfig performance bug

Fix kconfig performance bug

Roman, I'm pretty sure this patch is correct, but obviously someone more familiar with the kconfig code should check it over. If it's ok (i.e. it makes no change in external behaviour), please apply.

When doing its recursive dependency check, scripts/kconfig/conf uses the flag SYMBOL_CHECK_DONE to avoid rechecking a symbol it has already checked. However, that flag is only set at the top level, so if a symbol is first encountered as a dependency of another symbol it will be rechecked every time it is encountered until it's encountered at the top level.

This patch adjusts the flag setting so that each symbol will only be checked once, regardless of whether it is first encountered at the top level, or while recursing down from another symbol. On complex configurations, this vastly speeds up scripts/kconfig/conf. The config in the powerpc merge tree is particularly bad: this patch reduces the time for 'scripts/kconfig/conf -o arch/powerpc/Kconfig' by a factor of 40 on a G5. That's even including the time to print the config, so the speedup in the actual checking is more likely 2 or 3 orders of magnitude.

Signed-off-by David Gibson <[email protected]>
scripts/kconfig/symbol.c +2 -0
Index: working-2.6/scripts/kconfig/symbol.c
===================================================================
@@ -758,6 +758,8 @@
 out:
 	if (sym2)
 		printf(" %s", sym->name);
+	else
+		sym->flags |= SYMBOL_CHECK_DONE;
 	sym->flags &= ~SYMBOL_CHECK;
 	return sym2;
 }
scripts/kconfig/zconf.y +1 -2
Index: working-2.6/scripts/kconfig/zconf.y
===================================================================
@@ -495,10 +495,9 @@
 		exit(1);
 	menu_finalize(&rootmenu);
 	for_all_symbols(i, sym) {
+/* 		fprintf(stderr, "Checking %s...\n", sym->name); */
                 if (!(sym->flags & SYMBOL_CHECKED) && sym_check_deps(sym))
                         printf("\n");
-		else
-			sym->flags |= SYMBOL_CHECK_DONE;
         }
 
 	sym_change_count = 1;
scripts/kconfig/zconf.tab.c_shipped +0 -2
Index: working-2.6/scripts/kconfig/zconf.tab.c_shipped
===================================================================
@@ -1935,8 +1935,6 @@
 	for_all_symbols(i, sym) {
                 if (!(sym->flags & SYMBOL_CHECKED) && sym_check_deps(sym))
                         printf("\n");
-		else
-			sym->flags |= SYMBOL_CHECK_DONE;
         }
 
 	sym_change_count = 1;
Signature · 4 lines
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/people/dgibson
#1 lore raw

Hi,

Quoted 6 lines · David Gibson

When doing its recursive dependency check, scripts/kconfig/conf uses the flag SYMBOL_CHECK_DONE to avoid rechecking a symbol it has already checked. However, that flag is only set at the top level, so if a symbol is first encountered as a dependency of another symbol it will be rechecked every time it is encountered until it's encountered at the top level.

You're correct, the check does too much.

scripts/kconfig/symbol.c line 765

Quoted 13 lines

Index: working-2.6/scripts/kconfig/symbol.c
===================================================================

scripts/kconfig/symbol.c +2 -0
@@ -758,6 +758,8 @@
 out:
 	if (sym2)
 		printf(" %s", sym->name);
+	else
+		sym->flags |= SYMBOL_CHECK_DONE;
 	sym->flags &= ~SYMBOL_CHECK;
 	return sym2;
 }

Actually this way it becomes redundant with SYMBOL_CHECKED, could you merge these two flags? The above check would be also probably better:

	if (sym2) {
		printf(" %s", sym->name);
		if (sym2 == sym) {
			printf("\n");
			sym2 = NULL;
		}
	}

So that this check will stop when it hits the start symbol and continue looking for more dependency problems, which is I think I intended with the original code.

scripts/kconfig/zconf.y line 498

Quoted 9 lines

Index: working-2.6/scripts/kconfig/zconf.y
===================================================================

scripts/kconfig/zconf.y +1 -0
@@ -495,10 +495,9 @@
 		exit(1);
 	menu_finalize(&rootmenu);
 	for_all_symbols(i, sym) {
+/* 		fprintf(stderr, "Checking %s...\n", sym->name); */

One "quilt refresh" missing? :-)

bye, Roman

author
#2 lore raw
Quoted 13 lines · Roman Zippel

Hi,

Quoted 6 lines · David Gibson

When doing its recursive dependency check, scripts/kconfig/conf uses the flag SYMBOL_CHECK_DONE to avoid rechecking a symbol it has already checked. However, that flag is only set at the top level, so if a symbol is first encountered as a dependency of another symbol it will be rechecked every time it is encountered until it's encountered at the top level.

You're correct, the check does too much.

Quoted 16 lines

scripts/kconfig/symbol.c line 765

Quoted 13 lines

Index: working-2.6/scripts/kconfig/symbol.c
===================================================================

scripts/kconfig/symbol.c +2 -0
@@ -758,6 +758,8 @@
 out:
 	if (sym2)
 		printf(" %s", sym->name);
+	else
+		sym->flags |= SYMBOL_CHECK_DONE;
 	sym->flags &= ~SYMBOL_CHECK;
 	return sym2;
 }

Actually this way it becomes redundant with SYMBOL_CHECKED, could you merge these two flags? The above check would be also probably better:

Ok, done. There is now only SYMBOL_CHECKED (seemed a clearer name to me), but it's semantics are like those of SYMBOL_CHECK_DONE were.

Quoted 11 lines
	if (sym2) {
		printf(" %s", sym->name);
		if (sym2 == sym) {
			printf("\n");
			sym2 = NULL;
		}
	}

So that this check will stop when it hits the start symbol and continue looking for more dependency problems, which is I think I intended with the original code.

Erm.. ok. I don't entirely understand the intent of this is, but applied anyway.

Quoted 11 lines

scripts/kconfig/zconf.y line 498

Quoted 9 lines

Index: working-2.6/scripts/kconfig/zconf.y
===================================================================

scripts/kconfig/zconf.y +1 -0
@@ -495,10 +495,9 @@
 		exit(1);
 	menu_finalize(&rootmenu);
 	for_all_symbols(i, sym) {
+/* 		fprintf(stderr, "Checking %s...\n", sym->name); */

One "quilt refresh" missing? :-)

Oops. Something like that.

Oh.. one caveat, the diffs I have here to zconf.tab.c_shipped are direct edits to match zconf.y - I didn't regenerate the file with bison. I've done that to getting a whole lot of irrelevant changes in the patch because I'm using a different version of bison to that used for the existing zconf.tab.[ch]_shipped

Anyway, revised version below:

Signed-off-by David Gibson <[email protected]>
scripts/kconfig/symbol.c +10 -3
Index: working-2.6/scripts/kconfig/symbol.c
===================================================================
@@ -731,14 +731,14 @@
 	struct symbol *sym2;
 	struct property *prop;
 
-	if (sym->flags & SYMBOL_CHECK_DONE)
+	if (sym->flags & SYMBOL_CHECKED)
 		return NULL;
 	if (sym->flags & SYMBOL_CHECK) {
 		printf("Warning! Found recursive dependency: %s", sym->name);
 		return sym;
 	}
 
-	sym->flags |= (SYMBOL_CHECK | SYMBOL_CHECKED);
+	sym->flags |= SYMBOL_CHECK;
 	sym2 = sym_check_expr_deps(sym->rev_dep.expr);
 	if (sym2)
 		goto out;

@@ -756,8 +756,15 @@
 			goto out;
 	}
 out:
-	if (sym2)
+	if (sym2) {
 		printf(" %s", sym->name);
+		if (sym2 == sym) {
+			printf("\n");
+			sym2 = NULL;
+		}
+	} else {
+		sym->flags |= SYMBOL_CHECKED;
+	}
 	sym->flags &= ~SYMBOL_CHECK;
 	return sym2;
 }
scripts/kconfig/zconf.y +0 -2
Index: working-2.6/scripts/kconfig/zconf.y
===================================================================
@@ -497,8 +497,6 @@
 	for_all_symbols(i, sym) {
                 if (!(sym->flags & SYMBOL_CHECKED) && sym_check_deps(sym))
                         printf("\n");
-		else
-			sym->flags |= SYMBOL_CHECK_DONE;
         }
 
 	sym_change_count = 1;
scripts/kconfig/zconf.tab.c_shipped +0 -2
Index: working-2.6/scripts/kconfig/zconf.tab.c_shipped
===================================================================
@@ -1935,8 +1935,6 @@
 	for_all_symbols(i, sym) {
                 if (!(sym->flags & SYMBOL_CHECKED) && sym_check_deps(sym))
                         printf("\n");
-		else
-			sym->flags |= SYMBOL_CHECK_DONE;
         }
 
 	sym_change_count = 1;
scripts/kconfig/expr.h +0 -1
Index: working-2.6/scripts/kconfig/expr.h
===================================================================
@@ -93,7 +93,6 @@
 #define SYMBOL_NEW		0x0800
 #define SYMBOL_AUTO		0x1000
 #define SYMBOL_CHECKED		0x2000
-#define SYMBOL_CHECK_DONE	0x4000
 #define SYMBOL_WARNED		0x8000
 
 #define SYMBOL_MAXLENGTH	256
Signature · 4 lines
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/people/dgibson
author
#3 lore raw
Quoted 63 lines · David Gibson
Quoted 13 lines · Roman Zippel

Hi,

Quoted 6 lines · David Gibson

When doing its recursive dependency check, scripts/kconfig/conf uses the flag SYMBOL_CHECK_DONE to avoid rechecking a symbol it has already checked. However, that flag is only set at the top level, so if a symbol is first encountered as a dependency of another symbol it will be rechecked every time it is encountered until it's encountered at the top level.

You're correct, the check does too much.

Quoted 16 lines

scripts/kconfig/symbol.c line 765

Quoted 13 lines

Index: working-2.6/scripts/kconfig/symbol.c
===================================================================

scripts/kconfig/symbol.c +2 -0
@@ -758,6 +758,8 @@
 out:
 	if (sym2)
 		printf(" %s", sym->name);
+	else
+		sym->flags |= SYMBOL_CHECK_DONE;
 	sym->flags &= ~SYMBOL_CHECK;
 	return sym2;
 }

Actually this way it becomes redundant with SYMBOL_CHECKED, could you merge these two flags? The above check would be also probably better:

Ok, done. There is now only SYMBOL_CHECKED (seemed a clearer name to me), but it's semantics are like those of SYMBOL_CHECK_DONE were.

Quoted 11 lines
	if (sym2) {
		printf(" %s", sym->name);
		if (sym2 == sym) {
			printf("\n");
			sym2 = NULL;
		}
	}

So that this check will stop when it hits the start symbol and continue looking for more dependency problems, which is I think I intended with the original code.

Erm.. ok. I don't entirely understand the intent of this is, but applied anyway.

Quoted 11 lines

scripts/kconfig/zconf.y line 498

Quoted 9 lines

Index: working-2.6/scripts/kconfig/zconf.y
===================================================================

scripts/kconfig/zconf.y +1 -0
@@ -495,10 +495,9 @@
 		exit(1);
 	menu_finalize(&rootmenu);
 	for_all_symbols(i, sym) {
+/* 		fprintf(stderr, "Checking %s...\n", sym->name); */

One "quilt refresh" missing? :-)

Oops. Something like that.

Quoted 7 lines

Oh.. one caveat, the diffs I have here to zconf.tab.c_shipped are direct edits to match zconf.y - I didn't regenerate the file with bison. I've done that to getting a whole lot of irrelevant changes in the patch because I'm using a different version of bison to that used for the existing zconf.tab.[ch]_shipped

Anyway, revised version below:

Now that 2.6.14 is out, do you intend to pass this patch on to Linus?

Signature · 4 lines
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/people/dgibson