In fact, if you use smarter compression than RLE, I wouldn't be surprised if the update was larger than the original binaries after the xor, as an offset xor will likely increase chaos (entropy) in the file, making it compresss worse than the original.
bsdiff was specifically designed to intelligently handle these situations, which is why it works.
Just tested it on Chromium from my package server (90.0.4430.72 vs 90.0.4430.212):
- Original binary: 266MB
- Gzipped binary: 106MB
- Gzipped XOR "patch": 228MB
- bsdiff patch: 47MB
XOR-and-RLE works well for binaries from non-HLL languages (assembler, mostly) where — due mostly to early assemblers' lack of support for forward-referencing subroutine labels from the data section — subroutines tend to ossify into having defined address-space positions.
You can observe this by the fact that IPS-patchfile representations (which, while a different algorithm, is basically equivalent to XOR-and-RLE in its results) of the deltas between different versions/releases of old game ROMs written in assembly, are actually rather small relative to the sizes of the ROM images themsleves. The v1.1 ROMs are almost always byte-for-byte identical in ROM-image layout to the v1.0 versions, except for where (presumably) explicit changes were made in the assembler source code. Translated releases are the same (sometimes, but not always, because they were actually done by the localization team bit-twiddling the original ROM, because they didn't have access to the original team's assembly code.)
(This is also why archives that contain all the various versions/releases of a given game ROM, are highly compressible using generic compressors like LZMA.)
That said, patches aren't really downloaded as standalone patches anymore because of Steam distribution. The way Steam handles it is documented, and if you're interested, it's available here: https://partner.steamgames.com/doc/sdk/uploading#Building_Ef...
But as an overview, Steam splits files into 1MB chunks and only downloads the 1MB chunks that have changed. The 1MB chunks are compressed in transit. Steam also dedups the 1MB chunks. I would assume that this works fine to manage the tradeoffs between size and efficiency.
Games are directories/packfiles containing many individual files, mostly binary art assets, plus one executable that takes up a negligible proportion of the total size. When binary art assets in the directory/packfile are updated between versions, they don't really "change" in the sense that a source-code file might be changed a git commit; instead, they get replaced. (I.e. every file change is essentially a 100% change.)
The "binary diff patching" you're talking about the game industry using, was just the result of xor-ing the old and new packfiles, and then RLE-encoding the result (so areas that were "the same" were then represented by an RLE symbol saying "run of zeros, length N"). For the particular choices being made, this is indeed much less bandwidth-efficient than just sending a new packfile containing the new assets, and then overlay-mounting the new packfile over the old packfile.
bsdiff isn't for directories full of files that get 100% rewritten on update. (There's already a pretty good solution to that — tar's differential archives, esp. as automated by a program like http://tardiff.sourceforge.net/tardiff-help.html .)
Instead, bsdiff is for updates to executable binaries themselves (think Chrome updates), or to disk images containing mostly executable binaries + library code (think OS sealed-base-image updates — like CoreOS; or, as mentioned above, macOS as of Catalina + APFS.)
In these cases, almost all the files that change, change partially rather than fully. Often with very small changes. The patches can be much smaller, if they're done on the level of e.g. individual compiled function that have changed within a library, rather than on the level of the entire library. (Also, more modern algorithms than xor+RLE can be used — and bsdiff does — but even xor + RLE would be a win here, given the shape of the data.)
There's also Google's Courgette (https://www.chromium.org/developers/design-documents/softwar...), which goes further in optimizing for this specific problem domain (diffing executable binaries), by having the diff tool understand the structure/format of executables well-enough to be able to create efficient patches for when functions are inserted, deleted, moved around, or updated such that their emitted code changes size — in other words, at times when the object code gets rearranged and jumps/pointers must be updated.
The goal of tools like bsdiff or Courgette isn't to reduce an update from 1GB to 200MB for ~10k customers. The goal is to reduce an update from 10MB to 50KB for 100 million customers. At those scales, you really don't want to be sending even a 10MB file if you can at-all help it. The server time required to crunch of the patch is more than paid off by your peering-bandwidth savings.