diff options
| author | Kari Argillander <kari.argillander@gmail.com> | 2021-09-02 18:40:49 +0300 |
|---|---|---|
| committer | Konstantin Komarov <almaz.alexandrovich@paragon-software.com> | 2021-09-13 19:41:46 +0300 |
| commit | ef9297007e9904588682699e618c56401f61d1c2 (patch) | |
| tree | cb57d22b955150be0d78cc85cb34adcd63c1da4b /fs/ntfs3/index.c | |
| parent | 162333efa8dc4984d2ca0a2eb85528e13366f271 (diff) | |
fs/ntfs3: Make binary search to search smaller chunks in beginning
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>
Signed-off-by: Konstantin Komarov <almaz.alexandrovich@paragon-software.com>
Diffstat (limited to 'fs/ntfs3/index.c')
| -rw-r--r-- | fs/ntfs3/index.c | 7 |
1 files changed, 5 insertions, 2 deletions
diff --git a/fs/ntfs3/index.c b/fs/ntfs3/index.c index a16256ab3e9f..3ad1ee608e53 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 "debug.h" #include "ntfs.h" @@ -679,8 +680,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; @@ -700,7 +702,7 @@ fill_table: off += e_size; max_idx++; - if (max_idx < ARRAY_SIZE(offs)) + if (max_idx < table_size) goto fill_table; max_idx--; @@ -718,6 +720,7 @@ binary_search: return NULL; max_idx = 0; + table_size = min(table_size * 2, 128); goto fill_table; } } else if (diff2 < 0) { |