Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Comparison with wimlib #16

Closed
chungy opened this issue Dec 3, 2020 · 6 comments
Closed

Comparison with wimlib #16

chungy opened this issue Dec 3, 2020 · 6 comments
Labels
documentation Improvements or additions to documentation

Comments

@chungy
Copy link

chungy commented Dec 3, 2020

DwarFS seems pretty nice. File access within the archive is quick. Main feature seems to be deduplication. Judging by resulting file sizes, I'm guessing this is based on whole file deduplication rather than being block-based?

Downside... DwarFS seems slow to make, compared to both wimlib wimcapture and squashfs.

Testing with a copy of every released Wine version, extracted by doing for tag in $(git tag); do git archive --prefix=$tag/ $tag | tar -xC /mnt/wine; done (requires, naturally, the Wine git repository):

$ time mkdwarfs -i wine -o wine.dwarfs
10:04:50.260867 scanning wine
10:04:59.692484 waiting for background scanners...
14:10:05.911222 assigning directory and link inodes...
14:10:06.312963 finding duplicate files...
14:10:11.475558 saved 53.69 GiB / 64.85 GiB in 2907224/3117413 duplicate files
14:10:11.475645 ordering 210189 inodes by similarity...
14:10:11.642889 210189 inodes ordered [167.2ms]
14:10:11.642926 assigning file inodes...
14:10:11.644702 building metadata...
14:10:11.644753 building blocks...
14:10:11.644802 saving names and links...
14:10:12.103973 updating name and link indices...
14:43:56.247557 waiting for block compression to finish...
14:43:56.247884 saving chunks...
14:43:56.275000 saving directories...
14:43:58.693785 waiting for compression to finish...
14:43:58.813425 compressed 64.85 GiB to 183.4 MiB (ratio=0.00276233)
14:43:59.328251 filesystem created without errors [1.675e+04s]
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
waiting for block compression to finish
scanned/found: 362904/362904 dirs, 0/0 links, 3117413/3117413 files
original size: 64.85 GiB, dedupe: 53.69 GiB (2907224 files), segment: 6.309 GiB
filesystem: 4.847 GiB in 311 blocks (1460981 chunks, 210189/210189 inodes)
compressed filesystem: 311 blocks/183.4 MiB written
█████████████████████████████████████████████████████████████████████████▏100% /

real	279m9.270s
user	26m17.945s
sys	3m53.332s
$ time mksquashfs wine wine.squashfs -comp zstd
Parallel mksquashfs: Using 12 processors
Creating 4.0 filesystem on wine.squashfs, block size 131072.
[=================================================================================|] 3284743/3284743 100%

Exportable Squashfs 4.0 filesystem, zstd compressed, data block size 131072
	compressed data, compressed metadata, compressed fragments,
	compressed xattrs, compressed ids
	duplicates are removed
Filesystem size 2074564.87 Kbytes (2025.94 Mbytes)
	3.04% of uncompressed filesystem size (68204545.10 Kbytes)
Inode table size 31817047 bytes (31071.33 Kbytes)
	28.29% of uncompressed inode table size (112449867 bytes)
Directory table size 28385936 bytes (27720.64 Kbytes)
	41.57% of uncompressed directory table size (68284423 bytes)
Number of duplicate files found 2907225
Number of inodes 3480317
Number of files 3117413
Number of fragments 47404
Number of symbolic links  0
Number of device nodes 0
Number of fifo nodes 0
Number of socket nodes 0
Number of directories 362904
Number of ids (unique uids + gids) 1
Number of uids 1
	chungy (1000)
Number of gids 1
	chungy (1000)

real	153m19.319s
user	89m22.676s
sys	2m14.197s
$ time wimcapture --unix-data --solid wine wine.wim
Scanning "wine"
64 GiB scanned (3117413 files, 362904 directories)    
Using LZMS compression with 12 threads
Archiving file data: 11 GiB of 11 GiB (100%) done

real	79m20.722s
user	42m30.817s
sys	1m37.350s
$ du wine.*
184M	wine.dwarfs
2.0G	wine.squashfs
173M	wine.wim

wimlib is significantly faster to create this massive archive than DwarFS, and the resulting file size is marginally smaller. Git itself stores the Wine history in about 310MB, though that's not the fairest of comparisons given git's delta-based storage and the inclusion of every interim commit between the releases too.

