






                 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           13 October 2004                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+o+dule2
                             +-++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.


    -----------
    Copyright   (C)  1997  Peter  Miller;  All  rights
    reserved.



    Peter Miller           13 October 2004                Page 2





    AUUGN'97                   Recursive Make Considered Harmful


    This  paper assumes that you have installed GNU Make on your
    system and are moderately familiar with its features.   Some
    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



    Peter Miller           13 October 2004                Page 3





    AUUGN'97                   Recursive Make Considered Harmful


    used.

    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.




    Peter Miller           13 October 2004                Page 4





    AUUGN'97                   Recursive Make Considered Harmful


    The above Makefile can be drawn as a DAG  in  the  following
    form:
    
                                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
    flattens it all out again, right at the end.




    Peter Miller           13 October 2004                Page 5





    AUUGN'97                   Recursive Make Considered Harmful


    The directory structure is as follows:
                          +++
                          ++-_P+_r+_o_j_e_c_t
                           ++++Maanktefile
                           |++-++Makefile
                           | +-++main.c
                           ++++b+e+e
                             +-++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           13 October 2004                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           13 October 2004                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           13 October 2004                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,
    making  it  useless,  because  all  of the sub-makes are all
    doing their builds ("clean" then "all")  in  parallel,  con-
    stantly  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



    Peter Miller           13 October 2004                Page 9





    AUUGN'97                   Recursive Make Considered Harmful


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



    Peter Miller           13 October 2004               Page 10





    AUUGN'97                   Recursive Make Considered Harmful


    thing, or complain to your vendor.

    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  Make-
    file, simply by using a specific target, and an alias if the
    command 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.



    Peter Miller           13 October 2004               Page 11





    AUUGN'97                   Recursive Make Considered Harmful


    Secondly, that these inevitable delays are unacceptable when
    a developer wants to quickly compile and link the  one  file
    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
    seconds, 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?





    Peter Miller           13 October 2004               Page 12





    AUUGN'97                   Recursive Make Considered Harmful


    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.

    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



    Peter Miller           13 October 2004               Page 13





    AUUGN'97                   Recursive Make Considered Harmful


      trigger to remind the developer to do this, other than the
      ire of fellow developers.

    +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
      different  places, even when you are in the ant directory.
      This is of concern when include dependencies are automati-
      cally 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 tra-
    ditional  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



    Peter Miller           13 October 2004               Page 14





    AUUGN'97                   Recursive Make Considered Harmful


    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:

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



    Peter Miller           13 October 2004               Page 15





    AUUGN'97                   Recursive Make Considered Harmful


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






    Peter Miller           13 October 2004               Page 16





    AUUGN'97                   Recursive Make Considered Harmful


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



    Peter Miller           13 October 2004               Page 17





    AUUGN'97                   Recursive Make Considered Harmful


    recalculated, and potentially the C file will not be  recom-
    piled,  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.

    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'' suf-
    fix.  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) $* > $@ |
                  +------------------------------+

    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.




    Peter Miller           13 October 2004               Page 18





    AUUGN'97                   Recursive Make Considered Harmful


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

                +-----------------------------------+
                |#!/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) $* > $@ |
            +-------------------------------------------+
    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           13 October 2004               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           13 October 2004               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+e+e
                           | +-++module.mk
                           | +-++parse.y
                           +-++de|pend.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           13 October 2004               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,
    without loss of modularity.



    Peter Miller           13 October 2004               Page 22





    AUUGN'97                   Recursive Make Considered Harmful


    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           13 October 2004               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           13 October 2004               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           13 October 2004               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           13 October 2004               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           13 October 2004               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           13 October 2004               Page 28


