[Bug gcov-profile/67992] New: GCOV takes an absurdly long time to process a file

[Bug gcov-profile/67992] New: GCOV takes an absurdly long time to process a file

[Pidgeot18 at gmail dot com]

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

[Bug gcov-profile/67992] GCOV takes an absurdly long time to process a file

[Pidgeot18 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67992

--- Comment #1 from Joshua Cranmer <Pidgeot18 at gmail dot com> ---
Created attachment 36531
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36531&action=edit
Implementation of Hawick's algorithm in C++

This is test code I wrote to figure out why I couldn't reproduce the output of
gcov correctly (which eventually led me to discovering bug 67937). It's an
ersatz variant of gcov (whose code is not included), except the latter half of
processing was replaced with my own code. So there's a mixture of use of both
gcov's arc_t, block_t, etc. structures with my own C++ classes Arc/Block/etc. I
also ripped out the code that supported options I didn't need to use (I
effectively only do gcov -a -b -p).

The main code in question is getCycleCounts (on line 494) and the cycle
detection code that comprises the prior 100 lines of code. The
has_negate/rerunning findCycles trick is needed because of bug 67937. This
roughly replaces the main Tiernan's algorithm loop of accumulate_line_counts
(about line 2200 of gcov.c) (the rest of the function is more fully captured by
LineInfo::computeCounts/CoverageMap::computeLineCounts).

I'd do a patch myself, but, honestly, the C code of gcov is painful for me to
follow, and I've never set myself up to do gcc development.

[Bug gcov-profile/67992] GCOV takes an absurdly long time to process a file

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67992

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think there is a duplicate about gcov slowness for some sort of CFGs.