DwarFS still beats out this particular WIM archive for performance as a mounted file system, because I used solid compression and random access in wimlib is not fast in this circumstance. I also think (correct me if I'm wrong!) that a solid archive was the better comparison, since DwarFS seems to group like files together and compress them as one unit (311 blocks in this particular file system). wimcapture's mode compresses each stream individually and the archive size balloons up to 2.4GB while making random access much quicker.

@mhx
Copy link
Owner

mhx commented Dec 3, 2020

Hi @chungy, thanks for letting me know about wimlib! I'll be sure to include it in the benchmarks when I get some time!

I'm looking at your mkdwarfs run and it looks like it spends most of its time on the initial scan:

10:04:59.692484 waiting for background scanners...
14:10:05.911222 assigning directory and link inodes...

That's 4 solid hours. Whoa! Also, the actual CPU time spent by mkdwarfs is the least of the 3 candidates. This makes me wonder if the input data is stored on a slow drive, and some of the data gets cached during the first run and that speeds up the following runs? I'm not saying it is that, it could just as well be that the scanning strategy in mkdwarfs is horrible for slow drives, I haven't really had time to dig into this particular problem. But just to give you an idea, I've repeated your test and mkdwarfs finished compressing the 64G of wine source code in about 10 minutes... ;)

So here we go, mkdwarfs first, then mksquashfs, then wimcapture:

$ time ./mkdwarfs -i winesrc -o winesrc.dwarfs
09:21:15.310675 scanning winesrc
09:21:30.465686 waiting for background scanners...
09:24:10.473763 assigning directory and link inodes...
09:24:11.124776 finding duplicate files...
09:24:20.417065 saved 53.69 GiB / 64.85 GiB in 2907224/3117413 duplicate files
09:24:20.417153 ordering 210189 inodes by similarity...
09:24:20.655659 210189 inodes ordered [238.5ms]
09:24:20.655727 assigning file inodes...
09:24:20.661540 assigning device inodes...
09:24:20.744299 assigning pipe/socket inodes...
09:24:20.826927 building metadata...
09:24:20.826973 building blocks...
09:24:20.827050 saving names and links...
09:24:21.529395 updating name and link indices...
09:31:38.744146 waiting for block compression to finish...
09:31:38.744309 saving chunks...
09:31:38.797756 saving directories...
09:31:43.938137 waiting for compression to finish...
09:31:47.887444 compressed 64.85 GiB to 183.4 MiB (ratio=0.00276233)
09:31:48.657980 filesystem created without errors [633.3s]
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
waiting for block compression to finish
scanned/found: 362904/362904 dirs, 0/0 links, 3117413/3117413 files
original size: 64.85 GiB, dedupe: 53.69 GiB (2907224 files), segment: 6.309 GiB
filesystem: 4.847 GiB in 311 blocks (1460981 chunks, 210189/210189 inodes)
compressed filesystem: 311 blocks/183.4 MiB written
████████████████████████████████████████████████████████████████████████▏100% -

real    10m33.481s
user    43m46.202s
sys     3m45.483s

$ time ./mkdwarfs -i winesrc.dwarfs -o winesrc-l9.dwarfs -l 9 --recompress
09:37:55.658899 filesystem rewritten [277.9s]
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
filesystem: 4.847 GiB in 311 blocks (0 chunks, 0 inodes)
compressed filesystem: 311/311 blocks/126 MiB written
████████████████████████████████████████████████████████████████████████▏100% \

real    4m38.049s
user    47m49.684s
sys     1m6.820s

$ time mksquashfs winesrc winesrc.squashfs -comp zstd
Parallel mksquashfs: Using 12 processors
Creating 4.0 filesystem on winesrc.squashfs, block size 131072.
[=======================================================\] 3284743/3284743 100%

Exportable Squashfs 4.0 filesystem, zstd compressed, data block size 131072
        compressed data, compressed metadata, compressed fragments,
        compressed xattrs, compressed ids
        duplicates are removed
Filesystem size 2074550.26 Kbytes (2025.93 Mbytes)
        3.04% of uncompressed filesystem size (68204545.11 Kbytes)
Inode table size 31803457 bytes (31058.06 Kbytes)
        28.28% of uncompressed inode table size (112449867 bytes)
Directory table size 28385904 bytes (27720.61 Kbytes)
        41.57% of uncompressed directory table size (68284423 bytes)
Number of duplicate files found 2907225
Number of inodes 3480317
Number of files 3117413
Number of fragments 47404
Number of symbolic links  0
Number of device nodes 0
Number of fifo nodes 0
Number of socket nodes 0
Number of directories 362904
Number of ids (unique uids + gids) 2
Number of uids 1
        mhx (1000)
Number of gids 1
        users (100)

