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

[Mateusz Guzik]

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>