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

[Konstantin Komarov]

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!