prerequisite scaling (was: strcache scaling issue)

[Ralf Wildenhues]

Continuing with the previous example makefile, but this time with 'make
-r', I get a bit further, but only to hit the next bumper: this is with
max=40000:

  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 96.75     25.88    25.88   120000     0.00     0.00  record_files
  0.79     26.09     0.21  1120000     0.00     0.00  find_char_unquote
  0.64     26.26     0.17  1212990     0.00     0.00  hash_find_slot
  0.26     26.33     0.07   799239     0.00     0.00  str_hash_1

read.c:
        -: 2065:      /* Add the dependencies to this file entry.  */
   168000: 2066:      if (this != 0)
        -: 2067:        {
        -: 2068:          /* Add the file's old deps and the new ones in THIS 
together.  */
   112000: 2069:          if (f->deps == 0)
    56002: 2070:            f->deps = this;
    55998: 2071:          else if (cmds != 0)
        -: 2072:            {
    #####: 2073:              struct dep *d = this;
[...]
        -: 2081:            }
        -: 2082:          else
        -: 2083:            {
    55998: 2084:              struct dep *d = f->deps;
        -: 2085:
        -: 2086:              /* A rule without commands: put its prereqs at 
the end.  */
928027998: 2087:              while (d->next != 0)
927916002: 2088:                d = d->next;
        -: 2089:
    55998: 2090:              d->next = this;
        -: 2091:            }
        -: 2092:        }


Ouch.

A doubly-linked list would be overkill (and memory-intensive), but I
think storing an end pointer to the dep chain in 'struct file' might
be prudent.  That requires some changes throughout the code though,
and warrants some data structure change to avoid the obvious error
(of updating only ->deps but not ->deps_end).  Maybe a

  struct dep_list {
    struct dep *deps;       /* all dependencies, including duplicates */
    struct dep *last_dep;   /* last dependency in the deps list */
  };

(the second one could be a double pointer if removal is ever needed)
and 'struct file' containing such a struct?

If you agree, I might work on a patch; but I certainly won't mind being
beaten to it.

Cheers,
Ralf