Re: reduce forks during autoconf

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Bruno Haible on 5/14/2008 4:08 AM:
| Btw, does the use of m4_append_uniq cause quadratic runtime?

It was much worse in autoconf prior to 2.62, using two regular expressions
per addition.  In 2.62, it uses a much faster memmem search.  But yes,
when collecting n unique items into a list, the entire existing list is
scanned, so m4_append_uniq grows quadratically.

| I.e. when
| there are n invocations of AC_LIBSOURCES, will the time spent in the
| m4_append_uniq calls be O(n²) total? Would it be O(n) total if m4_append was
| used instead?

Good point.  This would allow duplicates in the list, but linear
processing of duplicates in the shell's for list is likely faster than the
quadratic m4 time spent in guaranteeing no duplicates.  So I'm committing
this:

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkgq3nwACgkQ84KuGfSFAYBycwCgsI2WDPpQj5J1pbAga5UgxmnD
DboAn0d7+ITGVRFwHBfhg0vweA9FSicy
=tne8
-----END PGP SIGNATURE-----

>From 83332ed7cb60db2caee1883875eb24e9c41f505f Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Wed, 14 May 2008 06:42:55 -0600
Subject: [PATCH] Avoid quadratic growth in gl_LIBSOURCES.

* gnulib-tool (func_emit_initmacro_done): s/\(m4_append\)_uniq/\1/.
Suggested by Bruno Haible.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog   |    4 ++++
 gnulib-tool |    2 +-
 2 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 4962795..f809215 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
 2008-05-14  Eric Blake  <address@hidden>
 
+       Avoid quadratic growth in gl_LIBSOURCES.
+       * gnulib-tool (func_emit_initmacro_done): s/\(m4_append\)_uniq/\1/.
+       Suggested by Bruno Haible.
+
        Test xmemdup0.
        * modules/xmemdup0-tests: New file.
        * tests/test-xmemdup0.c: Likewise.
diff --git a/gnulib-tool b/gnulib-tool
index 65de980..a3b9df5 100755
--- a/gnulib-tool
+++ b/gnulib-tool
@@ -2130,7 +2130,7 @@ func_emit_initmacro_done ()
   echo "  m4_foreach([_gl_NAME], [\$1], ["
   echo "    m4_if(_gl_NAME, [alloca.c], [], ["
   echo "      m4_define([${macro_prefix_arg}_LIBSOURCES_DIR], 
[$sourcebase_arg])"
-  echo "      m4_append_uniq([${macro_prefix_arg}_LIBSOURCES_LIST], _gl_NAME, 
[ ])"
+  echo "      m4_append([${macro_prefix_arg}_LIBSOURCES_LIST], _gl_NAME, [ ])"
   echo "    ])"
   echo "  ])"
   echo "])"
-- 
1.5.5.1