buildroot

graph-depends: optimize remove_transitive_deps()

For large configurations, the execution time of
remove_transitive_deps() becomes really high, due to the number of
nested loops + the is_dep() function being recursive.

For an allyespackageconfig, the remove_extra_deps() function takes 334
seconds to execute, and the overall time to generate the .dot file is
6 minutes and 39 seconds. Here is a timing of the different
graph-depends steps and the overall execution time:

  Getting dependencies:   42.5735 seconds
  Turn deps into a dict:   0.0023 seconds
  Remove extra deps:     334.1542 seconds
  Get version:            22.4919 seconds
  Generate .dot:           0.0197 seconds

  real	6m39.289s
  user	6m16.644s
  sys	0m8.792s

By adding a very simple cache for the results of is_dep(), we bring
down the execution time of the "Remove extra deps" step from 334
seconds to just 4 seconds, reducing the overall execution time to 1
minutes and 10 seconds:

  Getting dependencies:  42.9546 seconds
  Turn deps into a dict:  0.0025 seconds
  Remove extra deps:      4.9643 seconds
  Get version:           22.1865 seconds
  Generate .dot:          0.0207 seconds

  real	1m10.201s
  user	0m47.716s
  sys	0m7.948s

Signed-off-by: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
Tested-by: Gustavo Zacarias <gustavo.zacarias@free-electrons.com>
[yann.morin.1998@free.fr:
  - rename is_dep() to is_dep_uncached(), keep existig code as-is
  - add is_dep() as a cached-version of is_dep_uncached()
  - use constructs more conform with 2to3
  - use exceptions (EAFP) rather than check-before-use (LBYL) to be more
    pythonist; that even decreases the duration yet a little bit more!
]
Signed-off-by: Yann E. MORIN <yann.morin.1998@free.fr>