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!
