DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
@ 2014-12-17 13:31 Jay Rolette
  2014-12-17 14:27 ` Thomas Monjalon
  2015-09-09 10:35 ` Gonzalez Monroy, Sergio
  0 siblings, 2 replies; 19+ messages in thread
From: Jay Rolette @ 2014-12-17 13:31 UTC (permalink / raw)
  To: dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-17 13:31 [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library Jay Rolette
@ 2014-12-17 14:27 ` Thomas Monjalon
  2014-12-17 15:07   ` Jay Rolette
  2015-09-09 10:35 ` Gonzalez Monroy, Sergio
  1 sibling, 1 reply; 19+ messages in thread
From: Thomas Monjalon @ 2014-12-17 14:27 UTC (permalink / raw)
  To: Jay Rolette; +Cc: dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-17 14:27 ` Thomas Monjalon
@ 2014-12-17 15:07   ` Jay Rolette
  2014-12-17 15:27     ` Bruce Richardson
  0 siblings, 1 reply; 19+ messages in thread
From: Jay Rolette @ 2014-12-17 15:07 UTC (permalink / raw)
  To: Thomas Monjalon; +Cc: Dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-17 15:07   ` Jay Rolette
@ 2014-12-17 15:27     ` Bruce Richardson
  0 siblings, 0 replies; 19+ messages in thread
From: Bruce Richardson @ 2014-12-17 15:27 UTC (permalink / raw)
  To: Jay Rolette; +Cc: Dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-17 13:31 [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library Jay Rolette
  2014-12-17 14:27 ` Thomas Monjalon
@ 2015-09-09 10:35 ` Gonzalez Monroy, Sergio
  2015-09-10 11:49   ` Jay Rolette
  1 sibling, 1 reply; 19+ messages in thread
From: Gonzalez Monroy, Sergio @ 2015-09-09 10:35 UTC (permalink / raw)
  To: Jay Rolette; +Cc: dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2015-09-09 10:35 ` Gonzalez Monroy, Sergio
@ 2015-09-10 11:49   ` Jay Rolette
  0 siblings, 0 replies; 19+ messages in thread
From: Jay Rolette @ 2015-09-10 11:49 UTC (permalink / raw)
  To: Gonzalez Monroy, Sergio; +Cc: dev

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
>

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-17 13:08         ` Qiu, Michael
@ 2014-12-17 13:35           ` Jay Rolette
  0 siblings, 0 replies; 19+ messages in thread
From: Jay Rolette @ 2014-12-17 13:35 UTC (permalink / raw)
  To: Qiu, Michael; +Cc: Dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-17 11:00       ` Ananyev, Konstantin
@ 2014-12-17 13:08         ` Qiu, Michael
  2014-12-17 13:35           ` Jay Rolette
  0 siblings, 1 reply; 19+ messages in thread
From: Qiu, Michael @ 2014-12-17 13:08 UTC (permalink / raw)
  To: Jay Rolette; +Cc: Dev

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


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-16 19:20     ` Jay Rolette
@ 2014-12-17 11:00       ` Ananyev, Konstantin
  2014-12-17 13:08         ` Qiu, Michael
  0 siblings, 1 reply; 19+ messages in thread
From: Ananyev, Konstantin @ 2014-12-17 11:00 UTC (permalink / raw)
  To: Jay Rolette; +Cc: Dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-16 19:18   ` Jay Rolette
@ 2014-12-16 19:20     ` Jay Rolette
  2014-12-17 11:00       ` Ananyev, Konstantin
  0 siblings, 1 reply; 19+ messages in thread
From: Jay Rolette @ 2014-12-16 19:20 UTC (permalink / raw)
  To: Ananyev, Konstantin; +Cc: Dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-16 18:39 ` Ananyev, Konstantin
@ 2014-12-16 19:18   ` Jay Rolette
  2014-12-16 19:20     ` Jay Rolette
  0 siblings, 1 reply; 19+ messages in thread
From: Jay Rolette @ 2014-12-16 19:18 UTC (permalink / raw)
  To: Ananyev, Konstantin; +Cc: Dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-11 16:05 Jay Rolette
  2014-12-15  9:05 ` Wodkowski, PawelX
@ 2014-12-16 18:39 ` Ananyev, Konstantin
  2014-12-16 19:18   ` Jay Rolette
  1 sibling, 1 reply; 19+ messages in thread
From: Ananyev, Konstantin @ 2014-12-16 18:39 UTC (permalink / raw)
  To: Jay Rolette, Dev


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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-15 14:29       ` Jay Rolette
@ 2014-12-15 14:55         ` Richardson, Bruce
  0 siblings, 0 replies; 19+ messages in thread
From: Richardson, Bruce @ 2014-12-15 14:55 UTC (permalink / raw)
  To: Jay Rolette, Wodkowski, PawelX; +Cc: Dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-15 13:20     ` Wodkowski, PawelX
@ 2014-12-15 14:29       ` Jay Rolette
  2014-12-15 14:55         ` Richardson, Bruce
  0 siblings, 1 reply; 19+ messages in thread
From: Jay Rolette @ 2014-12-15 14:29 UTC (permalink / raw)
  To: Wodkowski, PawelX; +Cc: Dev

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

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-15  9:05 ` Wodkowski, PawelX
  2014-12-15 13:17   ` Jay Rolette
@ 2014-12-15 14:24   ` Ananyev, Konstantin
  1 sibling, 0 replies; 19+ messages in thread
From: Ananyev, Konstantin @ 2014-12-15 14:24 UTC (permalink / raw)
  To: Wodkowski, PawelX, Jay Rolette, Dev



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




^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-15 13:17   ` Jay Rolette
@ 2014-12-15 13:20     ` Wodkowski, PawelX
  2014-12-15 14:29       ` Jay Rolette
  0 siblings, 1 reply; 19+ messages in thread
From: Wodkowski, PawelX @ 2014-12-15 13:20 UTC (permalink / raw)
  To: Jay Rolette; +Cc: Dev

> Because it doesn't work correctly :-)

It should, what I am missing here? :P

Pawel


^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-15  9:05 ` Wodkowski, PawelX
@ 2014-12-15 13:17   ` Jay Rolette
  2014-12-15 13:20     ` Wodkowski, PawelX
  2014-12-15 14:24   ` Ananyev, Konstantin
  1 sibling, 1 reply; 19+ messages in thread
From: Jay Rolette @ 2014-12-15 13:17 UTC (permalink / raw)
  To: Wodkowski, PawelX; +Cc: Dev

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);
>
>

^ permalink raw reply	[flat|nested] 19+ messages in thread

* Re: [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
  2014-12-11 16:05 Jay Rolette
@ 2014-12-15  9:05 ` Wodkowski, PawelX
  2014-12-15 13:17   ` Jay Rolette
  2014-12-15 14:24   ` Ananyev, Konstantin
  2014-12-16 18:39 ` Ananyev, Konstantin
  1 sibling, 2 replies; 19+ messages in thread
From: Wodkowski, PawelX @ 2014-12-15  9:05 UTC (permalink / raw)
  To: Jay Rolette, Dev

> -----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);


^ permalink raw reply	[flat|nested] 19+ messages in thread

* [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library
@ 2014-12-11 16:05 Jay Rolette
  2014-12-15  9:05 ` Wodkowski, PawelX
  2014-12-16 18:39 ` Ananyev, Konstantin
  0 siblings, 2 replies; 19+ messages in thread
From: Jay Rolette @ 2014-12-11 16:05 UTC (permalink / raw)
  To: Dev

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

--

^ permalink raw reply	[flat|nested] 19+ messages in thread

end of thread, other threads:[~2015-09-10 11:49 UTC | newest]

Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-12-17 13:31 [dpdk-dev] [PATCH] replaced O(n^2) sort in sort_by_physaddr() with qsort() from standard library Jay Rolette
2014-12-17 14:27 ` Thomas Monjalon
2014-12-17 15:07   ` Jay Rolette
2014-12-17 15:27     ` Bruce Richardson
2015-09-09 10:35 ` Gonzalez Monroy, Sergio
2015-09-10 11:49   ` Jay Rolette
  -- strict thread matches above, loose matches on Subject: below --
2014-12-11 16:05 Jay Rolette
2014-12-15  9:05 ` Wodkowski, PawelX
2014-12-15 13:17   ` Jay Rolette
2014-12-15 13:20     ` Wodkowski, PawelX
2014-12-15 14:29       ` Jay Rolette
2014-12-15 14:55         ` Richardson, Bruce
2014-12-15 14:24   ` Ananyev, Konstantin
2014-12-16 18:39 ` Ananyev, Konstantin
2014-12-16 19:18   ` Jay Rolette
2014-12-16 19:20     ` Jay Rolette
2014-12-17 11:00       ` Ananyev, Konstantin
2014-12-17 13:08         ` Qiu, Michael
2014-12-17 13:35           ` Jay Rolette

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).