Re: (subset) [PATCH 22/32] vfs: inode cache conversion to hash-bl

Mateusz Guzik
2023-10-21T12:13:57Z

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>