Unit tests take a long time to run. Valgrind problem? Gcov problem?

I've created a unit test suite for a project I'm working on. My unit tests used to run very quickly... 200+ of them would run within a few seconds. Typically each test would take less than 10 milliseconds. Now while using Valgrind and Gcov each test can take over 1.5 minutes to run! Has anyone had any experience with ver开发者_StackOverflowy slow unit tests? Does Valgrind, gcov, or Google Test cause significant slowdown of program execution in any particular situations? What's even more confusing is that some of the unit test run just fine (i.e. very quickly) while others take many seconds to run. And often, when running the unit tests again, the same tests take a different amount of time to run. I'm basically trying to figure out where the bottleneck is. Below is an example:

[ RUN      ] BandwidthAlgorithmTest.TerminalsOnly
[       OK ] BandwidthAlgorithmTest.TerminalsOnly (34 ms)
[ RUN      ] BandwidthAlgorithmTest.AlohaAndTerminals
[       OK ] BandwidthAlgorithmTest.AlohaAndTerminals (38 ms)
[ RUN      ] BandwidthAlgorithmTest.AllocatePeriodic
[       OK ] BandwidthAlgorithmTest.AllocatePeriodic (304 ms)
[ RUN      ] BandwidthAlgorithmTest.AllocatePeriodic_Disabled
[       OK ] BandwidthAlgorithmTest.AllocatePeriodic_Disabled (152 ms)
[ RUN      ] BandwidthAlgorithmTest.AllocateFair
[       OK ] BandwidthAlgorithmTest.AllocateFair (109 ms)
[ RUN      ] BandwidthAlgorithmTest.AllocateFair_Disabled
[       OK ] BandwidthAlgorithmTest.AllocateFair_Disabled (64 ms)
[----------] 12 tests from BandwidthAlgorithmTest (2763 ms total)

[----------] 7 tests from BacklogHelperTest
[ RUN      ] BacklogHelperTest.ChangeInrouteState
[       OK ] BacklogHelperTest.ChangeInrouteState (80613 ms)
[ RUN      ] BacklogHelperTest.GetInvalidInroute
[       OK ] BacklogHelperTest.GetInvalidInroute (98471 ms)

If you're disappointed by valgrind's performance, you can try the fledgling AddressSanitizer from Google. http://blog.chromium.org/2011/06/testing-chromium-addresssanitizer-fast.html It requires recompiling your code with a special compiler, but no source-level changes are needed.

One potential reason is mentioned here: https://groups.google.com/forum/#!topic/gnu.gcc.help/aS3mQGzGE_4 - it seems gcov has an O(n^2) step somewhere and is sensitive to long (post-CPP) source lines, or something along these lines.