lkml.org 
[lkml]   [2021]   [Sep]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH 2/3] fs/ntfs3: Make binary search to search smaller chunks in beginning
Date
We could try to optimize algorithm to first fill just small table and
after that use bigger table all the way up to ARRAY_SIZE(offs). This
way we can use bigger search array, but not lose benefits with entry
count smaller < ARRAY_SIZE(offs).

Signed-off-by: Kari Argillander <kari.argillander@gmail.com>
---
fs/ntfs3/index.c | 7 +++++--
1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/fs/ntfs3/index.c b/fs/ntfs3/index.c
index 8bac9d20e7e3..e336d5645628 100644
--- a/fs/ntfs3/index.c
+++ b/fs/ntfs3/index.c
@@ -8,6 +8,7 @@
#include <linux/blkdev.h>
#include <linux/buffer_head.h>
#include <linux/fs.h>
+#include <linux/kernel.h>
#include <linux/nls.h>

#include "debug.h"
@@ -680,8 +681,9 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
#ifdef NTFS3_INDEX_BINARY_SEARCH
struct NTFS_DE *found = NULL;
int min_idx = 0, mid_idx, max_idx = 0;
+ int table_size = 8;
int diff2;
- u16 offs[64];
+ u16 offs[128];

if (end > 0x10000)
goto next;
@@ -701,7 +703,7 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
off += e_size;

max_idx++;
- if (max_idx < ARRAY_SIZE(offs))
+ if (max_idx < table_size)
goto fill_table;

max_idx--;
@@ -719,6 +721,7 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
return NULL;

max_idx = 0;
+ table_size = min(table_size * 2, 128);
goto fill_table;
}
} else if (diff2 < 0) {
--
2.25.1
\
 
 \ /
  Last update: 2021-09-02 17:42    [W:0.150 / U:25.032 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site