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 <seh...@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 >