It seems to depend very non-linearly on the amount of memory. I don't have a better solution yet other than just making sure you give it enough memory. For me anything above -Xmx1024M works fine, 768M is slow, 512M crashed after more than 10 min of high CPU load. It is strange because last week I was able to run it with only -Xmx256M. These are the timings I get now:

-Xmx4096M:   55 s
-Xmx1024M:   58 s
-Xmx768M:     2 min 26 s
-Xmx512M:     > 10 min, out of memory