Note that "git prune" could be sped up ENORMOUSLY if git-fsck-cache could be taught to (optionally) not open, uncompress, hash, and verify any blob objects. Just assume that they're okay.
I had a look at the code briefly, but it was a little bit hairier (a more invasive change) than I felt like dealing with.