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.

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.

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.

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

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.

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.

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.

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.