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=4:

  %   cumulative   self  self total   
 time   seconds   secondscalls   s/call   s/call  name
 96.75 25.8825.88   12 0.00 0.00  record_files
  0.79 26.09 0.21  112 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

___
Bug-make mailing list
Bug-make@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-make

Re: prerequisite scaling (was: strcache scaling issue)

[Dave Hart]

Ralf Wildenhues Ralf.Wildenhues at gmx.de writes:
 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)

Hi Ralf,

All of this is ground well tread before.  BSDs refer to these as
STAILQs, or singly-linked tail queue.  I notice a subset of of the BSD
sys/queue.h macros is present on Debian stable, not including STAILQs,
but perhaps you could pick up that implementation.  [1]

I don't care for the API of BSD's sys/queue.h, so when I needed
similar stuff in ntpd, I adapted it.  I used the identier FIFO.  The
ntp_lists.h header has the implementation [2] while most of the code
using the FIFOs is in ntp_config.c [3] with a healthy chunk in
ntp_parser.y [4].

The BSD STAILQ macros require the elements to be structs and take the
struct tag as a parameter.  NTP's FIFO macros allow the elements to be
any type and take the complete type name as a parameter.  BSD STAILQ
has a more complete set of macros, aligned with the other list
alternatives in sys/queue.h, but I felt it was too heavyweight for the
relatively simple FIFO case.  I didn't provide an iterator macro, for
example, following a singly-linked list is easy enough code to get
right by hand.  BSD's STAILQ stores the address of its distinct head
structure's next pointer in the indirect tail pointer of an empty
STAILQ, NTP's uses NULL for both pointers in an empty FIFO.

I didn't reply on-list as I'm not on the GNU make bugs list, but don't
consider this reply private, forward/repost as you like.

[1]  http://fxr.watson.org/fxr/source/sys/queue.h
[2]  http://ntp.bkbits.net:8080/ntp-dev/include/ntp_lists.h
[3]  http://ntp.bkbits.net:8080/ntp-dev/ntpd/ntp_config.c
[4]  http://ntp.bkbits.net:8080/ntp-dev/ntpd/ntp_parser.y

Cheers,
Dave Hart


___
Bug-make mailing list
Bug-make@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-make