Confirmed resolved in git-plugin 2.1.0. Sample job using https://github.com/MarkEWaite/JENKINS-5724-many-branches went from 3 minutes for an empty build to 1.5 seconds for the same build with git-plugin 2.1.0.

Code changed in jenkins
User: Niklas Hambüchen
Path:
src/main/java/hudson/plugins/git/util/GitUtils.java
http://jenkins-ci.org/commit/git-plugin/ba3271bb40d3933aa5e6dd117581937b03ab1030
Log:
filterTipBranches: Use O instead of O(n^2) algorithm.

Fixes JENKINS-5724.

Before, this made slaves run on 100% CPU for days when idle.

This makes it a few thousand times faster for a repo with 500 branches.

Ok, I rebased it (see the Github pull-request).

I also made a script to create a small test repo for reproducing this; find it at https://gist.github.com/nh2/9902001.

I don't think this is resolved; https://github.com/jenkinsci/git-plugin/blob/master/src/main/java/hudson/plugins/git/util/GitUtils.java#L141 still looks like the original algorithm.

Unfortunately I don't have time to perform a rebase on top of a new major release (as asked for in https://github.com/jenkinsci/git-plugin/pull/156#issuecomment-26217539) until earliest in 2 weeks.

After no feedback for 9 months, I'm closing this as resolved.

I fixed that in this pull request:

https://github.com/jenkinsci/git-plugin/pull/156

It is much faster now, please try it and tell me if it works.

This remains a big problem for anyone with a large number of branches. I eventually abandoned the git plugin entirely in favor of custom scripts to handle checkouts.

Use case for this issue was resolved by implementing Gerrit Build chooser, so there's no need for this at the moment. Problem still exists, though.