Re: [PATCH 5/5] xfs: reverse search directory freespace indexes

["Darrick J. Wong" <darrick.wong@oracle.com>]

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
>