Blog

Performance Corner: Small Changes Pack a Punch

Dec 14, 2021

SunnyFlunk

Distro Engineer

Here we have another round of changes to make packages smaller and show just how much we care about performance and efficiency! Today we are focusing mainly on moss-format changes to reduce the size of its payloads. The purpose of these changes is to reduce the size of packages, DB storage for transactions and memory usage for moss. These changes were made just before we moved out of bootstrap, so we wouldn’t have to rebuild the world after changing the format. Lets get started!

Squeezing Out the Last Blit of Performance

Blitting in Serpent OS is the process of setting up a root, using hardlinks of files installed in the moss store to construct the system /usr directory. Some initial testing showed buildPath using about 3% of the total events when installing a package with many files. As a system is made up of over 100,000 files, that’s a lot of paths that need to be calculated! Performance is therefore important to minimize time taken and power consumed.

After running a few benchmarks of buildPath, there were a few tweaks which could improve the performance. Rather than calculating the full path of the file, we can reuse the constant root path for each file instead, reducing buildPath events by 15%. Here we see some callgrind data from this small change (as it was difficult to pickup in the noise).

Before:
   48,766,347 ( 1.50%)  /usr/include/dlang/ldc/std/path.d:pure nothrow @safe immutable(char)[] std.path.buildPath
   34,241,805 ( 1.05%)  /usr/include/dlang/ldc/std/utf.d:pure nothrow @safe immutable(char)[] std.path.buildPath
   14,363,684 ( 0.44%)  /usr/include/dlang/ldc/std/range/package.d:pure nothrow @safe immutable(char)[] std.path.buildPath

After:
   40,357,800 ( 1.25%)  /usr/include/dlang/ldc/std/path.d:pure nothrow @safe immutable(char)[] std.path.buildPath
   29,523,966 ( 0.91%)  /usr/include/dlang/ldc/std/utf.d:pure nothrow @safe immutable(char)[] std.path.buildPath
   12,814,283 ( 0.40%)  /usr/include/dlang/ldc/std/range/package.d:pure nothrow @safe immutable(char)[] std.path.buildPath

Only Record What’s Needed!

Our Index Payload is used for extracting the Content Payload into its hashed file names. As it has one job (and then discarded), we could hone in on including only the information we needed. Previously an entry was a 32 byte key and storing a 33 byte hash. We have now integrated the hash as a ubyte[16] field, cut other unneeded fields so that we can fit the whole entry into 32 bytes. That’s a 51% reduction in the size of the Index Payload and about 25% smaller when compressed.

Before: Index [Records: 3688 Compression: Zstd, Savings: 60.61%, Size: 239.72 KB]
After:  Index [Records: 3688 Compression: Zstd, Savings: 40.03%, Size: 118.02 KB]

Too Many Entries Makes for a Large Payload

One of the bugbears about the Layout Payload, was the inclusion of Directory paths for every single directory. This is handy in that directories can be created easily before any files are included (to ensure they exist), but it comes at a price. The issue was twofold, the extra entries made inspecting the file list take longer and also made the Layout Payload larger than it needed to be. Therefore directories are no longer included as Layout entries with the exceptions of empty directories and directories with different permissions. Lets compare nano and glibc builds before and after the change:

nano
Before: Layout [Records: 174 Compression: Zstd, Savings: 80.58%, Size: 13.78 KB]
After:  Layout [Records:  93 Compression: Zstd, Savings: 73.49%, Size:  9.15 KB]

glibc
Before: Layout [Records: 7879 Compression: Zstd, Savings: 86.88%, Size: 755.00 KB]
After:  Layout [Records: 6813 Compression: Zstd, Savings: 86.24%, Size: 689.20 KB]

A surprisingly large impact from a small change, with 1,000 fewer entries for glibc and cutting the Layout Payload size of nano by a third. What it shows is that it’s hugely beneficial where locales are involved and % size reduction increases where you have fewer files. To give an example of how bad it could be, the KDE Frameworks package ktexteditor would have produced 300 entries in the Layout Payload, where 200 of those would have been for directories! I’d estimate a 50% reduction in the Layout Payload size for this package! Here’s an example of how a locale file used to be stored (where only the last line is added now).

  - /usr/share/locale [Directory]
  - /usr/share/locale/bg [Directory]
  - /usr/share/locale/bg/LC_MESSAGES [Directory]
  - /usr/share/locale/bg/LC_MESSAGES/nano.mo -> ec5b82819ec2355d4e7bbccc7d78ce60 [Regular]

