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]>
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
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
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 <[email protected]>
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
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