f2fs: use find_next_bit_le rather than test_bit_le in, find_in_block

-----Original Message-----
From: Gu Zheng [mailto:[email protected]]
Sent: Tuesday, June 24, 2014 6:21 PM
To: Jaegeuk Kim
Cc: fsdevel; f2fs
Subject: [f2fs-dev] [PATCH 3/4] f2fs: use find_next_bit_le rather than test_bit_le in, find_in_block

Use find_next_bit_le rather than test_bit_le to improve search speed lightly.

Signed-off-by Gu Zheng <[email protected]>

---
 fs/f2fs/dir.c |   43 +++++++++++++++++++++----------------------
 1 files changed, 21 insertions(+), 22 deletions(-)

fs/f2fs/dir.c +2 -11

index 3edd561..ba510fb 100644
@@ -93,42 +93,41 @@ static struct f2fs_dir_entry *find_in_block(struct page *dentry_page,
 			const char *name, size_t namelen, int *max_slots,
 			f2fs_hash_t namehash, struct page **res_page)
 {
-	struct f2fs_dir_entry *de;
-	unsigned long bit_pos = 0;
+	unsigned long bit_pos = 0, bit_start = 0;
 	struct f2fs_dentry_block *dentry_blk = kmap(dentry_page);
 	const void *dentry_bits = &dentry_blk->dentry_bitmap;
-	int max_len = 0;
 
-	while (bit_pos < NR_DENTRY_IN_BLOCK) {
-		if (!test_bit_le(bit_pos, dentry_bits)) {
-			if (bit_pos == 0)
-				max_len = 1;
-			else if (!test_bit_le(bit_pos - 1, dentry_bits))
-				max_len++;
-			bit_pos++;
-			continue;
+	while (bit_start < NR_DENTRY_IN_BLOCK) {

fs/f2fs/dir.c +9 -12

 		}
+
+		if (bit_pos >= NR_DENTRY_IN_BLOCK)
+			break;
+
 		de = &dentry_blk->dentry[bit_pos];
 		if (early_match_name(name, namelen, namehash, de)) {
 			if (!memcmp(dentry_blk->filename[bit_pos],
 							name, namelen)) {
 				*res_page = dentry_page;
-				goto found;
+				return de;
 			}
 		}
-		if (max_len > *max_slots) {
-			*max_slots = max_len;
-			max_len = 0;
-		}
-		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
+
+		bit_start = bit_pos
+				+ GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
 	}
 
-	de = NULL;
 	kunmap(dentry_page);
-found:
-	if (max_len > *max_slots)
-		*max_slots = max_len;
-	return de;
+	return NULL;
 }
 
 static struct f2fs_dir_entry *find_in_level(struct inode *dir,
--

1.7.7

------------------------------------------------------------------------------
Open source business process management suite built on Java and Eclipse Turn processes into business applications with Bonita BPM Community Edition Quickly connect people, data, and systems into organized workflows Winner of BOSSIE, CODIE, OW2 and Gartner awards
http://p.sf.net/sfu/Bonitasoft
_______________________________________________
Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

Hi Gu,

Just one nitpick.

Quoted 44 lines

-----Original Message-----
From: Gu Zheng [mailto:[email protected]]
Sent: Tuesday, June 24, 2014 6:21 PM
To: Jaegeuk Kim
Cc: fsdevel; f2fs
Subject: [f2fs-dev] [PATCH 3/4] f2fs: use find_next_bit_le rather than test_bit_le in, find_in_block

Use find_next_bit_le rather than test_bit_le to improve search speed lightly.

Signed-off-by Gu Zheng <[email protected]>

---
 fs/f2fs/dir.c |   43 +++++++++++++++++++++----------------------
 1 files changed, 21 insertions(+), 22 deletions(-)

fs/f2fs/dir.c +6 -11

index 3edd561..ba510fb 100644
@@ -93,42 +93,41 @@ static struct f2fs_dir_entry *find_in_block(struct page *dentry_page,
 			const char *name, size_t namelen, int *max_slots,
 			f2fs_hash_t namehash, struct page **res_page)
 {
-	struct f2fs_dir_entry *de;
-	unsigned long bit_pos = 0;
+	unsigned long bit_pos = 0, bit_start = 0;
 	struct f2fs_dentry_block *dentry_blk = kmap(dentry_page);
 	const void *dentry_bits = &dentry_blk->dentry_bitmap;
-	int max_len = 0;
 
-	while (bit_pos < NR_DENTRY_IN_BLOCK) {
-		if (!test_bit_le(bit_pos, dentry_bits)) {
-			if (bit_pos == 0)
-				max_len = 1;
-			else if (!test_bit_le(bit_pos - 1, dentry_bits))
-				max_len++;
-			bit_pos++;
-			continue;
+	while (bit_start < NR_DENTRY_IN_BLOCK) {
+		struct f2fs_dir_entry *de;
+		int max_len = 0;
+
+		bit_pos = find_next_bit_le(dentry_bits,

fs/f2fs/dir.c static struct f2fs_dir_entry *find_in_block(struct page *dentry_page, · line 110

Quoted 6 lines

fs/f2fs/dir.c +6 -0

+					NR_DENTRY_IN_BLOCK, bit_start);
+
+		max_len = bit_pos - bit_start;
+		if (max_len > *max_slots) {
+			*max_slots = max_len;
+			max_len = 0;

It could be removed here, and also do not need to initialize above.

Thanks.
Yu

Quoted 38 lines

fs/f2fs/dir.c +9 -12

 		}
+
+		if (bit_pos >= NR_DENTRY_IN_BLOCK)
+			break;
+
 		de = &dentry_blk->dentry[bit_pos];
 		if (early_match_name(name, namelen, namehash, de)) {
 			if (!memcmp(dentry_blk->filename[bit_pos],
 							name, namelen)) {
 				*res_page = dentry_page;
-				goto found;
+				return de;
 			}
 		}
-		if (max_len > *max_slots) {
-			*max_slots = max_len;
-			max_len = 0;
-		}
-		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
+
+		bit_start = bit_pos
+				+ GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
 	}
 
-	de = NULL;
 	kunmap(dentry_page);
-found:
-	if (max_len > *max_slots)
-		*max_slots = max_len;
-	return de;
+	return NULL;
 }
 
 static struct f2fs_dir_entry *find_in_level(struct inode *dir,
--

1.7.7

Quoted 10 lines

------------------------------------------------------------------------------
Open source business process management suite built on Java and Eclipse Turn processes into business applications with Bonita BPM Community Edition Quickly connect people, data, and systems into organized workflows Winner of BOSSIE, CODIE, OW2 and Gartner awards
http://p.sf.net/sfu/Bonitasoft
_______________________________________________
Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

.

Use find_next_bit_le rather than test_bit_le to improve search speed lightly.

Signed-off-by Gu Zheng <[email protected]>

---
 fs/f2fs/dir.c |   43 +++++++++++++++++++++----------------------
 1 files changed, 21 insertions(+), 22 deletions(-)

fs/f2fs/dir.c +21 -22

index 3edd561..ba510fb 100644
@@ -93,42 +93,41 @@ static struct f2fs_dir_entry *find_in_block(struct page *dentry_page,
 			const char *name, size_t namelen, int *max_slots,
 			f2fs_hash_t namehash, struct page **res_page)
 {
-	struct f2fs_dir_entry *de;
-	unsigned long bit_pos = 0;
+	unsigned long bit_pos = 0, bit_start = 0;
 	struct f2fs_dentry_block *dentry_blk = kmap(dentry_page);
 	const void *dentry_bits = &dentry_blk->dentry_bitmap;
-	int max_len = 0;
 
-	while (bit_pos < NR_DENTRY_IN_BLOCK) {
-		if (!test_bit_le(bit_pos, dentry_bits)) {
-			if (bit_pos == 0)
-				max_len = 1;
-			else if (!test_bit_le(bit_pos - 1, dentry_bits))
-				max_len++;
-			bit_pos++;
-			continue;
+	while (bit_start < NR_DENTRY_IN_BLOCK) {
+		struct f2fs_dir_entry *de;
+		int max_len = 0;
+
+		bit_pos = find_next_bit_le(dentry_bits,
+					NR_DENTRY_IN_BLOCK, bit_start);
+
+		max_len = bit_pos - bit_start;
+		if (max_len > *max_slots) {
+			*max_slots = max_len;
+			max_len = 0;
 		}
+
+		if (bit_pos >= NR_DENTRY_IN_BLOCK)
+			break;
+
 		de = &dentry_blk->dentry[bit_pos];
 		if (early_match_name(name, namelen, namehash, de)) {
 			if (!memcmp(dentry_blk->filename[bit_pos],
 							name, namelen)) {
 				*res_page = dentry_page;
-				goto found;
+				return de;
 			}
 		}
-		if (max_len > *max_slots) {
-			*max_slots = max_len;
-			max_len = 0;
-		}
-		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
+
+		bit_start = bit_pos
+				+ GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
 	}
 
-	de = NULL;
 	kunmap(dentry_page);
-found:
-	if (max_len > *max_slots)
-		*max_slots = max_len;
-	return de;
+	return NULL;
 }
 
 static struct f2fs_dir_entry *find_in_level(struct inode *dir,

Signature · 1 line

1.7.7

Hi, Gu

Unfortunately, find_next_bit isn't always better than test_bit. Refer to commit 5d0c667121bfc8be76d1580f485bddbe73465d1a

I remember that
Perviously, Jaegeuk had changed find_next_bit to test_bit because find_next_bit spent much cpu time in the case of there is lot of dentries like a postmark.

Sorry, I should have reported this quickly.

Quoted 78 lines

Use find_next_bit_le rather than test_bit_le to improve search speed lightly.

Signed-off-by Gu Zheng <[email protected]>

---
 fs/f2fs/dir.c |   43 +++++++++++++++++++++----------------------
 1 files changed, 21 insertions(+), 22 deletions(-)

fs/f2fs/dir.c +21 -22

index 3edd561..ba510fb 100644
@@ -93,42 +93,41 @@ static struct f2fs_dir_entry *find_in_block(struct page *dentry_page,
 			const char *name, size_t namelen, int *max_slots,
 			f2fs_hash_t namehash, struct page **res_page)
 {
-	struct f2fs_dir_entry *de;
-	unsigned long bit_pos = 0;
+	unsigned long bit_pos = 0, bit_start = 0;
 	struct f2fs_dentry_block *dentry_blk = kmap(dentry_page);
 	const void *dentry_bits = &dentry_blk->dentry_bitmap;
-	int max_len = 0;
 
-	while (bit_pos < NR_DENTRY_IN_BLOCK) {
-		if (!test_bit_le(bit_pos, dentry_bits)) {
-			if (bit_pos == 0)
-				max_len = 1;
-			else if (!test_bit_le(bit_pos - 1, dentry_bits))
-				max_len++;
-			bit_pos++;
-			continue;
+	while (bit_start < NR_DENTRY_IN_BLOCK) {
+		struct f2fs_dir_entry *de;
+		int max_len = 0;
+
+		bit_pos = find_next_bit_le(dentry_bits,
+					NR_DENTRY_IN_BLOCK, bit_start);
+
+		max_len = bit_pos - bit_start;
+		if (max_len > *max_slots) {
+			*max_slots = max_len;
+			max_len = 0;
 		}
+
+		if (bit_pos >= NR_DENTRY_IN_BLOCK)
+			break;
+
 		de = &dentry_blk->dentry[bit_pos];
 		if (early_match_name(name, namelen, namehash, de)) {
 			if (!memcmp(dentry_blk->filename[bit_pos],
 							name, namelen)) {
 				*res_page = dentry_page;
-				goto found;
+				return de;
 			}
 		}
-		if (max_len > *max_slots) {
-			*max_slots = max_len;
-			max_len = 0;
-		}
-		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
+
+		bit_start = bit_pos
+				+ GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
 	}
 
-	de = NULL;
 	kunmap(dentry_page);
-found:
-	if (max_len > *max_slots)
-		*max_slots = max_len;
-	return de;
+	return NULL;
 }
 
 static struct f2fs_dir_entry *find_in_level(struct inode *dir,

Signature · 1 line

1.7.7

Use find_next_bit_le rather than test_bit_le to improve search speed lightly.

Signed-off-by Gu Zheng <[email protected]>

---
 fs/f2fs/dir.c |   43 +++++++++++++++++++++----------------------
 1 files changed, 21 insertions(+), 22 deletions(-)

fs/f2fs/dir.c +21 -22

index 3edd561..ba510fb 100644
@@ -93,42 +93,41 @@ static struct f2fs_dir_entry *find_in_block(struct page *dentry_page,
 			const char *name, size_t namelen, int *max_slots,
 			f2fs_hash_t namehash, struct page **res_page)
 {
-	struct f2fs_dir_entry *de;
-	unsigned long bit_pos = 0;
+	unsigned long bit_pos = 0, bit_start = 0;
 	struct f2fs_dentry_block *dentry_blk = kmap(dentry_page);
 	const void *dentry_bits = &dentry_blk->dentry_bitmap;
-	int max_len = 0;
 
-	while (bit_pos < NR_DENTRY_IN_BLOCK) {
-		if (!test_bit_le(bit_pos, dentry_bits)) {
-			if (bit_pos == 0)
-				max_len = 1;
-			else if (!test_bit_le(bit_pos - 1, dentry_bits))
-				max_len++;
-			bit_pos++;
-			continue;
+	while (bit_start < NR_DENTRY_IN_BLOCK) {
+		struct f2fs_dir_entry *de;
+		int max_len = 0;
+
+		bit_pos = find_next_bit_le(dentry_bits,
+					NR_DENTRY_IN_BLOCK, bit_start);
+
+		max_len = bit_pos - bit_start;
+		if (max_len > *max_slots) {
+			*max_slots = max_len;
+			max_len = 0;
 		}
+
+		if (bit_pos >= NR_DENTRY_IN_BLOCK)
+			break;
+
 		de = &dentry_blk->dentry[bit_pos];
 		if (early_match_name(name, namelen, namehash, de)) {
 			if (!memcmp(dentry_blk->filename[bit_pos],
 							name, namelen)) {
 				*res_page = dentry_page;
-				goto found;
+				return de;
 			}
 		}
-		if (max_len > *max_slots) {
-			*max_slots = max_len;
-			max_len = 0;
-		}
-		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
+
+		bit_start = bit_pos
+				+ GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
 	}
 
-	de = NULL;
 	kunmap(dentry_page);
-found:
-	if (max_len > *max_slots)
-		*max_slots = max_len;
-	return de;
+	return NULL;
 }
 
 static struct f2fs_dir_entry *find_in_level(struct inode *dir,

Signature · 1 line

1.7.7

Thanks Changman for reminding this. :)

If there are a lot of ones in the bit stream, find_next_bit_le would cause some overhead to translate the bits.

However, it would be effective to use find_next_bit_le if the bit stream looks like 0000000001.

Well, IMO the former case would be a little bit more common.

Gu,
Can you provide some performance numbers wrt this?

Quoted 78 lines

Use find_next_bit_le rather than test_bit_le to improve search speed lightly.

Signed-off-by Gu Zheng <[email protected]>

---
 fs/f2fs/dir.c |   43 +++++++++++++++++++++----------------------
 1 files changed, 21 insertions(+), 22 deletions(-)

fs/f2fs/dir.c +21 -22

index 3edd561..ba510fb 100644
@@ -93,42 +93,41 @@ static struct f2fs_dir_entry *find_in_block(struct page *dentry_page,
 			const char *name, size_t namelen, int *max_slots,
 			f2fs_hash_t namehash, struct page **res_page)
 {
-	struct f2fs_dir_entry *de;
-	unsigned long bit_pos = 0;
+	unsigned long bit_pos = 0, bit_start = 0;
 	struct f2fs_dentry_block *dentry_blk = kmap(dentry_page);
 	const void *dentry_bits = &dentry_blk->dentry_bitmap;
-	int max_len = 0;
 
-	while (bit_pos < NR_DENTRY_IN_BLOCK) {
-		if (!test_bit_le(bit_pos, dentry_bits)) {
-			if (bit_pos == 0)
-				max_len = 1;
-			else if (!test_bit_le(bit_pos - 1, dentry_bits))
-				max_len++;
-			bit_pos++;
-			continue;
+	while (bit_start < NR_DENTRY_IN_BLOCK) {
+		struct f2fs_dir_entry *de;
+		int max_len = 0;
+
+		bit_pos = find_next_bit_le(dentry_bits,
+					NR_DENTRY_IN_BLOCK, bit_start);
+
+		max_len = bit_pos - bit_start;
+		if (max_len > *max_slots) {
+			*max_slots = max_len;
+			max_len = 0;
 		}
+
+		if (bit_pos >= NR_DENTRY_IN_BLOCK)
+			break;
+
 		de = &dentry_blk->dentry[bit_pos];
 		if (early_match_name(name, namelen, namehash, de)) {
 			if (!memcmp(dentry_blk->filename[bit_pos],
 							name, namelen)) {
 				*res_page = dentry_page;
-				goto found;
+				return de;
 			}
 		}
-		if (max_len > *max_slots) {
-			*max_slots = max_len;
-			max_len = 0;
-		}
-		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
+
+		bit_start = bit_pos
+				+ GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
 	}
 
-	de = NULL;
 	kunmap(dentry_page);
-found:
-	if (max_len > *max_slots)
-		*max_slots = max_len;
-	return de;
+	return NULL;
 }
 
 static struct f2fs_dir_entry *find_in_level(struct inode *dir,

Signature · 1 line

1.7.7

Thanks Changman for reminding this. :)

If there are a lot of ones in the bit stream, find_next_bit_le would cause some overhead to translate the bits.

However, it would be effective to use find_next_bit_le if the bit stream looks like 0000000001.

Well, IMO the former case would be a little bit more common.

Gu,
Can you provide some performance numbers wrt this?

Quoted 75 lines · Gu Zheng

Use find_next_bit_le rather than test_bit_le to improve search speed lightly.

Signed-off-by Gu Zheng <[email protected]>

---
 fs/f2fs/dir.c |   43 +++++++++++++++++++++----------------------
 1 files changed, 21 insertions(+), 22 deletions(-)

fs/f2fs/dir.c +21 -22

index 3edd561..ba510fb 100644
@@ -93,42 +93,41 @@ static struct f2fs_dir_entry *find_in_block(struct page *dentry_page,
 			const char *name, size_t namelen, int *max_slots,
 			f2fs_hash_t namehash, struct page **res_page)
 {
-	struct f2fs_dir_entry *de;
-	unsigned long bit_pos = 0;
+	unsigned long bit_pos = 0, bit_start = 0;
 	struct f2fs_dentry_block *dentry_blk = kmap(dentry_page);
 	const void *dentry_bits = &dentry_blk->dentry_bitmap;
-	int max_len = 0;
 
-	while (bit_pos < NR_DENTRY_IN_BLOCK) {
-		if (!test_bit_le(bit_pos, dentry_bits)) {
-			if (bit_pos == 0)
-				max_len = 1;
-			else if (!test_bit_le(bit_pos - 1, dentry_bits))
-				max_len++;
-			bit_pos++;
-			continue;
+	while (bit_start < NR_DENTRY_IN_BLOCK) {
+		struct f2fs_dir_entry *de;
+		int max_len = 0;
+
+		bit_pos = find_next_bit_le(dentry_bits,
+					NR_DENTRY_IN_BLOCK, bit_start);
+
+		max_len = bit_pos - bit_start;
+		if (max_len > *max_slots) {
+			*max_slots = max_len;
+			max_len = 0;
 		}
+
+		if (bit_pos >= NR_DENTRY_IN_BLOCK)
+			break;
+
 		de = &dentry_blk->dentry[bit_pos];
 		if (early_match_name(name, namelen, namehash, de)) {
 			if (!memcmp(dentry_blk->filename[bit_pos],
 							name, namelen)) {
 				*res_page = dentry_page;
-				goto found;
+				return de;
 			}
 		}
-		if (max_len > *max_slots) {
-			*max_slots = max_len;
-			max_len = 0;
-		}
-		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
+
+		bit_start = bit_pos
+				+ GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
 	}
 
-	de = NULL;
 	kunmap(dentry_page);
-found:
-	if (max_len > *max_slots)
-		*max_slots = max_len;
-	return de;
+	return NULL;
 }
 

Quoted 3 lines

fs/f2fs/dir.c +0 -0

 static struct f2fs_dir_entry *find_in_level(struct inode *dir,

Signature · 1 line

1.7.7

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

Quoted 89 lines · Jaegeuk Kim

Thanks Changman for reminding this. :)

If there are a lot of ones in the bit stream, find_next_bit_le would cause some overhead to translate the bits.

However, it would be effective to use find_next_bit_le if the bit stream looks like 0000000001.

Well, IMO the former case would be a little bit more common.

Gu,
Can you provide some performance numbers wrt this?

Quoted 75 lines · Gu Zheng

Use find_next_bit_le rather than test_bit_le to improve search speed lightly.

Signed-off-by Gu Zheng <[email protected]>

---
 fs/f2fs/dir.c |   43 +++++++++++++++++++++----------------------
 1 files changed, 21 insertions(+), 22 deletions(-)

fs/f2fs/dir.c +21 -22

index 3edd561..ba510fb 100644
@@ -93,42 +93,41 @@ static struct f2fs_dir_entry *find_in_block(struct page *dentry_page,
 			const char *name, size_t namelen, int *max_slots,
 			f2fs_hash_t namehash, struct page **res_page)
 {
-	struct f2fs_dir_entry *de;
-	unsigned long bit_pos = 0;
+	unsigned long bit_pos = 0, bit_start = 0;
 	struct f2fs_dentry_block *dentry_blk = kmap(dentry_page);
 	const void *dentry_bits = &dentry_blk->dentry_bitmap;
-	int max_len = 0;
 
-	while (bit_pos < NR_DENTRY_IN_BLOCK) {
-		if (!test_bit_le(bit_pos, dentry_bits)) {
-			if (bit_pos == 0)
-				max_len = 1;
-			else if (!test_bit_le(bit_pos - 1, dentry_bits))
-				max_len++;
-			bit_pos++;
-			continue;
+	while (bit_start < NR_DENTRY_IN_BLOCK) {
+		struct f2fs_dir_entry *de;
+		int max_len = 0;
+
+		bit_pos = find_next_bit_le(dentry_bits,
+					NR_DENTRY_IN_BLOCK, bit_start);
+
+		max_len = bit_pos - bit_start;
+		if (max_len > *max_slots) {
+			*max_slots = max_len;
+			max_len = 0;
 		}
+
+		if (bit_pos >= NR_DENTRY_IN_BLOCK)
+			break;
+
 		de = &dentry_blk->dentry[bit_pos];
 		if (early_match_name(name, namelen, namehash, de)) {
 			if (!memcmp(dentry_blk->filename[bit_pos],
 							name, namelen)) {
 				*res_page = dentry_page;
-				goto found;
+				return de;
 			}
 		}
-		if (max_len > *max_slots) {
-			*max_slots = max_len;
-			max_len = 0;
-		}
-		bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
+
+		bit_start = bit_pos
+				+ GET_DENTRY_SLOTS(le16_to_cpu(de->name_len));
 	}
 
-	de = NULL;
 	kunmap(dentry_page);
-found:
-	if (max_len > *max_slots)
-		*max_slots = max_len;
-	return de;
+	return NULL;
 }
 

Quoted 4 lines

Quoted 3 lines

fs/f2fs/dir.c +0 -0

 static struct f2fs_dir_entry *find_in_level(struct inode *dir,

Signature · 1 line

1.7.7

#include <linux/module.h>

__u8 bitmaps[20][27] = {
		{1, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{2, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{4, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{8, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{16, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 1,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{32, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{64, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 1, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 2, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 4, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 8, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 1, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 1,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 1, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 1,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 1, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 1,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 1, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 1}
		};

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();

	for (i = 0; i < 20; i++) {
		printk("Test bitmap %d... \n", i);

		bit_addr = &bitmaps[i];

		tsc_s = rdtsc();

		for (j = 0; j < 1000; j++)
			find_next_bit_le(bit_addr, 216, 0);

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

		printk("find_next_bit_le: %llu \n", tsc_diff);

		pos = 0;
		tsc_s = rdtsc();

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

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

		printk("test_bit_le     : %llu \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");

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
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,

Quoted 39 lines · Gu Zheng

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

Hi Jaegeuk, Gu, Changman

Quoted 7 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
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

Quoted 43 lines

Well, how about testing with many ones in the bit streams? Thanks,

Quoted 39 lines · Gu Zheng

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

.

Hi Yu,
Thanks.

Quoted 142 lines · Chao Yu

Hi Jaegeuk, Gu, Changman

Quoted 7 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
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

Quoted 43 lines

Well, how about testing with many ones in the bit streams? Thanks,

Quoted 39 lines · Gu Zheng

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

Quoted 8 lines

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

Quoted 3 lines

.

#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");

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Saturday, July 05, 2014 2:26 PM
To: '이창만'
Cc: Gu Zheng; Chao Yu; 'f2fs'; 'fsdevel'
Subject: Re: [PATCH 3/4] f2fs: use find_next_bit_le rather than test_bit_le in, find_in_block

To Changman,

Just for sure, can you reproduce this issue in the x86 machine with proper benchmarks? (i.e., test_bit_le vs. find_next_bit_le)

To all,

I cautiously suspect that the performances might be different when processing f2fs_find_entry, since L1/L2 cache misses due to the intermediate routines like matching strings can make some effect on it.

But, IMO, it is still worth to investigate this issue and contemplate how to detect all ones or not.

Ah, one solution may be using 2 bytes from the reserved space, total 3, to indicate how many valid dentries are stored in the dentry block.

Any ideas?

Thanks,

Quoted 12 lines · Gu Zheng

Hi Yu,
Thanks.

Quoted 8 lines · Chao Yu

Hi Jaegeuk, Gu, Changman

Quoted 6 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
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

Quoted 287 lines

Quoted 134 lines

Quoted 44 lines

Well, how about testing with many ones in the bit streams? Thanks,

Quoted 39 lines · Gu Zheng

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

Quoted 8 lines

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

Quoted 3 lines

.

#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);

Quoted 2 lines

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

--
Jaegeuk Kim

To Changman,

Just for sure, can you reproduce this issue in the x86 machine with proper benchmarks? (i.e., test_bit_le vs. find_next_bit_le)

To all,

I cautiously suspect that the performances might be different when processing f2fs_find_entry, since L1/L2 cache misses due to the intermediate routines like matching strings can make some effect on it.

But, IMO, it is still worth to investigate this issue and contemplate how to detect all ones or not.

Ah, one solution may be using 2 bytes from the reserved space, total 3, to indicate how many valid dentries are stored in the dentry block.

Any ideas?

Thanks,

Quoted 294 lines · Gu Zheng

Hi Yu,
Thanks.

Quoted 142 lines · Chao Yu

Hi Jaegeuk, Gu, Changman

Quoted 7 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
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

Quoted 43 lines

Well, how about testing with many ones in the bit streams? Thanks,

Quoted 39 lines · Gu Zheng

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

Quoted 8 lines

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

Quoted 3 lines

.

#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) {

Quoted 7 lines

}

module_init(start_test);
module_exit(exit_test);

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

Signature · 1 line

Jaegeuk Kim

Hello,

Quoted 4 lines · Jaegeuk Kim

To Changman,

Just for sure, can you reproduce this issue in the x86 machine with proper benchmarks? (i.e., test_bit_le vs. find_next_bit_le)

It shows quite a different result of bit_mod_test between server and desktop.

CPU i5 x86_64 Ubuntu Server - 3.16.0-rc3

[266627.204776] find_next_bit_le    test_bit_le
[266627.205319]     1832                1774
[266627.206223]     1292                1746
[266627.207092]     1205                1746
[266627.207876]      914                1746
[266627.208710]     1082                1746
[266627.209506]      956                1746
[266627.210175]      523                1746

[266627.211839]     3907                1746
[266627.212898]     1850                1746
[266627.214046]     2153                1746
[266627.215118]     1894                1746

CPU i7 x86_64 Mint Desktop - 3.13.0-24-generic

[432284.422356] find_next_bit_le    test_bit_le
[432284.423470]     3771                3878
[432284.425400]     2671                3696
[432284.427221]     2492                3760
[432284.428908]     1971                3696
[432284.430640]     2191                3730
[432284.432323]     1986                3696
[432284.433741]     1123                3698

[432284.437269]     8299                3696
[432284.439487]     3842                3696
[432284.441850]     4334                3696
[432284.444080]     3885                3696

Quoted 7 lines

To all,

I cautiously suspect that the performances might be different when processing f2fs_find_entry, since L1/L2 cache misses due to the intermediate routines like matching strings can make some effect on it.

Quoted 7 lines

But, IMO, it is still worth to investigate this issue and contemplate how to detect all ones or not.

Ah, one solution may be using 2 bytes from the reserved space, total 3, to indicate how many valid dentries are stored in the dentry block.

Any ideas?

Agree. In the case of one bits is over than half, test_bit is better than find_next_bit. So we can decide whether using test_bit or find_next_bit depending on count of one bits.

When just comparing test_bit and find_next_bit, I think test_bit is more effective in f2fs because let's think about f2fs's dentry management policy. One dentry bucket is filled then next dentry bucket is filled from lower to higher level. If empty slots of lower level exist, they are used first. So, I guess that one bits are getting more than zero bits as time goes by.

Thanks,

Quoted 3 lines

Thanks,