This will be exceptionally useful for keeping the LayoutDB slimmer and faster as the number of packages grows.

Cutting Back 1 Byte at a Time

Next we removed recording the timestamps of files, which for reproducible builds, is often a number of little relevance as you have to force them all to a fixed number. As moss is de-duplicating for files, there’s a second issue where two packages could have different timestamps for the same hash. Therefore it was considered an improvement to simply exclude timestamps altogether. This improved install time as we no longer overwrite the timestamps and made the payload more compressible due to replacing it with 8 bytes of padding. Unfortunately we weren’t quite able to free up 16 bytes to reduce the size of each entry, but will be something to pursue in future.

Another quick improvement was reducing the lengths of paths for each entry. moss creates system roots and switches between them by changing the /usr symlink. Therefore, all system files need to be installed into /usr or they will not make up your base system. Therefore we have no need to store /usr in the Payload so we strip /usr/ from the paths (the extra / gives us another byte off!) which we recreate on install. This improved the uncompressed size of the Payload, with only a minor reduction when compressed.

Combined these result in about a 5% decrease in the compressed and uncompressed size of the Layout Payload.

Before: Layout [Records: 6812 Compression: Zstd, Savings: 86.24%, Size: 689.10 KB]
After: Layout [Records: 6812 Compression: Zstd, Savings: 86.20%, Size: 655.00 KB]

Storing the Hash Efficiently

Using the same method for the Index Payload, we are now storing the hash as ubyte[16], but not directly in the Payload Entry. This gives us a sizeable reduction of 17 bytes per entry which is the most significant of all the Layout Payload changes. As the extra space was unneeded, it compressed well so only resulted in a small reduction in the compressed Payload size.

Before: Layout [Records: 6812 Compression: Zstd, Savings: 86.20%, Size: 655.00 KB]
After: Layout [Records: 6812 Compression: Zstd, Savings: 83.92%, Size: 539.26 KB]

Hang On, Why am I Getting Faster Installation?

As a side-effect of small code rewrites to implement these changes, we’ve seen a nice decrease in time to install packages. There are fewer entries to iterate over with the removal of directories and buildPath is now only called once for each path. It goes to show that focusing on the small details leads to less, more efficient and faster code. Here we find that we have now essentially halved the number of events related to buildPath with all the changes resulting in about a 5% reduction in install time. Note that for this test, over 80% of time is spent in zstd decompressing the package which we haven’t optimized (yet!). Here’s another look the buildPath numbers factoring in all the changes:

Before:
   48,766,347 ( 1.50%)  /usr/include/dlang/ldc/std/path.d:pure nothrow @safe immutable(char)[] std.path.buildPath
   34,241,805 ( 1.05%)  /usr/include/dlang/ldc/std/utf.d:pure nothrow @safe immutable(char)[] std.path.buildPath
   14,363,684 ( 0.44%)  /usr/include/dlang/ldc/std/range/package.d:pure nothrow @safe immutable(char)[] std.path.buildPath

After:
   25,145,625 ( 0.79%)  /usr/include/dlang/ldc/std/path.d:pure nothrow @safe immutable(char)[] std.path.buildPath
   17,967,216 ( 0.57%)  /usr/include/dlang/ldc/std/utf.d:pure nothrow @safe immutable(char)[] std.path.buildPath
    7,761,417 ( 0.24%)  /usr/include/dlang/ldc/std/range/package.d:pure nothrow @safe immutable(char)[] std.path.buildPath

Summing it All Up

It was a pretty awesome weekend of work (a few weeks ago now), making some quick changes that will improve Serpent OS a great deal for a long time to come. This also means we have integrated all the quick format changes so we won’t have to rebuild packages while bringing up the repos.

Here’s a quick summary of the results of all these small changes:

• 51% reduction in the uncompressed size of the Index Payload
• 25% reduction in the compressed size of the Index Payload
• 29-50% reduction in the uncompressed size of the Layout Payload (much more with fewer files and more locales)
• 12-15% reduction in the compressed size of the Layout Payload
• 5% faster package installation for our benchmark (800ms to 760ms)

These are some pretty huge numbers and even excluded the massive improvements we made in the previous blog!

What if We Include the Previous Changes?

