erofs-utils: lib: use bitmaps to accelerate bucket selection
Instead of looping over bucket lists directly, maintain bitmaps
for more efficient greedy selection.
ILSVRC2012_img_train.tar (1,281,168 inodes) [1]
uncompressed EROFS (vanilla): 147,059,949,568B 36m29.529s
uncompressed EROFS (patched): 147,059,511,296B 1m14.920s
ILSVRC2012_img_val.tar (50,001 inodes) 6,744,924,160B [2]
uncompressed EROFS (vanilla): 6,713,278,464B 29.998s
uncompressed EROFS (patched): 6,713,188,352B 23.753s
[1] https://image-net.org/data/ILSVRC/2012/ILSVRC2012_img_train.tar
$ mkdir train; tar -xOf ILSVRC2012_img_train.tar | tar -xi -C train
[2] https://image-net.org/data/ILSVRC/2012/ILSVRC2012_img_vol.tar
$ mkfs.erofs --tar=f --sort none foo.erofs ILSVRC2012_img_vol.tar
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
Link: https://lore.kernel.org/r/20250103090338.740593-5-hsiangkao@linux.alibaba.com