[PATCH] erofs-utils: use qsort() to sort dir->i_subdirs

[PATCH] erofs-utils: use qsort() to sort dir->i_subdirs

[Hu Weiwen]

Original implementation use insertion sort, and its time complexity is
O(n^2). This patch use qsort instead. When I create a directory with
100k entries, this reduces the user space time from around 3 mins to
0.5s.

Create such a large directory for benchmark with:
mkdir large; cd large; touch $(seq 100000);

Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
---
 lib/inode.c | 53 +++++++++++++++++++++++++++++++++--------------------
 1 file changed, 33 insertions(+), 20 deletions(-)

diff --git a/lib/inode.c b/lib/inode.c
index d52facf..9217127 100644
--- a/lib/inode.c
+++ b/lib/inode.c
@@ -96,21 +96,6 @@ unsigned int erofs_iput(struct erofs_inode *inode)
 	return 0;
 }
 
-static int dentry_add_sorted(struct erofs_dentry *d, struct list_head *head)
-{
-	struct list_head *pos;
-
-	list_for_each(pos, head) {
-		struct erofs_dentry *d2 =
-			container_of(pos, struct erofs_dentry, d_child);
-
-		if (strcmp(d->name, d2->name) < 0)
-			break;
-	}
-	list_add_tail(&d->d_child, pos);
-	return 0;
-}
-
 struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
 				   const char *name)
 {
@@ -122,7 +107,7 @@ struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
 	strncpy(d->name, name, EROFS_NAME_LEN - 1);
 	d->name[EROFS_NAME_LEN - 1] = '\0';
 
-	dentry_add_sorted(d, &parent->i_subdirs);
+	list_add_tail(&d->d_child, &parent->i_subdirs);
 	return d;
 }
 
@@ -156,10 +141,19 @@ static int __allocate_inode_bh_data(struct erofs_inode *inode,
 	return 0;
 }
 
+static int comp_subdir(const void *a, const void *b)
+{
+	const struct erofs_dentry *d_a, *d_b;
+
+	d_a = *((const struct erofs_dentry **)a);
+	d_b = *((const struct erofs_dentry **)b);
+	return strcmp(d_a->name, d_b->name);
+}
+
-int erofs_prepare_dir_file(struct erofs_inode *dir)
+int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
 {
-	struct erofs_dentry *d;
-	unsigned int d_size, i_nlink;
+	struct erofs_dentry *d, **all_d;
+	unsigned int d_size, i_nlink, i;
 	int ret;
 
 	/* dot is pointed to the current dir inode */
@@ -172,6 +166,22 @@ int erofs_prepare_dir_file(struct erofs_inode *dir)
 	d->inode = erofs_igrab(dir->i_parent);
 	d->type = EROFS_FT_DIR;
 
+	/* sort subdirs */
+	nr_subdirs += 2;
+	all_d = malloc(nr_subdirs * sizeof(d));
+	if (!all_d)
+		return -ENOMEM;
+	i = 0;
+	list_for_each_entry(d, &dir->i_subdirs, d_child)
+		all_d[i++] = d;
+	DBG_BUGON(i != nr_subdirs);
+	qsort(all_d, nr_subdirs, sizeof(d), comp_subdir);
+	init_list_head(&dir->i_subdirs);
+	for (i = 0; i < nr_subdirs; i++)
+		list_add_tail(&all_d[i]->d_child, &dir->i_subdirs);
+	free(all_d);
+	all_d = NULL;
+
 	/* let's calculate dir size and update i_nlink */
 	d_size = 0;
 	i_nlink = 0;
@@ -922,6 +932,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
 	DIR *_dir;
 	struct dirent *dp;
 	struct erofs_dentry *d;
+	unsigned int nr_subdirs;
 
 	ret = erofs_prepare_xattr_ibody(dir);
 	if (ret < 0)
@@ -961,6 +972,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
 		return ERR_PTR(-errno);
 	}
 
