Much faster incremental apt updates
I run an ecosystem of tens of millions of "end users" who are working with a GUI package manager I developed (Cydia) built on APT (using libapt). We stress APT to its limit, with users often using very large numbers (thirty is common, but I have seen well over a hundred) repositories that are often hosted by random people of varying skill at IT (and so tend to be slow or have errors in their metadata; DNS errors and 200 OK HTML error pages abound).We have so many non- and semi- skilled people using APT that if you Google many APT errors, you actually tend to come across people using Cydia as the primary people discussing the error condition ;P. Our package churn and update rate is faster than Debian, and we have run into all of the arbitrary limits in various versions of APT (total number of packages known about, total number of delete versions, total number of bytes in the cache): really, we use APT a lot.1) Despite APT supporting cumulative diffs (where the client gets a single diff from the server to bring them up to date rather than downloading a ton of tiny incremental updates and applying them in sequence), Debian's core repositories are not configured to generate these. I can tell you from experience that providing cumulative diffs is seriously important.So, while a 20x speed-up applying a diff is cool and all, users of Debian's servers are doing this 20x more often that they need to, applying diff after diff after diff to get the final file. This is an example of an optimization at a low-level that may or may not be useful as the real issue is at the higher-level in the algorithm design.What is extra-confusing is that the most popular repository management tool, reprepro, can build cumulative diffs automatically, and I think it does so by default. Debian really should switch to using this feature: I keep seeing Debian users complain on forums and blog posts that APT diff updates are dumb as you end up downloading 30 files... no: the real issue is that debian isn't using their own tool well :(.2) The #1 performance issue I deal with while using APT even on my server is the amount of time it takes to build the cache file every time there is a package update. It sits there showing you a percentage as it does this on the console. On older iPhones this step was absolutely brutal. This step was taking some of my users minutes, but again: that is the step I most notice on my server.I spent a week working on this years ago, and made drastic improvements. I determined most of the time was spent in "paper cuts": tiny memory allocations and copies distributed through the entire project which over the course of running the code hemorrhaged all the time.The culprit (of course ;P) was std::string. As a 20-year user of C++ who spent five years in the PC gaming industry, I hate std::string (and most of STL really: std::map is downright idiotic.. it allocates memory even if you never put anything into the map, and I can tell you from writing my own C++ red-black tree tools that there is no good reason for this).Sure, maybe APT is using C++11 by now and has a bunch of move constructors all over the place that mitigate the issue somewhat (I haven't looked recently), but it still feels "weirdly slow" to do this step on my insanely fast server (where by all rights it should be instantaneous) and frankly: APT's C++ code when I was last seriously looking at the codebase was abysmal. It was essentially written against one of the very first available versions of C++ by someone who didn't really know much about the language (meaning it uses all the bad parts and none of the good; this happens when Java programmers try to use C++98, for example, but APT is much much worse) and has no rhyme or reason to a lot of the design. It reminds me a little of WebKit's slapped together "hell of random classes and pointers that constantly leads to use-after-free bugs".Regardless, I rewrote almost every single usage of std::string in the update path to use a bare pointer and a size and pass around fragments of what had been memory mapped from the original file whenever possible without making any copies. I got to be at least twice if not four times faster (I don't remember). I made the code entirely unmaintable while doing this, though, and so I have never felt my patches were worth even trying to merge back (though it also took me years to ever find the version control repository where APT was developed anyway... ;P). To this day I ship some older version of APT that I forked rather than updating to something newer, due to a combination of this and the gratuitous-and-unnecessary ABI breakage in APT (they blame using C++, but that isn't quite right: the primary culprit is their memory-mapped cache format, and rather than use tricks when possible to maintain the ABI for it they just break it with abandon; but even so, the C++ is buying me as a user absolutely nothing: they should give me a thin C API to their C++ core.)If I were to do this again "for real" I would spend the time to build some epic string class designed especially for APT, but I just haven't needed to do this as my problem is now "sort of solved well enough" as I almost have never cared about the new features that have been added to APT, and I have back ported the few major bug fixes I needed (and frankly have much better error correction now in my copy, which is so unmaintainably drifted due to this performance patch as to not be easily mergable back :/ but we really really need APT to never just give up entirely or crash if a repository is corrupt, and so they are also critical for us in a way they aren't for Debian or Ubuntu).If anyone is curious what these miserable patches look like, here you go... check out "tornado" in particular. (Patches are applied by my build system in alphabetical order.) (Actually, I have been reading through my tornado patch and I actually did at some point while working on it build a tiny custom string class to help abstract the fix, but I assuredly didn't do it well or anything. I really only point any of this maintainability issue out at all, by the way, as I don't want people to assume that performance fundamentally comes at the price of unmaintainable implementations.)http://svn.telesphoreo.org/trunk/data/_apt7/