The depgraph._select_pkg_highest_available method has a memoization cache, but the whole cache is discarded each time that a package is added to the graph. I have written a patch which selectively invalidates the cache, and it significantly improves performance of dependency calculations. On one of my computers, 'emerge -puvDN @world' 15% less time, and results in 58% fewer _select_pkg_highest_available_imp calls.
The patch is in the following branch: https://github.com/zmedico/portage/tree/bug_530010 I've posted it for review here: http://gentoo.2317880.n4.nabble.com/PATCH-select-pkg-highest-available-selective-cache-invalidation-530010-td288338.html
This is in the master branch: https://github.com/gentoo/portage/commit/5f0541c8739bd0342a94aa108e5101588eaefc16
This is in the portage-2.2.15 release.
