From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 27868 invoked by alias); 16 May 2013 13:09:34 -0000 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 Received: (qmail 27856 invoked by uid 89); 16 May 2013 13:09:33 -0000 X-Spam-SWARE-Status: No, score=-6.5 required=5.0 tests=AWL,BAYES_00,RCVD_IN_HOSTKARMA_W,RCVD_IN_HOSTKARMA_WL,RP_MATCHES_RCVD,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.1 Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Thu, 16 May 2013 13:09:32 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r4GD9UTI020271 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Thu, 16 May 2013 09:09:31 -0400 Received: from localhost.localdomain (ovpn-112-16.ams2.redhat.com [10.36.112.16]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id r4GD9Trk005814 for ; Thu, 16 May 2013 09:09:30 -0400 Message-ID: <5194DA88.6020705@redhat.com> Date: Thu, 16 May 2013 13:09:00 -0000 From: Phil Muldoon MIME-Version: 1.0 To: "gdb-patches@sourceware.org" Subject: [patch] Convert frame_stash to a hash table Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-SW-Source: 2013-05/txt/msg00609.txt.bz2 One of the things I have noticed with frame filters is a significant penalty when printing backtraces. This is because the frame filters invalidate the frame_stash. The reason for this is as follows. Python frames do not store the GDB frame, nor should they. If they did, every time the frame cache is invalidated the Python object would be pointing to the memory freed by the invalidated frame. What Python frames do store is the frame_id. This is permanent, and allows Python to fetch the frame on demand. This on-demand nature is facilitated by a macro in the Python code: FRAPY_REQUIRE_VALID which fetches the frame with frame_find_by_id. All Python frame functions call this macro, and thus, all Python frame functions end up using frame_find_by_id before each operation. That's fine until you consider that Python frames almost act like a random access method of fetching frames, and the existing frame_stash being a single entry stash cannot cope with this. On single or occasional frame access this is fine and not noticeable. But on large numbers of sustained frame accesses, like in backtrace, this performance penalty of searching the frame cache (because the frame_stash has been invalidated) mounts up and causes a significant penalty. Here are some tests from the existing code in GDB: Test case is 20,000 frames printed in a backtrace. Before patch, no frame filters. real 0m3.081s user 0m1.745s sys 0m0.435s Before patch, with frame filters. real 4m16.094s user 3m42.718s sys 0m30.561s As you can see there is a considerable performance penalty. With the patch that converts frame_stash to a hash table, these are the numbers: After patch, no frame filters real 0m3.089s user 0m1.765s sys 0m0.414s After patch, with frame filters real 0m3.867s user 0m3.296s sys 0m0.414s As you can see, the performance penalty is removed. The "no frame filters" timings after the patch do appear to be slightly larger, but, using "time" is not very deterministic on such small numbers. I largely think we can ignore the difference with "no frame filters" before and after the patch. However "with frame filters" shows a massive improvement. Here are some gprof images that show the profiling statistics of "with frame filters" before and after the patch: Before patch: http://picobot.org/withoutpatch_filters.png After patch: http://picobot.org/withpatch_filters.png (These are large images) The numbers in the brackets in each box are the important ones to look at. Without the patch, GDB spends a large amount of time in get_prev_frame, which indicates constant hitting of the frame cache. I think this patch improves the frame_stash "with filters" without affecting "no filters" performance. Tested on x8664 with no regressions. What do you think? Cheers, Phil 2013-05-16 Phil Muldoon * frame.c (frame_stash): Convert to htab. (frame_addr_hash): New function. (frame_addr_hash_eq): New function. (frame_stash_create): Convert function to create a hash table. (frame_stash_add): Convert function to add an entry to a hash table. (frame_stash_find): Convert function to search the hash table. (frame_stash_invalidate): Convert function to empty the hash table. (get_frame_id): Only add to stash if a frame_id is created. (_initialize_frame): Call frame_stash_create. -- Index: frame.c =================================================================== RCS file: /cvs/src/src/gdb/frame.c,v retrieving revision 1.317 diff -u -r1.317 frame.c --- frame.c 10 Apr 2013 15:11:11 -0000 1.317 +++ frame.c 16 May 2013 12:57:05 -0000 @@ -43,6 +43,7 @@ #include "block.h" #include "inline-frame.h" #include "tracepoint.h" +#include "hashtab.h" static struct frame_info *get_prev_frame_1 (struct frame_info *this_frame); static struct frame_info *get_prev_frame_raw (struct frame_info *this_frame); @@ -128,38 +129,101 @@ enum unwind_stop_reason stop_reason; }; -/* A frame stash used to speed up frame lookups. */ +/* A frame stash used to speed up frame lookups. Create a hash table + to stash frames previously accessed from the frame cache for + quicker subsequent retrieval. The hash table is emptied whenever + the frame cache is invalidated. */ +static htab_t frame_stash; + +/* Internal function to calculate a hash from the frame_id addresses, + using as many valid addresses as possible. Frames below level 0 + are not stored in the hash table. */ +static hashval_t +frame_addr_hash (const void *ap) +{ + const struct frame_info *frame = ap; + const struct frame_id f_id = frame->this_id.value; + hashval_t hash = 0; + + if (! f_id.stack_addr_p && ! f_id.code_addr_p && ! f_id.special_addr) + gdb_assert ("Cannot calculate hash for frame_id."); + + if (f_id.stack_addr_p == 1) + hash = iterative_hash (&f_id.stack_addr, + sizeof (f_id.stack_addr), hash); + if (f_id.code_addr_p == 1) + hash = iterative_hash (&f_id.code_addr, + sizeof (f_id.code_addr), hash); + if (f_id.special_addr_p == 1) + hash = iterative_hash (&f_id.special_addr, + sizeof (f_id.special_addr), hash); -/* We currently only stash one frame at a time, as this seems to be - sufficient for now. */ -static struct frame_info *frame_stash = NULL; + return hash; +} -/* Add the following FRAME to the frame stash. */ +/* Internal equality function for the hash table. This function + defers equality operations to frame_id_eq. */ +static int +frame_addr_hash_eq (const void *a, const void *b) +{ + const struct frame_info *f_entry = a; + const struct frame_info *f_element = b; + + return frame_id_eq (f_entry->this_id.value, + f_element->this_id.value); +} +/* Internal function to create the frame_stash hash table. 100 seems + to be a good compromise to start the hash table at. */ static void -frame_stash_add (struct frame_info *frame) +frame_stash_create (void) { - frame_stash = frame; + frame_stash = htab_create (100, + frame_addr_hash, + frame_addr_hash_eq, + NULL); } -/* Search the frame stash for an entry with the given frame ID. - If found, return that frame. Otherwise return NULL. */ +/* Internal function to add a frame to the frame_stash hash table. Do + not store frames below 0 as they may not have any addresses to + calculate a hash. */ +static void +frame_stash_add (struct frame_info *frame) +{ + /* Do not stash frames below level 0. */ + if (frame->level >= 0) + { + struct frame_info **slot; + + slot = (struct frame_info **) htab_find_slot (frame_stash, + frame, + INSERT); + if (*slot != frame) + *slot = frame; + } +} +/* Internal function to search the frame stash for an entry with the + given frame ID. If found, return that frame. Otherwise return + NULL. */ static struct frame_info * frame_stash_find (struct frame_id id) { - if (frame_stash && frame_id_eq (frame_stash->this_id.value, id)) - return frame_stash; + struct frame_info dummy; + struct frame_info *frame; - return NULL; + dummy.this_id.value = id; + frame = htab_find (frame_stash, &dummy); + return frame; } -/* Invalidate the frame stash by removing all entries in it. */ - +/* Internal function to invalidate the frame stash by removing all + entries in it. This only occurs when the frame cache is + invalidated. */ static void frame_stash_invalidate (void) { - frame_stash = NULL; + htab_empty (frame_stash); } /* Flag to control debugging. */ @@ -345,10 +409,9 @@ fprint_frame_id (gdb_stdlog, fi->this_id.value); fprintf_unfiltered (gdb_stdlog, " }\n"); } + frame_stash_add (fi); } - frame_stash_add (fi); - return fi->this_id.value; } @@ -2451,6 +2514,8 @@ { obstack_init (&frame_cache_obstack); + frame_stash_create (); + observer_attach_target_changed (frame_observer_target_changed); add_prefix_cmd ("backtrace", class_maintenance, set_backtrace_cmd, _("\ --