I’m glad you asked, cause I was curious too! Here we see a before and after with all the changes included. For the Layout Payload we see a ~45% reduction in the compressed and uncompressed size. For the Index Payload we have reduced the uncompressed size by 67% and the compressed size by 56%. Together resulting in halving the compressed and uncompressed size of the metadata of our stone packages!

Before:
Payload: Layout [Records: 5441 Compression: Zstd, Savings: 83.13%, Size: 673.46 KB] (113.61 KB compressed)
Payload: Index [Records: 2550 Compression: Zstd, Savings: 55.08%, Size: 247.35 KB] (111.11 KB compressed)

After:
Payload: Layout [Records: 4718 Compression: Zstd, Savings: 83.62%, Size: 374.42 KB] (61.33 KB compressed)
Payload: Index [Records: 2550 Compression: Zstd, Savings: 39.85%, Size: 81.60 KB] (49.01 KB compressed)

Now we proceed towards bringing up repos to enjoy our very efficient packages!

Tags:

• news

Out of the Bootstrap - Towards Serpent OS

Dec 2, 2021

SunnyFlunk

Distro Engineer

The initial stone packages that will seed the first Serpent OS repo have now been finalized! This means that work towards setting up the infrastructure for live package updates begins now. We plan on taking time to streamline the processes with a focus of fixing issues at the source. In this way we can make packaging fast and efficient so we can spend time working on features rather than package updates.

The End of Bootstrap

Bootstrapping a distribution involves building a new toolchain and many packages needed to support it. For us bootstrap was getting us to the point where we have built stone packages that we can use to start an initial repository with full working dependencies. This has been enabled by integrating dependencies into moss, creating the first repo index. Of note is that it is already enabled for 32bit support, so we have you covered there. While this is the end of bootstrap, the fun has only just begun!

Where to Next?

The next goal is to make Serpent OS self-hosting, where we can build packages in a container and update the repo index with the newly built packages. It is essentially a live repository accessible from the internet. There’s still plenty of improvements to be made with the tooling, but will soon enable more users to participate in bringing Serpent OS into fruition.

Becoming More Inclusive

While there’s a strong focus in Serpent OS on performance, the decision has been made to lower the initial requirements for users. Despite AVX2 being an older technology, there are still computers sold today that don’t support it. Because of this (and already having interested users who don’t have newer machines), the baseline requirement for Serpent OS will be x86_64-v2, which only requires SSE4.2.

It was always the plan to add support for these machines, just later down the track. In reality, this makes a lot more sense, as there will be many cases where building 2 versions of a package provides little value. This is where a package takes a long time to build and doesn’t result in a notable performance improvement. We will always need the x86_64-v2 version of a package to be compatible with the older machines. With this approach we can reduce the build server requirements without a noticeable impact to users as only a few packages you use will be without extra optimizations (and probably don’t benefit from them anyway).

I want to make it clear that this will be temporary, with impactful x86_64-v3+ packages rolling out as soon as possible. This change paves the way to integrate our technology stack taking care of your system for you and increases its priority. Users meeting the requirements of the x86_64-v3+ instruction set (this includes additional instructions beyond x86_64-v3) will automatically start installing these faster packages as they become available. Our subscriptions model will seamlessly take care of everything for you behind the scenes so you don’t need to read a wiki or forum to learn how to get these faster packages. We can utilize the same approach in future for our ARM stack, offering more optimized packages where it provides the most benefit.

Note that from the bootstrap, most packages built in under 15s and only three took longer than 2 minutes.

Trying Out Some Tweaks From the Get Go

While the project is young is a great time to test out new technologies. The use of clang and lld open up new possibilities to reduce file sizes, shorten load times and decrease memory usage. Some of these choices may have impacts on compatibility, so testing them out will be the best way to grasp that. Making sure that you can run apps like Steam is vital to the experience, so whatever happens we will make sure it works. The good news is that due to the unique architecture of Serpent OS, we can push updates that break compatibility with just a reboot, so if we ever feel the need to change the libc, we can make the change without you having to reinstall! More importantly, we can test major stack updates by rebooting into a staged update and go straight back to the old system, regardless of your file system.

Speed Packaging!

In the early days of the repository, tooling to make creating new packages as simple as possible is vital for efficiency. Spending some time automating as much of the process as possible will take weeks off bringing up Serpent OS. By making packaging as easy as possible will also help users when creating their own packages. While it would be faster to work around issues, the build tooling upgrades will benefit everyone.

