Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1620957 > unrolled thread

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

Back to article view | Back to linux.kernel

Contents

  [PATCH v1]] lib/btree.c: optimise the code by previously getpos function Leno Hou <lenohou@gmail.com> - 2017-04-11 09:00 +0200
    Re: [PATCH v1]] lib/btree.c: optimise the code by previously getpos  function Christoph Hellwig <hch@infradead.org> - 2017-04-11 18:30 +0200
      Re: [PATCH v1]] lib/btree.c: optimise the code by previously getpos  function Christoph Hellwig <hch@infradead.org> - 2017-04-12 19:40 +0200
        Re: [PATCH v1]] lib/btree.c: optimise the code by previously getpos  function Leno Hou <lenohou@gmail.com> - 2017-04-19 16:50 +0200

#1620957 — [PATCH v1]] 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.

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

[toc] | [next] | [standalone]

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

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?

[toc] | [prev] | [next] | [standalone]

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

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.

[toc] | [prev] | [next] | [standalone]

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

> 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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web