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:
I've posted it for review here:
This is in the master branch:
This is in the portage-2.2.15 release.