Re: [PATCH 0/3] fs/ntfs3: Make entry binary search faster

From: Konstantin Komarov
Date: Mon Sep 13 2021 - 12:55:58 EST




On 02.09.2021 18:40, Kari Argillander wrote:
> This series will make binary search faster with removing the need of
> allocations. We will only use stack memory. This will also make possible
> to remove linear search completely.
>
> It is good also point out that full binary search not quite fit with
> entry search because entrys are not always same size. This why we first
> need linear table fill algorithm. My implementation try to use the fact
> that we should not linear fill full table before not doing any checking
> of the entrys. It is example 50/50 change if we are in middle that entry
> is in first half. So it is very inefficient to fill table after we are
> middle point.
>
> We could also predict how many entrys there is and use this information,
> but I did not do that in this point. I'm more than happy to improve this
> more if someone has ideas.
>
> I have tested this with xfstests and did not see regressions. Checkpatch
> and build tests for every patch have been done. I haven't done major
> bench marking with this one. Idea that this is better is just my two
> cent. Paragon has hopefully done bencmarking with old binary search
> compared to linear search? I'm quite certain that this will win old
> binary search algorithm because no need for allocations.
>
> Thanks Joe for let me notice this improvement.
>
> Kari Argillander (3):
> fs/ntfs3: Limit binary search table size
> fs/ntfs3: Make binary search to search smaller chunks in beginning
> fs/ntfs3: Always use binary search with entry search
>
> fs/ntfs3/index.c | 153 ++++++++++++++---------------------------------
> fs/ntfs3/ntfs.h | 3 -
> 2 files changed, 45 insertions(+), 111 deletions(-)
>
>
> base-commit: d3624466b56dd5b1886c1dff500525b544c19c83
>

Hi Joe, Kari!

Applied, thanks!