The InnoDB deadlock detector was rewritten in MySQL 5.7.1, in a merge commit that does not mention any WL or bug number, nor any reviewer. I did not review those changes, and I cannot say whether the algorithmic complexity of the deadlock checker was reduced. Possibly the rewrite replaced procedural recursion with iteration over a data structure that explicitly represents a stack.
