• Yury Norov's avatar
    lib: find_*_bit reimplementation · 2c57a0e2
    Yury Norov authored
    This patchset does rework to find_bit function family to achieve better
    performance, and decrease size of text.  All rework is done in patch 1.
    Patches 2 and 3 are about code moving and renaming.
    
    It was boot-tested on x86_64 and MIPS (big-endian) machines.
    Performance tests were ran on userspace with code like this:
    
    	/* addr[] is filled from /dev/urandom */
    	start = clock();
    	while (ret < nbits)
    		ret = find_next_bit(addr, nbits, ret + 1);
    
    	end = clock();
    	printf("%ld\t", (unsigned long) end - start);
    
    On Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz measurements are: (for
    find_next_bit, nbits is 8M, for find_first_bit - 80K)
    
    	find_next_bit:		find_first_bit:
    	new	current		new	current
    	26932	43151		14777	14925
    	26947	43182		14521	15423
    	26507	43824		15053	14705
    	27329	43759		14473	14777
    	26895	43367		14847	15023
    	26990	43693		15103	15163
    	26775	43299		15067	15232
    	27282	42752		14544	15121
    	27504	43088		14644	14858
    	26761	43856		14699	15193
    	26692	43075		14781	14681
    	27137	42969		14451	15061
    	...			...
    
    find_next_bit performance gain is 35-40%;
    find_first_bit - no measurable difference.
    
    On ARM machine, there is arch-specific implementation for find_bit.
    
    Thanks a lot to George Spelvin and Rasmus Villemoes for hints and
    helpful discussions.
    
    This patch (of 3):
    
    New implementations takes less space in source file (see diffstat) and in
    object.  For me it's 710 vs 453 bytes of text.  It also shows better
    performance.
    
    find_last_bit description fixed due to obvious typo.
    
    [akpm@linux-foundation.org: include linux/bitmap.h, per Rasmus]
    Signed-off-by: default avatarYury Norov <yury.norov@gmail.com>
    Reviewed-by: default avatarRasmus Villemoes <linux@rasmusvillemoes.dk>
    Reviewed-by: default avatarGeorge Spelvin <linux@horizon.com>
    Cc: Alexey Klimov <klimov.linux@gmail.com>
    Cc: David S. Miller <davem@davemloft.net>
    Cc: Daniel Borkmann <dborkman@redhat.com>
    Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
    Cc: Lai Jiangshan <laijs@cn.fujitsu.com>
    Cc: Mark Salter <msalter@redhat.com>
    Cc: AKASHI Takahiro <takahiro.akashi@linaro.org>
    Cc: Thomas Graf <tgraf@suug.ch>
    Cc: Valentin Rothberg <valentinrothberg@gmail.com>
    Cc: Chris Wilson <chris@chris-wilson.co.uk>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    2c57a0e2
find_last_bit.c 1.05 KB