From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 25933 invoked by alias); 3 Sep 2009 18:37:25 -0000 Received: (qmail 25925 invoked by uid 22791); 3 Sep 2009 18:37:24 -0000 X-SWARE-Spam-Status: No, hits=-2.5 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; Thu, 03 Sep 2009 18:37:18 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 187232BABFA for ; Thu, 3 Sep 2009 14:37:16 -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 tvygE6hcHEIp for ; Thu, 3 Sep 2009 14:37:15 -0400 (EDT) Received: from joel.gnat.com (localhost.localdomain [127.0.0.1]) by rock.gnat.com (Postfix) with ESMTP id 8A6362BAC0F for ; Thu, 3 Sep 2009 14:37:14 -0400 (EDT) Received: by joel.gnat.com (Postfix, from userid 1000) id D7F72F589A; Thu, 3 Sep 2009 11:36:58 -0700 (PDT) Date: Thu, 03 Sep 2009 18:37:00 -0000 From: Joel Brobecker To: gdb-patches@sourceware.org Subject: [RFA/PATCH] PR/9711: quadratic slowdown for deep stack traces Message-ID: <20090903183658.GJ4343@adacore.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="SLDf9lqlvOQaIe6s" Content-Disposition: inline User-Agent: Mutt/1.5.18 (2008-05-17) 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/msg00085.txt.bz2 --SLDf9lqlvOQaIe6s Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-length: 2128 Re: http://www.sourceware.org/ml/gdb/2009-09/msg00009.html This patch implements a suggestion from Daniel to cache the last frame whose ID was accessed. This is useful in the case where we do get_prev_register that returns a value that points to the next frame. This reduces the time from 30+ seconds to under 0.5 sec when dealing with 10,000 iterations in the example provided by the PR. We only cache one frame at a time, since this is sufficient to fix the quadratic behavior (I don't like introducing optimizations unless I can measure the improvement). My only complaint with this patch is that it introduces a slight confusion: The current code says we "cache" all the frames when it talks about the frame chain corresponding to the backtrace. My patch introduces a "frame cache". I'm OK with renaming my cache into something else, but couldn't find a better name. I'll also attach a couple of files that move the new frame cache to a different file (frame-cache.c). I think it's cleaner, but the issue is that we cannot access the frame ID from the frame since struct frame is opaque. As a result, one has to pass the frame ID in addition to the frame itself when adding it to the frame cache. The code is actually smaller if kept in frame.c, so in the end I chose the simpler approach, but I don't mind using frame-cache.c instead if others think it's better. Any suggestion of a new name for my frame_cache? Any objection to me checking in this patch? I'm planning on checking in this patch by the end of the week if no one objects. 2009-09-03 Joel Brobecker Avoid quadratic behavior when computing the value of a register. * frame.c (frame_cache): New static constant. (frame_cache_add, frame_cache_find, frame_cache_invalidate): New functions. (get_frame_id): Minor reformatting. Add the frame to the frame cache. (frame_find_by_id): Search the frame cache first before walking all frames starting from te current_frame. (reinit_frame_cache): Add call to frame_cache_invalidate (); Tested on x86_64-linux. -- Joel --SLDf9lqlvOQaIe6s Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="frame.diff" Content-length: 2682 commit d918a8fb8cbca3b3ac6c73fc62b38d21f5b70386 Author: Joel Brobecker Date: Thu Sep 3 11:16:44 2009 -0700 Avoid quadratic behavior when computing the value of a register. * frame.c (frame_cache): New static constant. (frame_cache_add, frame_cache_find, frame_cache_invalidate): New functions. (get_frame_id): Minor reformatting. Add the frame to the frame cache. (frame_find_by_id): Search the frame cache first before walking all frames starting from te current_frame. (reinit_frame_cache): Add call to frame_cache_invalidate (); diff --git a/gdb/frame.c b/gdb/frame.c index 67e0607..c12be5e 100644 --- a/gdb/frame.c +++ b/gdb/frame.c @@ -122,6 +122,37 @@ struct frame_info enum unwind_stop_reason stop_reason; }; +/* A Frame cache used to speed up frame lookups. */ + +/* We currently only cache one frame, as this seems to be sufficient + for now. */ +static struct frame_info *frame_cache = NULL; + +/* Add the following FRAME to the frame cache. */ +static void +frame_cache_add (struct frame_info *frame) +{ + frame_cache = frame; +} + +/* 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; +} + +/* Invalidate the frame cache by removing all entries in the cache. */ +static void +frame_cache_invalidate (void) +{ + frame_cache = NULL; +} + /* Flag to control debugging. */ int frame_debug; @@ -279,9 +310,8 @@ struct frame_id get_frame_id (struct frame_info *fi) { if (fi == NULL) - { - return null_frame_id; - } + return null_frame_id; + if (!fi->this_id.p) { if (frame_debug) @@ -300,6 +330,9 @@ get_frame_id (struct frame_info *fi) fprintf_unfiltered (gdb_stdlog, " }\n"); } } + + frame_cache_add (fi); + return fi->this_id.value; } @@ -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 = frame_cache_find (id); + if (frame && frame_id_eq (frame->this_id.value, id)) + return frame; + for (frame = get_current_frame (); ; frame = prev_frame) { struct frame_id this = get_frame_id (frame); @@ -1285,6 +1323,7 @@ reinit_frame_cache (void) current_frame = NULL; /* Invalidate cache */ select_frame (NULL); + frame_cache_invalidate (); if (frame_debug) fprintf_unfiltered (gdb_stdlog, "{ reinit_frame_cache () }\n"); } --SLDf9lqlvOQaIe6s Content-Type: text/x-chdr; charset=us-ascii Content-Disposition: attachment; filename="frame-cache.h" Content-length: 450 #include "defs.h" #include "frame.h" /* Add the following FRAME to the frame cache. */ void frame_cache_add (struct frame_info *frame, struct frame_id id); /* Search the frame cache for an entry with the given frame ID. If found, return that frame. Otherwise return NULL. */ struct frame_info *frame_cache_find (struct frame_id id); /* Invalidate the frame cache by removing all entries in the cache. */ void frame_cache_invalidate (void); --SLDf9lqlvOQaIe6s Content-Type: text/x-csrc; charset=us-ascii Content-Disposition: attachment; filename="frame-cache.c" Content-length: 823 #include "defs.h" #include "frame-cache.h" struct frame_cache_entry { struct frame_id id; struct frame_info *frame; }; /* The current implementation currently only caches one frame. */ struct frame_cache_entry frame_cache; void frame_cache_add (struct frame_info *frame, struct frame_id id) { frame_cache.id = id; frame_cache.frame = frame; } struct frame_info * frame_cache_find (struct frame_id id) { if (frame_id_eq (frame_cache.id, id)) return frame_cache.frame; return NULL; } void frame_cache_invalidate (void) { frame_cache.id = null_frame_id; frame_cache.frame = NULL; } /* Provide a prototype to silence -Wmissing-prototypes. */ extern initialize_file_ftype _initialize_frame_cache; void _initialize_frame_cache (void) { frame_cache.id = null_frame_id; frame_cache.frame = NULL; } --SLDf9lqlvOQaIe6s--