Patrick Steinhardt forwarded an IRC report that 'git log --stat --follow -- include/linux/rsc_table.h' on linux.git takes almost 8 minutes with Git 2.56, compared with roughly 33 seconds on 2.55. He bisected it to 304812ed33 (log: improve --follow following renames for non-linear history) and copied its author.
Junio C Hamano explained how the older behavior avoided the cost. The original follow-renames code only ran the expensive try_to_follow_renames() when the followed path was missing in the parent, as checked by diff_might_be_rename(). Reading today's log_tree_commit(), he noted that propagate_follow_pathspec_to_parent() is also called, which his message indicates is where the extra work comes from.
Miklos Vajna then posted a fix. His measurements on the same command are about 28 seconds before the commit and 6m43s after. He says propagate_follow_pathspec_to_parent() does a fairly expensive rename detection of the current commit against all of its parents.
The patch adds two shortcuts. It only does that work when the path is added relative to a parent. If the path is the same as in one of the parents, it follows that history directly. According to the commit message, these shortcuts keep the existing use cases working. Review of the patch has not yet appeared in the excerpts.