diff mbox

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

Message ID 1418823077-9129-1-git-send-email-rolette@infiniteio.com (mailing list archive)
State Changes Requested, archived
Headers show

Commit Message

Jay Rolette Dec. 17, 2014, 1:31 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

Thomas Monjalon Dec. 17, 2014, 2:27 p.m. UTC | #1
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.
Jay Rolette Dec. 17, 2014, 3:07 p.m. UTC | #2
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
Bruce Richardson Dec. 17, 2014, 3:27 p.m. UTC | #3
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
Sergio Gonzalez Monroy Sept. 9, 2015, 10:35 a.m. UTC | #4
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
Jay Rolette Sept. 10, 2015, 11:49 a.m. UTC | #5
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
>
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;
 }