From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Jean-Philippe Gravel Newsgroups: gmane.emacs.bugs Subject: bug#10580: 24.0.92; gdb initialization takes more than one minute at 100 Date: Thu, 13 Dec 2012 23:14:59 -0500 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=f46d042f92525d3be404d0c84621 X-Trace: ger.gmane.org 1355458947 10161 80.91.229.3 (14 Dec 2012 04:22:27 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 14 Dec 2012 04:22:27 +0000 (UTC) To: 10580@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Fri Dec 14 05:22:41 2012 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TjMnA-0001KJ-Sz for geb-bug-gnu-emacs@m.gmane.org; Fri, 14 Dec 2012 05:22:33 +0100 Original-Received: from localhost ([::1]:51962 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TjMmx-0005XI-Ux for geb-bug-gnu-emacs@m.gmane.org; Thu, 13 Dec 2012 23:22:19 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:49469) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TjMmr-0005MF-Fq for bug-gnu-emacs@gnu.org; Thu, 13 Dec 2012 23:22:16 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TjMmm-0002ue-23 for bug-gnu-emacs@gnu.org; Thu, 13 Dec 2012 23:22:13 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:59653) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TjMml-0002ua-VC for bug-gnu-emacs@gnu.org; Thu, 13 Dec 2012 23:22:07 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1TjMnf-0002bg-HL for bug-gnu-emacs@gnu.org; Thu, 13 Dec 2012 23:23:03 -0500 X-Loop: help-debbugs@gnu.org In-Reply-To: Resent-From: Jean-Philippe Gravel Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 14 Dec 2012 04:23:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 10580 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 10580-submit@debbugs.gnu.org id=B10580.13554589449904 (code B ref 10580); Fri, 14 Dec 2012 04:23:03 +0000 Original-Received: (at 10580) by debbugs.gnu.org; 14 Dec 2012 04:22:24 +0000 Original-Received: from localhost ([127.0.0.1]:41664 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TjMn0-0002Zb-HM for submit@debbugs.gnu.org; Thu, 13 Dec 2012 23:22:23 -0500 Original-Received: from mail-pa0-f44.google.com ([209.85.220.44]:60356) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TjMgm-0002LS-C2 for 10580@debbugs.gnu.org; Thu, 13 Dec 2012 23:16:13 -0500 Original-Received: by mail-pa0-f44.google.com with SMTP id hz11so2049665pad.3 for <10580@debbugs.gnu.org>; Thu, 13 Dec 2012 20:14:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=ckv1Y80yiaDVGiLyHF9aeZg8O0SbIFG/SFpHGJxXc2M=; b=S4eyts0/DcGgFXi75YGSdtnvy8SknbYaW3NFHvhUWp2NudzAkC/xRnntveFqLq272w zy1R3xQqLM0GpgSxBYJlR6GtXlyFLB1u4fQOgq3uN7H29MRD73jow6aD66NCYL/N/7TR 4gTS8Rq7k2gAEup5Pk1hBTI70tsm3fkihkwGK2eri+bvAZ40gl6fZQVkMqn9SHHU4Z1q 0v82uDpq+vakEppJQv7xihsFJ+ktJiyaVrCILS3JgS1sVwWA4Dxa6bgHEKK0mXwkL0ZX BNP8EVjqfCcUWdK2BbszqiPOYwlXXK9t72Df3cOCL2tw7iYxnsxapskO+J4l1KDCFmAR NEDQ== Original-Received: by 10.66.73.132 with SMTP id l4mr12452483pav.48.1355458499394; Thu, 13 Dec 2012 20:14:59 -0800 (PST) Original-Received: by 10.68.50.36 with HTTP; Thu, 13 Dec 2012 20:14:59 -0800 (PST) X-Mailman-Approved-At: Thu, 13 Dec 2012 23:22:18 -0500 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:68495 Archived-At: --f46d042f92525d3be404d0c84621 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable 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=92ll 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=92ll g= et 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 =91too long to even tell=92, 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 =93gud-next= =94 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! --f46d042f92525d3be404d0c84621 Content-Type: text/html; charset=windows-1252 Content-Transfer-Encoding: quoted-printable

Hi guys,

=A0

I actually have a fix for this pro= blem.

=A0

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

=A0

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

=A0

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

=A0

The first thing that strikes the e= ye is the way it handles the fact that there are several types of GDB replies possible. =A0Instead of parsing the = data stream linearly, accepting the GDB messages in the order of arrival, it looks over the whole stream fo= r the first type of message, then the second, then the next.=A0 Complexity: O= (nm), where n is the size of the steam and m is the number of message types.=A0 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 origin= al location with spaces.=A0 Complexity: O(ni), where i is the number of messages.

=A0

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

=A0

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

=A0

I just need to finalize a few thin= gs and I can send you a patch file.

=A0

Cheers!

--f46d042f92525d3be404d0c84621--