[ltt-dev] [PATCH 9/9] rculfhash: compare hash value before call compare_fct()

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 10/14/2011 10:31 PM, Mathieu Desnoyers wrote:
> > * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> >> On 10/11/2011 09:23 AM, Lai Jiangshan wrote:
> >>> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >>> ---
> >>>  rculfhash.c |    2 ++
> >>>  1 files changed, 2 insertions(+), 0 deletions(-)
> >>>
> >>> diff --git a/rculfhash.c b/rculfhash.c
> >>> index eca3a4e..71ef411 100644
> >>> --- a/rculfhash.c
> >>> +++ b/rculfhash.c
> >>> @@ -880,6 +880,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> >>>  				goto gc_node;
> >>>  			if ((mode == ADD_UNIQUE || mode == ADD_REPLACE)
> >>>  			    && !is_dummy(next)
> >>> +			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash
> >>>  			    && !ht->compare_fct(node->key, node->key_len,
> >>>  						clear_flag(iter)->key,
> >>>  						clear_flag(iter)->key_len)) {
> >>> @@ -1329,6 +1330,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> >>>  		next = rcu_dereference(node->p.next);
> >>>  		if (likely(!is_removed(next))
> >>>  		    && !is_dummy(next)
> >>> +		    && clear_flag(next)->p.reverse_hash == reverse_hash
> >>>  		    && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
> >>>  				break;
> >>>  		}
> >>
> >>
> >> Sorry, This patch is :
> >>
> >> commit 78c543f6fa15045a465f78e7c7ef9086e4fe8b03
> >> Author: Lai Jiangshan <laijs at cn.fujitsu.com>
> >> Date:   Mon Oct 10 21:55:00 2011 +0800
> >>
> >>     compare hash value before call compare_fct()
> >>     
> >>     Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> >>
> >> diff --git a/rculfhash.c b/rculfhash.c
> >> index eca3a4e..3ded228 100644
> >> --- a/rculfhash.c
> >> +++ b/rculfhash.c
> >> @@ -880,6 +880,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
> >>  				goto gc_node;
> >>  			if ((mode == ADD_UNIQUE || mode == ADD_REPLACE)
> >>  			    && !is_dummy(next)
> >> +			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash
> >>  			    && !ht->compare_fct(node->key, node->key_len,
> >>  						clear_flag(iter)->key,
> >>  						clear_flag(iter)->key_len)) {
> >> @@ -1329,6 +1330,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
> >>  		next = rcu_dereference(node->p.next);
> >>  		if (likely(!is_removed(next))
> >>  		    && !is_dummy(next)
> >> +		    && clear_flag(node)->p.reverse_hash == reverse_hash
> > 
> > this takes care of the next -> node concern. Can you respin this patch
> > taking care of cds_lfht_next_duplicate() too ? Thanks!
> 
> cds_lfht_next_duplicate() don't need such test.

Good point. We are already checking if node->p.reverse_hash >
reverse_hash from a node which has a known reverse hash starting point,
and return NULL as soon as the reverse hash value changes.

Merged as:


commit ae450da3b54fe3c8ea8fc92ec9a9ce2ad8f131cb
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Mon Oct 17 10:26:58 2011 -0400

    compare hash value before call compare_fct()
    
    [ Edit by Mathieu Desnoyers:
    
      This is an optimisation that checks if the reverse hash value is
      equal before calling the comparison function. Given comparing a
      reverse hash is much faster than comparison, this accelarates the
      lookups and add. ]
    
    Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

diff --git a/rculfhash.c b/rculfhash.c
index 189f8c8..6e07878 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -892,6 +892,7 @@ struct cds_lfht_node *_cds_lfht_add(struct cds_lfht *ht,
 				goto gc_node;
 			if ((mode == ADD_UNIQUE || mode == ADD_REPLACE)
 			    && !is_dummy(next)
+			    && clear_flag(iter)->p.reverse_hash == node->p.reverse_hash
 			    && !ht->compare_fct(node->key, node->key_len,
 						clear_flag(iter)->key,
 						clear_flag(iter)->key_len)) {
@@ -1341,6 +1342,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, void *key, size_t key_len,
 		next = rcu_dereference(node->p.next);
 		if (likely(!is_removed(next))
 		    && !is_dummy(next)
+		    && clear_flag(node)->p.reverse_hash == reverse_hash
 		    && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
 				break;
 		}


> 
> Thanks
> Lai
> 
> > 
> > Mathieu
> > 
> >>  		    && likely(!ht->compare_fct(node->key, node->key_len, key, key_len))) {
> >>  				break;
> >>  		}
> > 
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com