The other way we’ll be speeding up the process is by holding back some of the tuning options by default. LTO for instance can result in much longer build times so will not initially be the default. The same is true for debug packages, where it slows down progress without any tangible benefit.

Things Are Happening!

We hope you are as excited as we are!

Tags:

• news

It All Depends

Nov 23, 2021

Ikey

Founder

It all depends.. it really does. On shared libraries.. interpreters.. pkg-config providers and packages. It’s the same story for all “package managers”, how do we ensure that the installed software has everything it needs at runtime?

Our merry crew has been involved in designing and building Linux distributions for a very, very long time, so we didn’t want to simply repeat history.

Thanks to many improvements across our codebase, including moss-deps, we automatically analyse the assets in a package (rapidly too) to determine any dependencies we can add without requiring the maintainer to list them. This is similar in nature to RPM’s behaviour.

As such we encode dependencies into our (endian-aware, binary) format which is then stored in the local installation database. Global providers are keyed for quick access, and the vast majority of packages will not explicitly depend on another package’s name, rather, they’ll depend on a capability or provider. For subpackage dependencies that usually depend on “NEVRA” equality (i.e. matching against a name with a minimum version, release, matching epoch and architecture), we’ll introduce a lockstep dependency that can only be resolved from its origin source (repo).

Lastly, we’ll always ensure there is no possibility for “partial update” woes. With these considerations, we have no need to support >= style dependencies, and instead rely on strict design goals and maintainer responsibility.

First and foremost!

The rapid move we’re enjoying from concept, to prototype, and soon to be fully fledged Linux distribution, is only possible with the amazing community support. The last few months have seen us pull off some amazing feats, and we’re now executing on our first public milestones. With your help, more and more hours can be spent getting us ready for release, and would probably help to insulate my shed office! (Spoiler: its plastic and electric heaters are expensive =))

The Milestones

We have created our initial milestones that our quite literally our escape trajectory from bootstrap to distro. We’re considerably closer now, hence this open announcement.

v0.0: Container (systemd-nspawn)

Our first release medium will be a systemd-nspawn compatible container image. Our primary driver for this is to allow us to add encapsulation for our build tool, boulder, permitting us to create distributable builder images to seed our infrastructure and first public binary repository.

v0.1: Bootable “image”

Once our build infra is up and running (honestly a lot of work has been completed for this in advance) we’ll work towards our first 0.1 image. This will initially target VM usage, with a basic console environment and tooling (moss, boulder, etc).

And then..

We have a clear linear path ahead of us, with each stage unlocking the next. During the development of v0.0 and v0.1 we’ll establish our build and test infrastructure, and begin hosting our package sources and binaries. At this point we can enter a rapid development cycle with incremental, and considerable improvements. Such as a usable desktop experience and installer.. :)

Recent changes

I haven’t blogged in quite a while, as I’ve been deep in the trenches working on our core features. As we’ve expressed before, we tend to work on the more complex systems first and then glue them together after to form a cohesive hole. The last few days have involved plenty of glue, and we now have distinct package management features.

Refactor

• Replaced defunct InstallDB with reusable MetaDB for local installation of archives as well as forming the backbone of repository support.
• Added ActivePackagesPlugin to identify installed packages
• Swapped non cryptographic hash usage with xxhash

Dependencies

• Introduced new Transaction type to utilise a directed acyclical graph for dependency solving.
• Reworked moss-deps into plugins + registry core for all resolution operations.
• Locally provided .stone files handled by CobblePlugin to ensure we depsolve from this set too.
• New Transaction set management for identifying state changes and ensuring full resolution of target system state.
• Shared library and interpreter (DT_INTERP) dependencies and producers automatically encoded into packages and resolved by depsolver.

Package Installation

We handle locally provided .stone packages passed to the install command identically to those found in a repository. This eliminates a lot of special casing for local archives and allows us to find dependencies within the provided set, before looking to the system and the repositories.

Dependency resolution is performed now for our package installation and is validated at multiple points, allowing a package like nano to depend on compact automatic dependencies:

  Dependency(DependencyType.SharedLibraryName, "libc.so.6(x86_64)");

Note our format and database are binary and endian aware. The dependency type only requires 1 byte of storage and no string comparisons.

List packages

Thanks to the huge refactor, we can now trivially access the installed packages as a list. This code will be reused for a list available command in future.

