• Matthias Männich's avatar
    Ninja: Improve performance with deeply-dependent custom targets · ed19e813
    Matthias Männich authored
    The commit v3.7.0-rc1~339^2 (Ninja: Fix inter-target order-only
    dependencies of custom command, 2016-07-20) might cause performance
    degradations for larger projects.  Especially when using custom
    commands as an input for each compilation rule (e.g. generated headers).
    
    For reference in the following I am referring to
      Source/cmGlobalNinjaGenerator.cxx:
        -> cmGlobalNinjaGenerator::AppendTargetDependsClosure
        -> cmGlobalNinjaGenerator::ComputeTargetDependsClosure
    
    It turned out that the mentioned commit is doing (indirectly) some
    redundant work that might impact performance when generating large
    projects.
    
    Imagine the dependency tree of custom targets:
    
        A
         \
          C - D - E
         /
        B
    
    For each target the transitive closure is calculated recursively, but as
    the TargetDependsClosures are only cached on the top most level, everything
    downstream has to be recalculated. I.e.
    
        A->C->D->E
        B->C->D->E
    
    This ultimately leads to a lot of redundant calls to AppendTargetOutputs.
    The recursive nature of the algorithm itself is not significant to the
    problem, but reducing the work to actually to be done work, eliminates the
    performance problem.
    
    This patch changes the way, intermediate results are cached. Rather than
    caching the closure of targets, we cache the closure of outputs. Such that
    in the example above at B->C the cache already would kick in.
    
    Caching the outputs has one disadvantage that the patch takes care of.
    In case of such a structure
    
        A       E
         \     / \
          C - D   G
         /     \ /
        B       F
    
    the calling order for A would be
    
        A->C->D->E->G  (at which time G is seen to the recursion)
    
    then the recursion returns until it reaches
    
        A->C->D->F     (at which the seen G would prevent to recurse down to G)
    
    But this would poison the cache for F with a wrong value (without G).
    Hence we use a local result set to ensure the cache is still consistently
    populated.
    
    For a large C++ project with around 25k targets this reduced the CMake
    configure / generate time from ~40s to ~29s.
    Signed-off-by: Matthias Männich's avatarMatthias Maennich <matthias@maennich.net>
    ed19e813
cmNinjaTypes.h 565 Bytes