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>
