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

[Jean-Philippe Gravel]

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!