From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12913 invoked by alias); 7 Sep 2009 07:30:07 -0000 Received: (qmail 12901 invoked by uid 22791); 7 Sep 2009 07:30:04 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL,BAYES_00,SARE_MSGID_LONG40,SPF_PASS X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.33.17) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 07 Sep 2009 07:29:59 +0000 Received: from wpaz29.hot.corp.google.com (wpaz29.hot.corp.google.com [172.24.198.93]) by smtp-out.google.com with ESMTP id n877TtOf005065 for ; Mon, 7 Sep 2009 08:29:56 +0100 Received: from yxe35 (yxe35.prod.google.com [10.190.2.35]) by wpaz29.hot.corp.google.com with ESMTP id n877TrxO008052 for ; Mon, 7 Sep 2009 00:29:53 -0700 Received: by yxe35 with SMTP id 35so6673325yxe.2 for ; Mon, 07 Sep 2009 00:29:53 -0700 (PDT) MIME-Version: 1.0 Received: by 10.150.238.1 with SMTP id l1mr23363077ybh.68.1252308593240; Mon, 07 Sep 2009 00:29:53 -0700 (PDT) In-Reply-To: <20090903183658.GJ4343@adacore.com> References: <20090903183658.GJ4343@adacore.com> Date: Mon, 07 Sep 2009 07:30:00 -0000 Message-ID: Subject: Re: [RFA/PATCH] PR/9711: quadratic slowdown for deep stack traces From: Doug Evans To: Joel Brobecker Cc: gdb-patches@sourceware.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-System-Of-Record: true X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2009-09/txt/msg00154.txt.bz2 On Thu, Sep 3, 2009 at 11:36 AM, Joel Brobecker wrot= e: > 2009-09-03 =A0Joel Brobecker =A0 > > =A0 =A0 =A0 =A0Avoid quadratic behavior when computing the value of a reg= ister. > =A0 =A0 =A0 =A0* frame.c (frame_cache): New static constant. > =A0 =A0 =A0 =A0(frame_cache_add, frame_cache_find, frame_cache_invalidate= ): > =A0 =A0 =A0 =A0New functions. > =A0 =A0 =A0 =A0(get_frame_id): Minor reformatting. Add the frame to the f= rame cache. > =A0 =A0 =A0 =A0(frame_find_by_id): Search the frame cache first before wa= lking all > =A0 =A0 =A0 =A0frames starting from te current_frame. > =A0 =A0 =A0 =A0(reinit_frame_cache): Add call to frame_cache_invalidate (= ); Hi. Nit: It seems like there's a redundant call to frame_id_eq in frame_find_by= _id. +/* Search the frame cache for an entry with the given frame ID. + If found, return that frame. Otherwise return NULL. */ +static struct frame_info * +frame_cache_find (struct frame_id id) +{ + if (frame_cache && frame_id_eq (frame_cache->this_id.value, id)) + return frame_cache; + + return NULL; +} @@ -514,6 +547,11 @@ frame_find_by_id (struct frame_id id) if (!frame_id_p (id)) return NULL; + /* Try using the frame cache first. */ + frame =3D frame_cache_find (id); + if (frame && frame_id_eq (frame->this_id.value, id)) + return frame; + for (frame =3D get_current_frame (); ; frame =3D prev_frame) { struct frame_id this =3D get_frame_id (frame);