The java version spends 75% of it's time gc? That smells fishy to me.

edit: I just got to section VI of the paper, which does some gc tuning. In my playing, I also found about a 20% speedup by changing the HavlakLoopFinder.UnionFindMode class to being a statuc class.