[cmake-developers] cost of usage requirements (was: Compiler features/extensions remaining/future issues)

[Brad King]

On 06/10/2014 01:17 PM, Ben Boeckel wrote:
> Brad is going to take a deeper look at it and might have more
> information in the next few days.

Here is a sscce::

  cmake_minimum_required(VERSION 2.8.9)
  project(ManyLibs C)
  set(LibPrev)
  foreach(n RANGE 100)
    add_library(Lib${n} SHARED lib.c)
    target_link_libraries(Lib${n} LINK_PUBLIC ${LibPrev})
    set(LibPrev Lib${n})
  endforeach()

On my machine:

  ========= ========= ========= ========
  version     real      user      sys
  ========= ========= ========= ========
  2.8.9     0m0.428s  0m0.384s  0m0.036s
  2.8.12.2  0m2.100s  0m2.016s  0m0.060s
  3.0.0     0m2.856s  0m2.796s  0m0.052s
  487b6ccd  0m5.232s  0m5.176s  0m0.044s
  see below 0m3.450s  0m3.356s  0m0.084s
  ========= ========= ========= ========

The usage requirement features have added a big performance
cost even when they are not used.  The transitive INTERFACE
$<TARGET_PROPERTY> lookups cause O(n^2) computation time for
link chains of length n due to the dependency on headTarget.
(For reference of others, the "headTarget" is the target
whose build rules are currently being computed, and its
dependencies may report different usage requirements based
on what is consuming them.)

I was able to lower the constant factor on the O(n^2) time
locally with a change to make GetTransitiveTargetClosure
callers:

 http://cmake.org/gitweb?p=cmake.git;a=blob;f=Source/cmTarget.cxx;hb=487b6ccd#l5215
 http://cmake.org/gitweb?p=cmake.git;a=blob;f=Source/cmTarget.cxx;hb=487b6ccd#l5431

receive the value returned by reference from an internal map
that memoizes the result.  See attached patch series.

However, please look at improving the implementation to have
something under O(n^2) complexity when the usage requirements
do not actually depend on the headTarget.

Thanks,
-Brad