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 -- 2.25.1