Example list installed output:

                   file (5.4) - File type identification utility
             file-32bit (5.4) - Provides 32-bit runtime libraries for file
       file-32bit-devel (5.4) - Provides development files for file-32bit
             file-devel (5.4) - Development files for file
                   nano (5.5) - GNU Text Editor

Inspect archives

For debugging and development purposes, we’ve moved our old “info” command to a new “inspect” command to work directly on local .stone files. This displays extended information on the various payloads and their compression stats.

For general users - the new info command displays basic metadata and package dependencies.

Package Removal

Upon generating a new system state, “removed” packages are simply no longer installed. As such no live mutation is performed. As of today we can now request the removal of packages from the current state, which generates a new filtered state. Additionally we remove all reverse dependencies, direct and transitive. This is accomplished by utilising a transposed copy of the directed acyclical graph, identifying the relevant subgraph and occluding the set from the newly generated state.

Lastly

The past few weeks have been especially enjoyable. I’ve truly had a fantastic time working on the project and cannot wait for the team and I to start offering our first downloads, and iterate as a truly new Linux distribution that borrows some ideas from a lot of great places, and fuses them into something awesome.

Keep toasty - this train isn’t slowing down.

Tags:

• news

Performance Corner: Faster Builds, Smaller Packages

Nov 5, 2021

SunnyFlunk

Distro Engineer

Performance Corner is a new series where we highlight to you some changes in Serpent OS that may not be obvious, but show a real improvement. Performance is a broad term that also covers efficiency, so things like making files smaller, making things faster or reducing power consumption. In general things that are unquestionably improvements with little or no downside. While the technical details may be of interest to some, the main purpose is to highlight the real benefit to users and/or developers that will make using Serpent OS a more enjoyable experience. Show me the numbers!

Here we focus on a few performance changes Ikey has been working on to the build process that are showing some pretty awesome results! If you end up doing any source builds, you’ll be thankful for these improvements. Special thanks to ermo for the research into hash algorithms and enabling our ELF processing.

Start From the Beginning

When measuring changes, it’s always important to know where you’re starting from. Here are some results from a recent glibc build, but before these latest changes were incorporated.

Payload: Layout [Records: 5441 Compression: Zstd, Savings: 83.13%, Size: 673.46 KB]
Payload: Index [Records: 2550 Compression: Zstd, Savings: 55.08%, Size: 247.35 KB]
Payload: Content [Records: 2550 Compression: Zstd, Savings: 81.46%, Size: 236.72 MB]
 ==> 'BuildState.Build' finished [4 minutes, 6 secs, 136 ms, 464 μs, and 7 hnsecs]
 ==> 'BuildState.Analyse' finished [21 secs, 235 ms, 300 μs, and 2 hnsecs]
 ==> 'BuildState.ProducePackages' finished [25 secs, 624 ms, 996 μs, and 8 hnsecs]

The build time is a little high, but a lot of that is due to a slow compiler on the host machine. But analysing and producing packages was also taking a lot longer than it needed to.

The Death of moss-jobs in boulder

In testing an equivalent build outside of boulder, the build stages were about 5% faster. Testing under perf, the jobs system was a bit excessive for the needs of boulder, polling for work when we already know the times when parallel jobs would be useful. Removing moss-jobs allowed for simpler codepaths using multiprocessing techniques from the core language. This work is integrated in moss-deps and the excess overhead of the build has now been eliminated.

Before:
 ==> 'BuildState.Build' finished [4 minutes, 6 secs, 136 ms, 464 μs, and 7 hnsecs]
 ==> 'BuildState.Analyse' finished [21 secs, 235 ms, 300 μs, and 2 hnsecs]
After:
[Build] Finished: 3 minutes, 53 secs, 386 ms, 306 μs, and 4 hnsecs
[Analyse] Finished: 8 secs, 136 ms, 22 μs, and 8 hnsecs

The new results reflect a 26s reduction in the overall build time. But only 13s of this relates to the moss-jobs removal. The other major change is making the analyse stage parallel in moss-deps (a key part of why we wanted parallelism to begin with). Decreasing the time from 21.2s to 8.1s is a great achievement despite it doing more work as we’ve also added ELF scanning for dependency information in-between these results.

New Hashing Algorithm

One of the unique features in moss is using hashes for file names which allows full deduplication within packages, the running system, previous system roots and for source builds with boulder. Initially this was hooked up using sha256, but it was proving to be a bit of a slowdown.

