Re: Speeding up Brotli Patch Generation w/ Custom Encoding

I'm also starting to look at some potentially related issues.

The required patch format is based on VCDIFF. I hadn't peeked at that format before but one of its main features is that it's agnostic to how the "windows" of the "source file" (for us, the previous subset) are mapped to the "target file" (the next subset) -- that's left up to the generator.

This is great for subsetting because we already know a good mapping: The window from the previous subset used as a source for the next subset should be the region generated from the same portion of the original, complete font file.

Accordingly, suppose when harfbuzz is generating a subset it additionally generates a file with a sequence of these records, in output file order:

  1.  Offset in subset file
  2.  Length in subset file
  3.  Offset in original file
  4.  Length in original file
  5.  (Optional:) "Final" flag, meaning that the portion won't change in future subsets (either because of gid stability or because the GIDs have the same mapping as the source file and can't change further).

With this info from the previous and next subset we can efficiently map the windows and therefore can diff only "within" those windows, instead of analyzing the two files to discover them. (With an accurate "Final" flag we can also skip the comparison and just copy those regions that are final in both subsets.) The cost will be the loss of additional, incidental file similarities but those should be relatively modest and somewhat addressed by compression.

Happily, this solution would also be compatible with the current required format. There are some details, such as combining sequential VCDIFF windows after diffing to lower their overhead, and potentially dealing with different patterns of original offset, length pairs, but those seem tractable.

Of course, this does require some additional harfbuzz functionality, which is what I'm starting to look into.

Skef
________________________________
From: Garret Rieger <grieger@google.com>
Sent: Monday, September 19, 2022 3:06 PM
To: w3c-webfonts-wg (public-webfonts-wg@w3.org) <public-webfonts-wg@w3.org>
Subject: Speeding up Brotli Patch Generation w/ Custom Encoding


EXTERNAL: Use caution when clicking on links or opening attachments.


After our discussions at TPAC I've been thinking about how we could speed up brotli patch generation by implementing custom brotli encoding logic (thanks Sergey and Dominik for the idea). It turns out that internally brotli uses the concept of a meta block<https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fhtml%2Frfc7932%23section-2&data=05%7C01%7Csiterum%40adobe.com%7Ce6303c9f8f46471db99b08da9a8b4d09%7Cfa7b1b5a7b34438794aed2c178decee1%7C0%7C0%7C637992220331735484%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=6iON2ADk4Vyo5ac8%2B9wCTFUpz3P%2B%2FsmEzhSHV%2BSOU9U%3D&reserved=0>, which can optionally contain a self contained block of compressed data<https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fhtml%2Frfc7932%23section-11.3&data=05%7C01%7Csiterum%40adobe.com%7Ce6303c9f8f46471db99b08da9a8b4d09%7Cfa7b1b5a7b34438794aed2c178decee1%7C0%7C0%7C637992220331735484%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=Z30%2F5xptlCEai3yPGWTWBYDj10oYmVDdlXFaFsuLmJo%3D&reserved=0>. This is great news as that then allows a server to easily incorporate precompressed data blocks into the generation of the brotli compressed stream.

I've started to document my thoughts on how we could actually apply this in a server implementation here: Speeding up Incremental Transfer Patch Generation<https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdocs.google.com%2Fdocument%2Fd%2F1MdtB_WPC2grAx3vFgLHA1-CqRzQtWj_cJYx40W2VQgI%2Fedit%3Fusp%3Dsharing&data=05%7C01%7Csiterum%40adobe.com%7Ce6303c9f8f46471db99b08da9a8b4d09%7Cfa7b1b5a7b34438794aed2c178decee1%7C0%7C0%7C637992220331735484%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=w2DaBOZMpOAjriqEzjGcO1wPe9xwowsNFJ75nJY93mE%3D&reserved=0>. The doc is still a work in progress, but the main ideas are there.

At a high level I believe we should be able to:

  *   Cache precompressed immutable segments of the original font for use during initial response generation.
  *   Cache precompressed blocks of glyph data to allow for fast compressed patch generation (for the first and subsequent requests) via concatenation..

Where run-time performance is a concern this should allow for significantly reduced computational requirements at the cost of potentially larger patches. The best part is that none of this would require any specification changes, this can all be done within the existing brotli patch mechanism. So this could eliminate the need for the addition of a third, new, patching format as discussed at the last meeting.

As next steps I'm looking into building a simplistic prototype to demonstrate the idea works and gather some initial data on performance and patch sizes.