+	nr_subdirs = 0;
 	while (1) {
 		/*
 		 * set errno to 0 before calling readdir() in order to
@@ -984,6 +996,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
 			ret = PTR_ERR(d);
 			goto err_closedir;
 		}
+		nr_subdirs++;
 
 		/* to count i_nlink for directories */
 		d->type = (dp->d_type == DT_DIR ?
@@ -996,7 +1009,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
 	}
 	closedir(_dir);
 
-	ret = erofs_prepare_dir_file(dir);
+	ret = erofs_prepare_dir_file(dir, nr_subdirs);
 	if (ret)
 		goto err;
 
-- 
2.25.1

Re: [PATCH] erofs-utils: use qsort() to sort dir->i_subdirs

[Gao Xiang]

Hi Weiwen,

On Thu, Apr 01, 2021 at 09:52:51PM +0800, Hu Weiwen wrote:
> Original implementation use insertion sort, and its time complexity is
> O(n^2). This patch use qsort instead. When I create a directory with
> 100k entries, this reduces the user space time from around 3 mins to
> 0.5s.
> 
> Create such a large directory for benchmark with:
> mkdir large; cd large; touch $(seq 100000);
> 
> Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>

Thanks for your work. Yeah, it's another path that needs to be
optimized for huge dirs.

The overall looks good to me, some nits below...

> ---
>  lib/inode.c | 53 +++++++++++++++++++++++++++++++++--------------------
>  1 file changed, 33 insertions(+), 20 deletions(-)
> 
> diff --git a/lib/inode.c b/lib/inode.c
> index d52facf..9217127 100644
> --- a/lib/inode.c
> +++ b/lib/inode.c
> @@ -96,21 +96,6 @@ unsigned int erofs_iput(struct erofs_inode *inode)
>  	return 0;
>  }
>  
> -static int dentry_add_sorted(struct erofs_dentry *d, struct list_head *head)
> -{
> -	struct list_head *pos;
> -
> -	list_for_each(pos, head) {
> -		struct erofs_dentry *d2 =
> -			container_of(pos, struct erofs_dentry, d_child);
> -
> -		if (strcmp(d->name, d2->name) < 0)
> -			break;
> -	}
> -	list_add_tail(&d->d_child, pos);
> -	return 0;
> -}
> -
>  struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
>  				   const char *name)
>  {
> @@ -122,7 +107,7 @@ struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
>  	strncpy(d->name, name, EROFS_NAME_LEN - 1);
>  	d->name[EROFS_NAME_LEN - 1] = '\0';
>  
> -	dentry_add_sorted(d, &parent->i_subdirs);
> +	list_add_tail(&d->d_child, &parent->i_subdirs);
>  	return d;
>  }
>  
> @@ -156,10 +141,19 @@ static int __allocate_inode_bh_data(struct erofs_inode *inode,
>  	return 0;
>  }
>  
> +static int comp_subdir(const void *a, const void *b)
> +{
> +	const struct erofs_dentry *d_a, *d_b;
> +
> +	d_a = *((const struct erofs_dentry **)a);
> +	d_b = *((const struct erofs_dentry **)b);
> +	return strcmp(d_a->name, d_b->name);
> +}

How about just use `da' and `db' for size?

