erofs-utils: lib: use bitmaps to accelerate bucket selection
authorGao Xiang <hsiangkao@linux.alibaba.com>
Fri, 3 Jan 2025 09:03:38 +0000 (17:03 +0800)
committerGao Xiang <hsiangkao@linux.alibaba.com>
Sat, 5 Apr 2025 16:25:21 +0000 (00:25 +0800)
commitd97c0017450b2cba82759c224f94c6d92501c321
treed852f2872c291ff384e847d23006b7094ff4e568
parenta42dc09f1dee5bb09bfcbcb9c2047c149614c6ab
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
include/erofs/cache.h
lib/cache.c