There is a misbehavior in the depgraph._serialize_tasks method, where PDEPEND can cause the runtime cycle code to merge a very large runtime cycle and its dependencies, even though it would be more optimal to merge the dependencies first. In the main "while mygraph:" loop, the problem occurs when the prefer_asap flag is True, and there's a node in the asap_nodes list. The smallest_cycle variable ends up with a large runtime cycle along with some dependencies that are not involved in the cycle (which should therefore be merged earlier than the rest).
Some existing relevant code is visible in these commits, but apparently it doesn't always work as intended: https://gitweb.gentoo.org/proj/portage.git/commit/?id=603569311daee6e2460051f46728a05cbae66880 https://gitweb.gentoo.org/proj/portage.git/commit/?id=075ce106b3ae1e55cc810b4c946deea83bcb4a8e
I have a working patch in the following branch: https://github.com/zmedico/portage/tree/bug_590514 I'll submit it for review after I've added a test case.
Posted for review here: https://archives.gentoo.org/gentoo-portage-dev/message/23fb8cfa5e8c8ad207c5e42e65024742 https://github.com/gentoo/portage/pull/39
This is in the master branch: https://gitweb.gentoo.org/proj/portage.git/commit/?id=6412205462671735f6e8b3196a780bc4b0d6a077
Fixed in portage-2.3.3.