From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 6449 invoked by alias); 2 Sep 2009 04:52:50 -0000 Received: (qmail 6439 invoked by uid 22791); 2 Sep 2009 04:52:48 -0000 X-SWARE-Spam-Status: No, hits=-2.4 required=5.0 tests=AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from rock.gnat.com (HELO rock.gnat.com) (205.232.38.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 02 Sep 2009 04:52:43 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id ACCA92BABA3; Wed, 2 Sep 2009 00:52:41 -0400 (EDT) Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id lywyiOL5qVv6; Wed, 2 Sep 2009 00:52:41 -0400 (EDT) Received: from joel.gnat.com (localhost.localdomain [127.0.0.1]) by rock.gnat.com (Postfix) with ESMTP id 1EB482BAB48; Wed, 2 Sep 2009 00:52:41 -0400 (EDT) Received: by joel.gnat.com (Postfix, from userid 1000) id 47580F5893; Tue, 1 Sep 2009 21:52:32 -0700 (PDT) Date: Wed, 02 Sep 2009 04:52:00 -0000 From: Joel Brobecker To: Paul Pluzhnikov Cc: gdb@sourceware.org Subject: Re: More info on PR/9711 (quadratic slowdown for deep stack traces) Message-ID: <20090902045232.GM4379@adacore.com> References: <20090901204815.GK4379@adacore.com> <8ac60eac0909012041i1a9d4f8fmbd13d19ec8039ef0@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <8ac60eac0909012041i1a9d4f8fmbd13d19ec8039ef0@mail.gmail.com> User-Agent: Mutt/1.5.18 (2008-05-17) Mailing-List: contact gdb-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-owner@sourceware.org X-SW-Source: 2009-09/txt/msg00012.txt.bz2 > AFAIR, the real problem showed up while debugging GDB itself, when I > made it go into infinite recursion loop. Making programs spin into the > ground via infinite recursion is not that uncommon (IMHO) and when > that happens, you do get 100_000 or more frames, and usually you only > care about the outermost 10 of so. It is quite annoying if GDB takes > several minutes to tell you what these 10 interesting frames are. I should probably say that I am not contesting the fact that the problem can happen in real life. I did assume that, given the requirements for it to happen, the problem was not that common, and perhaps I was mistaken. It's always hard to say how common an issue is. That being said, here are the current parameters: - I will submit a patch tomorrow that implements the first idea that I floated. Namely, if the previous frame has already been computed, then have get_prev_frame return that. This cuts down most of the time spent during the register value computation (roughly 60% with 10_000 frames). - I don't see how, right now, we could get rid of the quadratic behavior. It's embedded in the current design: We now get register values, and values cannot store the frame directly, it has to be the frame ID. This means a frame lookup from ID, which is the second loop causing the n^2 behavior. I am hoping that Daniel, who has more experience than I do in the area of unwinding, might be able to suggest something that would help us get rid of the double loop. But, assuming that my patch is approved, do you think that we should delay the release in order to get this changed into an O(n) behavior? -- Joel