summaryrefslogtreecommitdiffstats
path: root/tests/test_user_name.out
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2017-03-20 20:53:43 -0400
committerTavian Barnes <tavianator@tavianator.com>2017-03-20 20:53:43 -0400
commitc32385d4c8eb0e54af27712ff3fc82df1bda01e8 (patch)
tree1b600020913daea141aee44ef7bce8743f3ccaa7 /tests/test_user_name.out
parent139405503359f97867cbcb3cd580b4efde60a02d (diff)
downloadbfs-c32385d4c8eb0e54af27712ff3fc82df1bda01e8.tar.xz
bftw: Fix quadratic reference counting complexity
dircache_entry refcounts used to count every single descendant, resulting in n refcount updates to create/delete an entry at depth n, and thus O(n^2) complexity overall for deep directory structures. Fix it by only counting direct children instead. The cache eviction policy is changed to prefer shallower entries in all cases, attempting to save at least some of the benefit of the previous accounting scheme. Unfortunately, the average number of traversed components for openat() calls still went up by ~20%, but the performance in practice is roughly unchanged in my tests.
Diffstat (limited to 'tests/test_user_name.out')
0 files changed, 0 insertions, 0 deletions