[PATCH v1]] lib/btree.c: optimise the code by previously getpos function

[PATCH v1]] lib/btree.c: optimise the code by previously getpos function

[Leno Hou]

This patch optimized the code by previously getpos function call.
Therefore, It's takes the convenience to understand logic of code.

Signed-off-by: Leno Hou <lenohou@gmail.com>
---
 lib/btree.c | 41 +++++++++++++++++------------------------
 1 file changed, 17 insertions(+), 24 deletions(-)

diff --git a/lib/btree.c b/lib/btree.c
index f93a945..87d690f 100644
--- a/lib/btree.c
+++ b/lib/btree.c
@@ -238,6 +238,19 @@ static int keyzero(struct btree_geo *geo, unsigned long *key)
 	return 1;
 }
 
+static int getpos(struct btree_geo *geo, unsigned long *node,
+		unsigned long *key)
+{
+	int i;
+
+	for (i = 0; i < geo->no_pairs; i++) {
+		if (keycmp(geo, node, i, key) <= 0)
+			break;
+	}
+	return i;
+}
+
+
 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
 		unsigned long *key)
 {
@@ -248,9 +261,7 @@ void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
 		return NULL;
 
 	for ( ; height > 1; height--) {
-		for (i = 0; i < geo->no_pairs; i++)
-			if (keycmp(geo, node, i, key) <= 0)
-				break;
+		i = getpos(geo, node, key);
 		if (i == geo->no_pairs)
 			return NULL;
 		node = bval(geo, node, i);
@@ -278,9 +289,7 @@ int btree_update(struct btree_head *head, struct btree_geo *geo,
 		return -ENOENT;
 
 	for ( ; height > 1; height--) {
-		for (i = 0; i < geo->no_pairs; i++)
-			if (keycmp(geo, node, i, key) <= 0)
-				break;
+		i = getpos(geo, node, key);
 		if (i == geo->no_pairs)
 			return -ENOENT;
 		node = bval(geo, node, i);
@@ -326,9 +335,7 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
 
 	node = head->node;
 	for (height = head->height ; height > 1; height--) {
-		for (i = 0; i < geo->no_pairs; i++)
-			if (keycmp(geo, node, i, key) <= 0)
-				break;
+		i = getpos(geo, node, key);
 		if (i == geo->no_pairs)
 			goto miss;
 		oldnode = node;
@@ -360,18 +367,6 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
 }
 EXPORT_SYMBOL_GPL(btree_get_prev);
 
-static int getpos(struct btree_geo *geo, unsigned long *node,
-		unsigned long *key)
-{
-	int i;
-
-	for (i = 0; i < geo->no_pairs; i++) {
-		if (keycmp(geo, node, i, key) <= 0)
-			break;
-	}
-	return i;
-}
-
 static int getfill(struct btree_geo *geo, unsigned long *node, int start)
 {
 	int i;
@@ -392,9 +387,7 @@ static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
 	int i, height;
 
 	for (height = head->height; height > level; height--) {
-		for (i = 0; i < geo->no_pairs; i++)
-			if (keycmp(geo, node, i, key) <= 0)
-				break;
+		i = getpos(geo, node, key);
 
 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {
 			/* right-most key is too large, update it */
-- 
1.8.3.1

Re: [PATCH v1]] lib/btree.c: optimise the code by previously getpos function

[Christoph Hellwig]

On Tue, Apr 11, 2017 at 02:53:56AM -0400, Leno Hou wrote:
> This patch optimized the code by previously getpos function call.
> Therefore, It's takes the convenience to understand logic of code.

How did you test this change?

Re: [PATCH v1]] lib/btree.c: optimise the code by previously getpos function

[Christoph Hellwig]

On Wed, Apr 12, 2017 at 06:03:10PM +0800, Leno Hou wrote:
> 1. Actually, this is cleanup of the code to human being read but not
> optimize. And When I compiled the kernel
>     and checked with object code . It proved as same as before. So it's no
> need to test this change.
> 
> 2. This Simple B+ Tree in Memory was used by SCSI driver QLA2XXX. so it
> would be better to merge this
>    cleanup for future optimize. Thanks.

If you care about the btree code a good first step would be to write a
test suite instead of micro-optimizing it out of the blue without
actually being able to test it.

Re: [PATCH v1]] lib/btree.c: optimise the code by previously getpos function

[Leno Hou]

> On 13 Apr 2017, at 1:32 AM, Christoph Hellwig <hch@infradead.org> wrote:
> 
> On Wed, Apr 12, 2017 at 06:03:10PM +0800, Leno Hou wrote:
>> 1. Actually, this is cleanup of the code to human being read but not
>> optimize. And When I compiled the kernel
>>    and checked with object code . It proved as same as before. So it's no
>> need to test this change.
>> 
>> 2. This Simple B+ Tree in Memory was used by SCSI driver QLA2XXX. so it
>> would be better to merge this
>>   cleanup for future optimize. Thanks.
> 
> If you care about the btree code a good first step would be to write a
> test suite instead of micro-optimizing it out of the blue without
> actually being able to test it.

OK. Thanks Christoph, I’m the newbie of kernel developer and will take more
time to search how to write test suite to prove that was optimized.

-Leno Hou

Re: [PATCH v1]] lib/btree.c: optimise the code by previously getpos function

[Andy Shevchenko]

On Tue, Apr 11, 2017 at 9:53 AM, Leno Hou <lenohou@gmail.com> wrote:
> This patch optimized the code by previously getpos function call.
> Therefore, It's takes the convenience to understand logic of code.

Besides what Christoph told you (I agree with him, writing test suites
/ modules is quite good exercise for newbies) my 2 cents for below
code that you may consider in the future as a technique of cleaning
up,

> +static int getpos(struct btree_geo *geo, unsigned long *node,
> +               unsigned long *key)
> +{

> +       int i;

unsigned int i;

> +
> +       for (i = 0; i < geo->no_pairs; i++) {
> +               if (keycmp(geo, node, i, key) <= 0)

> +                       break;

Here you return directly
return i;

> +       }

> +       return i;

And here is the best to return negative error code instead, like

return -ENOENT;

> +}

>         for ( ; height > 1; height--) {
> -               for (i = 0; i < geo->no_pairs; i++)
> -                       if (keycmp(geo, node, i, key) <= 0)
> -                               break;

> +               i = getpos(geo, node, key);
>                 if (i == geo->no_pairs)
>                         return NULL;

Taking above into consideration you may do

        i = getpos(geo, node, key);
        if (i < 0)
          return NULL;

Rationale behind that:
1) getpos() return value may be directly used whenever we need return
code to return;
2) you hide implementation details in your helper function
(geo->no_pairs dereference).

Though here both of them kinda minors you may use such technique in
the future for more complex code.

-- 
With Best Regards,
Andy Shevchenko