Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 as permitted sender) client-ip=23.128.96.37;
MIME-Version: 1.0
In-Reply-To: <CAGudoHHqpk+1b6KqeFr6ptnm-578A_72Ng3H848WZP0GoyUQbw@mail.gmail.com>
References: <20230509165657.1735798-1-kent.overstreet@linux.dev>
 <20230509165657.1735798-23-kent.overstreet@linux.dev> <20230523-zujubeln-heizsysteme-f756eefe663e@brauner>
 <20231019153040.lj3anuescvdprcq7@f> <20231019155958.7ek7oyljs6y44ah7@f>
 <ZTJmnsAxGDnks2aj@dread.disaster.area> <CAGudoHHqpk+1b6KqeFr6ptnm-578A_72Ng3H848WZP0GoyUQbw@mail.gmail.com>
From:   Mateusz Guzik <mjguzik@gmail.com>
Date:   Sat, 21 Oct 2023 14:13:52 +0200
Message-ID: <CAGudoHFcz1wQgQ53sy-HPJvJhx_DHhXcVVg3FfrFKHHdxt=scg@mail.gmail.com>
Subject: Re: (subset) [PATCH 22/32] vfs: inode cache conversion to hash-bl
To:     Dave Chinner <david@fromorbit.com>
Cc:     Christian Brauner <brauner@kernel.org>,
        Dave Chinner <dchinner@redhat.com>,
        linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org,
        linux-bcachefs@vger.kernel.org,
        Kent Overstreet <kent.overstreet@linux.dev>,
        Alexander Viro <viro@zeniv.linux.org.uk>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

It was bugging me that find_inode_fast is at the top of the profile
(modulo the locking routine).

Internals don't look too bad (it skips collisions without taking
locks), so I started wondering if hashing is any good.

I re-ran the scan of 20 mln and started counting visited inodes for
each call, got this:

[0, 1)             58266 |                                                    |
[1, 2)            385228 |@@@                                                 |
[2, 3)           1252480 |@@@@@@@@@@                                          |
[3, 4)           2710082 |@@@@@@@@@@@@@@@@@@@@@@@                             |
[4, 5)           4385945 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@               |
[5, 6)           5662628 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@    |
[6, 7)           6074390 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[7, 8)           5575381 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@     |
[8, 9)           4475706 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@              |
[9, 10)          3183676 |@@@@@@@@@@@@@@@@@@@@@@@@@@@                         |
[10, 11)         2041743 |@@@@@@@@@@@@@@@@@                                   |
[11, 12)         1189850 |@@@@@@@@@@                                          |
[12, 13)          637683 |@@@@@                                               |
[13, 14)          313830 |@@                                                  |
[14, 15)          143277 |@                                                   |
[15, 16)           61501 |                                                    |
[16, 17)           25116 |                                                    |
[17, 18)            9693 |                                                    |
[18, 19)            3435 |                                                    |
[19, 20)            1120 |                                                    |
[20, 21)             385 |                                                    |
[21, 22)              99 |                                                    |
[22, 23)              45 |                                                    |
[23, 24)              15 |                                                    |
[24, 25)               2 |                                                    |
[25, 26)               2 |                                                    |
[26, 27)               2 |                                                    |

I compared this to literally just taking the ino & i_hash_mask as the
value, got this:
[0, 1)            119800 |                                                    |
[1, 2)            508063 |@@@                                                 |
[2, 3)           1576390 |@@@@@@@@@@@                                         |
[3, 4)           2763163 |@@@@@@@@@@@@@@@@@@@                                 |
[4, 5)           3696348 |@@@@@@@@@@@@@@@@@@@@@@@@@@                          |
[5, 6)           5975274 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@          |
[6, 7)           7253615 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[7, 8)           6563736 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@     |
[8, 9)           5012728 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                 |
[9, 10)          3495208 |@@@@@@@@@@@@@@@@@@@@@@@@@                           |
[10, 11)         1606659 |@@@@@@@@@@@                                         |
[11, 12)          459458 |@@@                                                 |
[12, 13)            3940 |                                                    |
[13, 14)              21 |                                                    |
[14, 15)               6 |                                                    |
[15, 16)               2 |                                                    |

That is to say distribution is much better, in particular the longest
streak is 15 (as opposed to 26).

While I'm not saying just taking ino is any good, I am saying there is
room for improvement here as far as one mount point is concerned.

Side note is that sb could have a randomly generated seed instead of
its address, which should help distributing this better.

So tl;dr hash distribution leaves some room for improvement and
*maybe* I'll prod it some time next month. One can also grow the table
of course, but that's for later.

-- 
Mateusz Guzik <mjguzik gmail.com>