From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-vk0-f52.google.com (mail-vk0-f52.google.com [209.85.213.52]) by dpdk.org (Postfix) with ESMTP id B87F358CB for ; Thu, 10 Sep 2015 13:49:56 +0200 (CEST) Received: by vkhf67 with SMTP id f67so7771495vkh.1 for ; Thu, 10 Sep 2015 04:49:56 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=WK3FKvy6FhBtMRcYK2A1/COHulnus9IrE55QrXRTdAU=; b=eRYLpqiDtBriUA4dm/eLuL5ZgYyksKmaESyMWqRjb75ccKug6AbQRju35Ql9m9mlTU 5J60ZXVgAtR/4qSnka5/nI4CCRkPrYS36mNcpLHvx4aumrSw7MwQ4Tbv97K3eb9C2tXr 7z7vsu3NXsDhPrHu6avw8pH+/Uo76/E9a25eg6Kd6xuGNIkLLAT8JzrOm4DlSmNlE1is x3DRX5tVgEs2/OqonaqZbWskE8Qn8MghRQBoQI7q8HBVgx7u3J30HzkKfY+s4CGqd/4t QE8vHlMrHWdflCypAUTo9PDWA6IEIIGigUtmsZFPCFHKHUjV4NqQoXdzWqxsc2EohmYW 1N0g== X-Gm-Message-State: ALoCoQnZD7ASatchskqdgOAY/5ZpzCG9mOJsYkTLlh6o84oOTUGOKlUVo7omrJNwl1cxrp2YRoRt MIME-Version: 1.0 X-Received: by 10.31.128.78 with SMTP id b75mr1299092vkd.70.1441885796147; Thu, 10 Sep 2015 04:49:56 -0700 (PDT) Received: by 10.103.69.17 with HTTP; Thu, 10 Sep 2015 04:49:56 -0700 (PDT) In-Reply-To: <55F00B8D.9010704@intel.com> References: <1418823077-9129-1-git-send-email-rolette@infiniteio.com> <55F00B8D.9010704@intel.com> Date: Thu, 10 Sep 2015 06:49:56 -0500 Message-ID: From: Jay Rolette To: "Gonzalez Monroy, Sergio" Content-Type: text/plain; charset=UTF-8 X-Content-Filtered-By: Mailman/MimeDel 2.1.15 Cc: "dev@dpdk.org" Subject: Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Sep 2015 11:49:57 -0000 Thanks for the feedback, Sergio. Responses inline below, but unfortunately I don't have time to submit a new patch right now. I'm at the tail-end of our release cycle. Last year when I originally submitted the patch, it would have been easy to update it and resubmit. Jay On Wed, Sep 9, 2015 at 5:35 AM, Gonzalez Monroy, Sergio < sergio.gonzalez.monroy@intel.com> wrote: > Following conversation in > http://dpdk.org/ml/archives/dev/2015-September/023230.html : > > On 17/12/2014 13:31, rolette at infiniteio.com (Jay Rolette) wrote: > >> Signed-off-by: Jay Rolette >> --- >> > Update commit title/description, maybe something like: > eal/linux: use qsort for sorting hugepages > Replace O(n^2) sort in sort_by_physaddr() with qsort() from standard > library Ok. Pretty minor, but easy enough. > lib/librte_eal/linuxapp/eal/eal_memory.c | 59 >> +++++++++++--------------------- >> 1 file changed, 20 insertions(+), 39 deletions(-) >> >> diff --git a/lib/librte_eal/linuxapp/eal/eal_memory.c >> b/lib/librte_eal/linuxapp/eal/eal_memory.c >> index bae2507..3656515 100644 >> --- a/lib/librte_eal/linuxapp/eal/eal_memory.c >> +++ b/lib/librte_eal/linuxapp/eal/eal_memory.c >> @@ -670,6 +670,25 @@ error: >> return -1; >> } >> +static int >> +cmp_physaddr(const void *a, const void *b) >> +{ >> +#ifndef RTE_ARCH_PPC_64 >> + const struct hugepage_file *p1 = (const struct hugepage_file *)a; >> + const struct hugepage_file *p2 = (const struct hugepage_file *)b; >> +#else >> + // PowerPC needs memory sorted in reverse order from x86 >> + const struct hugepage_file *p1 = (const struct hugepage_file *)b; >> + const struct hugepage_file *p2 = (const struct hugepage_file *)a; >> +#endif >> + if (p1->physaddr < p2->physaddr) >> + return -1; >> + else if (p1->physaddr > p2->physaddr) >> + return 1; >> + else >> + return 0; >> +} >> + >> > There were a couple of comments from Thomas about the comments style and > #ifdef: > - Comment style should be modified as per > http://dpdk.org/doc/guides/contributing/coding_style.html#c-comment-style Yep, although that came along well after I submitted the patch - Regarding the #ifdef, I agree with Jay that it is the current approach in > the file. > > /* >> * Sort the hugepg_tbl by physical address (lower addresses first on >> x86, >> * higher address first on powerpc). We use a slow algorithm, but we >> won't >> @@ -678,45 +697,7 @@ error: >> static int >> sort_by_physaddr(struct hugepage_file *hugepg_tbl, struct hugepage_info >> *hpi) >> { >> - unsigned i, j; >> - int compare_idx; >> - uint64_t compare_addr; >> - struct hugepage_file tmp; >> - >> - for (i = 0; i < hpi->num_pages[0]; i++) { >> - compare_addr = 0; >> - compare_idx = -1; >> - >> - /* >> - * browse all entries starting at 'i', and find the >> - * entry with the smallest addr >> - */ >> - for (j=i; j< hpi->num_pages[0]; j++) { >> - >> - if (compare_addr == 0 || >> -#ifdef RTE_ARCH_PPC_64 >> - hugepg_tbl[j].physaddr > compare_addr) { >> -#else >> - hugepg_tbl[j].physaddr < compare_addr) { >> -#endif >> - compare_addr = hugepg_tbl[j].physaddr; >> - compare_idx = j; >> - } >> - } >> - >> - /* should not happen */ >> - if (compare_idx == -1) { >> - RTE_LOG(ERR, EAL, "%s(): error in physaddr >> sorting\n", __func__); >> - return -1; >> - } >> - >> - /* swap the 2 entries in the table */ >> - memcpy(&tmp, &hugepg_tbl[compare_idx], >> - sizeof(struct hugepage_file)); >> - memcpy(&hugepg_tbl[compare_idx], &hugepg_tbl[i], >> - sizeof(struct hugepage_file)); >> - memcpy(&hugepg_tbl[i], &tmp, sizeof(struct >> hugepage_file)); >> - } >> + qsort(hugepg_tbl, hpi->num_pages[0], sizeof(struct >> hugepage_file), cmp_physaddr); >> return 0; >> } >> > Why not just remove sort_by_physaddr() and call qsort() directly? That would be fine. I hadn't bothered to check whether sort_by_physaddr() was called anywhere else, so left it there. It's not, so no real value to keeping it in this case. > > Sergio >