For users mantaining systems with a lot of managed packages (such as desktop configurations), puppet runs can approach 30 minutes plus.
Most of this is due to yum being slow if run multiple times, and it is desirable to batch all yum invocations into single yum commands as much as possible.
It has been suggested that this also be done for rpmquery so as to not repeat it.
We should be able to walk the graph and move the yum/RPM opeartions together in a batchable way, and this would help tremendously with run time on RHEL/CentOS/Fedora.
(May offer similar savings WRT up2date, though IMHO yum on RHEL4 is a desirable practice if you are not a Satellite user.)