FYI: 4-gary-symtab-rewrite.patch

[Gary V. Vaughan]

Hi,

This one's a biggie.  I have been meaning to do this for over a year,
and some of the groundwaork was already in place...

The symbol table used to be an array of buckets that looked like this:


m4_symbol:
  next -----------> next ---------------> next: ........
  name: "foo"       name: "foo"           name: "bar"
  flags: blah       flags: copy of blah   flags: yadda
  traced: yes       traced: yes
  shadowed: no      shadowed: yes         shadowed: no
  data -----.       data -----.           data -----.
            |                 |                     |
            v                 v                     v
m4_token_data:
  type: TEXT        type: FUNC            type: VOID
  union value           ...                  ...
  

Lots of duplication, and extra symbols to traverse in each bucket if
any macros are pushdefed, and no way to tie a symbol back to the
module which defined it (though I added such a field to m4_symbol a
few months back to make this a little easier) forcing a manual trawl
of the whole symbol table comparing each symbol to every entry in the
builtin table of a module being unloaded.

This patch introduces an m4_hash ADT to abstract away key to value
(i.e. name to symbol) associations.  When a symbol is looked up in the
hash table by name, the following sort of layout is returned (for
a search for "foo" above, say):


m4_symbol:     .--> m4_token_data:  .--> m4_token_data:
  traced: yes  |    next -----------'    next: NULL
  data --------'    type: TEXT           type: FUNC
                    module handle        module handle
                    flags (not shadow!)  flags (not shadow!)
                    union value          union value
                    

Now, a chain of m4_token_data (all of which were pushdefed to the same
key) are returned, where the traced flag is associated with the whole
chain, but each node in the chain has its own parent module and value
and flags etc.  There is no need to synchronise the traced flag, or
duplicate the name field between shadowed symbols, nor any need to
skip shadowed symbols when traversing the table.  Autoconfing the m4
distribution using an m4 from before and after this patch shows a tiny
increase in speed too -- the main benefit is maintainability by laying
the structures out logically and avoiding synchronisation bugs.

   Average of 10 runs of autoconf over the current m4 configure.in:
   
        Before: real  0m0.472s
        After:  real  0m0.461s
        
   Or about 2.5% speedup... possibly a saving of several seconds on
   the sparc machines at work which take a couple of minutes to
   bootstrap the current revision!
        
I don't have a copy of m4-1.4 installed anymore, otherwise it would
have been fun to compare.

Anyway, enough of that.  Obviously there are no regressions, but I
am keen to see this tortured as much as possible since it has impacted
almost the entire codebase...

Cheers,
        Gary.
--
  ())_. Gary V. Vaughan     gary@(oranda.demon.co.uk|gnu.org)
  ( '/  Research Scientist  http://www.oranda.demon.co.uk       ,_())____
  / )=  GNU Hacker          http://www.gnu.org/software/libtool  \'      `&
`(_~)_  Tech' Author        http://sources.redhat.com/autobook   =`---d__/

4-gary-symtab-rewrite.patch
Description: Text document