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

Groups > linux.kernel > #1252815 > unrolled thread

[PATCH] regmap: rbtree: When adding a reg do a bsearch for target node

Back to article view | Back to linux.kernel

Contents

  [PATCH] regmap: rbtree: When adding a reg do a bsearch for target node Nikesh Oswal <nikesh@opensource.wolfsonmicro.com> - 2015-10-21 15:30 +0200
    Re: [PATCH] regmap: rbtree: When adding a reg do a bsearch for  target node Charles Keepax <ckeepax@opensource.wolfsonmicro.com> - 2015-10-22 11:10 +0200

#1252815 — [PATCH] regmap: rbtree: When adding a reg do a bsearch for target node

From: Nikesh Oswal <Nikesh.Oswal@wolfsonmicro.com>

A binary search is much more efficient rather than iterating
over the rbtree in ascending order which the current code is
doing.

During initialisation the reg defaults are written to the
cache in a large chunk and these are always sorted in the
ascending order so for this situation ideally we should have
iterated the rbtree in descending order.

But at runtime the drivers may write into the cache in any
random order so this patch selects to use a bsearch to give
an optimal runtime performance and also at initialisation
time when reg defaults are written the performance of binary
search would be much better than iterating in ascending order
which the current code was doing.
  
Signed-off-by: Nikesh Oswal <Nikesh.Oswal@wolfsonmicro.com>
---
 drivers/base/regmap/regcache-rbtree.c |    9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/drivers/base/regmap/regcache-rbtree.c b/drivers/base/regmap/regcache-rbtree.c
index 56486d9..353f602 100644
--- a/drivers/base/regmap/regcache-rbtree.c
+++ b/drivers/base/regmap/regcache-rbtree.c
@@ -413,8 +413,8 @@ static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
 		max = reg + max_dist;
 
 		/* look for an adjacent register to the one we are about to add */
-		for (node = rb_first(&rbtree_ctx->root); node;
-		     node = rb_next(node)) {
+		node = rbtree_ctx->root.rb_node;
+		while (node) {
 			rbnode_tmp = rb_entry(node, struct regcache_rbtree_node,
 					      node);
 
@@ -425,6 +425,11 @@ static int regcache_rbtree_write(struct regmap *map, unsigned int reg,
 				new_base_reg = min(reg, base_reg);
 				new_top_reg = max(reg, top_reg);
 			} else {
+				if (max < base_reg)
+					node = node->rb_left;
+				else
+					node = node->rb_right;
+
 				continue;
 			}
 
-- 
1.7.9.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1253604 — Re: [PATCH] regmap: rbtree: When adding a reg do a bsearch for target node

On Wed, Oct 21, 2015 at 02:16:14PM +0100, Nikesh Oswal wrote:
> From: Nikesh Oswal <Nikesh.Oswal@wolfsonmicro.com>

If you are going to use your non-opensource email, might as well
use the cirrus one here.

> 
> A binary search is much more efficient rather than iterating
> over the rbtree in ascending order which the current code is
> doing.
> 
> During initialisation the reg defaults are written to the
> cache in a large chunk and these are always sorted in the
> ascending order so for this situation ideally we should have
> iterated the rbtree in descending order.
> 
> But at runtime the drivers may write into the cache in any
> random order so this patch selects to use a bsearch to give
> an optimal runtime performance and also at initialisation
> time when reg defaults are written the performance of binary
> search would be much better than iterating in ascending order
> which the current code was doing.
>   
> Signed-off-by: Nikesh Oswal <Nikesh.Oswal@wolfsonmicro.com>
> ---

Patch looks fine to me though:

Reviewed-by: Charles Keepax <ckeepax@opensource.wolfsonmicro.com>

Thanks,
Charles
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web