Enter xxhash, the hash algorithm by Yann Collet for use in fast decompression software such as lz4 and zstd (and now in many places!). This is seriously fast, with the potential to produce hashes faster than RAM can feed the CPU. The hash is merely used as a unique identifier in the context of deduplication, not a cryptographic verification of origin. XXH3_128bit has been chosen due to it having an almost zero probability of a collision across 10s of millions of files.

The benefit is actually two-fold. First of all, the hash length is halved from sha256, so there’s savings in the package metadata. This shouldn’t be understated as hash data is generally not as compressible as typical text and there are packages with a lot of files! Here the metadata for the Layout and Index payloads has reduced by 232KB! That’s about a 25% reduction with no other changes.

Before:
Payload: Layout [Records: 5441 Compression: Zstd, Savings: 83.13%, Size: 673.46 KB]
Payload: Index [Records: 2550 Compression: Zstd, Savings: 55.08%, Size: 247.35 KB]
After:
Payload: Layout [Records: 5441 Compression: Zstd, Savings: 86.66%, Size: 522.97 KB]
Payload: Index [Records: 2550 Compression: Zstd, Savings: 60.02%, Size: 165.75 KB]

Compressed this turns out to be about a 89KB reduction in the package size. For larger packages, this probably doesn’t mean much but could help a lot more with delta packages. For deltas, we will be including the full metadata of the Layout and Index payloads, so the difference will be more significant there.

The other benefit of course is the speed and the numbers speak for themselves! A further 6.4s reduction in build time removing most of the delay at the end of the build for the final package. This will also improve speeds for caching or validating a package.

Before:
 ==> 'BuildState.Analyse' finished [21 secs, 235 ms, 300 μs, and 2 hnsecs]
After:
[Analyse] Finished: 1 sec, 688 ms, 681 μs, and 8 hnsecs

With these changes combined, building packages can take 12x less time in the analyse stage, while reducing the size of the metadata and the overall package. We do expect the analyse time to increase in future as we add more dependency types, debug handling and stripping, but with the integrated parallel model, we can minimize the increase in time.

We’re Not Done Yet

The first installment of Performance Corner shows some great wins to the Serpent OS tools and architecture. This is just the beginning and there will likely be a follow up soon (you may have also noticed that it takes too long to make the packages), and there’s a couple more tweaks to further decrease the size of the metadata. Kudos to Ikey for getting these implemented!

Tags:

• news

Optimal File Locality

Oct 4, 2021

SunnyFlunk

Distro Engineer

File locality in this post refers to the order of files in our content payload. Yes that’s right, we’re focused on the small details and incremental improvements that combined add up to significant benefits! All of this came about from testing the efficiency of content payload in moss-format and how well it compared against a plain tarball. One day boulder was looking extremely inefficient and then retesting the following day was proving to be extremely efficient without any changes made to boulder or moss-format. What on Earth was going on?

Making Sure you Aren’t Going Crazy!

To test the efficiency our content payload, the natural choice was to compare it to a tarball containing the same files. When first running the test the results were quite frankly awful! Our payload was 10% larger than the equivalent tarball! It was almost unbelievable in a way, so the following day I repeated the test again only this time the content payload was smaller than the tarball. This didn’t actually make sense, I made the tarball with the same files, but only changed the directory it was created from. Does it really matter?

File Locality Really Matters!

Of course it does (otherwise it would be a pretty crappy blog post!). When extracting a .stone package it creates two directories, mossExtract where the sha256sum named files are stored and mossInstall where those files are hardlinked to their full path name. The first day I created the tarball from mossInstall and the second day I realised that creating the tarball from mossExtract would provide the closest match to the content payload since it was a direct comparison. When compressing the tarballs to match the .stone compression level, the tarball compressed from mossInstall was 10% smaller, despite the uncompressed tarball being slightly larger.

Compression Wants to Separate Apples and Oranges

In simplistic terms, the way compression works is comparing data that it’s currently reading versus data that it’s read earlier in the file. zstd has some great options like --long that increases the distance in which these matches can be made at the cost of increased memory use. To limit memory use while making compression and decompression fast, it takes shortcuts that reduce the compression ratio. For optimal compression, you want files that are most similar to each other to be as close as possible. You won’t get as many matches from a text file to an ELF file as you would from a similar looking text file.

