[dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Jay Rolette]

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 at 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 <rolette at infiniteio.com>
>> ---
>>
> 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
>