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

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

[Jay Rolette]

Signed-off-by: Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org>
---
 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;
+}
+
 /*
  * 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;
 }

--

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Wodkowski, PawelX]

> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Jay Rolette
> Sent: Thursday, December 11, 2014 5:06 PM
> To: Dev
> Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with
> qsort() from standard library
> 
> Signed-off-by: Jay Rolette <rolette@infiniteio.com>
> ---
>  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;
> +}
> +

Why not simply

return (int)(p1->physaddr - p2->physaddr);

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Jay Rolette]

Because it doesn't work correctly :-)

On Mon, Dec 15, 2014 at 3:05 AM, Wodkowski, PawelX <
pawelx.wodkowski-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org> wrote:
>
> > -----Original Message-----
> > From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org] On Behalf Of Jay Rolette
> > Sent: Thursday, December 11, 2014 5:06 PM
> > To: Dev
> > Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr()
> with
> > qsort() from standard library
> >
> > Signed-off-by: Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org>
> > ---
> >  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;
> > +}
> > +
>
> Why not simply
>
> return (int)(p1->physaddr - p2->physaddr);
>
>

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Wodkowski, PawelX]

> Because it doesn't work correctly :-)

It should, what I am missing here? :P

Pawel

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Jay Rolette]

FWIW, it surprised the heck out of me as well.

Turns out that even though I'm compiling in 64-bit mode, gcc has
sizeof(int) as 4 bytes rather than 8. Not really sure what the scoop is on
that, but the standard leaves that up to the compiler. I'm used to int
always being the "natural size" on the CPU/OS, so for a 64-bit executable
on Intel, I assumed int would be 64-bit.

Being an embedded developer for so many years, I rarely use semi-defined
data types just to avoid these sorts of problems.

On Mon, Dec 15, 2014 at 7:20 AM, Wodkowski, PawelX <
pawelx.wodkowski-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org> wrote:
>
> > Because it doesn't work correctly :-)
>
> It should, what I am missing here? :P
>
> Pawel
>
>

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Richardson, Bruce]

Interestingly, in 64-bit mode the default size of operands on IA is still 32-bit. Instructions often need to have the REX prefix on them to actually use 64-bit data. The REX prefix is explained in section 2.2.1 of the "Intel® 64 and IA-32 Architectures Software Developer’s Manual", Volume 2

Regards,
/Bruce

-----Original Message-----
From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Jay Rolette
Sent: Monday, December 15, 2014 2:29 PM
To: Wodkowski, PawelX
Cc: Dev
Subject: Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

FWIW, it surprised the heck out of me as well.

Turns out that even though I'm compiling in 64-bit mode, gcc has
sizeof(int) as 4 bytes rather than 8. Not really sure what the scoop is on that, but the standard leaves that up to the compiler. I'm used to int always being the "natural size" on the CPU/OS, so for a 64-bit executable on Intel, I assumed int would be 64-bit.

Being an embedded developer for so many years, I rarely use semi-defined data types just to avoid these sorts of problems.

On Mon, Dec 15, 2014 at 7:20 AM, Wodkowski, PawelX < pawelx.wodkowski@intel.com> wrote:
>
> > Because it doesn't work correctly :-)
>
> It should, what I am missing here? :P
>
> Pawel
>
>

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Ananyev, Konstantin]

> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Wodkowski, PawelX
> Sent: Monday, December 15, 2014 9:05 AM
> To: Jay Rolette; Dev
> Subject: Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
> 
> > -----Original Message-----
> > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Jay Rolette
> > Sent: Thursday, December 11, 2014 5:06 PM
> > To: Dev
> > Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with
> > qsort() from standard library
> >
> > Signed-off-by: Jay Rolette <rolette@infiniteio.com>
> > ---
> >  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;
> > +}
> > +
> 
> Why not simply
> 
> return (int)(p1->physaddr - p2->physaddr);

physaddr is uint64_t.

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Ananyev, Konstantin]

Hi Jay,

> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Jay Rolette
> Sent: Thursday, December 11, 2014 4:06 PM
> To: Dev
> Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
> 
> Signed-off-by: Jay Rolette <rolette@infiniteio.com>

The patch itself looks good to me.
Though it seems something wrong with formatting - all lines start with offset 0.
Probably your mail client?
Konstantin


> ---
>  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;
> +}
> +
>  /*
>   * 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;
>  }
> 
> --

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Jay Rolette]

Thanks Konstantin. Yes, I'll resend. Not sure why gmail is removing
whitespace when I sent in Plain Text mode.

Ultimately I'll need to figure out how to properly configure git to send
these directly instead of handling them more manually. The examples I saw
assumed you were using a gmail.com email rather than a corporate email
hosted via google apps.

Jay

On Tue, Dec 16, 2014 at 12:39 PM, Ananyev, Konstantin <
konstantin.ananyev-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org> wrote:
>
>
> Hi Jay,
>
> > -----Original Message-----
> > From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org] On Behalf Of Jay Rolette
> > Sent: Thursday, December 11, 2014 4:06 PM
> > To: Dev
> > Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr()
> with qsort() from standard library
> >
> > Signed-off-by: Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org>
>
> The patch itself looks good to me.
> Though it seems something wrong with formatting - all lines start with
> offset 0.
> Probably your mail client?
> Konstantin
>
>
> > ---
> >  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;
> > +}
> > +
> >  /*
> >   * 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;
> >  }
> >
> > --
>

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Jay Rolette]

Actually, I just relooked at the email I sent and it looks correct
(properly indented, etc.). Any suggestions for what might be going on?

On Tue, Dec 16, 2014 at 1:18 PM, Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org> wrote:
>
> Thanks Konstantin. Yes, I'll resend. Not sure why gmail is removing
> whitespace when I sent in Plain Text mode.
>
> Ultimately I'll need to figure out how to properly configure git to send
> these directly instead of handling them more manually. The examples I saw
> assumed you were using a gmail.com email rather than a corporate email
> hosted via google apps.
>
> Jay
>
> On Tue, Dec 16, 2014 at 12:39 PM, Ananyev, Konstantin <
> konstantin.ananyev-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org> wrote:
>>
>>
>> Hi Jay,
>>
>> > -----Original Message-----
>> > From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org] On Behalf Of Jay Rolette
>> > Sent: Thursday, December 11, 2014 4:06 PM
>> > To: Dev
>> > Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr()
>> with qsort() from standard library
>> >
>> > Signed-off-by: Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org>
>>
>> The patch itself looks good to me.
>> Though it seems something wrong with formatting - all lines start with
>> offset 0.
>> Probably your mail client?
>> Konstantin
>>
>>
>> > ---
>> >  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;
>> > +}
>> > +
>> >  /*
>> >   * 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;
>> >  }
>> >
>> > --
>>
>

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Ananyev, Konstantin]

Hi Jay,

From: Jay Rolette [mailto:rolette@infiniteio.com]
Sent: Tuesday, December 16, 2014 7:21 PM
To: Ananyev, Konstantin
Cc: Dev
Subject: Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

Actually, I just relooked at the email I sent and it looks correct (properly indented, etc.). Any suggestions for what might be going on?

On Tue, Dec 16, 2014 at 1:18 PM, Jay Rolette <rolette@infiniteio.com<mailto:rolette@infiniteio.com>> wrote:
Thanks Konstantin. Yes, I'll resend. Not sure why gmail is removing whitespace when I sent in Plain Text mode.

Sorry, don’t know either.
Wonder, did you see this:
https://www.kernel.org/pub/software/scm/git/docs/git-format-patch.html
There is a section about different mailers, etc.
Konstantin

Ultimately I'll need to figure out how to properly configure git to send these directly instead of handling them more manually. The examples I saw assumed you were using a gmail.com<http://gmail.com> email rather than a corporate email hosted via google apps.

Jay

On Tue, Dec 16, 2014 at 12:39 PM, Ananyev, Konstantin <konstantin.ananyev@intel.com<mailto:konstantin.ananyev@intel.com>> wrote:

Hi Jay,

> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org<mailto:dev-bounces@dpdk.org>] On Behalf Of Jay Rolette
> Sent: Thursday, December 11, 2014 4:06 PM
> To: Dev
> Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
>
> Signed-off-by: Jay Rolette <rolette@infiniteio.com<mailto:rolette@infiniteio.com>>

The patch itself looks good to me.
Though it seems something wrong with formatting - all lines start with offset 0.
Probably your mail client?
Konstantin


> ---
>  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;
> +}
> +
>  /*
>   * 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;
>  }
>
> --

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Qiu, Michael]

On 12/17/2014 7:01 PM, Ananyev, Konstantin wrote:
> Hi Jay,
>
> From: Jay Rolette [mailto:rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org]
> Sent: Tuesday, December 16, 2014 7:21 PM
> To: Ananyev, Konstantin
> Cc: Dev
> Subject: Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
>
> Actually, I just relooked at the email I sent and it looks correct (properly indented, etc.). Any suggestions for what might be going on?
>
> On Tue, Dec 16, 2014 at 1:18 PM, Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org<mailto:rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org>> wrote:
> Thanks Konstantin. Yes, I'll resend. Not sure why gmail is removing whitespace when I sent in Plain Text mode.
>
> Sorry, don’t know either.
> Wonder, did you see this:
> https://www.kernel.org/pub/software/scm/git/docs/git-format-patch.html
> There is a section about different mailers, etc.
> Konstantin
>
> Ultimately I'll need to figure out how to properly configure git to send these directly instead of handling them more manually. The examples I saw assumed you were using a gmail.com<http://gmail.com> email rather than a corporate email hosted via google apps.
Hi Jay,

I was ever use git send-email with my gmail account, it works.

So do you config your git send-email correctly?

Thanks,
Michael

 
> Jay
>
> On Tue, Dec 16, 2014 at 12:39 PM, Ananyev, Konstantin <konstantin.ananyev@intel.com<mailto:konstantin.ananyev-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>> wrote:
>
> Hi Jay,
>
>> -----Original Message-----
>> From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org<mailto:dev-bounces-VfR2kkLFssw@public.gmane.org>] On Behalf Of Jay Rolette
>> Sent: Thursday, December 11, 2014 4:06 PM
>> To: Dev
>> Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
>>
>> Signed-off-by: Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org<mailto:rolette@infiniteio.com>>
> The patch itself looks good to me.
> Though it seems something wrong with formatting - all lines start with offset 0.
> Probably your mail client?
> Konstantin
>
>
>> ---
>>  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;
>> +}
>> +
>>  /*
>>   * 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;
>>  }
>>
>> --

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Jay Rolette]

Thanks to some help from Matthew Hall, it looks like I have it working now.
I just resent the patch directly from git. Please let me know if it looks
ok now?

Sorry for the hassles. We use Mercurial internally, so while there is a lot
of overlap, sending patches isn't something I have to worry about
day-to-day. Appreciate the help getting things configured!

Jay

On Wed, Dec 17, 2014 at 7:08 AM, Qiu, Michael <michael.qiu-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org> wrote:
>
> On 12/17/2014 7:01 PM, Ananyev, Konstantin wrote:
> > Hi Jay,
> >
> > From: Jay Rolette [mailto:rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org]
> > Sent: Tuesday, December 16, 2014 7:21 PM
> > To: Ananyev, Konstantin
> > Cc: Dev
> > Subject: Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in
> sort_by_physaddr() with qsort() from standard library
> >
> > Actually, I just relooked at the email I sent and it looks correct
> (properly indented, etc.). Any suggestions for what might be going on?
> >
> > On Tue, Dec 16, 2014 at 1:18 PM, Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org
> <mailto:rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org>> wrote:
> > Thanks Konstantin. Yes, I'll resend. Not sure why gmail is removing
> whitespace when I sent in Plain Text mode.
> >
> > Sorry, don’t know either.
> > Wonder, did you see this:
> > https://www.kernel.org/pub/software/scm/git/docs/git-format-patch.html
> > There is a section about different mailers, etc.
> > Konstantin
> >
> > Ultimately I'll need to figure out how to properly configure git to send
> these directly instead of handling them more manually. The examples I saw
> assumed you were using a gmail.com<http://gmail.com> email rather than a
> corporate email hosted via google apps.
> Hi Jay,
>
> I was ever use git send-email with my gmail account, it works.
>
> So do you config your git send-email correctly?
>
> Thanks,
> Michael
>
>
> > Jay
> >
> > On Tue, Dec 16, 2014 at 12:39 PM, Ananyev, Konstantin <
> konstantin.ananyev-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org<mailto:konstantin.ananyev-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>> wrote:
> >
> > Hi Jay,
> >
> >> -----Original Message-----
> >> From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org<mailto:dev-bounces-VfR2kkLFssw@public.gmane.org>]
> On Behalf Of Jay Rolette
> >> Sent: Thursday, December 11, 2014 4:06 PM
> >> To: Dev
> >> Subject: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr()
> with qsort() from standard library
> >>
> >> Signed-off-by: Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org<mailto:
> rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org>>
> > The patch itself looks good to me.
> > Though it seems something wrong with formatting - all lines start with
> offset 0.
> > Probably your mail client?
> > Konstantin
> >
> >
> >> ---
> >>  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;
> >> +}
> >> +
> >>  /*
> >>   * 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;
> >>  }
> >>
> >> --
>
>

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

[Jay Rolette]

Signed-off-by: Jay Rolette <rolette-bIuJOMs36aleGPcbtGPokg@public.gmane.org>
---
 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;
+}
+
 /*
  * 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;
 }
 
-- 
1.9.3 (Apple Git-50)

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Thomas Monjalon]

Hi Jay,

Please read http://dpdk.org/dev#send for submission guidelines.

A description of why you do it would be welcome in the commit log.

> +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

Comments shall be C-style (/* */).

