From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 17524 invoked by alias); 27 Mar 2013 14:50:48 -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 17475 invoked by uid 89); 27 Mar 2013 14:50:41 -0000 X-Spam-SWARE-Status: No, score=-7.0 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,RCVD_IN_DNSWL_HI,RCVD_IN_HOSTKARMA_W,RP_MATCHES_RCVD,SPF_HELO_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; Wed, 27 Mar 2013 14:50:38 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r2REoZS3018097 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Wed, 27 Mar 2013 10:50:35 -0400 Received: from host2.jankratochvil.net (ovpn-116-39.ams2.redhat.com [10.36.116.39]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r2REoTFC030693 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Wed, 27 Mar 2013 10:50:33 -0400 Date: Wed, 27 Mar 2013 18:08:00 -0000 From: Jan Kratochvil To: Aleksandar Ristovski Cc: "gdb-patches@sourceware.org" Subject: Re: [patch 6/6] gdbserver build-id attribute generator Message-ID: <20130327145028.GA17905@host2.jankratochvil.net> References: <51278984.3070208@qnx.com> <20130310210843.GG21130@host2.jankratochvil.net> <514C56D4.1060906@qnx.com> <20130326204157.GC12291@host2.jankratochvil.net> <51530465.30503@qnx.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <51530465.30503@qnx.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes X-SW-Source: 2013-03/txt/msg01021.txt.bz2 On Wed, 27 Mar 2013 15:38:29 +0100, Aleksandar Ristovski wrote: > On 13-03-26 04:41 PM, Jan Kratochvil wrote: > >>>+ if (build_id_list_p) > >>>+ qsort (VEC_address (build_id_list_s, data.list), > >>>+ VEC_length (build_id_list_s, data.list), > >>>+ sizeof (build_id_list_s), compare_build_id_list); > >It is always already sorted by Linux kernel, rather a for cycle to verify it > >really is sorted. > > Can we guarantee this is always the case? Yes. The problem is that if it is unsorted there is a bug somewhere and that qsort will hide that bug. > Even if it is, qsort would > do similar to what a loop would (i.e. no moves would take place). (a) qsort has the n*log(n) complexity no matter how sorted the input is. You are right omitting the read/writes of swapping should speed it up, just it won't because: (b) glibc qsort uses msort (=mergesort), therefore it always moves all the data anyway. I did not take any benchmarks but I do not think sorted vs. unsorted input will make any performance difference with glibc. > I'd leave it with qsort unless you feel strongly about it. Yes, please change it. It would hide bugs of some unsorted or corrupted data, and after all it is really needlessly expensive when there are efforts to optimize the shared libraries reading. Thanks, Jan