[PATCH] Fix Kconfig performance bug

[PATCH] Fix Kconfig performance bug

[David Gibson]

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 <david@gibson.dropbear.id.au>

Index: working-2.6/scripts/kconfig/symbol.c
===================================================================
--- working-2.6.orig/scripts/kconfig/symbol.c	2005-10-20 12:40:45.000000000 +1000
+++ working-2.6/scripts/kconfig/symbol.c	2005-10-20 12:41:43.000000000 +1000
@@ -758,6 +758,8 @@
 out:
 	if (sym2)
 		printf(" %s", sym->name);
+	else
+		sym->flags |= SYMBOL_CHECK_DONE;
 	sym->flags &= ~SYMBOL_CHECK;
 	return sym2;
 }
Index: working-2.6/scripts/kconfig/zconf.y
===================================================================
--- working-2.6.orig/scripts/kconfig/zconf.y	2005-10-20 12:40:45.000000000 +1000
+++ working-2.6/scripts/kconfig/zconf.y	2005-10-20 12:41:43.000000000 +1000
@@ -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;
Index: working-2.6/scripts/kconfig/zconf.tab.c_shipped
===================================================================
--- working-2.6.orig/scripts/kconfig/zconf.tab.c_shipped	2005-10-12 17:10:16.000000000 +1000
+++ working-2.6/scripts/kconfig/zconf.tab.c_shipped	2005-10-20 13:01:50.000000000 +1000
@@ -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;


-- 
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

Re: [PATCH] Fix Kconfig performance bug

[Roman Zippel]

Hi,

On Thu, 20 Oct 2005, David Gibson wrote:

> 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.

> Index: working-2.6/scripts/kconfig/symbol.c
> ===================================================================
> --- working-2.6.orig/scripts/kconfig/symbol.c	2005-10-20 12:40:45.000000000 +1000
> +++ working-2.6/scripts/kconfig/symbol.c	2005-10-20 12:41:43.000000000 +1000
> @@ -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.

> Index: working-2.6/scripts/kconfig/zconf.y
> ===================================================================
> --- working-2.6.orig/scripts/kconfig/zconf.y	2005-10-20 12:40:45.000000000 +1000
> +++ working-2.6/scripts/kconfig/zconf.y	2005-10-20 12:41:43.000000000 +1000
> @@ -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

Re: [PATCH] Fix Kconfig performance bug

[David Gibson]

On Fri, Oct 21, 2005 at 02:46:30AM +0200, Roman Zippel wrote:
> Hi,
> 
> On Thu, 20 Oct 2005, David Gibson wrote:
> 
> > 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.
> 
> > Index: working-2.6/scripts/kconfig/symbol.c
> > ===================================================================
> > --- working-2.6.orig/scripts/kconfig/symbol.c	2005-10-20 12:40:45.000000000 +1000
> > +++ working-2.6/scripts/kconfig/symbol.c	2005-10-20 12:41:43.000000000 +1000
> > @@ -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.

> 	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.

> > Index: working-2.6/scripts/kconfig/zconf.y
> > ===================================================================
> > --- working-2.6.orig/scripts/kconfig/zconf.y	2005-10-20 12:40:45.000000000 +1000
> > +++ working-2.6/scripts/kconfig/zconf.y	2005-10-20 12:41:43.000000000 +1000
> > @@ -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 <david@gibson.dropbear.id.au>

Index: working-2.6/scripts/kconfig/symbol.c
===================================================================
--- working-2.6.orig/scripts/kconfig/symbol.c	2005-10-21 11:29:33.000000000 +1000
+++ working-2.6/scripts/kconfig/symbol.c	2005-10-21 11:41:07.000000000 +1000
@@ -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;
 }
Index: working-2.6/scripts/kconfig/zconf.y
===================================================================
--- working-2.6.orig/scripts/kconfig/zconf.y	2005-10-21 11:29:33.000000000 +1000
+++ working-2.6/scripts/kconfig/zconf.y	2005-10-21 11:31:01.000000000 +1000
@@ -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;
Index: working-2.6/scripts/kconfig/zconf.tab.c_shipped
===================================================================
--- working-2.6.orig/scripts/kconfig/zconf.tab.c_shipped	2005-10-21 11:29:33.000000000 +1000
+++ working-2.6/scripts/kconfig/zconf.tab.c_shipped	2005-10-21 11:29:37.000000000 +1000
@@ -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;
Index: working-2.6/scripts/kconfig/expr.h
===================================================================
--- working-2.6.orig/scripts/kconfig/expr.h	2005-05-24 14:12:26.000000000 +1000
+++ working-2.6/scripts/kconfig/expr.h	2005-10-21 11:30:13.000000000 +1000
@@ -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


-- 
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

Re: [PATCH] Fix Kconfig performance bug

[David Gibson]

On Fri, Oct 21, 2005 at 11:49:55AM +1000, David Gibson wrote:
> On Fri, Oct 21, 2005 at 02:46:30AM +0200, Roman Zippel wrote:
> > Hi,
> > 
> > On Thu, 20 Oct 2005, David Gibson wrote:
> > 
> > > 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.
> > 
> > > Index: working-2.6/scripts/kconfig/symbol.c
> > > ===================================================================
> > > --- working-2.6.orig/scripts/kconfig/symbol.c	2005-10-20 12:40:45.000000000 +1000
> > > +++ working-2.6/scripts/kconfig/symbol.c	2005-10-20 12:41:43.000000000 +1000
> > > @@ -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.
> 
> > 	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.
> 
> > > Index: working-2.6/scripts/kconfig/zconf.y
> > > ===================================================================
> > > --- working-2.6.orig/scripts/kconfig/zconf.y	2005-10-20 12:40:45.000000000 +1000
> > > +++ working-2.6/scripts/kconfig/zconf.y	2005-10-20 12:41:43.000000000 +1000
> > > @@ -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:

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

-- 
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