Re: [PATCH 3/4] f2fs: use find_next_bit_le rather than test_bit_le in, find_in_block

[Gu Zheng <guz.fnst@cn.fujitsu.com>]

[-- Attachment #1: Type: text/plain, Size: 4627 bytes --]

Hi Yu,
Thanks.
On 07/04/2014 02:21 PM, Chao Yu wrote:

> Hi Jaegeuk, Gu, Changman
> 
>> -----Original Message-----
>> From: Jaegeuk Kim [mailto:jaegeuk@kernel.org]
>> Sent: Friday, July 04, 2014 1:36 PM
>> To: Gu Zheng
>> Cc: f2fs; fsdevel; 이창만; 俞
>> Subject: Re: [PATCH 3/4] f2fs: use find_next_bit_le rather than test_bit_le in, find_in_block
>>
>> Well, how about testing with many ones in the bit streams?
>> Thanks,
>>
>> On Thu, Jul 03, 2014 at 06:14:02PM +0800, Gu Zheng wrote:
>>> Hi Jaegeuk, Changman
>>>
>>> Just a simple test, not very sure it can address
>>> our qualm.
>>>
>>> Bitmap size:216(the same as f2fs dentry_bits).
>>> CPU: Intel i5 x86_64.
>>>
>>> Time counting based on tsc(the less the fast).
>>> [Index of 1]	find_next_bit_le	test_bit_le
>>> 0		20			117
>>> 1		20			114
>>> 2		20			113
>>> 3		20			139
>>> 4		22			121
>>> 5		22			118
>>> 6		22			115
>>> 8		22			112
>>> 9		22			106
>>> 10		22			105
>>> 11		22			100
>>> 16		22			98
>>> 48		22			97
>>> 80		27			95
>>> 104		27			92
>>> 136		32			95
>>> 160		32			92
>>> 184		32			90
>>> 200		27			87
>>> 208		35			84
>>>
>>> According to the result, find_next_bit_le is always
>>> better than test_bit_le, though there may be some
>>> noise, but I think the result is clear.
>>> Hope it can help us.:)
>>> ps.The sample is attached too.
>>>
>>> Thanks,
>>> Gu
> 
> I hope this could provide some help for this patch.
> 
> I modify Gu's code like this, and add few test case:
> 
> static void test_bit_search_speed(void)
> {
> 	unsigned long flags;
> 	uint64_t tsc_s_b1, tsc_s_e1, tsc_s_b2, tsc_s_e2;
> 	int i, j, pos;
> 	const void *bit_addr;
> 
> 	local_irq_save(flags);
> 	preempt_disable();
> 	
> 	printk("find_next_bit	test_bit_le\n");
> 
> 	for (i = 0; i < 24; i++) {
> 
> 		bit_addr = &bitmaps[i];
> 
> 		tsc_s_b1 = rdtsc();
> 
> 		for (j = 0, pos = 0; j < 1000; j++, pos = 0)
> 			while (pos < 216)
> 				pos = find_next_bit_le(bit_addr, 216, pos) + 1;
> 
> 		mb();
> 		tsc_s_e1 = rdtsc();
> 		tsc_s_e1 -= tsc_s_b1;
> 		do_div(tsc_s_e1, 1000);
> 
> 		tsc_s_b2 = rdtsc();
> 
> 		for (j = 0, pos = 0; j < 1000; j++, pos = 0)
> 			while (pos < 216)
> 				test_bit_le(pos++, bit_addr);
> 
> 		mb();
> 		tsc_s_e2 = rdtsc();
> 		tsc_s_e2 -= tsc_s_b2;
> 		do_div(tsc_s_e2, 1000);
> 
> 		printk("%-16llu %-16llu\n", tsc_s_e1, tsc_s_e2);
> 	}
> 
> 	preempt_enable();
> 	local_irq_restore(flags);
> }
> case: 11111111 11111111
> 		{255, 255, 255, 255, 255, 255, 255,
> 		 255, 255, 255, 255, 255, 255, 255,
> 		 255, 255, 255, 255, 255, 255, 255,
> 		 255, 255, 255, 255, 255, 255},
> case: 10101010 10101010
> 		{170, 170, 170, 170, 170, 170, 170,
> 		 170, 170, 170, 170, 170, 170, 170,
> 		 170, 170, 170, 170, 170, 170, 170,
> 		 170, 170, 170, 170, 170, 170},
> case: 11111111 00000000
> 		{255, 0, 255, 0, 255, 0, 255,
> 		 0, 255, 0, 255, 0, 255, 0,
> 		 255, 0, 255, 0, 255, 0, 255,
> 		 0, 255, 0, 255, 0, 255},
> case: 00001111 00001111
> 		 {15, 15, 15, 15, 15, 15, 15,
> 		 15, 15, 15, 15, 15, 15, 15,
> 		 15, 15, 15, 15, 15, 15, 15,
> 		 15, 15, 15, 15, 15, 15}
> 
> and here are test result in my env. (Ubuntu vm, 768MB, i3-3220)
> It seems find_next_bit works not so bad as I thought.
> 
> find_next_bit    test_bit_le
> 73               4209
> 62               1271
> 69               1585
> 50               2031
> 67               2255
> 82               2261
> 52               4007
> 79               2159
> 50               2043
> 55               2215
> 53               2393
> 72               3784
> 76               1879
> 61               2562
> 70               2702
> 62               2489
> 56               2307
> 54               2063
> 51               2258
> 69               2712
> 4133             3989  -- case: 11111111 11111111
> 2370             3024  -- case: 10101010 10101010
> 2608             2413  -- case: 11111111 00000000
> 2457             2506  -- case: 00001111 00001111

