There's a collection of articles they wrote talking about regexes and various pitfalls: https://swtch.com/~rsc/regexp/
1#token
/ *, */
This is, I also think, another reason why "simple" text protocols are not really so simple. The grammar above is "trivial", and yet, this is the end result. I don't feel like the library is particularly at fault: I doubt I would have caught this in code review.
That's an odd thing about the tech world, it's accessible. As you get better in different areas you are actually more and more likely to make contact with important people (big names? people who did important stuff?). This can creep up on you if you're not aware what level you're operating at. It can be a small world.
about 15 minutes later Guido van Rossum answered my question.
It's amazing how often doing this completely bypasses any corporate first-line-support structure in the way, and just puts the email right into the inbox of the line engineers working directly on the product. It's also amazing how quickly those line engineers reply. (It's as if they treat "replying to random messages on the product mailing list" as their highest-priority job. Or maybe it's just that they're technical people, and my questions are usually very nerd-snipe-y, and get them hooked.)
My point was that there are often public mailing lists, where engineers with real engineering problems could discuss those problems with the engineers responsible for the product/service; and yet the engineer with the problem nevertheless doesn't even think of using the mailing list to reach out, but instead decides to go through regular customer-service support channels to get their problem solved.
The point is that I shouldn't have to bypass the official channels that way. These organisations are operating at the level of ad-hoc individual heroics, which is the lowest tier in terms of organisational maturity. In a start-up where everyone has to do everything and no-one has worked anything out yet, that's completely understandable. In a many-billions-of-dollars business with enough influence that someone's quality of life or the viability of some other business could be profoundly affected if the giant screwed up, we should be demanding better by now.
In one sense, it's hard to blame them. After all, if no-one who matters to their revenue stream is actually going to change behaviour because of that dismissive policy, it saves them all the overheads of providing useful support and costs them practically nothing. It's just good business, right?
What is strange is how they've got away with it for so long and most people still don't seem to be switching to alternatives, even as the tech giants casually squash them without even noticing. At some point around here, the words "competition" and "regulation" enter the room.
Imo, this is not scalable or sustainable, and mailing lists are not a replacement for adequate customer support.
The only reason sending emails directly to mailing lists for specific Google products works is precisely because those mailing lists are not public and not flooded with bajillions of emails from the general public. So those who send the emails are already somewhat pre-screened in a way, because if you know that mailing list email address in the first place, you are very unlikely to send something like "my cousin couldn't remember password to their google photos account, can you fix this please". That's why everything there ends up being read and addressed. If those mailing lists were public, then they would be just as useless and ineffective as the current customer support routes currently are for Google.
Tl;dr: mailing lists for specific products are a nifty workaround for the time being, but they aren't a good sustainable solution for shitty customer support. Making those mailing lists public will not only not help solving the problem, it will just make those mailing lists as ineffective as the current customer support. There is no "one weird trick" to solve the customer support adequacy issues with Google,it has to be an actual customer solution that won't be easy and will take time.
By my thinking, that's a "public" mailing list. They're not hiding it from you. The opposite, really — they're trying to get everyone to know and use it, by making it free to any GCP customer, while the actual CSR kind of support requires paying for a subscription to a higher support tier. The mailing list, presented in Google Groups format, is literally what GCP calls their "support forum." It's supposed to take on all comers, including dumb customer asks.
I like Discord, especially in the early days, you can reach out to the principal dev, etc. But it soon seems like they either disappear to get work done (good) or spend all thier time on it (bad). Either way you end up with chaos.
1. they're encouraged to do so in public, so that other community members can help if possible, and/or so bots can reply with suggested FAQ answers;
2. the Community Manager will answer with the company line for questions the company has set answers to (e.g. "when are you releasing X?" or "why is [abusive DoS-like pattern of requests to your service] not working?");
3. otherwise, if the Community Manager knows the answer for sure off the top of their head, they'll give the answer;
4. and if not, the Community Manager relays the question to an engineer in our Slack, where we either have an answer off the top of our heads, or we file it as an issue.
Seems to work just fine for us so far.
Some of the engineers are also sometimes in the Discord (and we're all registered to it), but other than the Community Manager, it's not our job to be in there.
I've had similar experiences in other language/framework communities. It's amazing how helpful some of these very productive people can be to random chat visitors :)!
I do feel a little bit embarrassed if it turns out they're reading the docs to me, but I feel embarrassed about that whether it's an expert or a fellow n00b ;)
> Maybe it's just that they're technical people, and my questions are usually very nerd-snipe-y, and get them hooked.
Integrating sales or classic customer support is boring.
I mean, I get that it pays the bills, but when I've got a million priorities, boring work that I don't really get credit for goes to the bottom of the pile.
I almost always solve problems with the products/services we use myself — up to and including forking the vendor's codebase to fix their shit for them — because it's almost always the fastest way to do things. I've already been working with their product for a while, and I already know exactly what my own problem is. Provided I also know the language their code is written in, that translates to being able to code a patch myself, faster than I can get someone on their end to comprehend the problem I'm having.
That applies up until the point where there's a problem surface that's just plain inaccessible to me (i.e. the inside of a proprietary mobile app or SaaS service), at which point I have to reach out to tell them that it's broken / missing something on their end. (And even then, if I have a spare hour and access to the offending binary, I'll reverse-engineer it a bit to see if I can hotpatch it while waiting for them to get back to me.)
I suppose, for people who don't think this way, there can be value in "support." But IMHO there's more value in just hiring some DevOps engineers who do think that way. Then all the easy "support" requests get handled in-house, and so you'll only ever need the kind of "support" that involves direct bug reports to the engineers from the vendor who built the thing.
if your product is targeted to everyone but only power users can figure it out when there is an issue... well you have a problem.
also, being able to figure something out != you should figure it out. your time is limited and the complexity of remembering all those things that you figured out (even if you have the time) will quickly overwhelm you. unless it’s literally your job to support the product you should care about the interface of the product and what guarantees it makes
re: hiring devops engineers. i’m sorry, what? if my email suddenly does not work I’m supposed to hire a devops engineer now?
How well does that work for a hosted cloud service?
But otherwise, like I said, that's when "the problem surface is inaccessible."
Apparently the guy answers about 1000 emails per day.
I didn't realise the author of that tool was in the channel - kinda neat that we have such a flat open structure at times.
Reportedly, this was also a major factor in Google's strategy shift to open-source a lot of their infrastructure (GRPC, Bazel, TensorFlow, LevelDB, etc.)
Pretty good bad idea
In 2007, an academic argues with PG and others. After long exchange, academic defensively states their own achievements.
Another user challenges academic with GP question, to which academic provides unexpected affirmative response.
More often, we refer to ourselves in the first person plural.
Tarsnap's still there though, so I'd say that's a good defense.
But I was having a bad day, and I said things in a different and more abrasive way than I normally would.
10-ish years later, I'm doing other stuff but still working with Blizzard-related tooling sometimes. I was talking to a Battle.net engineer about their latest-and-greatest game update protocols. He tells me they're thinking of adopting this great thing called bsdiff for the next version. I giggled a bit.
Anyway, hi! I implemented a version of your algorithm when I still barely knew wtf I was doing. https://github.com/jleclanche/python-ptch
What are some real life use cases for it? When does a developer need such a tool?
Games frequently use an override directory or file. The patch contains only the files that have changed and is loaded after the main index and replaces the entries in the index with the updated ones. This is the most common way of doing a patch if it's not just overwriting the original files.
Some games load their file as a virtual filesystem and then the patch just replaces the entries in the virtual store with new ones. Guild Wars 2 works this way. This is only common in MMOs though.
Another reason is that certain operating systems originating in the state of Washington have performance problems when you access small files or directories containing many files.
There may be prior art to that, but as a young coder that was the first time I’d seen it
I wouldn't be surprised if the other consoles also do things this way. It's a very sensible way to manage updates — especially when a game is running off of physical media but the updates are held in local storage. It also means there's no point where the update gets "merged in" to the base image, which means updates can be an atomic thing — either you have the whole update file downloaded + sig-checked (and thus it gets added to the overlay-list at boot) or you don't.
And, if all the consoles are doing it, I wouldn't be surprised if studios that do a lot of work on console don't just use that update strategy even on PC, for uniformity of QA, rather than for "obfuscation."
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.
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.
Also, as a dev, you have no idea what version your users are updating _from_. You either need to generate some number of patches for every version you could be updating from, and figure out if you should just download the whole thing again in any of those cases anyway.
The simplest one is generate patches for recent versions, where recent can be years in the past. It is a linear operation but you only run it on release so it probably isn't a huge cost. You can also use some heuristics such as if if diff is >20% of the file just stop and force users still on that version to do a full update.
A second option is using zsync[1]. zsync is basically a precomputed rolling checksum. The client can download this manifest and they download just the parts of the file they need. This way you don't care about the source, if there is any similarity they can save resources.
And of course these can be combined. Generate exact deltas for recent versions and a zsync manifest for fallback.
[1] http://zsync.moria.org.uk/
Side note: One nice thing about zsync is that the actual download happens from the original file using range requests. This is nice for caching as a proxy only needs to cache the new data once. Is there a diff tool that generates a similar manifest for exact diffs? So instead of storing the new data in the delta file it just references ranges of the new file.
Instead, we just pack the uncompressed files together (frequently using normal zip in a no-compression mode) so that we can avoid needing to ask the OS to open and close files for us or examining the contents of a directory, both of which can be kind of startlingly slow (by video game standards) on some common OSes. Instead, we will generally cache the directory data from the zip file and just use that rather than go to disk.
(of course, the whole download/patch would all be compressed for network transfer, but files would then be decompressed during the installation process)
_You_ mightn't but the last three AAA games I worked on do/did. PS5 expectes compressed files, and does HW decompression (ahem, mostly) on the fly.
Ps4 also did the compressed packages by default thing if I remember right. The upside there being ample cpu for decompression such that no compression was never fastest.
On the Windows/Mac/Linux title I’m working on now, I definitely measure a sizeable improvement to performance when loading from an uncompressed zip rather than from a compressed one. But even that could be down to the particular set of libraries I’m using to handle it.
Did you actually benchmark this? It probably makes sense in your head, but on any vaguely modern hardware it's very unlikely to actually be true because of how exponential the memory hierarchy is.
It feels a bit egregious when I have to download a 100MB update just because a few characters were buffed or nerfed. More involved changes end up being over 1GB.
Not all versions are made equal either - one might be a character buff, another might reorder assets in the "big huge binary blob file" for performance improvements. At a certain point, rather than downloading 30MB per update for 25 versions, and applying each incrementally (remember that you have to do them in order too), just download the full 1GB once and overwrite the whole whing.
Most backup software is able to do good binary deltas of arbitrary data for decades. Even dumb checkpointing resolves problem of downloading 25 versions - you download latest checkpoint and deltas from there.
Don't excuse poor design and programming, when you know a file structure, creating a differential update should be short task. With a tiny bit of algorithmic knowledge you could even optimize the process to only download needed assets inside of you big binary blob - if the asset was changed 7 times during your last 25 version you only need to download the last one.
It is a complete image, but phones today have nontrivial state that may be a problem - e.g. your baseband processor might have its own rom with its own update protocol, which changed between image 2 and image 7, so image 10 after image 1 will be unable to update the baseband.
I honestly consider that a pretty reasonable trade-off.
Does this happen with more advanced compression algorithms? I've rsynced zip files of different versions of internal software and the diff was always much, much smaller than the entire package.
I'd argue that zip is a relatively simple compressed archive format. Its simplicity is its charm and the reason it's so popular. More space-efficient algorithms would be less likely to be "patchable" as there would be less redundancy / structure in the compressed representation to exploit (the best compression seems like it would have similar properties of random data.)
Clarification: .zip (unlike .tar.gz for example, or "solid" .7z) compresses each file separately, that's nothing to do with the compression algorithm used. In addition, DEFLATE, the LZ77-based compression which is by far most commonly used in .zip (and also by gzip) has a window size of 32kB (uncompressed). So yes, even if you used DEFLATE on a solid stream (e.g. zipped a .tar archive) it couldn't remove any cross-file redundancy once it's gone past the first 32kB of each file.
Each file is 1k-20k, of which there are 40,000 or so. But they are catalogued in 3-4 deep directories, so if you just zip them, the metadata takes 30% or so of the zip.
But the metadata does compress very well, so they zip it again.
zstd itself also has the (pretty new) ability to use a shared file as shorthand during compression. What that means in practice is that diffs can be REALLY tiny if you have the previous archive download.
Hi dang.
For zip files each individual file is compressed independently. So unchanged files and prefixes don't need to be resent, even if once a file changes the entire tail end of it needs to be resent.
Some times compression algorithms "reset" periodically. For example the `gzip --rsyncable` patch. This basically resets the compression stream so that a change will only affect part of the compressed file. This does have a cost in terms of compressed size because the compressor can't deduplicate across resets. However if the resets are infrequent you can maintain fairly good delta transfer with little space overhead.
Additionally some delta transfer tools detect common compression and decompress the file "in transfer", performing the delta checks on the original file.
Heresay, but from what I've heard modern games may ship multiple copies of some assets with different levels or features so they can be loaded as a sequential read off the disk. While a block-oriented compression algorithm might sync up more reliably, if you're packing 200MB of assets for a level and they're all compressed to take advantage of the fact they'll be read sequentially could mean a change 25MB in would still ship ~175MB of changes.
It is just really poor programming, nothing more. And it's everywhere. If find source >/dev/null takes 6 seconds there is no reason for gradle to take 2 minutes on a rebuild. If the dev is used to that, why would they even think about patch optimisation?
The reason games (and software in general) do full downloads instead of binary patches is purely overdefensive and/or stupid. Store software could just check checksums after a patch and re-download only if they fail.
I actually could really see using it, now that I understand what it does.
I've worked on some firmware projects where we did OTA updates and were guilty of shipping the entire binary. Luckily, even the entire binary was rather small, but still it would have been very cool to be able to create a diff and ship only the diff!
/s end open source entitlement section
Thanks for your great work
https://blog.chromium.org/2009/07/smaller-is-faster-and-safe...
The explanation here is pretty fascinating
https://www.chromium.org/developers/design-documents/softwar...
The game industry really hasn't used binary diffs and patching since the 90s when they used RTPatch.
Flight Simulator downloads tens of GB every time I start it. :-/
https://www.chromium.org/developers/design-documents/softwar...
It‘s a binary diff/patch utility.
> What are some real life use cases for it? When does a developer need such a tool?
Incrementally update binary files e.g. assets or runnable binaries instead if having to re-send the entire thing on every update so e.g. games, browsers, package managers, …
The standard diff/patch utilities are text-based and even when they do extend to binary data their algorithms and heuristics tend to be biased towards textual contents.
Bsdiff was built specifically with an eye towards executables.
(Just to be clear, there was no license violation involved in this case; just a lack of awareness of the provenance of the open source software they were using.)