From: Konstantin Komarov <almaz.alexandrovich@paragon-software.com>
To: Kari Argillander <kari.argillander@gmail.com>, <ntfs3@lists.linux.dev>
Cc: <linux-kernel@vger.kernel.org>, Joe Perches <joe@perches.com>
Subject: Re: [PATCH 0/3] fs/ntfs3: Make entry binary search faster
Date: Mon, 13 Sep 2021 19:55:50 +0300 [thread overview]
Message-ID: <d2636759-7809-e080-952a-b24123744eb1@paragon-software.com> (raw)
In-Reply-To: <20210902154050.5075-1-kari.argillander@gmail.com>
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!
prev parent reply other threads:[~2021-09-13 16:55 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-09-02 15:40 [PATCH 0/3] fs/ntfs3: Make entry binary search faster Kari Argillander
2021-09-02 15:40 ` [PATCH 1/3] fs/ntfs3: Limit binary search table size Kari Argillander
2021-09-02 15:40 ` [PATCH 2/3] fs/ntfs3: Make binary search to search smaller chunks in beginning Kari Argillander
2021-09-02 15:40 ` [PATCH 3/3] fs/ntfs3: Always use binary search with entry search Kari Argillander
2021-09-13 16:55 ` Konstantin Komarov [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=d2636759-7809-e080-952a-b24123744eb1@paragon-software.com \
--to=almaz.alexandrovich@paragon-software.com \
--cc=joe@perches.com \
--cc=kari.argillander@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=ntfs3@lists.linux.dev \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).