https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67992
Bug ID: 67992
Summary: GCOV takes an absurdly long time to process a file
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: gcov-profile
Assignee: unassigned at gcc dot gnu.org
Reporter: Pidgeot18 at gmail dot com
Target Milestone: ---
Created attachment 36529
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36529&action=edit
Simple file that exhibits the absurd slowdown.
The loop processing code in gcov takes an absurdly long time to compile
relatively small files. This comes most obviously into play if you have
macro-heavy unrolled code
(<https://dxr.mozilla.org/comm-central/source/mozilla/media/libjpeg/jchuff.c#562>
is the case in mind here--it's so slow my scripts delete the file rather than
wait to process that file).
How slow is it? With the attached file:
jcranmer@huitzilopochtli /tmp/gcov-bug $ gcc --coverage min.c
jcranmer@huitzilopochtli /tmp/gcov-bug $ ./a.out
jcranmer@huitzilopochtli /tmp/gcov-bug $ time gcov -a -b -p min.c.gcda
File 'min.c'
Lines executed:25.00% of 8
Branches executed:0.00% of 168
Taken at least once:0.00% of 168
No calls
Creating 'min.c.gcov'
real 11m20.474s
user 11m21.476s
sys 0m0.000s
Some of the literature I've seen claims that the algorithm in use's runtime
isn't O(N^3) (as gcov's comment claims) but actually O(k^N).
By comparison, using Hawick's algorithm (see
<http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf>), it took just:
jcranmer@huitzilopochtli /tmp/gcov-bug $ time
~/source/mozilla-tools/newcov/newcov min.c.gcda
real 0m0.113s
user 0m0.112s
sys 0m0.000s
