How to get the file ordering *after* compression ?

[T-3B]

I wanted to know which file order DwarFS choose. As mkdwarfs does not report the nilsimsa-sorting result, I thought I could dwarfsck:

$ dwarfsck -d directory_tree in.dwarfs
created by: libdwarfs v0.14.1
created on: 2026-02-09 17:52:43
<inode:0> ---drwxr-xr-x (12 entries, parent=0)
  <inode:8> ----rw-r--r-- dickens [60, 88] 10192446
  <inode:12> ----rw-r--r-- mozilla [234, 593] 51220480
  <inode:6> ----rw-r--r-- mr [30, 59] 9970564
  <inode:10> ----rw-r--r-- nci [161, 214] 33553445
  <inode:2> ----rw-r--r-- ooffice [20, 25] 6152192
  <inode:7> ----rw-r--r-- osdb [59, 60] 10085684
  <inode:3> ----rw-r--r-- reymont [25, 27] 6627202
  <inode:9> ----rw-r--r-- samba [88, 161] 21606400
  <inode:4> ----rw-r--r-- sao [27, 29] 7251944
  <inode:11> ----rw-r--r-- webster [214, 234] 41458703
  <inode:5> ----rw-r--r-- x-ray [29, 30] 8474240
  <inode:1> ----rw-r--r-- xml [0, 20] 5345280

I really thought this output was sorted alphabetically, and that inodes number were the actual ordering.
But I was plain wrong, as giving my own file ordering managed to make the archive smaller. The only difference I see with that smaller archive, is the number in squared brackets [60, 88], for which none the help message nor the man page says what it represents.

This is simply the silesia corpus, and no option were given (all defaults).

[mhx]

I wanted to know which file order DwarFS choose.

There actually isn't a way to do this. See below for details.

I really thought this output was sorted alphabetically, and that inodes number were the actual ordering.

That output is asciibetically ordered, but the inode numbers don't have an extra meaning attached to them. They are guaranteed to be consistent across multiple runs when using the same options, but that's about it.

But I was plain wrong, as giving my own file ordering managed to make the archive smaller.

That doesn't really come as a surprise. Nilsimsa works fine on average, but it is by no means perfect.

The only difference I see with that smaller archive, is the number in squared brackets [60, 88], for which none the help message nor the man page says what it represents.

True, that output isn't really documented at the moment. The two numbers in square brackets are the begin and end indices of the chunk range for the inode (see the metadata format description). But chunks can reference block data in any order, so that won't help much either.

The reason there's no output of an overall file order is that there isn't really one well-defined "overall file order". Nilsimsa ordering is done per-stream (i.e. per category). Each file can be decomposed into multiple fragments by the categorizers, each of which can end up in a different stream, and each fragment can be ordered differently within its stream. So there isn't really "one" order in this case. Also, since multiple segmenter streams are later merged into a single stream of file system blocks, this would potentially require the previously determined fragment order(s) to be updated somehow. Finally, this still leaves the problem that in each stream, a fragment A that is nilsimsa-ordered after fragment B can refer to data in fragment C which itself is nilsimsa-ordered before A.

That being said, when dwarfsextract extracts a DwarFS image, or when using dwarfsck --checksum, file system entries are approximately ordered by the block number of the first chunk to improve cache hit rate during extraction. But this doesn't account for e.g. ordering of multiple files within a single file system block, as it's irrelevant for the use case.

It would certainly be possible to output per-stream fragment order. If you only have a single stream (i.e. no categorizers enabled), you can already get that indirectly by enabling --log-level=trace and looking for "adding fragment" output from the segmenter:

mkdwarfs -i /usr/include/fuse3 -o /dev/null --force --log-level=trace 2>&1 | grep 'adding fragment'  
T 15:07:42.094076 [segmenter.cpp:1530] adding fragment at offset 0 of inode 6 [fuse_lowlevel.h] - size: 76739
T 15:07:42.094687 [segmenter.cpp:1530] adding fragment at offset 0 of inode 5 [fuse.h] - size: 49015
T 15:07:42.095055 [segmenter.cpp:1530] adding fragment at offset 0 of inode 4 [fuse_common.h] - size: 37021
T 15:07:42.095339 [segmenter.cpp:1530] adding fragment at offset 0 of inode 3 [fuse_opt.h] - size: 7549
T 15:07:42.095394 [segmenter.cpp:1530] adding fragment at offset 0 of inode 1 [fuse_log.h] - size: 2244
T 15:07:42.095411 [segmenter.cpp:1530] adding fragment at offset 0 of inode 2 [cuse_lowlevel.h] - size: 2573
T 15:07:42.095447 [segmenter.cpp:1530] adding fragment at offset 0 of inode 0 [libfuse_config.h] - size: 275

[T-3B]

Thanks for your reply, I completely missed the blocks fragmentation.
I also found that dwarfsextract -i raspbian-9.dwarfs -f ustar will write the files in the almost same order as explicitely given when creating the image with --order none.
In my silesia corpus example, there's only a single swap between adjacent files (there are 12 files in total).

As a side note, in my limited testing, binsort -o 1000 always beats dwarfs sorting, but is also quite slower. They're apparently using simHash distance.

[mhx]

I also found that dwarfsextract -i raspbian-9.dwarfs -f ustar will write the files in the almost same order as explicitely given when creating the image with --order none.

Yes, that is what I was referring to earlier when I said the entries are "approximately ordered" when extracting.

As a side note, in my limited testing, binsort -o 1000 always beats dwarfs sorting, but is also quite slower. They're apparently using simHash distance.

Interesting, I didn't know about either of those!

I'm sure there's still plenty of room for improvement in the area or similarity sorting. Nilsimsa (the similarity hash used by DwarFS), as far as I know, was primarily aimed at emails, so might not perform very well for other data. However, the fact that it uses a fixed hash size means its digests are cheap to store and compare.

One issue with binsort seems to be that "Results are not stable with more than one thread". I've spent quite a bit of effort to make nilsimsa sorting multi-threaded and stable at the same time.

If you have lots of input files, you can tweak some settings to try to improve similarity ordering quality.