| Message ID | 20190829104710.28239-6-david@fromorbit.com (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
| Series | xfs: speed up large directory modifications | expand |
On Thu, Aug 29, 2019 at 08:47:10PM +1000, Dave Chinner wrote: > From: Dave Chinner <dchinner@redhat.com> > > 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@redhat.com> Heh, neat. Reviewed-by: Darrick J. Wong <darrick.wong@oracle.com> --D > --- > fs/xfs/libxfs/xfs_dir2_node.c | 13 +++++-------- > 1 file changed, 5 insertions(+), 8 deletions(-) > > diff --git a/fs/xfs/libxfs/xfs_dir2_node.c b/fs/xfs/libxfs/xfs_dir2_node.c > index a81f56d9e538..705c4f562758 100644 > --- a/fs/xfs/libxfs/xfs_dir2_node.c > +++ b/fs/xfs/libxfs/xfs_dir2_node.c > @@ -1745,10 +1745,11 @@ xfs_dir2_node_find_freeblk( > struct xfs_inode *dp = args->dp; > struct xfs_trans *tp = args->trans; > struct xfs_buf *fbp = NULL; > + xfs_dir2_db_t firstfbno; > xfs_dir2_db_t lastfbno; > xfs_dir2_db_t ifbno = -1; > xfs_dir2_db_t dbno = -1; > - xfs_dir2_db_t fbno = -1; > + xfs_dir2_db_t fbno; > xfs_fileoff_t fo; > __be16 *bests = NULL; > int findex = 0; > @@ -1780,7 +1781,6 @@ xfs_dir2_node_find_freeblk( > * We'll start at the beginning of the freespace entries. > */ > ifbno = fblk->blkno; > - fbno = ifbno; > xfs_trans_brelse(tp, fbp); > fbp = NULL; > fblk->bp = NULL; > @@ -1794,12 +1794,9 @@ xfs_dir2_node_find_freeblk( > if (error) > return error; > lastfbno = xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo); > + firstfbno = xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET); > > - /* If we haven't get a search start block, set it now */ > - if (fbno == -1) > - fbno = xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET); > - > - for ( ; fbno < lastfbno; fbno++) { > + for (fbno = lastfbno - 1; fbno >= firstfbno; fbno--) { > /* If it's ifbno we already looked at it. */ > if (fbno == ifbno) > continue; > @@ -1822,7 +1819,7 @@ xfs_dir2_node_find_freeblk( > dp->d_ops->free_hdr_from_disk(&freehdr, free); > > /* Scan the free entry array for a large enough free space. */ > - for (findex = 0; findex < freehdr.nvalid; findex++) { > + for (findex = freehdr.nvalid - 1; findex >= 0; findex--) { > if (be16_to_cpu(bests[findex]) != NULLDATAOFF && > be16_to_cpu(bests[findex]) >= length) { > dbno = freehdr.firstdb + findex; > -- > 2.23.0.rc1 >
On Thu, Aug 29, 2019 at 08:47:10PM +1000, Dave Chinner wrote: > From: Dave Chinner <dchinner@redhat.com> > > 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@redhat.com> Same here. Otherwise looks good: Reviewed-by: Christoph Hellwig <hch@lst.de>
diff --git a/fs/xfs/libxfs/xfs_dir2_node.c b/fs/xfs/libxfs/xfs_dir2_node.c index a81f56d9e538..705c4f562758 100644 --- a/fs/xfs/libxfs/xfs_dir2_node.c +++ b/fs/xfs/libxfs/xfs_dir2_node.c @@ -1745,10 +1745,11 @@ xfs_dir2_node_find_freeblk( struct xfs_inode *dp = args->dp; struct xfs_trans *tp = args->trans; struct xfs_buf *fbp = NULL; + xfs_dir2_db_t firstfbno; xfs_dir2_db_t lastfbno; xfs_dir2_db_t ifbno = -1; xfs_dir2_db_t dbno = -1; - xfs_dir2_db_t fbno = -1; + xfs_dir2_db_t fbno; xfs_fileoff_t fo; __be16 *bests = NULL; int findex = 0; @@ -1780,7 +1781,6 @@ xfs_dir2_node_find_freeblk( * We'll start at the beginning of the freespace entries. */ ifbno = fblk->blkno; - fbno = ifbno; xfs_trans_brelse(tp, fbp); fbp = NULL; fblk->bp = NULL; @@ -1794,12 +1794,9 @@ xfs_dir2_node_find_freeblk( if (error) return error; lastfbno = xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo); + firstfbno = xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET); - /* If we haven't get a search start block, set it now */ - if (fbno == -1) - fbno = xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET); - - for ( ; fbno < lastfbno; fbno++) { + for (fbno = lastfbno - 1; fbno >= firstfbno; fbno--) { /* If it's ifbno we already looked at it. */ if (fbno == ifbno) continue; @@ -1822,7 +1819,7 @@ xfs_dir2_node_find_freeblk( dp->d_ops->free_hdr_from_disk(&freehdr, free); /* Scan the free entry array for a large enough free space. */ - for (findex = 0; findex < freehdr.nvalid; findex++) { + for (findex = freehdr.nvalid - 1; findex >= 0; findex--) { if (be16_to_cpu(bests[findex]) != NULLDATAOFF && be16_to_cpu(bests[findex]) >= length) { dbno = freehdr.firstdb + findex;