From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26777 invoked by alias); 13 Oct 2009 18:34:08 -0000 Received: (qmail 26769 invoked by uid 22791); 13 Oct 2009 18:34:08 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 13 Oct 2009 18:34:03 +0000 Received: from int-mx08.intmail.prod.int.phx2.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.21]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id n9DIY1Cs030974 for ; Tue, 13 Oct 2009 14:34:02 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx08.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id n9DIY1We016170; Tue, 13 Oct 2009 14:34:01 -0400 Received: from opsy.redhat.com (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id n9DIY0vV031655; Tue, 13 Oct 2009 14:34:00 -0400 Received: by opsy.redhat.com (Postfix, from userid 500) id A6C0FC88141; Tue, 13 Oct 2009 12:33:59 -0600 (MDT) From: Tom Tromey To: Jan Kratochvil Cc: gdb-patches@sourceware.org Subject: Re: [patch] Performance optimize large bp_location count References: <20090904201706.GA26300@host0.dyn.jankratochvil.net> Reply-To: tromey@redhat.com Date: Tue, 13 Oct 2009 18:34:00 -0000 In-Reply-To: <20090904201706.GA26300@host0.dyn.jankratochvil.net> (Jan Kratochvil's message of "Fri, 4 Sep 2009 22:17:06 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii 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-10/txt/msg00282.txt.bz2 >>>>> "Jan" == Jan Kratochvil writes: Jan> Every breakpoint being inserted runs check_duplicates() which was Jan> quadratic => the whole operation was cubic. n^3 becomes n^2*log(n) Jan> by this patch. n^2*log(n) still seems high, but since it dropped off the profile, then that is good enough. I puzzled over the choice of a sorted array here, wondering if there were perhaps some better data structure. A bit of rationale and overview in the patch email would go a long way. Jan> + /* Left boundary, right boundary and media element of our binary search. */ Jan> + unsigned bc_l, bc_r, bc; I think s/media/median/ Jan> + /* Find BC_L which is a leftmost element which may affect BUF content. It is Jan> + safe to report lower value but a failure to report higher one. */ Jan> + Jan> + bc_l = 0; Jan> + bc_r = bp_location_count; Jan> + while (bc_l + 1 < bc_r) Jan> + { Jan> + struct bp_location *b; Jan> + Jan> + bc = (bc_l + bc_r) / 2; Jan> + b = bp_location[bc]; Jan> + Jan> + if (b->address + bp_location_shadow_len_after_address_max >= b->address Jan> + && b->address + bp_location_shadow_len_after_address_max <= memaddr) Jan> + bc_l = bc; Jan> + else Jan> + bc_r = bc; Jan> + } It isn't obvious to me why this finds the leftmost element when there are multiple overlapping ones. What am I missing? Jan> - cleanups = make_cleanup (do_vec_free, &old_locations); I think this is the only use of do_vec_free, so that function can be removed. Tom