So I decided to finally (after all of this compatibility work) take TAP::Harness out for a spin and make TAP::Harness::Parallel. That comes with some pain about the output formatting API (and I'll push it to CPAN as soon as we stabilize that -- right now you have to ride along and get TAP::Harness from its svn too (and possibly r491 because we're still working-through the single-process assumptions in the formatter.)) But, the preliminary results are between 40-60% reduced waiting. If your test suite takes more than 10s to run, it is probably worth it.
runtests -r -j 9
Note: I symlink bin/prove to runtests -- the Test::Harness transition isn't quite complete.
Expect about 40% time reduction in typical tests suites. The perl 5.8.8 core tests dropped to 200s from 500s. The parrot tests seem to be playing along as well. (Both of these require the directory-based partitioning.)
The biggest problem is resource conflicts. Have you ever run your tests simultaneously before? Probably not -- it is likely that they reuse tempfile names, server ports, etc. Time to start tacking $$ onto your tempfiles or using File::Temp. Of course, the directory-based partitioning (run each directory as a process) tends to help drop-in compatibility, but can block performance if things are unbalanced.
Next steps probably involve more switches and various forms of partitioning.