






                 Recursive Make Considered Harmful

                            _P_e_t_e_r _M_i_l_l_e_r
                      millerp@canb.auug.org.au



                              AABBSSTTRRAACCTT
         For large UNIX projects, the traditional method of
         building the project is to use recursive _m_a_k_e_.  On
         some  projects,  this results in build times which
         are unacceptably large, when all you want to do is
         change one file.    In examining the source of the
         overly long build times, it became evident that  a
         number of apparently unrelated problems combine to
         produce the delay, but on analysis  all  have  the
         same root cause.
         This paper explores a number of problems regarding
         the use of recursive _m_a_k_e_, and shows that they are
         all  symptoms  of the same problem.  Symptoms that
         the UNIX community have long accepted as a fact of
         life,  but  which  need not be endured any longer.
         These problems include recursive _m_a_k_es which  take
         "forever"  to  work out that they need to do noth-
         ing, recursive _m_a_k_es which do  too  much,  or  too
         little, recursive _m_a_k_es which are overly sensitive
         to changes in the source code and require constant
         Makefile intervention to keep them working.
         The  resolution  of these problems can be found by
         looking at what _m_a_k_e does, from first  principles,
         and  then  analyzing  the  effects  of introducing
         recursive _m_a_k_e to  this  activity.   The  analysis
         shows  that  the problem stems from the artificial
         partitioning of the build into  separate  subsets.
         This,  in  turn,  leads to the symptoms described.
         To avoid the symptoms, it  is  only  necessary  to
         avoid the separation; to use a single _m_a_k_e session
         to build the whole project, which is not quite the
         same as a single Makefile.
         This  conclusion  runs counter to much accumulated
         folk wisdom in building large  projects  on  UNIX.
         Some  of  the  main objections raised by this folk
         wisdom are examined and  shown  to  be  unfounded.
         The  results  of actual use are far more encourag-
         ing, with routine development performance improve-
         ments  significantly  faster  than  intuition  may
         indicate, and without the intuitvely expected com-
         promise of modularity.  The use of a whole project
         _m_a_k_e is not as difficult to put into  practice  as
         it may at first appear.






    Peter Miller           23 October 2008                Page 1





    AUUGN'97                   Recursive Make Considered Harmful


               +------------------------------------+
               |Miller, P.A. (1998), _R_e_c_u_r_s_i_v_e _M_a_k_e |
               |_C_o_n_s_i_d_e_r_e_d _H_a_r_m_f_u_l_,                 |
               |AUUGN Journal of AUUG Inc.,  19(1), |
               |pp. 14-25.                          |
               +------------------------------------+



    11..  IInnttrroodduuccttiioonn

    For  large  UNIX  software  development projects, the tradi-
    tional methods of building the project use what has come  to
    be  known  as "recursive _m_a_k_e."  This refers to the use of a
    hierarchy of directories containing  source  files  for  the
    modules  which  make  up the project, where each of the sub-
    directories contains a _M_a_k_e_f_i_l_e which  describes  the  rules
    and instructions for the _m_a_k_e program.  The complete project
    build is done by arranging for  the  top-level  Makefile  to
    change directory into each of the sub-directories and recur-
    sively invoke _m_a_k_e_.

    This paper explores some  significant  problems  encountered
    when  developing  software projects using the recursive _m_a_k_e
    technique.  A simple solution is offered, and  some  of  the
    implications of that solution are explored.

    Recursive _m_a_k_e results in a directory tree which looks some-
    thing like this:
                          +++
                          ++_P+_r|_o_j_e_c_t
                           ++++Mmaokdeufliel1e
                           |++ +|Makefile
                           | + +|source1.c
                           | + +|_e_t_c_._._.
                           ++++m+odule2
                             + +|Makefile
                             + +|source2.c
                             + +|_e_t_c_._._.

    This hierarchy of modules can be  nested  arbitrarily  deep.
    Real-world  projects  often  use two- and three-level struc-
    tures.

    11..11..  AAssssuummeedd KKnnoowwlleeddggee

    This paper assumes that the reader is familiar with develop-
    ing  software  on  UNIX, with the _m_a_k_e program, and with the
    issues of C programming and include file dependencies.

    This paper assumes that you have installed GNU Make on  your
    system  and are moderately familiar with its features.  Some
    -----------
    Copyright (C) 1997 Peter Miller



    Peter Miller           23 October 2008                Page 2





    AUUGN'97                   Recursive Make Considered Harmful


    features of _m_a_k_e described below may not be available if you
    are using the limited version supplied by your vendor.

    22..  TThhee PPrroobblleemm

    There  are  numerous  problems with recursive _m_a_k_e, and they
    are usually observed daily in practice.  Some of these prob-
    lems include:

    +o It is very hard to get the _o_r_d_e_r of the recursion into the
      sub-directories correct.  This order is very unstable  and
      frequently needs to be manually "tweaked."  Increasing the
      number of directories, or  increasing  the  depth  in  the
      directory tree, cause this order to be increasingly unsta-
      ble.

    +o It is often necessary to do more than one  pass  over  the
      sub-directories  to  build  the whole system.  This, natu-
      rally, leads to extended build times.

    +o Because the builds take so long, some dependency  informa-
      tion  is omitted, otherwise development builds take unrea-
      sonable lengths of time, and the developers are  unproduc-
      tive.  This usually leads to things not being updated when
      they need to be, requiring frequent  "clean"  builds  from
      scratch, to ensure everything has actually been built.

    +o Because inter-directory dependencies are either omitted or
      too hard to express, the Makefiles are  often  written  to
      build _t_o_o _m_u_c_h to ensure that nothing is left out.

    +o The  inaccuracy of the dependencies, or the simple lack of
      dependencies, can result in a product which  is  incapable
      of  building  cleanly,  requiring  the build process to be
      carefully watched by a human.

    +o Related to the above, some projects are incapable of  tak-
      ing  advantage  of various "parallel make" impementations,
      because the build does patently silly things.

    Not all projects experience all of  these  problems.   Those
    that  do  experience  the problems may do so intermittently,
    and dismiss the problems as unexplained  "one  off"  quirks.
    This  paper  attempts  to bring together a range of symptoms
    observed over long practice, and presents a systematic anal-
    ysis and solution.

    It  must be emphasized that this paper does not suggest that
    _m_a_k_e itself is the problem.  This paper is working from  the
    premise  that  _m_a_k_e  does nnoott have a bug, that _m_a_k_e does nnoott
    have a design flaw.  The problem is not in _m_a_k_e at all,  but
    rather  in  the  input given to _m_a_k_e - the way _m_a_k_e is being
    used.




    Peter Miller           23 October 2008                Page 3





    AUUGN'97                   Recursive Make Considered Harmful


    33..  AAnnaallyyssiiss

    Before it is possible to address these  seemingly  unrelated
    problems, it is first necessary to understand what _m_a_k_e does
    and how it does it.  It is then  possible  to  look  at  the
    effects recursive _m_a_k_e has on how _m_a_k_e behaves.

    33..11..  WWhhoollee PPrroojjeecctt MMaakkee

    _M_a_k_e  is  an  expert system.  You give it a set of rules for
    how to construct things, and a  target  to  be  constructed.
    The rules can be decomposed into pair-wise ordered dependen-
    cies between files.  _M_a_k_e takes the rules and determines how
    to  build  the  given target.  Once it has determined how to
    construct the target, it proceeds to do so.

    _M_a_k_e determines how to build the target  by  constructing  a
    _d_i_r_e_c_t_e_d  _a_c_y_c_l_i_c  _g_r_a_p_h_,  the DAG familiar to many Computer
    Science students.  The vertices of this graph are the  files
    in  the  system,  the edges of this graph are the inter-file
    dependencies.  The edges of the graph are  directed  because
    the  pair-wise  dependencies  are  ordered;  resulting in an
    _a_c_y_c_l_i_c graph - things which look like loops are resolved by
    the direction of the edges.

    This  paper  will use a small example project for its analy-
    sis.  While the number of files in this  example  is  small,
    there  is  sufficient  complexity  to demonstrate all of the
    above recursive _m_a_k_e problems.  First, however, the  project
    is presented in a non-recursive form.
                           +++
                           ++_P+_r|_o_j_e_c_t
                            + +|Mmaakienf.icle
                            + +|parse.c
                            + +|parse.h
                              -

    The Makefile in this small project looks like this:

                    +--------------------------+
                    |OBJ = main.o parse.o      |
                    |prog: $(OBJ)              |
                    |  $(CC) -o $@ $(OBJ)      |
                    |main.o: main.c parse.h    |
                    |  $(CC) -c main.c         |
                    |parse.o: parse.c parse.h  |
                    |  $(CC) -c parse.c        |
                    +--------------------------+
    Some  of  the  implicit  rules  of  _m_a_k_e  are presented here
    explicitly, to assist the reader in converting the  Makefile
    into its equivalent DAG.

    The  above  Makefile  can be drawn as a DAG in the following
    form:



    Peter Miller           23 October 2008                Page 4





    AUUGN'97                   Recursive Make Considered Harmful


    
                                prog



                          main.o   parse.o


                      main.c   parse.h  parse.c



    This is an _a_c_y_c_l_i_c graph because of the arrows which express
    the  ordering  of  the  relationship  between the files.  If
    there _w_a_s a circular dependency according to the arrows,  it
    would be an error.

    Note that the object files (.o) are dependent on the include
    files (.h) even though it is the source files (.c) which  do
    the  including.  This is because if an include file changes,
    it is the object files which are out-of-date, not the source
    files.

    The  second part of what _m_a_k_e does it to perform a _p_o_s_t_o_r_d_e_r
    traversal of the DAG.  That is, the dependencies are visited
    first.  The actual order of traversal is undefined, but most
    _m_a_k_e implementations work down the graph from left to  right
    for  edges  below the same vertex, and most projects implic-
    itly rely on this behavior.  The last-time-modified of  each
    file is examined, and higher files are determined to be out-
    of-date if any of the lower files on which they  depend  are
    younger.   Where a file is determined to be out-of-date, the
    action associated with the relevant graph edge is  performed
    (in the above example, a compile or a link).

    The  use of recursive _m_a_k_e affects both phases of the opera-
    tion of _m_a_k_e_: it causes _m_a_k_e to construct an inaccurate DAG,
    and  it  forces _m_a_k_e to traverse the DAG in an inappropriate
    order.

    33..22..  RReeccuurrssiivvee MMaakkee

    To examine the effects of recursive _m_a_k_es, the above example
    will  be  artificially segmented into two modules, each with
    its own Makefile, and a top-level Makefile  used  to  invoke
    each of the module Makefiles.

    This example is intentionally artificial, and thoroughly so.
    However, all "modularity" of all projects is artificial,  to
    some  extent.  Consider: for many projects, the linker flat-
    tens it all out again, right at the end.

    The directory structure is as follows:




    Peter Miller           23 October 2008                Page 5





    AUUGN'97                   Recursive Make Considered Harmful


                          +++
                          ++_P+_r|_o_j_e_c_t
                           ++++Maanktefile
                           |++ +|Makefile
                           | - +|main.c
                           ++++b+ee
                             + +|Makefile
                             + +|parse.c
                             + +|parse.h

    The top-level Makefile  often  looks  a  lot  like  a  shell
    script:

                  +-------------------------------+
                  |MODULES = ant bee              |
                  |all:                           |
                  |  for dir in $(MODULES); do \  |
                  |    (cd $$dir; ${MAKE} all); \ |
                  |  done                         |
                  +-------------------------------+
    The ant/Makefile looks like this:

                  +------------------------------+
                  |all: main.o                   |
                  |main.o: main.c ../bee/parse.h |
                  |  $(CC) -I../bee -c main.c    |
                  +------------------------------+
    and the equivalent DAG looks like this:
    
                               main.o



                          main.c    parse.h

    The bee/Makefile looks like this:

                   +----------------------------+
                   |OBJ = ../ant/main.o parse.o |
                   |all: prog                   |
                   |prog: $(OBJ)                |
                   |  $(CC) -o $@ $(OBJ)        |
                   |parse.o: parse.c parse.h    |
                   |  $(CC) -c parse.c          |
                   +----------------------------+
    and the equivalent DAG looks like this:











    Peter Miller           23 October 2008                Page 6





    AUUGN'97                   Recursive Make Considered Harmful


    
                              prog



                        main.o    parse.o


                             parse.h  parse.c



    Take  a  close look at the DAGs.  Notice how neither is com-
    plete - there are vertices and edges  (files  and  dependen-
    cies) missing from both DAGs.  When the entire build is done
    from the top level, everything will work.

    But what happens when small  changes  occur?   For  example,
    what would happen if the parse.c and parse.h files were gen-
    erated from a parse.y yacc grammar?  This would add the fol-
    lowing lines to the bee/Makefile:

                    +--------------------------+
                    |parse.c parse.h: parse.y  |
                    |  $(YACC) -d parse.y      |
                    |  mv y.tab.c parse.c      |
                    |  mv y.tab.h parse.h      |
                    +--------------------------+
    And the equivalent DAG changes to look like this:
    
                              prog



                        main.o    parse.o


                             parse.h  parse.c



                                  parse.y



    This  change  has  a  simple  effect:  if parse.y is edited,
    main.o will nnoott be constructed correctly.  This  is  because
    the DAG for ant knows about only some of the dependencies of
    main.o, and the DAG for bee knows none of them.

    To understand why this happens, it is necessary to  look  at
    the  actions _m_a_k_e will take _f_r_o_m _t_h_e _t_o_p _l_e_v_e_l_.  Assume that
    the project is in a self-consistent state.  Now edit parse.y
    in such a way that the generated parse.h file will have non-



    Peter Miller           23 October 2008                Page 7





    AUUGN'97                   Recursive Make Considered Harmful


    trivial differences.  However, when the  top-level  _m_a_k_e  is
    invoked,  first ant and then bee is visited.  But ant/main.o
    is _n_o_t recompiled, because  bee/parse.h  has  not  yet  been
    regenerated  and  thus  does not yet indicate that main.o is
    out-of-date.  It is not until bee is visited by  the  recur-
    sive  _m_a_k_e  that parse.c and parse.h are reconstructed, fol-
    lowed by parse.o.  When the program  is  linked  main.o  and
    parse.o  are  non-trivially incompatible.  That is, the pro-
    gram is _w_r_o_n_g_.

    33..33..  TTrraaddiittiioonnaall SSoolluuttiioonnss

    There are three traditional fixes for the above "glitch."

    33..33..11..  RReesshhuuffffllee

    The first is to manually tweak the order of the  modules  in
    the  top-level  Makefile.  But why is this tweak required at
    all?  Isn't _m_a_k_e supposed to be an expert system?   Is  _m_a_k_e
    somehow flawed, or did something else go wrong?

    To answer this question, it is necessary to look, not at the
    graphs, but the _o_r_d_e_r _o_f _t_r_a_v_e_r_s_a_l of the graphs.  In  order
    to operate correctly, _m_a_k_e needs to perform a _p_o_s_t_o_r_d_e_r tra-
    versal, but in separating the DAG into two pieces, _m_a_k_e  has
    not  been  _a_l_l_o_w_e_d  to  traverse  the graph in the necessary
    order - instead the project has dictated an order of traver-
    sal.   An order which, when you consider the original graph,
    is plain _w_r_o_n_g_.  Tweaking the  top-level  Makefile  corrects
    the order to one similar to that which _m_a_k_e could have used.
    Until the next dependency is added...

    Note that "make -j" (parallel build) invalidates many of the
    ordering  assumptions  implicit  in  the reshuffle solution,
    making it useless.  And then there are all  of the sub-makes
    all doing their builds in parallel, too.

    33..33..22..  RReeppeettiittiioonn

    The  second  traditional  solution  is to make more than one
    pass in the top-level Makefile, something like this:

                  +-------------------------------+
                  |MODULES = ant bee              |
                  |all:                           |
                  |  for dir in $(MODULES); do \  |
                  |    (cd $$dir; ${MAKE} all); \ |
                  |  done                         |
                  |  for dir in $(MODULES); do \  |
                  |    (cd $$dir; ${MAKE} all); \ |
                  |  done                         |
                  +-------------------------------+





    Peter Miller           23 October 2008                Page 8





    AUUGN'97                   Recursive Make Considered Harmful


    This doubles the length of time  it  takes  to  perform  the
    build.   But that is not all: there is no guarantee that two
    passes are enough!  The upper bound of the number of  passes
    is  not  even  proportional  to the number of modules, it is
    instead proportional to the  number  of  graph  edges  which
    cross module boundaries.

    33..33..33..  OOvveerrkkiillll

    We  have  already  seen an example of how recursive _m_a_k_e can
    build too little, but another common problem is to build too
    much.  The third traditional solution to the above glitch is
    to add even _m_o_r_e lines to ant/Makefile:

                    +--------------------------+
                    |.PHONY: ../bee/parse.h    |
                    |../bee/parse.h:           |
                    |    cd ../bee; \          |
                    |    make clean; \         |
                    |    make all              |
                    +--------------------------+
    This means that whenever main.o is made, parse.h will always
    be  considered to be out-of-date.  All of bee will always be
    rebuilt including parse.h, and  so  main.o  will  always  be
    rebuilt, _e_v_e_n _i_f _e_v_e_r_y_t_h_i_n_g _w_a_s _s_e_l_f _c_o_n_s_i_s_t_e_n_t_.

    Note that "make -j" (parallel build) invalidates many of the
    ordering assumptions implicit in the overkill solution, mak-
    ing  it  useless, because all of the sub-makes are all doing
    their builds ("clean" then "all")  in  parallel,  constantly
    interfering with each other in non-deterministic ways.

    44..  PPrreevveennttiioonn

    The  above  analysis  is based on one simple action: the DAG
    was artificially separated  into  incomplete  pieces.   This
    separation  resulted  in  all  of  the  problems familiar to
    recursive _m_a_k_e builds.

    Did _m_a_k_e get it wrong?  No.  This is a case of  the  ancient
    GIGO  principle:  _G_a_r_b_a_g_e _I_n_, _G_a_r_b_a_g_e _O_u_t_.  Incomplete Make-
    files are _w_r_o_n_g Makefiles.

    To avoid these problems, don't break the  DAG  into  pieces;
    instead, use one Makefile for the entire project.  It is not
    the recursion itself which is harmful, it  is  the  crippled
    Makefiles  which  are used in the recursion which are _w_r_o_n_g.
    It is not a deficiency of _m_a_k_e itself that recursive _m_a_k_e is
    broken,  it does the best it can with the flawed input it is
    given.

         "_B_u_t_, _b_u_t_, _b_u_t_._._.  _Y_o_u _c_a_n_'_t _d_o _t_h_a_t_!" I hear  you
         cry.   "_A _s_i_n_g_l_e Makefile _i_s _t_o_o _b_i_g_, _i_t_'_s _u_n_m_a_i_n_-
         _t_a_i_n_a_b_l_e_, _i_t_'_s _t_o_o _h_a_r_d _t_o _w_r_i_t_e _t_h_e _r_u_l_e_s_, _y_o_u_'_l_l



    Peter Miller           23 October 2008                Page 9





    AUUGN'97                   Recursive Make Considered Harmful


         _r_u_n  _o_u_t _o_f _m_e_m_o_r_y_, _I _o_n_l_y _w_a_n_t _t_o _b_u_i_l_d _m_y _l_i_t_t_l_e
         _b_i_t_, _t_h_e _b_u_i_l_d _w_i_l_l _t_a_k_e _t_o_o _l_o_n_g_.  _I_t_'_s _j_u_s_t  _n_o_t
         _p_r_a_c_t_i_c_a_l_."

    These  are  valid  concerns,  and  they frequently lead _m_a_k_e
    users to the conclusion that re-working their build  process
    does  not  have any short- or long-term benefits.  This con-
    clusion is based on ancient, enduring, false assumptions.

    The following sections will address each of  these  concerns
    in turn.

    44..11..  AA SSiinnggllee Makefile IIss TToooo BBiigg

    If  the  entire project build description were placed into a
    single Makefile this would certainly be true, however modern
    _m_a_k_e  implementations have _i_n_c_l_u_d_e statements.  By including
    a relevant fragment from each module, the total size of  the
    Makefile  and  its  include files need be no larger than the
    total size of the Makefiles in the recursive case.

    44..22..  AA SSiinnggllee Makefile IIss UUnnmmaaiinnttaaiinnaabbllee

    The complexity of using a single  top-level  Makefile  which
    includes a fragment from each module is no more complex than
    in the recursive case.  Because the DAG  is  not  segmented,
    this  form  of  Makefile becomes less complex, and thus _m_o_r_e
    maintainable, simply because fewer "tweaks" are required  to
    keep it working.

    Recursive  Makefiles  have a great deal of repetition.  Many
    projects solve this by using include files.  By using a sin-
    gle  Makefile  for  the  project,  the need for the "common"
    include files disappears - the single Makefile is the common
    part.

    44..33..  IItt''ss TToooo HHaarrdd TToo WWrriittee TThhee RRuulleess

    The only change required is to include the directory part in
    filenames in a number of places.  This is because  the  _m_a_k_e
    is  performed  from  the  top-level  directory;  the current
    directory is not the one in which the file  appears.   Where
    the  output file is explicitly stated in a rule, this is not
    a problem.

    GCC allows a -o option in conjunction with  the  -c  option,
    and  GNU Make knows this.  This results in the implicit com-
    pilation rule placing  the  output  in  the  correct  place.
    Older  and dumber C compilers, however, may not allow the -o
    option with the -c option, and will leave the object file in
    the  top-level  directory (_i_._e_. the wrong directory).  There
    are three ways for you to fix this: get GNU  Make  and  GCC,
    override  the  built-in  rule  with one which does the right
    thing, or complain to your vendor.



    Peter Miller           23 October 2008               Page 10





    AUUGN'97                   Recursive Make Considered Harmful


    Also, K&R C compilers will start  the  double-quote  include
    path  (#include  "_f_i_l_e_n_a_m_e_._h")  from  the current directory.
    This will not do what you want.  ANSI C compliant C  compil-
    ers,  however,  start the double-quote include path from the
    directory in which the source file appears; thus, no  source
    changes are required.  If you don't have an ANSI C compliant
    C compiler, you should consider installing GCC on your  sys-
    tem as soon as possible.

    44..44..  II OOnnllyy WWaanntt TToo BBuuiilldd MMyy LLiittttllee BBiitt

    Most  of  the  time,  developers are deep within the project
    tree and they edit one or two files and  then  run  _m_a_k_e  to
    compile  their  changes  and try them out.  They may do this
    dozens or hundreds of times a day.  Being  forced  to  do  a
    full project build every time would be absurd.

    Developers  always have the option of giving _m_a_k_e a specific
    target.  This is always the case, it's just that we  usually
    rely  on  the  default target in the Makefile in the current
    directory to shorten the command line for us.  Building  "my
    little bit" can still be done with a whole project Makefile,
    simply by using a specific target, and an alias if the  com-
    mand line is too long.

    Is  doing  a  full project build every time so absurd?  If a
    change made in a module has repercussions in other  modules,
    because  there  is  a dependency the developer is unaware of
    (but the Makefile is aware of), isn't  it  better  that  the
    developer  find out as early as possible?  Dependencies like
    this _w_i_l_l be found, because the DAG is more complete than in
    the recursive case.

    The  developer is rarely a seasoned old salt who knows every
    one of the million lines  of  code  in  the  product.   More
    likely the developer is a short-term contractor or a junior.
    You don't want implications like these to blow up after  the
    changes are integrated with the master source, you want them
    to blow up on the developer in some nice safe  sand-box  far
    away from the master source.

    If  you  want to make "just your little" bit because you are
    concerned that performing a full project build will  corrupt
    the  project  master  source, due to the directory structure
    used in your project, see the "Projects  _v_e_r_s_u_s  Sand-Boxes"
    section below.

    44..55..  TThhee BBuuiilldd WWiillll TTaakkee TToooo LLoonngg

    This  statement  can  be  made from one of two perspectives.
    First, that a whole project _m_a_k_e, even  when  everything  is
    up-to-date,  inevitably  takes a long time to perform.  Sec-
    ondly, that these inevitable delays are unacceptable when  a
    developer  wants  to  quickly  compile and link the one file



    Peter Miller           23 October 2008               Page 11





    AUUGN'97                   Recursive Make Considered Harmful


    that they have changed.

    44..55..11..  PPrroojjeecctt BBuuiillddss

    Consider a hypothetical project with 1000 source (.c) files,
    each  of which has its calling interface defined in a corre-
    sponding include (.h) file with defines,  type  declarations
    and  function  prototypes.   These 1000 source files include
    their own interface definition, plus the  interface  defini-
    tions  of any other module they may call.  These 1000 source
    files are compiled into 1000 object  files  which  are  then
    linked  into  an  executable  program.  This system has some
    3000 files which _m_a_k_e must be told about, and be told  about
    the  include  dependencies, and also explore the possibility
    that implicit rules (.y -> .c for example) may be necessary.

    In order to build the DAG, _m_a_k_e must "stat" 3000 files, plus
    an additional 2000 files or so, depending on which  implicit
    rules  your  _m_a_k_e  knows  about  and  your Makefile has left
    enabled.  On the author's humble 66MHz i486 this takes about
    10  seconds; on native disk on faster platforms it goes even
    faster.  With NFS over 10MB Ethernet it takes about 10  sec-
    onds, no matter what the platform.

    This  is an astonishing statistic!  Imagine being able to do
    a single file compile, out of 1000 source files, in only  10
    seconds, plus the time for the compilation itself.

    Breaking  the  set of files up into 100 modules, and running
    it as a recursive _m_a_k_e takes about 25 seconds.  The repeated
    process  creation  for the subordinate _m_a_k_e invocations take
    quite a long time.

    Hang on a minute!  On real-world  projects  with  less  than
    1000 files, it takes an awful lot longer than 25 seconds for
    _m_a_k_e to work out that  it  has  nothing  to  do.   For  some
    projects,  doing  it in only 25 minutes would be an improve-
    ment!  The above result tells us that it is not  the  number
    of  files  which is slowing us down (that only takes 10 sec-
    onds), and it is not the repeated process creation  for  the
    subordinate  _m_a_k_e  invocations  (that  only takes another 15
    seconds).  So just what _i_s taking so long?

    The traditional solutions  to  the  problems  introduced  by
    recursive _m_a_k_e often increase the number of subordinate _m_a_k_e
    invocations beyond the minimum described here; _e_._g_. to  per-
    form multiple repetitions (3.3.2), or to overkill cross-mod-
    ule dependencies (3.3.3).  These can take a long time,  par-
    ticularly  when combined, but do not account for some of the
    more spectacular build times; what else is taking so long?

    Complexity of the Makefile is what is taking so long.   This
    is covered, below, in the _E_f_f_i_c_i_e_n_t _M_a_k_e_f_i_l_e_s section.




    Peter Miller           23 October 2008               Page 12





    AUUGN'97                   Recursive Make Considered Harmful


    44..55..22..  DDeevveellooppmmeenntt BBuuiillddss

    If, as in the 1000 file example, it only takes 10 seconds to
    figure out which one of the files needs  to  be  recompiled,
    there is no serious threat to the productivity of developers
    if they do a whole-project _m_a_k_e as opposed to a  module-spe-
    cific  _m_a_k_e.  The advantage for the project is that the mod-
    ule-centric developer is reminded  at  relevant  times  (and
    only  relevant  times)  that  their work has wider ramifica-
    tions.

    By consistently using C include files which contain accurate
    interface  definitions (including function prototypes), this
    will produce compilation errors in many of the  cases  which
    would result in a defective product.  By doing whole-project
    builds, developers discover such errors very  early  in  the
    development  process, and can fix the problems when they are
    least expensive.

    44..66..  YYoouu''llll RRuunn OOuutt OOff MMeemmoorryy

    This is the most interesting response.  Once long ago, on  a
    CPU far, far away, it may even have been true.  When Feldman
    [feld78] first wrote _m_a_k_e it was 1978 and  he  was  using  a
    PDP11.  Unix processes were limited to 64KB of data.

    On  such  a  computer, the above project with its 3000 files
    detailed in the whole-project Makefile, would  probably  _n_o_t
    allow the DAG and rule actions to fit in memory.

    But  we  are not using PDP11s any more.  The physical memory
    of modern computers exceeds 10MB for  _s_m_a_l_l  computers,  and
    virtual  memory  often exceeds 100MB.  It is going to take a
    project with  hundreds  of  thousands  of  source  files  to
    exhaust  virtual  memory on a _s_m_a_l_l modern computer.  As the
    1000 source file example takes less  than  100KB  of  memory
    (try  it,  I did) it is unlikely that any project manageable
    in a single directory tree on a  single  disk  will  exhaust
    your computer's memory.

    44..77..  WWhhyy NNoott FFiixx TThhee DDAAGG IInn TThhee MMoodduulleess??

    It  was  shown in the above discussion that the problem with
    recursive _m_a_k_e is that the DAGs are incomplete.  It  follows
    that  by  adding the missing portions, the problems would be
    resolved without  abandoning  the  existing  recursive  _m_a_k_e
    investment.

    +o The  developer needs to remember to do this.  The problems
      will not affect the  developer  of  the  module,  it  will
      affect the developers of _o_t_h_e_r modules.  There is no trig-
      ger to remind the developer to do this, other than the ire
      of fellow developers.




    Peter Miller           23 October 2008               Page 13





    AUUGN'97                   Recursive Make Considered Harmful


    +o It  is  difficult to work out where the changes need to be
      made.  Potentially every Makefile in  the  entire  project
      needs  to  be  examined  for  possible  modifications.  Of
      course, you can wait for your fellow  developers  to  find
      them for you.

    +o The include dependencies will be recomputed unnecessarily,
      or will be interpreted incorrectly.  This is because  _m_a_k_e
      is string based, and thus "." and "../ant" are two differ-
      ent places, even when you are in the ant directory.   This
      is  of concern when include dependencies are automatically
      generated - as they are for all large projects.

    By making sure that each Makefile is complete, you arrive at
    the  point  where  the Makefile for at least one module con-
    tains the equivalent of  a  whole-project  Makefile  (recall
    that these modules form a single project and are thus inter-
    connected), and there is no need for the recursion any more.

    55..  EEffffiicciieenntt MMaakkeeffiilleess

    The central theme of this paper is the _s_e_m_a_n_t_i_c side-effects
    of artificially separating a Makefile into the pieces neces-
    sary  to perform a recursive _m_a_k_e.  However, once you have a
    large number of Makefiles,  the  speed  at  which  _m_a_k_e  can
    interpret this multitude of files also becomes an issue.

    Builds can take "forever" for both these reasons: the tradi-
    tional fixes for the separated DAG may be building too  much
    _a_n_d your Makefile may be inefficient.

    55..11..  DDeeffeerrrreedd EEvvaalluuaattiioonn

    The text in a Makefile must somehow be read from a text file
    and understood by _m_a_k_e so that the DAG can  be  constructed,
    and  the  specified  actions attached to the edges.  This is
    all kept in memory.

    The input language for Makefiles is deceptively  simple.   A
    crucial  distinction  that  often  escapes  both novices and
    experts alike is that _m_a_k_e's input language is  _t_e_x_t  _b_a_s_e_d_,
    as  opposed  to  token  based,  as is the case for C or AWK.
    _M_a_k_e does the very least possible to process input lines and
    stash them away in memory.

    As an example of this, consider the following assignment:

                    +--------------------------+
                    |OBJ = main.o parse.o      |
                    +--------------------------+
    Humans  read  this  as  the  variable OBJ being assigned two
    filenames "main.o" and "parse.o".  But _m_a_k_e does not see  it
    that  way.   Instead   OBJ  is  assigned  the _s_t_r_i_n_g "main.o
    parse.o".  It gets worse:



    Peter Miller           23 October 2008               Page 14





    AUUGN'97                   Recursive Make Considered Harmful


                    +--------------------------+
                    |SRC = main.c parse.c      |
                    |OBJ = $(SRC:.c=.o)        |
                    +--------------------------+
    In this case humans expect _m_a_k_e to assign two  filenames  to
    OBJ,  but  _m_a_k_e  actually assigns the string "$(SRC:.c=.o)".
    This is because it is a _m_a_c_r_o language with deferred evalua-
    tion, as opposed to one with variables and immediate evalua-
    tion.

    If this does not seem too problematic, consider the  follow-
    ing Makefile:

                   +-----------------------------+
                   |SRC = $(shell echo 'Ouch!' \ |
                   |  1>&2 ; echo *.[cy])        |
                   |OBJ = \                      |
                   |  $(patsubst %.c,%.o,\       |
                   |    $(filter %.c,$(SRC))) \  |
                   |  $(patsubst %.y,%.o,\       |
                   |    $(filter %.y,$(SRC)))    |
                   |test: $(OBJ)                 |
                   |  $(CC) -o $@ $(OBJ)         |
                   +-----------------------------+
    How  many  times  will the shell command be executed?  OOuucchh!!
    It will be executed _t_w_i_c_e just to construct the DAG,  and  a
    further _t_w_o times if the rule needs to be executed.

    If  this shell command does anything complex or time consum-
    ing (and it usually does) it will  take  _f_o_u_r  times  longer
    than you thought.

    But  it  is  worth looking at the other portions of that OBJ
    macro.  Each time it is named, a huge amount  of  processing
    is performed:

    +o The  argument  to  _s_h_e_l_l is a single string (all built-in-
      functions take a single string argument).  The  string  is
      executed  in  a sub-shell, and the standard output of this
      command is read back in, translating newlines into spaces.
      The result is a single string.

    +o The  argument to _f_i_l_t_e_r is a single string.  This argument
      is broken into two strings at the first comma.  These  two
      strings are then each broken into sub-strings separated by
      spaces.  The first set are the patterns,  the  second  set
      are  the  filenames.   Then,  for each of the pattern sub-
      strings, if a filename sub-string matches it,  that  file-
      name  is  included  in the output.  Once all of the output
      has been found, it is re-assembled into  a  single  space-
      separated string.

    +o The  argument  to _p_a_t_s_u_b_s_t is a single string.  This argu-
      ment is broken into three strings at the first and  second



    Peter Miller           23 October 2008               Page 15





    AUUGN'97                   Recursive Make Considered Harmful


      commas.   The third string is then broken into sub-strings
      separated by spaces, these are the filenames.   Then,  for
      each  of  the filenames which match the first string it is
      substituted according to the second string.  If a filename
      does  not match, it is passed through unchanged.  Once all
      of the output has been generated, it is re-assembled  into
      a single space-separated string.

    Notice how many times those strings are disassembled and re-
    assembled.  Notice how many  ways  that  happens.   _T_h_i_s  _i_s
    _s_l_o_w_.   The  example  here names just two files but consider
    how inefficient this would be for 1000 files.  Doing it _f_o_u_r
    times becomes decidedly inefficient.

    If  you  are using a dumb _m_a_k_e that has no substitutions and
    no built-in functions, this cannot bite you.  But  a  modern
    _m_a_k_e  has  lots  of  built-in  functions and can even invoke
    shell commands on-the-fly.  The  semantics  of  _m_a_k_e's  text
    manipulation  is  such  that  string manipulation in _m_a_k_e is
    very CPU intensive, compared to performing the  same  string
    manipulations in C or AWK.

    55..22..  IImmmmeeddiiaattee EEvvaalluuaattiioonn

    Modern  _m_a_k_e  implementations  have  an immediate evaluation
    ":=" assignment operator.  The above example can be re-writ-
    ten as

                  +------------------------------+
                  |SRC := $(shell echo 'Ouch!' \ |
                  |  1>&2 ; echo *.[cy])         |
                  |OBJ := \                      |
                  |  $(patsubst %.c,%.o,\        |
                  |    $(filter %.c,$(SRC))) \   |
                  |  $(patsubst %.y,%.o,\        |
                  |    $(filter %.y,$(SRC)))     |
                  |test: $(OBJ)                  |
                  |  $(CC) -o $@ $(OBJ)          |
                  +------------------------------+
    Note  that _b_o_t_h assignments are immediate evaluation assign-
    ments.  If the first  were  not,  the  shell  command  would
    always  be  executed  twice.   If  the  second were not, the
    expensive substitutions would be performed  at  least  twice
    and possibly four times.

    As  a rule of thumb: always use immediate evaluation assign-
    ment unless you knowingly want deferred evaluation.

    55..33..  IInncclluuddee FFiilleess

    Many Makefiles perform the same text processing (the filters
    above,  for  example)  for  every  single  _m_a_k_e run, but the
    results of the processing rarely change.   Wherever  practi-
    cal,  it is more efficient to record the results of the text



    Peter Miller           23 October 2008               Page 16





    AUUGN'97                   Recursive Make Considered Harmful


    processing into a file, and have the Makefile  include  this
    file.

    55..44..  DDeeppeennddeenncciieess

    Don't  be  miserly  with include files.  They are relatively
    inexpensive to read, compared to $(shell),  so  more  rather
    than less doesn't greatly affect efficiency.

    As  an  example of this, it is first necessary to describe a
    useful feature of GNU Make: once a Makefile  has  been  read
    in, if any of its included files were out-of-date (or do not
    yet exist), they are re-built, and then _m_a_k_e  starts  again,
    which  has  the  result that _m_a_k_e is now working with up-to-
    date include files.  This feature can be exploited to obtain
    automatic  include  file  dependency tracking for C sources.
    The obvious way to implement it, however, has a subtle flaw.

                    +--------------------------+
                    |SRC := $(wildcard *.c)    |
                    |OBJ := $(SRC:.c=.o)       |
                    |test: $(OBJ)              |
                    |  $(CC) -o $@ $(OBJ)      |
                    |include dependencies      |
                    |dependencies: $(SRC)      |
                    |  depend.sh $(CFLAGS) \   |
                    |    $(SRC) > $@           |
                    +--------------------------+
    The depend.sh script prints lines of the form

         _f_i_l_e.o: _f_i_l_e.c _i_n_c_l_u_d_e.h ...

    The  most  simple  implementation of this is to use _G_C_C_, but
    you will need an equivalent awk script or C program  if  you
    have a different compiler:

                    +--------------------------+
                    |#!/bin/sh                 |
                    |gcc -MM -MG "$@"          |
                    +--------------------------+
    This  implementation  of tracking C include dependencies has
    several serious flaws, but the one most commonly  discovered
    is  that  the  dependencies file does not, itself, depend on
    the C include files.  That is, it is not re-built if one  of
    the  include  files  changes.   There  is no edge in the DAG
    joining the dependencies vertex to any of the  include  file
    vertices.   If  an  include  file changes to include another
    file (a nested include), the dependencies will not be recal-
    culated,  and potentially the C file will not be recompiled,
    and thus the program will not be re-built correctly.

    A classic build-too-little problem, caused  by  giving  _m_a_k_e
    inadequate  information,  and  thus  causing  it to build an
    inadequate DAG and reach the wrong conclusion.



    Peter Miller           23 October 2008               Page 17





    AUUGN'97                   Recursive Make Considered Harmful


    The traditional solution is to build too much:

                    +--------------------------+
                    |SRC := $(wildcard *.c)    |
                    |OBJ := $(SRC:.c=.o)       |
                    |test: $(OBJ)              |
                    |  $(CC) -o $@ $(OBJ)      |
                    |include dependencies      |
                    |.PHONY: dependencies      |
                    |dependencies: $(SRC)      |
                    |  depend.sh $(CFLAGS) \   |
                    |    $(SRC) > $@           |
                    +--------------------------+
    Now, even if  the  project  is  completely  up-do-date,  the
    dependencies will be re-built.  For a large project, this is
    very wasteful, and can be a major contributor to _m_a_k_e taking
    "forever" to work out that nothing needs to be done.

    There  is  a  second problem, and that is that if any _o_n_e of
    the C files changes, _a_l_l of the C files will  be  re-scanned
    for  include dependencies.  This is as inefficient as having
    a Makefile which reads

                    +--------------------------+
                    |prog: $(SRC)              |
                    |  $(CC) -o $@ $(SRC)      |
                    +--------------------------+
    What is needed, in exact analogy to the C case, is  to  have
    an  intermediate form.  This is usually given a ".d" suffix.
    By exploiting the fact that more than one file may be  named
    in  an  include  line, there is no need to "link" all of the
    ".d" files together:

                    +--------------------------+
                    |SRC := $(wildcard *.c)    |
                    |OBJ := $(SRC:.c=.o)       |
                    |test: $(OBJ)              |
                    |  $(CC) -o $@ $(OBJ)      |
                    |include $(OBJ:.o=.d)      |
                    |%.d: %.c                  |
                    |  depend.sh $(CFLAGS) \   |
                    |    $*.c > $@             |
                    +--------------------------+

    This has one more thing to fix:  just  as  the  object  (.o)
    files  depend  on the source files and the include files, so
    do the dependency (.d) files.

         _f_i_l_e.d _f_i_l_e.o: _f_i_l_e.c _i_n_c_l_u_d_e.h

    This means tinkering with the depend.sh script again:






    Peter Miller           23 October 2008               Page 18





    AUUGN'97                   Recursive Make Considered Harmful


                +-----------------------------------+
                |#!/bin/sh                          |
                |gcc -MM -MG "$@" |                 |
                |sed -e 's@^\(.*\)\.o:@\1.d \1.o:@' |
                +-----------------------------------+

    This method of determining include file dependencies results
    in  the  Makefile  including  more  files  than the original
    method, but opening files is less expensive than  rebuilding
    all  of  the dependencies every time.  Typically a developer
    will edit one or two files before re-building;  this  method
    will  rebuild  the  _e_x_a_c_t  dependency file affected (or more
    than one, if you edited an include file).  On balance,  this
    will use less CPU, and less time.

    In  the case of a build where nothing needs to be done, _m_a_k_e
    will actually do  nothing,  and  will  work  this  out  very
    quickly.

    However,  the above technique assumes your project fits eni-
    trely within the one directory.  For  large  projects,  this
    usually  isn't  the  case.   This  means  tinkering with the
    depend.sh script again:

                +-----------------------------------+
                |#!/bin/sh                          |
                |DIR="$1"                           |
                |shift 1                            |
                |case "$DIR" in                     |
                |"" | ".")                          |
                |gcc -MM -MG "$@" |                 |
                |sed -e 's@^\(.*\)\.o:@\1.d \1.o:@' |
                |;;                                 |
                |*)                                 |
                |gcc -MM -MG "$@" |                 |
                |sed -e "s@^\(.*\)\.o:@$DIR/\1.d \  |
                |$DIR/\1.o:@"                       |
                |;;                                 |
                |esac                               |
                +-----------------------------------+
    And the rule needs to change, too, to pass the directory  as
    the first argument, as the script expects.

                    +---------------------------+
                    |%.d: %.c                   |
                    |  depend.sh `dirname $*` \ |
                    |    $(CFLAGS) $*.c > $@    |
                    +---------------------------+
    Note  that  the  .d  files will be relative to the top level
    directory.  Writing them so that they can be used  from  any
    level is possible, but beyond the scope of this paper.






    Peter Miller           23 October 2008               Page 19





    AUUGN'97                   Recursive Make Considered Harmful


    55..55..  MMuullttiipplliieerr

    All of the inefficiencies described in this section compound
    together.  If you do 100 Makefile interpretations, once  for
    each module, checking 1000 source files can take a very long
    time - if the interpretation requires complex processing  or
    performs  unnecessary  work, or both.  A whole project _m_a_k_e,
    on the other hand, only needs to interpret  a  single  Make-
    file.

    66..  PPrroojjeeccttss _v_e_r_s_u_s SSaanndd--bbooxxeess

    The  above discussion assumes that a project resides under a
    single directory tree, and this is often  the  ideal.   How-
    ever,  the realities of working with large software projects
    often lead to weird and wonderful  directory  structures  in
    order  to  have  developers working on different sections of
    the project without taking complete copies and thereby wast-
    ing precious disk space.

    It  is  possible to see the whole-project _m_a_k_e proposed here
    as impractical, because it does not match the evolved  meth-
    ods of your development process.

    The  whole-project _m_a_k_e proposed here does have an effect on
    development methods: it can give  you  cleaner  and  simpler
    build  environments  for  your  developers.  By using _m_a_k_e's
    VPATH feature, it is possible to copy only those  files  you
    need  to  edit  into  your private work area, often called a
    _s_a_n_d_-_b_o_x_.

    The simplest explanation of what VPATH does is  to  make  an
    analogy  with  the  include file search path specified using
    -I_p_a_t_h options to the  C  compiler.   This  set  of  options
    describes  where to look for files, just as VPATH tells _m_a_k_e
    where to look for files.

    By using VPATH, it is possible to "stack"  the  sand-box  _o_n
    _t_o_p _o_f the project master source, so that files in the sand-
    box take precedence, but it is the union of  all  the  files
    which _m_a_k_e uses to perform the build.
                      +          +
                     +_M+_a_s_t_e_r _S_o_u_r+_c+_e
                     +   main.c +   _C_o_m_b_i_n_e_d _V_i_e_w
                    +   parse.y+       main.c
                     _S_a_n_d_-_B_o_x    +     parse.y
                      main.c    ++   variable.c
                                +
                    variable.c +


    In  this  environment, the sand-box has the same tree struc-
    ture as the project master source.  This  allows  developers
    to  safely  change  things  across separate modules, _e_._g_. if



    Peter Miller           23 October 2008               Page 20





    AUUGN'97                   Recursive Make Considered Harmful


    they are changing a module interface.  It  also  allows  the
    sand-box  to be physically separate - perhaps on a different
    disk, or under their home directory.   It  also  allows  the
    project master source to be read-only, if you have (or would
    like) a rigorous check-in procedure.

    Note: in addition to adding a VPATH line to your development
    Makefile, you will also need to add -I options to the CFLAGS
    macro, so that the C compiler uses the  same  path  as  _m_a_k_e
    does.   This  is  simply done with a 3-line Makefile in your
    work area - set a macro, set the VPATH, and then include the
    Makefile from the project master source.

    66..11..  VVPPAATTHH SSeemmaannttiiccss

    For  the above discussion to apply, you need to use GNU make
    3.76 or later.  For versions of GNU Make earlier than  3.76,
    you  will  need  Paul  Smith's  VPATH+  patch.   This may be
    obtained from  ftp://ftp.wellfleet.com/netman/psmith/gmake/.

    The  POSIX  semantics  of  VPATH are slightly brain-dead, so
    many other _m_a_k_e implementations are too  limited.   You  may
    want to consider installing GNU Make.

    77..  TThhee BBiigg PPiiccttuurree

    This  section  brings  together all of the preceding discus-
    sion, and presents the example  project  with  its  separate
    modules,  but  with a whole-project Makefile.  The directory
    structure is changed little from the recursive case,  except
    that  the  deeper  Makefiles are replaced by module specific
    include files:
                          +++
                          ++_P+_r|_o_j_e_c_t
                           ++++Maanktefile
                           |++ +|module.mk
                           | - +|main.c
                           ++++b+ee
                           | + +|module.mk
                           | + +|parse.y
                           + +|depend.sh


    The Makefile looks like this:

                  +-------------------------------+
                  |MODULES := ant bee             |
                  |# look for include files in    |
                  |#   each of the modules        |
                  |CFLAGS += $(patsubst %,-I%,\   |
                  |  $(MODULES))                  |
                  |# extra libraries if required  |
                  |LIBS :=                        |
                  +-------------------------------+



    Peter Miller           23 October 2008               Page 21





    AUUGN'97                   Recursive Make Considered Harmful


                  +-------------------------------+
                  |# each module will add to this |
                  |SRC :=                         |
                  |# include the description for  |
                  |#   each module                |
                  |include $(patsubst %,\         |
                  |    %/module.mk,$(MODULES))    |
                  |# determine the object files   |
                  |OBJ :=                    \    |
                  |  $(patsubst %.c,%.o,     \    |
                  |    $(filter %.c,$(SRC))) \    |
                  |  $(patsubst %.y,%.o,     \    |
                  |    $(filter %.y,$(SRC)))      |
                  |# link the program             |
                  |prog: $(OBJ)                   |
                  |  $(CC) -o $@ $(OBJ) $(LIBS)   |
                  |# include the C include        |
                  |#   dependencies               |
                  |include $(OBJ:.o=.d)           |
                  |# calculate C include          |
                  |#   dependencies               |
                  |%.d: %.c                       |
                  |  depend.sh `dirname $*.c` \   |
                  |    $(CFLAGS) $*.c > $@        |
                  +-------------------------------+
    This looks absurdly large, but it has all of the common ele-
    ments  in  the  one place, so that each of the modules' _m_a_k_e
    includes may be small.

    The ant/module.mk file looks like:

                    +--------------------------+
                    |SRC += ant/main.c         |
                    +--------------------------+
    The bee/module.mk file looks like:

                    +--------------------------+
                    |SRC += bee/parse.y        |
                    |LIBS += -ly               |
                    |%.c %.h: %.y              |
                    |  $(YACC) -d $*.y         |
                    |  mv y.tab.c $*.c         |
                    |  mv y.tab.h $*.h         |
                    +--------------------------+

    Notice that the built-in rules are used for the C files, but
    we  need  special  yacc  processing  to get the generated .h
    file.

    The savings in this example  look  irrelevant,  because  the
    top-level  Makefile is so large.  But consider if there were
    100 modules, each with only a  few  non-comment  lines,  and
    those specifically relevant to the module.  The savings soon
    add up to a total size often _l_e_s_s _t_h_a_n the  recursive  case,



    Peter Miller           23 October 2008               Page 22





    AUUGN'97                   Recursive Make Considered Harmful


    without loss of modularity.

    The equivalent DAG of the Makefile after all of the includes
    looks like this:
    
                                prog



                          main.o   parse.o
                            main.d|  parse.d|

                      main.c   parse.h  parse.c



                                   parse.y



    The vertexes and edges for the include file dependency files
    are also present as these are important for _m_a_k_e to function
    correctly.

    77..11..  SSiiddee EEffffeeccttss

    There are a couple of desirable side-effects of using a sin-
    gle Makefile.

    +o  The  GNU  Make -j option, for parallel builds, works even
    better than before.  It can find even more unrelated  things
    to do at once, and no longer has some subtle problems.

    +o The general make -k option, to continue as far as possible
    even in the face of errors, works even better  than  before.
    It can find even more things to continue with.

    88..  LLiitteerraattuurree SSuurrvveeyy

    How  can  it be possible that we have been misusing _m_a_k_e for
    20 years?  How can it be possible that  behavior  previously
    ascribed to _m_a_k_e's limitations is in fact a result of misus-
    ing it?

    The author only started thinking about the  ideas  presented
    in  this  paper when faced with a number of ugly build prob-
    lems on utterly different projects, but  with  common  symp-
    toms.   By  stepping  back from the individual projects, and
    closely examining the thing they had  in  common,  _m_a_k_e,  it
    became  possible  to see the larger pattern.  Most of us are
    too caught up in the minutiae of  just  getting  the  rotten
    build  to  work that we don't have time to spare for the big
    picture.  Especially when the item in  question  "obviously"
    works, and has done so continuously for the last 20 years.



    Peter Miller           23 October 2008               Page 23





    AUUGN'97                   Recursive Make Considered Harmful


    It  is  interesting  that the problems of recursive _m_a_k_e are
    rarely mentioned in the very books Unix programmers rely  on
    for accurate, practical advice.

    88..11..  TThhee OOrriiggiinnaall PPaappeerr

    The  original  _m_a_k_e  paper [feld78] contains no reference to
    recursive _m_a_k_e_, let alone any discussion as to the  relative
    merits of whole project _m_a_k_e over recursive _m_a_k_e_.

    It is hardly surprising that the original paper did not dis-
    cuss recursive _m_a_k_e, Unix projects at the time  usually  _d_i_d
    fit into a single directory.

    It  may  be this which set the "one Makefile in every direc-
    tory" concept so firmly in the collective  Unix  development
    mind-set.

    88..22..  GGNNUU MMaakkee

    The GNU Make manual [stal93] contains several pages of mate-
    rial concerning recursive _m_a_k_e_, however  its  discussion  of
    the  merits or otherwise of the technique are limited to the
    brief statement that

         "This technique is useful when you want  to  sepa-
         rate makefiles for various subsystems that compose
         a larger system."

    No mention is made of the problems you may encounter.

    88..33..  MMaannaaggiinngg PPrroojjeeccttss wwiitthh MMaakkee

    The Nutshell Make book [talb91] specifically promotes recur-
    sive _m_a_k_e over whole project _m_a_k_e because

         "The  cleanest  way  to build is to put a separate
         description file in each directory, and  tie  them
         together  through  a  master description file that
         invokes _m_a_k_e recursively.  While  cumbersome,  the
         technique  is  easier  to  maintain than a single,
         enormous file that covers  multiple  directories."
         (p. 65)

    This  is  despite the book's advice only two paragraphs ear-
    lier that

         "_m_a_k_e is happiest when you keep all your files  in
         a single directory." (p. 64)

    Yet the book fails to discuss the contradiction in these two
    statements, and goes on to describe one of  the  traditional
    ways  of  treating the symptoms of incomplete DAGs caused by
    recursive _m_a_k_e.



    Peter Miller           23 October 2008               Page 24





    AUUGN'97                   Recursive Make Considered Harmful


    The book may give us a clue as to  why  recursive  _m_a_k_e  has
    been  used  in  this  way for so many years.  Notice how the
    above quotes confuse the concept of  a  directory  with  the
    concept of a Makefile.

    This  paper suggests a simple change to the mind-set: direc-
    tory trees, however deep, are places to store  files;  Make-
    files are places to describe the relationships between those
    files, however many.

    88..44..  BBSSDD MMaakkee

    The tutorial for BSD Make [debo88] says nothing at all about
    recursive  _m_a_k_e,  but  it  is  one of the few which actually
    described, however briefly, the relationship between a Make-
    file and a DAG (p. 30).  There is also a wonderful quote

         "If  _m_a_k_e doesn't do what you expect it to, it's a
         good chance the makefile is wrong." (p. 10)

    Which is a pithy summary of the thesis of this paper.

    99..  SSuummmmaarryy

    This paper presents a number of related problems, and demon-
    strates  that  they are not inherent limitations of _m_a_k_e, as
    is commonly believed,  but  are  the  result  of  presenting
    incorrect  information to _m_a_k_e.  This is the ancient _G_a_r_b_a_g_e
    _I_n_, _G_a_r_b_a_g_e _O_u_t principle at work.  Because  _m_a_k_e  can  only
    operate  correctly with a complete DAG, the error is in seg-
    menting the Makefile into incomplete pieces.

    This requires a shift in thinking: directory _t_r_e_e_s are  sim-
    ply a place to hold files, Makefiles are a place to remember
    relationships between files.  Do not confuse the two because
    it is as important to accurately represent the relationships
    between files in different directories as it is to represent
    the relationships between files in the same directory.  This
    has the implication that there should be exactly  one  Make-
    file for a project, but the magnitude of the description can
    be managed by using a _m_a_k_e include file in each directory to
    describe  the subset of the project files in that directory.
    This is just as modular as having a Makefile in each  direc-
    tory.

    This  paper  has shown how a project build and a development
    build can be equally brief for a whole-project _m_a_k_e.   Given
    this  parity  of time, the gains provided by accurate depen-
    dencies mean that this process will, in fact, be faster than
    the recursive _m_a_k_e case, and more accurate.







    Peter Miller           23 October 2008               Page 25





    AUUGN'97                   Recursive Make Considered Harmful


    99..11..  IInntteerr--ddeeppeennddeenntt PPrroojjeeccttss

    In organizations with a strong culture of re-use, implement-
    ing whole-project _m_a_k_e can present  challenges.   Rising  to
    these challenges, however, may require looking at the bigger
    picture.

    +o A module may be shared between two  programs  because  the
      programs  are  closely related.  Clearly, the two programs
      plus the shared module belong to  the  same  project  (the
      module  may  be self-contained, but the programs are not).
      The dependencies must be explicitly stated, and changes to
      the  module  must result in both programs being recompiled
      and re-linked as appropriate.  Combining them all  into  a
      single  project  means  that whole-project _m_a_k_e can accom-
      plish this.

    +o A module may be shared between two projects  because  they
      must  inter-operate.  Possibly your project is bigger than
      your current directory structure implies.   The  dependen-
      cies  must be explicitly stated, and changes to the module
      must result in both  projects  being  recompiled  and  re-
      linked  as  appropriate.  Combining them all into a single
      project means that whole-project _m_a_k_e can accomplish this.

    +o It  is  the  normal  case  to  omit the edges between your
      project and the operating system or other installed  third
      party tools.  So normal that they are ignored in the Make-
      files in this paper, and they are ignored in the  built-in
      rules of _m_a_k_e programs.
      Modules shared between your projects may fall into a simi-
      lar category: if they change, you  will  deliberately  re-
      build  to  include their changes, or quietly include their
      changes whenever the next build  may  happen.   In  either
      case,  you  do  not explicitly state the dependencies, and
      whole-project _m_a_k_e does not apply.

    +o Re-use may be better served if the module were used  as  a
      template,  and  divergence between two projects is seen as
      normal.  Duplicating the module in each project allows the
      dependencies  to  be explicitly stated, but requires addi-
      tional effort if maintenance is  required  to  the  common
      portion.

    How to structure dependencies in a strong re-use environment
    thus becomes an exercise in _r_i_s_k _m_a_n_a_g_e_m_e_n_t.   What  is  the
    danger  that  omitting  chunks  of  the  DAG  will harm your
    projects?  How vital is it to rebuild if a  module  changes?
    What  are  the consequences of _n_o_t rebuilding automatically?
    How can you tell when a rebuild is necessary if  the  depen-
    dencies  are  not  explicitly  stated?   What are the conse-
    quences of forgetting to rebuild?





    Peter Miller           23 October 2008               Page 26





    AUUGN'97                   Recursive Make Considered Harmful


    99..22..  RReettuurrnn OOnn IInnvveessttmmeenntt

    Some of the techniques presented in this paper will  improve
    the speed of your builds, even if you continue to use recur-
    sive _m_a_k_e.  These are not the focus of this paper, merely  a
    useful detour.

    The  focus  of this paper is that you will get more accurate
    builds of your project if you use whole-project _m_a_k_e  rather
    than recursive _m_a_k_e.

    +o The  time  for  _m_a_k_e  to work out that nothing needs to be
      done will not be more, and will often be less.

    +o The size and complexity of the total Makefile  input  will
      not be more, and will often be less.

    +o The  total  Makefile  input is no less modular than in the
      resursive case.

    +o The difficulty of maintaining  the  total  Makefile  input
      will not be more, and will often be less.

    The disadvantages of using whole-project _m_a_k_e over recursive
    _m_a_k_e are often un-measured.  How much time is spent figuring
    out  why  _m_a_k_e  did  something unexpected?  How much time is
    spent figuring out that _m_a_k_e ddiidd something unexpected?   How
    much  time is spent tinkering with the build process?  These
    activities are often  thought  of  as  "normal"  development
    overheads.

    Building  your  project is a fundamental activity.  If it is
    performing poorly, so are development, debugging  and  test-
    ing.  Building your project needs to be so simple the newest
    recruit can do it immediately with only  a  single  page  of
    instructions.   Building  your project needs to be so simple
    that it rarely needs any development effort at all.  Is your
    build process this simple?



















    Peter Miller           23 October 2008               Page 27





    AUUGN'97                   Recursive Make Considered Harmful


    1100..  RReeffeerreenncceess


         ddeebboo8888:: Adam de Boor (1988).  _P_M_a_k_e _- _A _T_u_t_o_r_i_a_l.  Uni-
    versity of California, Berkeley

         ffeelldd7788:: Stuart I. Feldman (1978).  _M_a_k_e _- _A _P_r_o_g_r_a_m _f_o_r
    _M_a_i_n_t_a_i_n_i_n_g  _C_o_m_p_u_t_e_r _P_r_o_g_r_a_m_s.  Bell Laboratories Computing
    Science Technical Report 57

         ssttaall9933:: Richard M. Stallman and Roland McGrath  (1993).
    _G_N_U _M_a_k_e_: _A _P_r_o_g_r_a_m _f_o_r _D_i_r_e_c_t_i_n_g _R_e_c_o_m_p_i_l_a_t_i_o_n.  Free Soft-
    ware Foundation, Inc.

         ttaallbb9911:: Steve Talbott (1991).  _M_a_n_a_g_i_n_g  _P_r_o_j_e_c_t_s  _w_i_t_h
    _M_a_k_e_, _2_n_d _E_d.  O'Reilly & Associates, Inc.

    1111..  AAbboouutt tthhee AAuutthhoorr

    Peter  Miller  has worked for many years in the software R&D
    industry, principally on UNIX systems. In that time  he  has
    written  tools  such as Aegis (a software configuration man-
    agement system) and Cook (yet  another  _m_a_k_e-oid),  both  of
    which  are freely available on the Internet.  Supporting the
    use of these tools  at  many  Internet  sites  provided  the
    insights which led to this paper.

    Please  visit  http://www.canb.auug.org.au/~millerp/  if you
    would like to look at some of the author's free software.




























    Peter Miller           23 October 2008               Page 28


