On Thu, Aug 29, 2019 at 08:47:10PM +1000, Dave Chinner wrote: > From: Dave Chinner <dchinner@xxxxxxxxxx> > > When a directory is growing rapidly, new blocks tend to get added at > the end of the directory. These end up at the end of the freespace > index, and when the directory gets large finding these new > freespaces gets expensive. The code does a linear search across the > frespace index from the first block in the directory to the last, > hence meaning the newly added space is the last index searched. > > Instead, do a reverse order index search, starting from the last > block and index in the freespace index. This makes most lookups for > free space on rapidly growing directories O(1) instead of O(N), but > should not have any impact on random insert workloads because the > average search length is the same regardless of which end of the > array we start at. > > The result is a major improvement in large directory grow rates: > > create time(sec) / rate (files/s) > File count vanilla Prev commit Patched > 10k 0.41 / 24.3k 0.42 / 23.8k 0.41 / 24.3k > 20k 0.74 / 27.0k 0.76 / 26.3k 0.75 / 26.7k > 100k 3.81 / 26.4k 3.47 / 28.8k 3.27 / 30.6k > 200k 8.58 / 23.3k 7.19 / 27.8k 6.71 / 29.8k > 1M 85.69 / 11.7k 48.53 / 20.6k 37.67 / 26.5k > 2M 280.31 / 7.1k 130.14 / 15.3k 79.55 / 25.2k > 10M 3913.26 / 2.5k 552.89 / 18.1k > > Signed-Off-By: Dave Chinner <dchinner@xxxxxxxxxx> Same here. Otherwise looks good: Reviewed-by: Christoph Hellwig <hch@xxxxxx>
