lkml.org 
[lkml]   [2023]   [Oct]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Date
    SubjectRe: (subset) [PATCH 22/32] vfs: inode cache conversion to hash-bl
    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>

    \
     
     \ /
      Last update: 2023-10-21 14:14    [W:8.492 / U:0.000 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site