Re: O(n) set manipulation

[Eric Blake]

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

According to Ralf Wildenhues on 7/31/2008 4:46 PM:
| Hi Eric,
|
| First, thanks a lot for your efficiency work on Autoconf!
|
| * Eric Blake wrote on Mon, Jul 28, 2008 at 03:10:45PM CEST:
|> I intentionally
|> documented m4_set output as unspecified order, to allow a future change
|> where the elements are maintained in sorted order rather than entry order,
|> by making set manipulation an m4 2.0 module.
|
| Does that mean that the Autoconf output will depend also on the M4
| version used, and possibly even system-specifics like type sizes
| or so?

Not so far.  The idea is that someday, when m4 2.0 allows the loading of
dynamic modules, some of the m4sugar macros currently implemented in m4
might instead be implemented as a module, where a more efficient algorithm
presents itself (ie. set membership via a module may be easier to track in
a sorted set than in the current insertion ordering, when m4_set_add can
be implemented as a single C code function rather than a series of m4
macros).  But as the release of M4 2.0 is still in the far distant future,
the only difference you should notice between using m4 1.4.x and 1.6 is
the speed in which the configure file is generated.  In fact, if m4 2.0
ever _does_ introduce a different ordering, the testsuite will catch it
(since it currently tests for insertion ordering), and we will then have
to decide whether to relax the testsuite, or more likely, tighten the
documentation and insist that loadable modules mirror existing m4sugar
semantics no matter the cost.  And even if we do provide an M4 2.0 dynamic
module, we will still have to support the same implementation (albeit less
efficient) in pure m4 as a fallback for platforms where dynamic loading
doesn't work well or where the developer has not installed M4 2.0 yet.

|  That would be a major pain for developers checking in configure
| scripts to their repositories, and breaking a (possibly unspoken)
| Autoconf promise.

Speeding up autoconf by the use of M4 2.0 loadable modules is a big enough
change that it will probably be worth bumping autoconf to the next major
numbering (3.0?).

As it is, developers who check in generated configure files already have
to worry about version skew.  In other words, the fact that the list of
AC_SUBST is now output in reverse order is no worse than the fact that
generated configure files already mention which version of autoconf
generated the file; when configure is checked in, developers already have
to agree on which canonical version of autoconf to use to generate the
checked in version.  But the version skew is only for autoconf versions,
not m4 versions (in all my testing, I ensure both m4 1.4.x and pre-1.6
generate identical files before I consider the alternate code paths worth
publishing).

|
| Also, it's a bit sad to see that neither of us has fixed any of the open
| regressions.  As I would really like to see a stable next release, I'm
| even wondering a bit whether we should consider releasing it without all
| these new changes, to avoid the risk of introducing new regressions.

I'm still planning on looking at that AC_USE_SYSTEM_EXTENSIONS issue this
coming week; all my work on O(n) operation stemmed from the bug report, if
you will call it that, of quadratic behavior of m4_append_uniq on large
sets (and real-life configure.ac really do have large sets of AC_SUBST).
I think the testsuite does a decent job of hammering out m4sugar changes,
particularly since the rest of autoconf depends so heavily on it.

| I for one would be less concerned if they had some more time in the git
| tree before being in a stable release.  But I certainly would like to
| hear your judgement about this (I unfortunately haven't had the time yet
| to read them carefully).

I would welcome any review.  But the thought of releasing known-quadratic
algorithms when linear algorithms are available bothers me, since scaling
performance in real-life projects is a real issue (just look at how much
faster libtool bootstraps now compared to when it was using a cubic
algorithm several years ago).

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

iEYEARECAAYFAkiVNckACgkQ84KuGfSFAYD70gCg0lA9m8MIEjfVqfNW+2WPBJao
jj4AoI/wMBiG+kebU3248aMBpVaSlFO/
=ltN3
-----END PGP SIGNATURE-----