Use JS ZIP library instead of WASM LibZip

[101arrowz]

There is little point to using LibZip because in Yarn, Node.js Zlib is used for decompression and the ZIP format itself is very cheap to parse. In fact, a JavaScript ZIP library will easily outperform LibZip when used in Yarn due to the cost of the WASM-JS boundary and the need for excessive memory copying when using WASM instead of JS. I ran a test comparing LibZip with fflate, a fast compression library with both a JS DEFLATE implementation and the potential to use custom (de)compressors.

Here's a small benchmark for decompression performance:

Code used

// Error checking isn't done in LibZip for the sake of simplicity,
// but if anything that will only make it slower

const libzip = require('@yarnpkg/libzip').getLibzipSync();
const zlib = require('zlib');
const fflate = require('fflate'), fs = require('fs');
let ts = Date.now();
const zip = libzip.open(process.argv[2]), nEntries = libzip.getNumEntries(zip, 0);
for (let i = 0; i < nEntries; ++i) {
  const file = libzip.fopenIndex(zip, i, 0, libzip.ZIP_FL_COMPRESSED);
  const stat = libzip.struct.statS();
  libzip.statIndex(zip, i, 0, 0, stat);
  const size = libzip.struct.statCompSize(stat);
  const compMethod = libzip.struct.statCompMethod(stat);
  const ptr = libzip.malloc(size);
  libzip.fread(file, ptr, size, 0);
  const data = Buffer.from(libzip.HEAPU8.subarray(ptr, ptr + size));
  console.log(libzip.getName(zip, i, 0), compMethod == 0
    ? data
    // To use the JS decompression:
    // : fflate.inflateSync(data)
    // Native decompression
    : zlib.inflateRawSync(data));
}
console.log(Date.now()-ts);
ts = Date.now();
let last = false;
let cnt = 0;
const uz = new fflate.Unzip(file => {
  ++cnt;
  const chks = [];
  file.ondata = (err, dat, final) => {
    chks.push(dat);
    if (final) {
      const out = Buffer.concat(chks);
      console.log(file.name, out);
      if (--cnt == 0 && last) {
        console.log(Date.now()-ts);
      }
    }
  };
  file.start();
});
class NativeInflate {
  constructor() {
    this.dcmp = zlib.createInflateRaw()
    let lastChunk;
    this.dcmp.on('data', dat => {
      if (lastChunk) this.ondata(null, lastChunk, false);
      lastChunk = dat;
    })
    this.dcmp.on('end', () => {
      this.ondata(null, lastChunk || new Uint8Array(0), true);
    })
  }
  push(data, final) {
    this.dcmp.write(data);
    if (final) this.dcmp.end()
  }
  static compression = 8;
}

// This line uses fflate's compression algorithm:
// uz.register(fflate.AsyncUnzipInflate);
// It's slower than the native version, only necessary in browsers
// (Don't think that applies to Yarn, but just in case)
// For synchronous, main-thread decompression, fflate.UnzipInflate instead

// This uses native Zlib
uz.register(NativeInflate);
const strm = fs.createReadStream(process.argv[2])
strm.on('data', dat => uz.push(dat));
strm.on('end', () => {
  uz.push(new Uint8Array(0));
  last = true;
});

Decompression performance	LibZip (JS Zlib)	LibZip (native Zlib)	fflate (JS Zlib)	fflate (native Zlib)
65kB NPM package	41ms	14ms	30ms	7ms
3.2MB large NPM package	200ms	47ms	290ms	34ms
353MB binary data	3428ms	1430ms	1401ms	738ms

Clearly, the decompression is the major factor, since both fflate and LibZip decrease the time taken by similar amounts using the native Zlib program over a JS implementation. However, the WASM overhead means fflate is always faster. The few discrepancies are due to the higher performance of the JS implementation when decompressing in memory as opposed to decompressing streamed data. The ability to optionally utilize data streaming is yet another benefit of using a JS library over LibZip.

Obviously there are more implementation details (such as saving any changes back into the archive, using append mode when adding files and overwriting when modifying, making the code less ugly) but I'd be willing to create a PR with fflate, archiver, or some other ZIP library in JS, since it's almost guaranteed to be faster than WASM.

[arcanis]

