Skip to contentSkip to conversation

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

PATCH Superseded Leno Hou 3 participants 5 messages Apr 11, 2017 – Apr 28, 2017 1 message not in the archive Library code

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Leno Hou

author
#0 lore raw

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

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

---
 lib/btree.c | 41 +++++++++++++++++------------------------
 1 file changed, 17 insertions(+), 24 deletions(-)
lib/btree.c +17 -24
index f93a945..87d690f 100644
@@ -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 */
Signature · 1 line
1.8.3.1
#1 lore raw
Quoted 2 lines · Leno Hou

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?

A message that is not in the archive (sent off-list or not yet received): CAGQVrL_2EanSVKkMEP_fBaeWSwu=tZYSq79nzOy-wXQ9m1WOuQ@mail.gmail.com

#3 lore raw
Quoted 8 lines · Leno Hou

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.

author
#4 lore raw
Quoted 9 lines · Christoph Hellwig
Quoted 5 lines · Leno Hou

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.

Quoted 7 lines
Quoted 3 lines

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

#5 lore raw
In reply to Leno Hou
Quoted 2 lines · Leno Hou

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,

lib/btree.c static int keyzero(struct btree_geo *geo, unsigned long *key) · line 244

Quoted 5 lines
lib/btree.c +4 -0
+static int getpos(struct btree_geo *geo, unsigned long *node,
+               unsigned long *key)
+{
 
+       int i;

unsigned int i;

lib/btree.c static int keyzero(struct btree_geo *geo, unsigned long *key) · line 248

Quoted 5 lines
lib/btree.c +4 -0
+
+       for (i = 0; i < geo->no_pairs; i++) {
+               if (keycmp(geo, node, i, key) <= 0)
 
+                       break;

Here you return directly
return i;

lib/btree.c static int keyzero(struct btree_geo *geo, unsigned long *key) · line 250

Quoted 3 lines
lib/btree.c +2 -0
+       }
 
+       return i;

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

return -ENOENT;

lib/btree.c void *btree_lookup(struct btree_head *head, struct btree_geo *geo, · line 266

Quoted 10 lines
lib/btree.c +2 -3
+}
 
        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.

Signature · 2 lines
With Best Regards,
Andy Shevchenko