> +	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;
> +}

One of the goal of EAL is to avoid #ifdef.
So that function would probably be better located in
lib/librte_eal/common/include/arch/* with different implemenations
depending of the architecture.

-- 
Thomas

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Jay Rolette]

Hi Thomas,

Please read http://dpdk.org/dev#send for submission guidelines.
>

I did when I was figuring out how to submit the patch, but possible I'm
missing something on the tools to get it to include the commit comment
correctly.

A description of why you do it would be welcome in the commit log.
>

How much are you looking for here? I thought replacing an O(n^2) algorithm
with qsort() was fairly self-evident. Less code and take advantage of
standard library code that is faster.

I get it in the general case. Just didn't seem necessary for this one.


> > +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
>
> Comments shall be C-style (/* */).
>

Single line comments ('//') have been part of the C standard since C99. Is
DPDK following C89 or is this just a style thing? If it is a style thing, a
link to a page with the rubric would be helpful. I didn't see one on the
submission guidelines.


> > +     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;
> > +}
>
> One of the goal of EAL is to avoid #ifdef.
> So that function would probably be better located in
> lib/librte_eal/common/include/arch/* with different implemenations
> depending of the architecture.
>

Hmm... I was following the approach already used in the module. See
map_all_hugepages(), remap_all_hugepages().

Regards,
Jay

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Bruce Richardson]

On Wed, Dec 17, 2014 at 09:07:45AM -0600, Jay Rolette wrote:
>
> > Comments shall be C-style (/* */).
> >
> 
> Single line comments ('//') have been part of the C standard since C99. Is
> DPDK following C89 or is this just a style thing? If it is a style thing, a
> link to a page with the rubric would be helpful. I didn't see one on the
> submission guidelines.
>
To to add here that I'd love to see the coding guidelines relaxed to allow
"//" style comments!

/Bruce

Re: [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library

[Gonzalez Monroy, Sergio]

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
>   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
- 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?

Sergio

Re: [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@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
>