The time cost of test_bit_le shakes violently, it should be
very smooth according to the test case, maybe it has relation
to your vm env.

To Jaegeuk,
Following test result is walking a bitmap via find_next_bit_le
and test_bit_le.
(Front 7 are random bitmaps, last four are cases from Yu, see
attached sample for detail):

find_next_bit_le    test_bit_le

     3615                3492 
     2640                3492 
     2431                3492 
     1957                3494 
     2160                3492 
     1933                3495 
     1096                3492 

     8078                3492 
     3732                3492 
     4237                3493 
     3824                3492

Thanks,
Gu 

> 
> .
> 



[-- Attachment #2: bit_test_mod.c --]
[-- Type: text/plain, Size: 2493 bytes --]

#include <linux/module.h>

__u8 bitmaps[11][27] = {
		{1, 123, 2, 3, 127, 200, 100,
		 123, 23, 13, 78, 42, 123, 50,
		 123, 56, 198, 0, 58, 22, 19,
		 123, 23, 13, 78, 42, 123},
		{2, 0, 0, 0, 0, 0, 0,
		 123, 23, 13, 78, 42, 123, 50,
		 123, 56, 198, 0, 58, 22, 19,
		 23, 123, 2, 34, 123, 12},
		{4, 0, 0, 0, 0, 0, 0,
		 123, 56, 198, 0, 58, 22, 19,
		 123, 23, 13, 78, 42, 123,
		 0, 0, 0, 34, 45, 29},
		{8, 0, 0, 0, 0, 0, 0,
		 1, 123, 2, 3, 127, 200, 100,
		 123, 23, 13, 78, 42, 123, 50,
		 0, 0, 0, 0, 0, 0},
		{16, 0, 0, 0, 0, 0, 0,
		 8, 78, 0, 0, 23, 0, 213,
		 0, 12, 0, 45, 0, 109, 111,
		 231, 11, 11, 88, 77, 99},
		{32, 0, 0, 0, 0, 0, 0,
		 8, 78, 0, 0, 23, 0, 213,
		 0, 12, 0, 45, 0, 109, 111,
		 231, 11, 11, 88, 77, 99},
		{64, 0, 0, 0, 0, 0, 0,
		 8, 78, 0, 0, 23, 0, 213,
		 0, 12, 0, 45, 0, 109, 111,
		 0, 0, 0, 0, 0, 0},
		{255, 255, 255, 255, 255, 255, 255,
		 255, 255, 255, 255, 255, 255, 255,
		 255, 255, 255, 255, 255, 255, 255,
		 255, 255, 255, 255, 255, 255},
		{170, 170, 170, 170, 170, 170, 170,
		 170, 170, 170, 170, 170, 170, 170,
		 170, 170, 170, 170, 170, 170, 170,
		 170, 170, 170, 170, 170, 170},
		{255, 0, 255, 0, 255, 0, 255,
		 0, 255, 0, 255, 0, 255, 0,
		 255, 0, 255, 0, 255, 0, 255,
		 0, 255, 0, 255, 0, 255},
		 {15, 15, 15, 15, 15, 15, 15,
		 15, 15, 15, 15, 15, 15, 15,
		 15, 15, 15, 15, 15, 15, 15,
		 15, 15, 15, 15, 15, 15}
		};

uint64_t rdtsc(void) {
uint32_t lo, hi;
__asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
return (uint64_t)hi << 32 | lo;
}

static void test_bit_search_speed(void)
{
	unsigned long flags;
	uint64_t tsc_s, tsc_diff;
	int i, j, pos;
	const void *bit_addr;

	local_irq_save(flags);
	preempt_disable();

	printk("find_next_bit_le    test_bit_le\n");

	for (i = 0; i < 11; i++) {
		bit_addr = &bitmaps[i];

		pos = 0;
		tsc_s = rdtsc();

		for (j = 0; j < 1000; j++, pos = 0)
			while (pos < 216)
				pos = find_next_bit_le(bit_addr, 216, pos) + 1;
		mb();
		tsc_diff = (rdtsc() - tsc_s)/1000;

		printk("%8llu", tsc_diff);

		pos = 0;
		tsc_s = rdtsc();

		for (j = 0; j < 1000; j++, pos = 0)
			while (pos < 216)
				test_bit_le(pos++, bit_addr);

		mb();
		tsc_diff = (rdtsc() - tsc_s)/1000;

		printk("%20llu \n", tsc_diff);
	}

	preempt_enable();
	local_irq_restore(flags);
}

static int __init start_test(void) {
	test_bit_search_speed();
	return 0;
}

static void __exit exit_test(void) {

}

module_init(start_test);
module_exit(exit_test);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Gu Zheng");