I ran a test just now:

For 1000 tags in the repository (999 of them nonversions):
6.85 real         0.70 user         2.47 sys
For 2000 tags... it didn't complete. I'll look into it deeper tomorrow.