bash_completion is too slow because it does strange things: it parses itself because it wants to emulate the behavior of "-o plusdirs".See https://bugzilla.redhat.com/show_bug.cgi?id=479936for a preliminary patch.
Thanks for pointing this out. This would indeed be a significant improvement!
Apparently, bash-completion is very active at the moment. They are currently trying to fix as many bugs as possible, and will then optimize bash-completion for Bash 3.x.
Nicolas