From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 44989 invoked by alias); 29 Nov 2016 15:47:33 -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 44917 invoked by uid 89); 29 Nov 2016 15:47:32 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-5.2 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_LOW,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 spammy=Tel, tel, office, commercial X-HELO: mga06.intel.com Received: from mga06.intel.com (HELO mga06.intel.com) (134.134.136.31) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 29 Nov 2016 15:47:22 +0000 Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by orsmga104.jf.intel.com with ESMTP; 29 Nov 2016 07:47:19 -0800 X-ExtLoop1: 1 Received: from irsmsx107.ger.corp.intel.com ([163.33.3.99]) by FMSMGA003.fm.intel.com with ESMTP; 29 Nov 2016 07:47:18 -0800 Received: from irsmsx104.ger.corp.intel.com ([169.254.5.52]) by IRSMSX107.ger.corp.intel.com ([169.254.10.66]) with mapi id 14.03.0248.002; Tue, 29 Nov 2016 15:47:17 +0000 From: "Metzger, Markus T" To: "Wiederhake, Tim" , "gdb-patches@sourceware.org" CC: "palves@redhat.com" Subject: RE: [PATCH v3 3/8] btrace: Use binary search to find instruction. Date: Tue, 29 Nov 2016 15:47:00 -0000 Message-ID: References: <1479743318-24523-1-git-send-email-tim.wiederhake@intel.com> <1479743318-24523-4-git-send-email-tim.wiederhake@intel.com> In-Reply-To: <1479743318-24523-4-git-send-email-tim.wiederhake@intel.com> Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2016-11/txt/msg00953.txt.bz2 > -----Original Message----- > From: Wiederhake, Tim > Sent: Monday, November 21, 2016 4:49 PM > To: gdb-patches@sourceware.org > Cc: palves@redhat.com; Metzger, Markus T > Subject: [PATCH v3 3/8] btrace: Use binary search to find instruction. >=20 > Currently, btrace_find_insn_by_number will iterate over all function call > segments to find the one that contains the needed instruction. This line= ar > search is too slow for the upcoming Python bindings that will use this > function to access instructions. This patch introduces a vector in struct > btrace_thread_info that holds pointers to all recorded function segments = and > allows to use binary search. >=20 > The proper solution is to turn the underlying tree into a vector of objec= ts > and use indices for access. This requires more work. A patch set is > currently being worked on and will be published later. >=20 > 2016-11-21 Tim Wiederhake >=20 > gdb/ChangeLog: > * btrace.c (btrace_fetch): Copy function call segments pointer > into a vector. > (btrace_clear): Clear the vector. > (btrace_find_insn_by_number): Use binary search to find the correct > function call segment. > * btrace.h (brace_fun_p): New typedef. > (struct btrace_thread_info) : New field. > - if (bfun =3D=3D NULL) > + lower =3D 0; > + bfun =3D VEC_index (btrace_fun_p, btinfo->functions, lower); > + if (number < bfun->insn_offset) > return 0; >=20 > - if (bfun->insn_offset + ftrace_call_num_insn (bfun) <=3D number) > + upper =3D VEC_length (btrace_fun_p, btinfo->functions) - 1; > + bfun =3D VEC_index (btrace_fun_p, btinfo->functions, upper); > + if (number >=3D bfun->insn_offset + ftrace_call_num_insn (bfun)) > return 0; >=20 > + average =3D lower + (upper - lower) / 2; > + bfun =3D VEC_index (btrace_fun_p, btinfo->functions, average); > + > + while ((number >=3D bfun->insn_offset + ftrace_call_num_insn (bfun)) > + || (number < bfun->insn_offset)) > + { > + if (number < bfun->insn_offset) > + upper =3D average - 1; > + else > + lower =3D average + 1; > + > + average =3D lower + (upper - lower) / 2; > + bfun =3D VEC_index (btrace_fun_p, btinfo->functions, average); > + } > + > it->function =3D bfun; > it->index =3D number - bfun->insn_offset; This could be simplified a bit. Instead of checking the very small (i.e. z= ero in practice) and very big numbers upfront, we can let them fall through the binary search loop - both cases are unlikely. Also the loop could be simplified by merging the termination check and the check in the loop body so we end up with only one of the checks for low numbers. The algorithm looks good, however, and IIUC we're going to change that again with an in-progress patch series. So we might as well leave it as-is and consider this in the final version. Looks good to me. Thanks, Markus. Intel Deutschland GmbH Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany Tel: +49 89 99 8853-0, www.intel.de Managing Directors: Christin Eisenschmid, Christian Lamprechter Chairperson of the Supervisory Board: Nicole Lau Registered Office: Munich Commercial Register: Amtsgericht Muenchen HRB 186928