diff mbox

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

Message ID CADNuJVo6=MuC5pJV4ew8Rr1Mu=PwUUsB=QwgKaRDcCZO6VBfhg@mail.gmail.com (mailing list archive)
State Superseded, archived
Headers show

Commit Message

Jay Rolette Dec. 11, 2014, 4:05 p.m. UTC
Signed-off-by: Jay Rolette <rolette@infiniteio.com>
---
 lib/librte_eal/linuxapp/eal/eal_memory.c | 59
+++++++++++---------------------
 1 file changed, 20 insertions(+), 39 deletions(-)

 }

--

Comments

Wodkowski, PawelX Dec. 15, 2014, 9:05 a.m. UTC | #1
> -----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);
Jay Rolette Dec. 15, 2014, 1:17 p.m. UTC | #2
Because it doesn't work correctly :-)

On Mon, Dec 15, 2014 at 3:05 AM, Wodkowski, PawelX <
pawelx.wodkowski@intel.com> wrote:
>
> > -----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);
>
>
Wodkowski, PawelX Dec. 15, 2014, 1:20 p.m. UTC | #3
> Because it doesn't work correctly :-)


It should, what I am missing here? :P

Pawel
Ananyev, Konstantin Dec. 15, 2014, 2:24 p.m. UTC | #4
> -----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.
Jay Rolette Dec. 15, 2014, 2:29 p.m. UTC | #5
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
>
>
Bruce Richardson Dec. 15, 2014, 2:55 p.m. UTC | #6
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

>

>
Ananyev, Konstantin Dec. 16, 2014, 6:39 p.m. UTC | #7
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;

>  }

> 

> --
Jay Rolette Dec. 16, 2014, 7:18 p.m. UTC | #8
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@intel.com> wrote:
>
>
> 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;
> >  }
> >
> > --
>
Jay Rolette Dec. 16, 2014, 7:20 p.m. UTC | #9
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> 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@intel.com> wrote:
>>
>>
>> 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;
>> >  }
>> >
>> > --
>>
>
Ananyev, Konstantin Dec. 17, 2014, 11 a.m. UTC | #10
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;

>  }

>

> --
Michael Qiu Dec. 17, 2014, 1:08 p.m. UTC | #11
On 12/17/2014 7:01 PM, Ananyev, Konstantin wrote:
> 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.
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@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;
>>  }
>>
>> --
Jay Rolette Dec. 17, 2014, 1:35 p.m. UTC | #12
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@intel.com> wrote:
>
> On 12/17/2014 7:01 PM, Ananyev, Konstantin wrote:
> > 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.
> 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@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;
> >>  }
> >>
> >> --
>
>
diff mbox

Patch

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;