erofs-utils: use qsort() to sort dir->i_subdirs
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);
Link: https://lore.kernel.org/r/20210405093816.149621-1-sehuww@mail.scut.edu.cn
Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
Reviewed-by: Gao Xiang <xiang@kernel.org>
Reviewed-by: Li Guifu <bluce.lee@aliyun.com>
Signed-off-by: Gao Xiang <xiang@kernel.org>
1 file changed