Probably worth checking whether the branch is tracking a remote branch and whether the commit hashes match there, and then maybe checking if any commits are reachable on that tracking branch, as an optimization, before going on enumerating all the remotes branches and all the local commits. Very likely the branch has been pushed at least once so that might hit a large chunk of use cases.
Fixes #343