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> --- 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