Spot the Difference

Files in mossExtract are listed in their sha256sum order, which is basically random, where files in mossInstall are ordered by their path. Sorting files by path actually does some semblance of sorting where binaries are in /usr/bin and libraries are in /usr/lib bringing them closer together. This is in no way a perfect order, but is a large improvement on a random order (up to 10% in our case!).

Our glibc package has been an interesting test case for boulder, where an uncompressed tarball of the install directory was just under 1GB. As boulder stores files by their sha256sum, it is able to deduplicate files that are the same even when the build hasn’t used symlinks or hardlinks to prevent the wasted space. In this case, the deduplication reduced the uncompressed size of the payload by 750MB alone (that’s a lot of duplicate locale data!). In the python package, it removes 1,870 duplicate cache files to reduce the installation size.

As part of the deduplication process boulder would sort files by sha256sum to remove duplicate hashes. If two files have the same sha256sum, then only one copy needs to be stored. It also felt clean with the output of moss info looking nice where the hashes are listed in alphabetical order. But it was having a significant negative impact on package sizes so that needed to be addressed by resorting the files by path order (a simple one-liner), making the content payload more efficient than a tarball once again.

Compression Level	sha256sum Order	File path Order
1	72,724,389	70,924,858
6	65,544,322	63,372,056
12	49,066,505	44,039,782
16	45,365,415	40,785,385
19	26,643,334	24,134,820
22	16,013,048	15,504,806

Testing has shown that higher compression levels (and enabling --long) is more forgiving of a suboptimal file order (3-11% smaller vs only 2-5% smaller when using --long). The table above is without --long so the difference is larger.

Hang On, Why Don’t You…

There’s certainly something to this and sorting by file order is a first step. In future we can consider creating an efficient order for files to improve locality. Putting all the ELF, image or text files together in the payload will help to shave a bit off our package sizes at only the cost to sort the files. However, we don’t want to go crazy here, the biggest impact on reducing package sizes will be using deltas as the optimal package delivery system (and there will be a followup on this approach shortly). The moss-format content payload is quite simple and contains no filenames or paths in it. Therefore it’s effectively costless to switch around the order of files, so we can try out a few things and see what happens.

An Academic Experiment

To prove the value of moss-format and the content payload, I tried out some crude sorting methods and their impact on compression for the package. As you want similar files chunked together, it divided the files into 4 groups, still sorted by their path order in their corresponding chunk:

• gz: gzipped files
• data: non-text files that weren’t ELF
• elf: ELF files
• text: text files (bash scripts, perl etc)

As the chart shows, you can get some decent improvements from reordering files within the tarball when grouping files in logical chunks. At the highest compression level, the package is reduced by 0.83% without any impact on compression or decompression time. In the compression world, such a change would be greatly celebrated!

Also important to note was that just moving the gzipped files to the front of the payload was able to capture 40% of the size improvement at high compression levels, but had slightly worse compression at levels 1-4. So simple changes to the order (in this case moving non-compressible files to the edge of the payload) can provide a reduction in size at the higher levels that we care about. We don’t want to spend a long time analyzing files for a small reduction in package size, so we can start off with some basic concepts like this. Moving files that don’t compress a lot such as already compressed files, images and video to the start of payload meaning that the remaining files are closer together. We also need to test out a broader range of packages and the impact any changes would have on them.

Food For Thought?

So ultimately the answer to the original question (was moss-format efficient?), the answer is yes! While there are some things that we still want to change to make it even better, in its current state package creation time was faster and overheads were lower than with compressing an equivalent tarball. The compressed tarball at zstd -16 was 700KB larger than the full .stone file (which contains a bit more data than the tarball).

The unique format also proves its worth in that we can make further adjustments to increase performance, reduce memory requirements and reduce package sizes. What this experiment shows is that file order really does matter, but using the basic sorting method of filepath gets you most of the way there and is likely good enough for most cases.

Here are some questions we can explore in future to see whether there’s greater value in tweaking the file order:

• Do we sort ELF files by path order, file name or by size?
• Does it matter the order of chunks in the file? (i.e. ELF-Images-Text vs Images-Text-ELF)
• How many categories do we need to segregate and order?
• Can we sort by extension? (i.e. for images, all the png files will be together and the jpegs together)
• Do we simply make a couple of obvious changes to order and leave zstd to do the heavy lifting?

Tags:

• news

Newer posts

Older posts