real    17m58.463s
user    181m25.736s
sys     2m30.018s

$ time wimcapture --unix-data --solid winesrc winesrc.wim
Scanning "winesrc"
64 GiB scanned (3117413 files, 362904 directories)    
Using LZMS compression with 12 threads
Archiving file data: 11 GiB of 11 GiB (100%) done

real    17m22.893s
user    84m47.557s
sys     2m12.384s

$ ll -hr --sort=size winesrc*.*
-rw-r--r-- 1 mhx users 127M Dec  3 09:37 winesrc-l9.dwarfs
-rw-r--r-- 1 mhx users 178M Dec  3 10:15 winesrc.wim
-rw-r--r-- 1 mhx users 184M Dec  3 09:31 winesrc.dwarfs
-rw-r--r-- 1 mhx users 2.0G Dec  3 09:57 winesrc.squashfs

So wimcapture and squashfs run at roughly the same speed, with wimcapture being significantly more CPU friendly. mkdwarfs still runs in 60% of the time, both wallclock and CPU, of wimcapture.

I also think (correct me if I'm wrong!) that a solid archive was the better comparison, since DwarFS seems to group like files together and compress them as one unit (311 blocks in this particular file system). wimcapture's mode compresses each stream individually and the archive size balloons up to 2.4GB while making random access much quicker.

By solid archive presumably you mean that in order to access a single file, you'd have to extract the whole archive, at least up to the point where the file you're looking for has been decompressed?

I think DwarFS is somewhere in the middle between a "classic" archive (each file compressed individually) and a solid archive. What it does is:

  • Order files by LSH similarity (or by whatever you want if you're willing to use the Lua interface)
  • Write file data to equally sized blocks (16 MiB by default), finding large (typically >2KiB) overlapping chunks in the files along the way and simply referencing them instead of writing them to the block again. This is a very poor man's compression, but it's good enough to save a pretty reasonably amount of data and has the advantage that fewer blocks have to be compressed/decompressed. So in this case, the fully decompressed DwarFS file system data is only 4.8 GiB compared to 11 GiB with wimlib.
  • Compress each of these blocks individually. So it's sort of a list of small solid archives. However, as the metadata is stored separately (and is typically stored uncompressed and practically needs close to no time to load), file data can be addressed directly and only the blocks containing the file's data need to be decompressed.

If you enable metadata compression, in this particular case you'll get a much smaller image as the metadata can be surprisingly well compressed. It's typically around 40%-50%, but in this instance it shrinks down to 20% and saves around 50 MiB. The only drawback of metadata compression is potentially slow mount time of the file system, and in this instance it seems to be well worth it.

@mhx
Copy link
Owner

mhx commented Dec 3, 2020

I did some more experiments with regards to scanning speed. I copied all wine versions from version 1.5 onwards to an EXT4-formatted 64GB SD card (I had to delete the earlier versions as the card wasn't big enough for all of them). This way I can make sure none of the data on the SD card is in the kernel cache simply by remounting the card. Also, it's a bit slower than my SSD that way.

Now, I wanted to ensure that I'm not doing something ridiculously stupid in mkdwarfs when scanning files, so I first ran

$ time tar cvf >(wc) /mnt/usb >tarfiles.txt 
tar: Removing leading `/' from member names

real    49m33.322s
user    0m48.919s
sys     3m51.369s

as a "gold standard" for how fast it is possible to consume all the data from the SD card. This is significantly longer than the 3 minutes it took mkdwarfs to scan the full tree of all versions from my SSD in the previous test, but that obviously had a large fraction of the data in the cache.

After unmounting/mounting the SD card:

$ time ./mkdwarfs -i /mnt/usb -o /dev/null 
13:01:37.141709 scanning /mnt/usb
13:06:40.736217 waiting for background scanners...
13:51:51.768286 assigning directory and link inodes...
13:51:52.167836 finding duplicate files...

I stopped it right there as that's when all the files have been scanned. That's the step that took 4 hours in your case. Here, it takes a bit more than 50 minutes (with ~20% less data), which is pretty much the same as what tar needed above, just that mkdwarfs has also computed two different sets of hash values along the way.

That all being said, I'm now quite certain that the slowness you saw with mkdwarfs was largely due to an I/O bottleneck.

@mhx mhx added the documentation Improvements or additions to documentation label Dec 4, 2020
@mhx
Copy link
Owner

mhx commented Dec 5, 2020

Hi @chungy, I just did some more reading through the wimcapture man page and it looks like --solid is actually doing a very similar thing to what DwarFS does. However, it uses a different block size by default (64 MiB, whereas DwarFS defaults to 16 MiB).

I'll do some more comparisons with matching block sizes and will add them to the documentation.

@mhx
Copy link
Owner

mhx commented Dec 6, 2020

I added some wimlib comparison & benchmarks to the documentation for the next release: https://github.com/mhx/dwarfs/tree/next-release#with-wimlib

@mhx mhx closed this as completed Dec 18, 2020
@mhx
Copy link
Owner

mhx commented Dec 19, 2020

Now in the main branch: https://github.com/mhx/dwarfs#with-wimlib

@mhx
Copy link
Owner

mhx commented Apr 6, 2021

FWIW, the latest release is about 5 times faster and also creates a significantly smaller image:

$ time mkdwarfs -i winesrc -o winesrc.dwarfs -l9
I 19:23:00.769309 scanning winesrc
I 19:23:58.497191 assigning directory and link inodes...
I 19:23:58.736385 waiting for background scanners...
I 19:23:58.739414 scanning CPU time: 202.3s
I 19:23:58.739458 finalizing file inodes...
I 19:24:03.023026 saved 53.69 GiB / 64.85 GiB in 2907224/3117413 duplicate files
I 19:24:03.030128 assigning device inodes...
I 19:24:03.075615 assigning pipe/socket inodes...
I 19:24:03.120688 building metadata...
I 19:24:03.120753 building blocks...
I 19:24:03.120835 saving names and symlinks...
I 19:24:03.121051 using a 4 KiB window at 256 B steps for segment analysis
I 19:24:03.121110 bloom filter size: 512 KiB
I 19:24:03.121181 ordering 210189 inodes using nilsimsa similarity...
I 19:24:03.134516 nilsimsa: depth=20000 (1000), limit=255
I 19:24:03.263653 updating name and link indices...
I 19:24:03.472861 pre-sorted index (354515 name, 75421 path lookups) [338.3ms]
I 19:25:09.210139 210189 inodes ordered [66.09s]
I 19:25:09.210193 waiting for segmenting/blockifying to finish...
I 19:25:09.848692 segmenting/blockifying CPU time: 44.52s
I 19:25:09.848773 bloom filter reject rate: 96.568% (TPR=1.390%, lookups=2084508585)
I 19:25:09.848815 segmentation matches: good=923206, bad=71173, total=999796
I 19:25:09.848855 segmentation collisions: L1=0.100%, L2=0.003% [9158338 hashes]
I 19:25:09.848902 saving chunks...
I 19:25:10.045947 saving directories...
I 19:25:10.626657 saving shared files table...
I 19:25:10.812261 saving names table... [12.18ms]
I 19:25:10.812334 saving symlinks table... [1.451us]
I 19:25:12.637675 waiting for compression to finish...
I 19:25:21.357412 compressed 64.85 GiB to 109.5 MiB (ratio=0.00164902)
I 19:25:21.715691 compression CPU time: 597.6s
I 19:25:21.715759 filesystem created without errors [140.9s]
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
waiting for block compression to finish
362904 dirs, 0/0 soft/hard links, 3117413/3117413 files, 0 other
original size: 64.85 GiB, dedupe: 53.69 GiB (2907224 files), segment: 8.973 GiB
filesystem: 2.184 GiB in 35 blocks (1523483 chunks, 210189/210189 inodes)
compressed filesystem: 35 blocks/109.5 MiB written [depth: 16405]
████████████████████████████████████████████████████████████████████████▏100% \

real    2m21.033s
user    13m47.990s
sys     1m46.581s

With more aggressive similarity ordering, the file size shrinks even more:

$ time mkdwarfs -i winesrc -o winesrc-l9-max.dwarfs -l9 --order=nilsimsa:255:250000:250000
[...]
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
waiting for block compression to finish
362904 dirs, 0/0 soft/hard links, 3117413/3117413 files, 0 other
original size: 64.85 GiB, dedupe: 53.69 GiB (2907224 files), segment: 9.083 GiB
filesystem: 2.073 GiB in 34 blocks (1613392 chunks, 210189/210189 inodes)
compressed filesystem: 34 blocks/75.1 MiB written [depth: 250000]
████████████████████████████████████████████████████████████████████████▏100% \

real    8m50.126s
user    15m27.058s
sys     1m44.213s

maxirmx added a commit to tamatebako/dwarfs-2 that referenced this issue Nov 4, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
documentation Improvements or additions to documentation
Projects
None yet
Development

No branches or pull requests

2 participants