bug#10580: 24.0.92; gdb initialization takes more than one minute at 100

[Jean-Philippe Gravel <jpgravel@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2441 bytes --]

Hi guys,



I actually have a fix for this problem.



I use Emacs to debug a software of colossal size.  With Emacs 23, it used
to be possible to start gdb within a minute.  With Emacs 24, it takes more
than a couple of hour.  I never actually had the patience to wait for it to
finish.



As stated in previous posts, the command -file-list-exec-source-files is
the one triggering the bottleneck.  In my case, the reply is 5Mb long.



It turns out that the problem IS the parsing of the data stream coming from
GDB.  The function gud-gdbmi-marker-filter is home to a colossal
bottleneck.  You’ll find in there not only one, but 4 major algorithmic
problems.



The first thing that strikes the eye is the way it handles the fact that
there are several types of GDB replies possible.  Instead of parsing the
data stream linearly, accepting the GDB messages in the order of arrival,
it looks over the whole stream for the first type of message, then the
second, then the next.  Complexity: O(nm), where n is the size of the steam
and m is the number of message types.  Then, when finding a message
matching the type we look for, it is removed from the stream by cloning the
whole string, but padding the original location with spaces.  Complexity:
O(ni), where i is the number of messages.



To go on with the analysis, consider the following: my tests indicate that
gdbmi-marker-filter receives data by chunk of about 225 bytes.  Since I
receive 5Mb of data, gdbmi ingests about 22000 packets.  For every chunk of
data received, the incoming data is concatenated to a new string: O(nj),
where j is the number of packets.  Each time, the whole parsing described
above is restarted: O(nmj) (!!!).  Feed in a 5Mb data stream and you’ll get
a hung emacs!



I fixed the above by writing a proper parser reading the data stream in
O(n).  With my test-case, the parse time goes down from ‘too long to even
tell’, to about 3 seconds.  Not only does it fix the startup problem, but
it makes pretty much all other gud commands impressively faster.  With
emacs 23, it used to take almost a full second to do a single “gud-next” in
my software.  When enabling gud-tooltip-mode, it was becoming totally
unusable.  By removing the bottleneck in gud-gdbmi-marker-filter, the above
become instantaneous.



I just need to finalize a few things and I can send you a patch file.



Cheers!

[-- Attachment #2: Type: text/html, Size: 4847 bytes --]