From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3177 invoked by alias); 1 May 2008 14:22:30 -0000 Received: (qmail 3152 invoked by uid 22791); 1 May 2008 14:22:26 -0000 X-Spam-Check-By: sourceware.org Received: from imr1.ericy.com (HELO imr1.ericy.com) (198.24.6.9) by sourceware.org (qpsmtpd/0.31) with ESMTP; Thu, 01 May 2008 14:22:02 +0000 Received: from eusrcmw751.eamcs.ericsson.se (eusrcmw751.exu.ericsson.se [138.85.77.51]) by imr1.ericy.com (8.13.1/8.13.1) with ESMTP id m41ELr7d030182; Thu, 1 May 2008 09:21:54 -0500 Received: from ecamlmw720.eamcs.ericsson.se ([142.133.1.72]) by eusrcmw751.eamcs.ericsson.se with Microsoft SMTPSVC(6.0.3790.1830); Thu, 1 May 2008 09:21:53 -0500 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: RE: [PATCH:MI] Return a subset of a variable object's children Date: Thu, 01 May 2008 14:22:00 -0000 Message-ID: <6D19CA8D71C89C43A057926FE0D4ADAA04E1BD0C@ecamlmw720.eamcs.ericsson.se> References: <18455.41299.899430.615138@kahikatea.snap.net.nz><6D19CA8D71C89C43A057926FE0D4ADAA042910B5@ecamlmw720.eamcs.ericsson.se> <18457.45600.692401.191218@kahikatea.snap.net.nz> From: "Marc Khouzam" To: "Nick Roberts" Cc: 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: 2008-05/txt/msg00009.txt.bz2 > The double loop is O(N*N). I guess it could be reduced to O(N*log(N)) > using some kind of sorting algorithm. > > > To me, the advantage of your > > patch is far larger in the fact that we no longer need to create all > > children varObj at once; my impression is that the memory allocation is= a > > small optimization in caparison. Is that a correct impression? Beside= s, > > currently, the memory is immediately allocated, so things wouldn't be a= ny > > worse :-) > >It's not just a question of memory allocation. It's computationally >inefficient because Gdb has to traverse a large sparsely populated vector = every >time it operates on it. It wouldn't be any _worse_ than current Gdb, but = I was >trying to make it significantly _better_. You are right. I was focusing on making the proposed algorithm more effici= ent but I didn't think about the other uses of the vector of children. So, as you mention above, keeping the vector ordered (without empty spaces), can reduce to O(N*log(N)). If fact, I think it would be reduced to O(log(N= )) since we would only need to find the location of the first new child; the p= osition of all other new children created in the same var-list-children can be dete= rmined from that first position. The expense would be in the insertion though, as the vector would have to be mem-copied N times, one for each child that is not at the end of the vector. I wonder if that is acceptable... Marc