[ltt-dev] [PATCH 8/9] rculfhash: simplify get_count_order()

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>

Merged with edit:

commit 920f8ef668b03c65ca414bd6d53db314da920d1f
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date:   Fri Oct 14 09:59:42 2011 -0500

    rculfhash: simplify get_count_order()
    
    [ Edit by Mathieu Desnoyers:
    
    - Updated comments.
    - Quick benchmark on Intel(R) Atom(TM) CPU Z520   @ 1.33GHz:
    
    get_count_order_ulong, from 0 to 100000000:
    
    previous:  3.840s
    new:       3.187s
    
    - Test comparing bit-exactness for ranges near 0:
    
    /*
     * fls: returns the position of the most significant bit.
     * Returns 0 if no bit is set, else returns the position of the most
     * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
     */
    static inline
    unsigned int fls_u32(uint32_t x)
    {
    	int r;
    
    	asm("bsrl %1,%0\n\t"
    	    "jnz 1f\n\t"
    	    "movl $-1,%0\n\t"
    	    "1:\n\t"
    	    : "=r" (r) : "rm" (x));
    	return r + 1;
    }
    
    static inline
    unsigned int fls_u64(uint64_t x)
    {
    	long r;
    
    	asm("bsrq %1,%0\n\t"
    	    "jnz 1f\n\t"
    	    "movq $-1,%0\n\t"
    	    "1:\n\t"
    	    : "=r" (r) : "rm" (x));
    	return r + 1;
    }
    
    static __attribute__((unused))
    unsigned int fls_u64(uint64_t x)
    {
    	unsigned int r = 64;
    
    	if (!x)
    		return 0;
    
    	if (!(x & 0xFFFFFFFF00000000ULL)) {
    		x <<= 32;
    		r -= 32;
    	}
    	if (!(x & 0xFFFF000000000000ULL)) {
    		x <<= 16;
    		r -= 16;
    	}
    	if (!(x & 0xFF00000000000000ULL)) {
    		x <<= 8;
    		r -= 8;
    	}
    	if (!(x & 0xF000000000000000ULL)) {
    		x <<= 4;
    		r -= 4;
    	}
    	if (!(x & 0xC000000000000000ULL)) {
    		x <<= 2;
    		r -= 2;
    	}
    	if (!(x & 0x8000000000000000ULL)) {
    		x <<= 1;
    		r -= 1;
    	}
    	return r;
    }
    
    static __attribute__((unused))
    unsigned int fls_u32(uint32_t x)
    {
    	unsigned int r = 32;
    
    	if (!x)
    		return 0;
    	if (!(x & 0xFFFF0000U)) {
    		x <<= 16;
    		r -= 16;
    	}
    	if (!(x & 0xFF000000U)) {
    		x <<= 8;
    		r -= 8;
    	}
    	if (!(x & 0xF0000000U)) {
    		x <<= 4;
    		r -= 4;
    	}
    	if (!(x & 0xC0000000U)) {
    		x <<= 2;
    		r -= 2;
    	}
    	if (!(x & 0x80000000U)) {
    		x <<= 1;
    		r -= 1;
    	}
    	return r;
    }
    
    unsigned int fls_ulong(unsigned long x)
    {
    	return fls_u32(x);
    	return fls_u64(x);
    }
    
    int get_count_order_u32(uint32_t x)
    {
    	int order;
    
    	order = fls_u32(x) - 1;
    	if (x & (x - 1))
    		order++;
    	return order;
    }
    
    int get_count_order_ulong(unsigned long x)
    {
    	int order;
    
    	order = fls_ulong(x) - 1;
    	if (x & (x - 1))
    		order++;
    	return order;
    }
    
    int test_get_count_order_u32(uint32_t x)
    {
    	if (!x)
    		return -1;
    	return fls_u32(x - 1);
    }
    
    /* find the minimum order that x <= (1UL << order) */
    int test_get_count_order_ulong(unsigned long x)
    {
    	if (!x)
    		return -1;
    	return fls_ulong(x - 1);
    }
    
    int main(int argc, char **argv)
    {
    	unsigned long i;
    
    	for (i = 0UL; i < 10000; i++) {
    		if (get_count_order_ulong(i) != test_get_count_order_ulong(i))
    			printf("Error for %lu\n", i);
    	}
    
    	for (i = 4294967293UL; i != 0; i++) {
    		if (get_count_order_ulong(i) != test_get_count_order_ulong(i))
    			printf("Error for %lu\n", i);
    	}
    
    	return 0;
    }
    
    ]
    
    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 cf822fc..fe8beed 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -446,24 +446,28 @@ unsigned int fls_ulong(unsigned long x)
 #endif
 }
 
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
 int get_count_order_u32(uint32_t x)
 {
-	int order;
+	if (!x)
+		return -1;
 
-	order = fls_u32(x) - 1;
-	if (x & (x - 1))
-		order++;
-	return order;
+	return fls_u32(x - 1);
 }
 
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
 int get_count_order_ulong(unsigned long x)
 {
-	int order;
+	if (!x)
+		return -1;
 
-	order = fls_ulong(x) - 1;
-	if (x & (x - 1))
-		order++;
-	return order;
+	return fls_ulong(x - 1);
 }
 
 #ifdef POISON_FREE


> ---
>  rculfhash.c |   18 ++++++++----------
>  1 files changed, 8 insertions(+), 10 deletions(-)
> 
> diff --git a/rculfhash.c b/rculfhash.c
> index 7b880d7..eca3a4e 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -445,24 +445,22 @@ unsigned int fls_ulong(unsigned long x)
>  #endif
>  }
>  
> +/* find the minimum order that x <= (1UL << order) */
>  int get_count_order_u32(uint32_t x)
>  {
> -	int order;
> +	if (!x)
> +		return -1;
>  
> -	order = fls_u32(x) - 1;
> -	if (x & (x - 1))
> -		order++;
> -	return order;
> +	return fls_u32(x - 1);
>  }
>  
> +/* find the minimum order that x <= (1UL << order) */
>  int get_count_order_ulong(unsigned long x)
>  {
> -	int order;
> +	if (!x)
> +		return -1;
>  
> -	order = fls_ulong(x) - 1;
> -	if (x & (x - 1))
> -		order++;
> -	return order;
> +	return fls_ulong(x - 1);
>  }
>  
>  #ifdef POISON_FREE
> -- 
> 1.7.4.4
> 

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