Thanks for the exact numbers, it's a nice reference. For context, it's been suggested before (by @andreialecu I believe), but the pushback I made at the time was that having two different zip implementations inside the core would increase the maintenance surface while giving us less control over the implementation (we'll always need to provide an fs-like API, and libzip happens to provide all the tools we need; using a different library would require its adapter to support the same functions). It's still a worry I have, although the numbers are tempting.

[101arrowz]

@merceyz AFAIK Node.js Zlib yields consistent outputs for GZIP (as long as you don't use the current time in the header), Zlib, and DEFLATE data. I haven't found any instances of compressed data changing over time when recompressing the same file. Do you have a reproducible example?

[arcanis]

Cf what happened here: npm/cli#2846 (comment)

Generally speaking we can't rely on native file generation for compression¹, because 1/ we won't control it at all 2/ we would be the ones to have to deal with the fallout of any divergence 3/ we'd likely have no way to fix such a problem once identified. Even if divergences are unlikely, the risk isn't worth it.

¹ That's unless the algorithm explicitly defines "pure function" as one of its features, but afaik this isn't the case for Node (which makes sense, considering the parallelism mentioned in the post I linked).

[andreialecu]

Would be interesting to see a benchmark for compression for zlib vs your custom js compression implementation @101arrowz .

but the pushback I made at the time was that having two different zip implementations inside the core would increase the maintenance surface

This could be mitigated by always using a JS based implementation to handle the ZIP format itself (headers, etc), but defer to libzip just for the stream compression part if necessary.

Since decompression should always produce the same results, and yarn actually uses zlib for that anyway, the impact would be minimal.

The main benefit would be that .pnp.cjs will not need to load WASM and would likely be substantially simpler.

[arcanis]

I'd certainly be interested to see what it'd look like, although I can't guarantee we'd end up using it (really depends on the perceived maintenance cost, I think). If someone is interested to go this way, the main thing you'll need to do is reimplement the FakeFS interface. For test you can just reimplement the method from ZipFS instead of creating a new class (we do a few instanceof checks if I remember correctly):

https://github.com/yarnpkg/berry/blob/master/packages/yarnpkg-fslib/sources/ZipFS.ts

[101arrowz]

@andreialecu fflate is significantly slower, despite all the micro-optimizations I employed, at cold start. However, over time it becomes way faster due to V8 warmup, and can eventually approach zlib. On very large files, or when matching output size (because fflate often yields smaller outputs), fflate can actually be much faster, but for the sake of comparison, I've provided specific benchmarks at compression level 1 (time in milliseconds)

{
  "fflate.deflate.cold": {
    "basic": 37,
    "text": 103,
    "smallImage": 208,
    "image": 450,
    "largeImage": 1254
  },
  "fflate.deflate.warm": {
    "basic": 0,
    "text": 35,
    "smallImage": 115,
    "image": 362,
    "largeImage": 1092
  },
  "zlib.deflate.cold": {
    "basic": 26,
    "text": 44,
    "smallImage": 105,
    "image": 262,
    "largeImage": 992
  },
  "zlib.deflate.warm": {
    "basic": 0,
    "text": 20,
    "smallImage": 90,
    "image": 202,
    "largeImage": 820
  }
}

Cold is after no warmup, i.e. the first run.
Warm is after compressing 5 files as warmup, at which both algorithms are close to fully optimized. Obviously, Zlib improves less because it's a native module.

Of course, for decompression, you shouldn't even consider fflate since you won't have any issues with binary mismatching when using zlib, and it's way faster. After all, I made fflate mainly for the browser, where the only alternative is WebAssembly, and as a matter of fact WASM (de)compression is slower than JS by a long shot (2-3x) because of the cost of transferring data over the WASM boundary.

[andreialecu]

Here's a past discussion on this topic https://discord.com/channels/226791405589233664/226793713722982400/777955526365544488

Thanks for providing benchmark numbers, and for pointing to fflate. I'm also in heavy support of this idea. I even started a quick and dirty prototype js zip implementation for this purpose that I didn't finish (https://github.com/andreialecu/tszip).

It would be interesting to see if the pure js implementation also parallelizes better. I suspect that yarn could take more advantage of it, and a pure js+zlib implementation would scale better.

[101arrowz]

That's true. I would then ask why the files aren't just expanded out rather than stored in a ZIP? The main point of ZIP is to provide single-file representation of multiple files; some compressed and others not. If there is no compression, and the files need to be split up anyway when accessing via the virtual FS, why use a ZIP?

[andreialecu]

I think the main reason would be the number of changes that needs to be tracked by source control systems. ZIP files encapsulate a package inside a single file.

Having hundreds to tens of thousands of changes active (which could easily happen when adding/removing/upgrading packages) would likely result in big problems for git.

Also see: nodejs/node#36812 (comment)

[arcanis]

It's also useful for atomicity and speed. Packages can be cached on disk and often moved in a single fs operation, which wouldn't be the case when expended. Copying them from the cache to the projects would also have an heavy cost in raw amount of IO operations. That's how the cache worked in v1, and it came with too many problems that zip solved in one fell swoop.

[101arrowz]

I highly recommend switching to a tarfile or similar format in that case. It's way more lightweight to parse than ZIP and, if necessary, can be compressed all at once rather than a file at a time. In all honesty, perhaps the Yarn team could develop a custom format that specifically meets Yarn's needs, since in theory end-users won't need to mess with their dependencies except when using yarn patch.

[arcanis]

Tar isn't a suitable format as we have a strong need for arbitrary file access (tar would require to unpack the whole archive to access one file). Using zip is less efficient in terms of size than other formats, but has the advantage of being very widely supported, including by OS and file explorers. While not necessary, it certainly adds a lot of value to the file format.

[larixer]

I have carried out experiment whether we will have perf boost due to zip in JS implementation compared to wasm libzip, the answer is no:
#3228