> +
> -int erofs_prepare_dir_file(struct erofs_inode *dir)
> +int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
>  {
> -	struct erofs_dentry *d;
> -	unsigned int d_size, i_nlink;
> +	struct erofs_dentry *d, **all_d;
> +	unsigned int d_size, i_nlink, i;
>  	int ret;
>  
>  	/* dot is pointed to the current dir inode */
> @@ -172,6 +166,22 @@ int erofs_prepare_dir_file(struct erofs_inode *dir)
>  	d->inode = erofs_igrab(dir->i_parent);
>  	d->type = EROFS_FT_DIR;
>  
> +	/* sort subdirs */
> +	nr_subdirs += 2;
> +	all_d = malloc(nr_subdirs * sizeof(d));

maybe just use `sorted' name here?

> +	if (!all_d)
> +		return -ENOMEM;
> +	i = 0;
> +	list_for_each_entry(d, &dir->i_subdirs, d_child)

I think we could list_del here, and use list_for_each_entry

> +		all_d[i++] = d;
> +	DBG_BUGON(i != nr_subdirs);
> +	qsort(all_d, nr_subdirs, sizeof(d), comp_subdir);
> +	init_list_head(&dir->i_subdirs);

After list_del, no need to init_list_head again.
The another reason is that some list_add_tail implementation
could check elements isn't in a list first.

> +	for (i = 0; i < nr_subdirs; i++)
> +		list_add_tail(&all_d[i]->d_child, &dir->i_subdirs);
> +	free(all_d);
> +	all_d = NULL;

no need to NULLify it..

Thanks,
Gao Xiang

Re: [PATCH] erofs-utils: use qsort() to sort dir->i_subdirs

[Gao Xiang]

On Fri, Apr 02, 2021 at 10:12:50AM +0800, Gao Xiang wrote:
> Hi Weiwen,
> 
> On Thu, Apr 01, 2021 at 09:52:51PM +0800, Hu Weiwen wrote:
> > Original implementation use insertion sort, and its time complexity is
> > O(n^2). This patch use qsort instead. When I create a directory with
> > 100k entries, this reduces the user space time from around 3 mins to
> > 0.5s.
> > 
> > Create such a large directory for benchmark with:
> > mkdir large; cd large; touch $(seq 100000);
> > 
> > Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
> 
> Thanks for your work. Yeah, it's another path that needs to be
> optimized for huge dirs.
> 
> The overall looks good to me, some nits below...
> 
> > ---
> >  lib/inode.c | 53 +++++++++++++++++++++++++++++++++--------------------
> >  1 file changed, 33 insertions(+), 20 deletions(-)
> > 
> > diff --git a/lib/inode.c b/lib/inode.c
> > index d52facf..9217127 100644
> > --- a/lib/inode.c
> > +++ b/lib/inode.c
> > @@ -96,21 +96,6 @@ unsigned int erofs_iput(struct erofs_inode *inode)
> >  	return 0;
> >  }
> >  
> > -static int dentry_add_sorted(struct erofs_dentry *d, struct list_head *head)
> > -{
> > -	struct list_head *pos;
> > -
> > -	list_for_each(pos, head) {
> > -		struct erofs_dentry *d2 =
> > -			container_of(pos, struct erofs_dentry, d_child);
> > -
> > -		if (strcmp(d->name, d2->name) < 0)
> > -			break;
> > -	}
> > -	list_add_tail(&d->d_child, pos);
> > -	return 0;
> > -}
> > -
> >  struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
> >  				   const char *name)
> >  {
> > @@ -122,7 +107,7 @@ struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
> >  	strncpy(d->name, name, EROFS_NAME_LEN - 1);
> >  	d->name[EROFS_NAME_LEN - 1] = '\0';
> >  
> > -	dentry_add_sorted(d, &parent->i_subdirs);
> > +	list_add_tail(&d->d_child, &parent->i_subdirs);
> >  	return d;
> >  }
> >  
> > @@ -156,10 +141,19 @@ static int __allocate_inode_bh_data(struct erofs_inode *inode,
> >  	return 0;
> >  }
> >  
> > +static int comp_subdir(const void *a, const void *b)
> > +{
> > +	const struct erofs_dentry *d_a, *d_b;
> > +
> > +	d_a = *((const struct erofs_dentry **)a);
> > +	d_b = *((const struct erofs_dentry **)b);
> > +	return strcmp(d_a->name, d_b->name);
> > +}
> 
> How about just use `da' and `db' for size?

... for these...

> 
> > +
> > -int erofs_prepare_dir_file(struct erofs_inode *dir)
> > +int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
> >  {
> > -	struct erofs_dentry *d;
> > -	unsigned int d_size, i_nlink;
> > +	struct erofs_dentry *d, **all_d;
> > +	unsigned int d_size, i_nlink, i;
> >  	int ret;
> >  
> >  	/* dot is pointed to the current dir inode */
> > @@ -172,6 +166,22 @@ int erofs_prepare_dir_file(struct erofs_inode *dir)
> >  	d->inode = erofs_igrab(dir->i_parent);
> >  	d->type = EROFS_FT_DIR;
> >  
> > +	/* sort subdirs */
> > +	nr_subdirs += 2;
> > +	all_d = malloc(nr_subdirs * sizeof(d));
> 
> maybe just use `sorted' name here?
> 
> > +	if (!all_d)
> > +		return -ENOMEM;
> > +	i = 0;
> > +	list_for_each_entry(d, &dir->i_subdirs, d_child)
> 
> I think we could list_del here, and use list_for_each_entry

Ah, I meant list_for_each_entry_safe. The reply was somewhat
buggy as well..

> 
> > +		all_d[i++] = d;
> > +	DBG_BUGON(i != nr_subdirs);
> > +	qsort(all_d, nr_subdirs, sizeof(d), comp_subdir);
> > +	init_list_head(&dir->i_subdirs);
> 
> After list_del, no need to init_list_head again.
> The another reason is that some list_add_tail implementation
> could check elements isn't in a list first.
> 
> > +	for (i = 0; i < nr_subdirs; i++)
> > +		list_add_tail(&all_d[i]->d_child, &dir->i_subdirs);
> > +	free(all_d);
> > +	all_d = NULL;
> 
> no need to NULLify it..
> 
> Thanks,
> Gao Xiang
> 

[PATCH v2] erofs-utils: use qsort() to sort dir->i_subdirs

[Hu Weiwen]

Original implementation use insertion sort, and its time complexity is
O(n^2). This patch use qsort instead. When I create a directory with
100k entries, this reduces the user space time from around 3 mins to
0.5s.

Create such a large directory for benchmark with:
mkdir large; cd large; touch $(seq 100000);

Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
---
 lib/inode.c | 53 +++++++++++++++++++++++++++++++++--------------------
 1 file changed, 33 insertions(+), 20 deletions(-)

diff --git a/lib/inode.c b/lib/inode.c
index d52facf..ef55e88 100644
--- a/lib/inode.c
+++ b/lib/inode.c
@@ -96,21 +96,6 @@ unsigned int erofs_iput(struct erofs_inode *inode)
 	return 0;
 }

-static int dentry_add_sorted(struct erofs_dentry *d, struct list_head *head)
-{
-	struct list_head *pos;
-
-	list_for_each(pos, head) {
-		struct erofs_dentry *d2 =
-			container_of(pos, struct erofs_dentry, d_child);
-
-		if (strcmp(d->name, d2->name) < 0)
-			break;
-	}
-	list_add_tail(&d->d_child, pos);
-	return 0;
-}
-
 struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
 				   const char *name)
 {
@@ -122,7 +107,7 @@ struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
 	strncpy(d->name, name, EROFS_NAME_LEN - 1);
 	d->name[EROFS_NAME_LEN - 1] = '\0';

-	dentry_add_sorted(d, &parent->i_subdirs);
+	list_add_tail(&d->d_child, &parent->i_subdirs);
 	return d;
 }

@@ -156,10 +141,19 @@ static int __allocate_inode_bh_data(struct erofs_inode *inode,
 	return 0;
 }

+static int comp_subdir(const void *a, const void *b)
+{
+	const struct erofs_dentry *da, *db;
+
+	da = *((const struct erofs_dentry **)a);
+	db = *((const struct erofs_dentry **)b);
+	return strcmp(da->name, db->name);
+}
+
-int erofs_prepare_dir_file(struct erofs_inode *dir)
+int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
 {
-	struct erofs_dentry *d;
-	unsigned int d_size, i_nlink;
+	struct erofs_dentry *d, *n, **sorted_d;
+	unsigned int d_size, i_nlink, i;
 	int ret;

 	/* dot is pointed to the current dir inode */
@@ -172,6 +166,22 @@ int erofs_prepare_dir_file(struct erofs_inode *dir)
 	d->inode = erofs_igrab(dir->i_parent);
 	d->type = EROFS_FT_DIR;

+	/* sort subdirs */
+	nr_subdirs += 2;
+	sorted_d = malloc(nr_subdirs * sizeof(d));
+	if (!sorted_d)
+		return -ENOMEM;
+	i = 0;
+	list_for_each_entry_safe(d, n, &dir->i_subdirs, d_child) {
+		list_del(&d->d_child);
+		sorted_d[i++] = d;
+	}
+	DBG_BUGON(i != nr_subdirs);
+	qsort(sorted_d, nr_subdirs, sizeof(d), comp_subdir);
+	for (i = 0; i < nr_subdirs; i++)
+		list_add_tail(&sorted_d[i]->d_child, &dir->i_subdirs);
+	free(sorted_d);
+
 	/* let's calculate dir size and update i_nlink */
 	d_size = 0;
 	i_nlink = 0;
@@ -922,6 +932,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
 	DIR *_dir;
 	struct dirent *dp;
 	struct erofs_dentry *d;
+	unsigned int nr_subdirs;

 	ret = erofs_prepare_xattr_ibody(dir);
 	if (ret < 0)
@@ -961,6 +972,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
 		return ERR_PTR(-errno);
 	}

+	nr_subdirs = 0;
 	while (1) {
 		/*
 		 * set errno to 0 before calling readdir() in order to
@@ -984,6 +996,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
 			ret = PTR_ERR(d);
 			goto err_closedir;
 		}
+		nr_subdirs++;

 		/* to count i_nlink for directories */
 		d->type = (dp->d_type == DT_DIR ?
@@ -996,7 +1009,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
 	}
 	closedir(_dir);

-	ret = erofs_prepare_dir_file(dir);
+	ret = erofs_prepare_dir_file(dir, nr_subdirs);
 	if (ret)
 		goto err;

--
2.25.1

Re: [PATCH v2] erofs-utils: use qsort() to sort dir->i_subdirs

[Gao Xiang]

On Mon, Apr 05, 2021 at 05:38:16PM +0800, Hu Weiwen wrote:
> Original implementation use insertion sort, and its time complexity is
> O(n^2). This patch use qsort instead. When I create a directory with
> 100k entries, this reduces the user space time from around 3 mins to
> 0.5s.
> 
> Create such a large directory for benchmark with:
> mkdir large; cd large; touch $(seq 100000);
> 
> Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>

This patch looks good to me, will test it later.

> ---
>  lib/inode.c | 53 +++++++++++++++++++++++++++++++++--------------------
>  1 file changed, 33 insertions(+), 20 deletions(-)
> 
> diff --git a/lib/inode.c b/lib/inode.c
> index d52facf..ef55e88 100644
> --- a/lib/inode.c
> +++ b/lib/inode.c
> @@ -96,21 +96,6 @@ unsigned int erofs_iput(struct erofs_inode *inode)
>  	return 0;
>  }
> 
> -static int dentry_add_sorted(struct erofs_dentry *d, struct list_head *head)
> -{
> -	struct list_head *pos;
> -
> -	list_for_each(pos, head) {
> -		struct erofs_dentry *d2 =
> -			container_of(pos, struct erofs_dentry, d_child);
> -
> -		if (strcmp(d->name, d2->name) < 0)
> -			break;
> -	}
> -	list_add_tail(&d->d_child, pos);
> -	return 0;
> -}
> -
>  struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
>  				   const char *name)
>  {
> @@ -122,7 +107,7 @@ struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
>  	strncpy(d->name, name, EROFS_NAME_LEN - 1);
>  	d->name[EROFS_NAME_LEN - 1] = '\0';
> 
> -	dentry_add_sorted(d, &parent->i_subdirs);
> +	list_add_tail(&d->d_child, &parent->i_subdirs);
>  	return d;
>  }
> 
> @@ -156,10 +141,19 @@ static int __allocate_inode_bh_data(struct erofs_inode *inode,
>  	return 0;
>  }
> 
> +static int comp_subdir(const void *a, const void *b)
> +{
> +	const struct erofs_dentry *da, *db;
> +
> +	da = *((const struct erofs_dentry **)a);
> +	db = *((const struct erofs_dentry **)b);
> +	return strcmp(da->name, db->name);
> +}
> +
> -int erofs_prepare_dir_file(struct erofs_inode *dir)
> +int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
>  {
> -	struct erofs_dentry *d;
> -	unsigned int d_size, i_nlink;
> +	struct erofs_dentry *d, *n, **sorted_d;
> +	unsigned int d_size, i_nlink, i;
>  	int ret;
> 
>  	/* dot is pointed to the current dir inode */
> @@ -172,6 +166,22 @@ int erofs_prepare_dir_file(struct erofs_inode *dir)
>  	d->inode = erofs_igrab(dir->i_parent);
>  	d->type = EROFS_FT_DIR;
> 
> +	/* sort subdirs */
> +	nr_subdirs += 2;
> +	sorted_d = malloc(nr_subdirs * sizeof(d));
> +	if (!sorted_d)
> +		return -ENOMEM;
> +	i = 0;
> +	list_for_each_entry_safe(d, n, &dir->i_subdirs, d_child) {
> +		list_del(&d->d_child);
> +		sorted_d[i++] = d;
> +	}
> +	DBG_BUGON(i != nr_subdirs);
> +	qsort(sorted_d, nr_subdirs, sizeof(d), comp_subdir);
> +	for (i = 0; i < nr_subdirs; i++)
> +		list_add_tail(&sorted_d[i]->d_child, &dir->i_subdirs);
> +	free(sorted_d);
> +
>  	/* let's calculate dir size and update i_nlink */
>  	d_size = 0;
>  	i_nlink = 0;
> @@ -922,6 +932,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
>  	DIR *_dir;
>  	struct dirent *dp;
>  	struct erofs_dentry *d;
> +	unsigned int nr_subdirs;
> 
>  	ret = erofs_prepare_xattr_ibody(dir);
>  	if (ret < 0)
> @@ -961,6 +972,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
>  		return ERR_PTR(-errno);
>  	}
> 
> +	nr_subdirs = 0;
>  	while (1) {
>  		/*
>  		 * set errno to 0 before calling readdir() in order to
> @@ -984,6 +996,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
>  			ret = PTR_ERR(d);
>  			goto err_closedir;
>  		}
> +		nr_subdirs++;
> 
>  		/* to count i_nlink for directories */
>  		d->type = (dp->d_type == DT_DIR ?
> @@ -996,7 +1009,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
>  	}
>  	closedir(_dir);
> 
> -	ret = erofs_prepare_dir_file(dir);
> +	ret = erofs_prepare_dir_file(dir, nr_subdirs);
>  	if (ret)
>  		goto err;
> 
> --
> 2.25.1
> 

Re: [PATCH v2] erofs-utils: use qsort() to sort dir->i_subdirs

[Li GuiFu via Linux-erofs]

Hu Weiwen
  It really do a high sort performance increase,
  I have a idea that keeping the erofs_prepare_dir_file() function
paramter stable, Using a independent function to do dirs sort.

On 2021/4/5 17:38, Hu Weiwen wrote:
> Original implementation use insertion sort, and its time complexity is
> O(n^2). This patch use qsort instead. When I create a directory with
> 100k entries, this reduces the user space time from around 3 mins to
> 0.5s.
> 
> Create such a large directory for benchmark with:
> mkdir large; cd large; touch $(seq 100000);
> 
> Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
> ---
>  lib/inode.c | 53 +++++++++++++++++++++++++++++++++--------------------
>  1 file changed, 33 insertions(+), 20 deletions(-)
> 
> diff --git a/lib/inode.c b/lib/inode.c
> index d52facf..ef55e88 100644
> --- a/lib/inode.c
> +++ b/lib/inode.c
> @@ -96,21 +96,6 @@ unsigned int erofs_iput(struct erofs_inode *inode)
>  	return 0;
>  }
> 
> -static int dentry_add_sorted(struct erofs_dentry *d, struct list_head *head)
> -{
> -	struct list_head *pos;
> -
> -	list_for_each(pos, head) {
> -		struct erofs_dentry *d2 =
> -			container_of(pos, struct erofs_dentry, d_child);
> -
> -		if (strcmp(d->name, d2->name) < 0)
> -			break;
> -	}
> -	list_add_tail(&d->d_child, pos);
> -	return 0;
> -}
> -
>  struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
>  				   const char *name)
>  {
> @@ -122,7 +107,7 @@ struct erofs_dentry *erofs_d_alloc(struct erofs_inode *parent,
>  	strncpy(d->name, name, EROFS_NAME_LEN - 1);
>  	d->name[EROFS_NAME_LEN - 1] = '\0';
> 
> -	dentry_add_sorted(d, &parent->i_subdirs);
> +	list_add_tail(&d->d_child, &parent->i_subdirs);
>  	return d;
>  }
> 
> @@ -156,10 +141,19 @@ static int __allocate_inode_bh_data(struct erofs_inode *inode,
>  	return 0;
>  }
> 
> +static int comp_subdir(const void *a, const void *b)
> +{
> +	const struct erofs_dentry *da, *db;
> +
> +	da = *((const struct erofs_dentry **)a);
> +	db = *((const struct erofs_dentry **)b);
> +	return strcmp(da->name, db->name);
> +}
> +
> -int erofs_prepare_dir_file(struct erofs_inode *dir)
> +int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
Todo 1: keep these function parameter stable

>  {
> -	struct erofs_dentry *d;
> -	unsigned int d_size, i_nlink;
> +	struct erofs_dentry *d, *n, **sorted_d;
> +	unsigned int d_size, i_nlink, i;
>  	int ret;
> 
>  	/* dot is pointed to the current dir inode */
> @@ -172,6 +166,22 @@ int erofs_prepare_dir_file(struct erofs_inode *dir)
>  	d->inode = erofs_igrab(dir->i_parent);
>  	d->type = EROFS_FT_DIR;
> 
> +	/* sort subdirs */
> +	nr_subdirs += 2;
> +	sorted_d = malloc(nr_subdirs * sizeof(d));
> +	if (!sorted_d)
> +		return -ENOMEM;
> +	i = 0;
> +	list_for_each_entry_safe(d, n, &dir->i_subdirs, d_child) {
> +		list_del(&d->d_child);
> +		sorted_d[i++] = d;
> +	}
> +	DBG_BUGON(i != nr_subdirs);
> +	qsort(sorted_d, nr_subdirs, sizeof(d), comp_subdir);
> +	for (i = 0; i < nr_subdirs; i++)
> +		list_add_tail(&sorted_d[i]->d_child, &dir->i_subdirs);
> +	free(sorted_d);
> +
Todo 2: make these codes refact to a independent function


>  	/* let's calculate dir size and update i_nlink */
>  	d_size = 0;
>  	i_nlink = 0;
> @@ -922,6 +932,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
>  	DIR *_dir;
>  	struct dirent *dp;
>  	struct erofs_dentry *d;
> +	unsigned int nr_subdirs;
> 
>  	ret = erofs_prepare_xattr_ibody(dir);
>  	if (ret < 0)
> @@ -961,6 +972,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
>  		return ERR_PTR(-errno);
>  	}
> 
> +	nr_subdirs = 0;
>  	while (1) {
>  		/*
>  		 * set errno to 0 before calling readdir() in order to
> @@ -984,6 +996,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
>  			ret = PTR_ERR(d);
>  			goto err_closedir;
>  		}
> +		nr_subdirs++;
> 
>  		/* to count i_nlink for directories */
>  		d->type = (dp->d_type == DT_DIR ?
> @@ -996,7 +1009,7 @@ struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
>  	}
>  	closedir(_dir);
> 
> -	ret = erofs_prepare_dir_file(dir);
> +	ret = erofs_prepare_dir_file(dir, nr_subdirs);
Todo 3 : nr_subdirs may not be needed, it can be get from one
for-loop-count fixly.
If it may cause perfermance decrease, try to add a dir count in the
erofs_inode struct


>  	if (ret)
>  		goto err;
> 
> --
> 2.25.1
> 

Re: [PATCH v2] erofs-utils: use qsort() to sort dir->i_subdirs

[Gao Xiang]

Guifu,

On Sun, Apr 11, 2021 at 10:10:09PM +0800, Li GuiFu via Linux-erofs wrote:
> Hu Weiwen
>   It really do a high sort performance increase,
>   I have a idea that keeping the erofs_prepare_dir_file() function
> paramter stable, Using a independent function to do dirs sort.
> 

I think Weiwen's implementation looks fine to me, if you tend to
not passing nr_subdirs as a cleaner solution, my suggestion would
be:
1) introduce a somewhat erofs_subdirs, which includes
   - a list_head for all subdir dentries generated from d_alloc;
   - a nr_subdirs count;
2) update erofs_d_alloc to
   erofs_d_alloc(struct erofs_subdirs *, const char *);
3) update erofs_prepare_dir_file to
   erofs_prepare_dir_file(struct erofs_inode *, struct erofs_subdir *).

Yet I'd like to apply the current solution first since it helps the
dir creation performance. If someone has interest to the solution
above, new cleanup is always welcomed.

Reviewed-by: Gao Xiang <xiang@kernel.org>

Thanks,
Gao Xiang

Re: [PATCH v2] erofs-utils: use qsort() to sort dir->i_subdirs

[Li GuiFu via Linux-erofs]

On 2021/4/11 22:41, Gao Xiang wrote:
> Guifu,
> 
> On Sun, Apr 11, 2021 at 10:10:09PM +0800, Li GuiFu via Linux-erofs wrote:
>> Hu Weiwen
>>   It really do a high sort performance increase,
>>   I have a idea that keeping the erofs_prepare_dir_file() function
>> paramter stable, Using a independent function to do dirs sort.
>>
> 
> I think Weiwen's implementation looks fine to me, if you tend to
> not passing nr_subdirs as a cleaner solution, my suggestion would
> be:
> 1) introduce a somewhat erofs_subdirs, which includes
>    - a list_head for all subdir dentries generated from d_alloc;
>    - a nr_subdirs count;
> 2) update erofs_d_alloc to
>    erofs_d_alloc(struct erofs_subdirs *, const char *);
> 3) update erofs_prepare_dir_file to
>    erofs_prepare_dir_file(struct erofs_inode *, struct erofs_subdir *).
> 
> Yet I'd like to apply the current solution first since it helps the
> dir creation performance. If someone has interest to the solution
> above, new cleanup is always welcomed.
> 
> Reviewed-by: Gao Xiang <xiang@kernel.org>
> 

ok, It is also good
Reviewed-by: Li Guifu <bluce.lee@aliyun.com>

Thanks,