17 ms·

Much faster incremental apt updates

172 points by edward 11y ago

IgorPartola 11y ago
I am really surprised that something as frequently used as apt had these obvious performance issues. Was there a technical reason for it? I noticed that it ran painfully slow on devices with slower disks. I suppose that is going to change now.
- devit 11y ago
  Based on the sort of issues fixed, it looks like no one ever bothered to benchmark it until now.
  - buster 11y ago
    As a Debian user, i find that updating can be slow, but it looks like spending much of its time on network traffic. Also 30 or 40 seconds is not large enough to be _really_ annoying. Nevertheless, i'm looking forward to this!
- jzwinck 11y ago
  A 20x speedup as reported here is not that unusual in my experience. If I work on optimizing something which has never had detailed performance analysis, I expect to achieve 3x to 10x speedups in most cases. Even 100x is not really rare. I once found a similar thing in a commercial setting. A program had been written which could set one bit in a shared memory region for use as a feature flag. It was slowly expanded in use until it was being run thousands of times a day on hundreds of very expensive computers. I wrote a replacement program which read commands from a file and set all the bits in one invocation. This saved well over 100k USD per year if you just added up the cost of computer time without staffing. I imagine this APT fix is worth more than that.
- deleted 11y ago
  [deleted]
- thrownaway2424 11y ago
  I doubt this is by any means the most important performance issue that Debian package installation faces. It looks like the speedup discussed here is in the no-update case, which is nice, but not the only case. I stopped using Debian at home several years ago, and one of the main reasons was the incredible slowness of groping around in GNOME's moronic XML settings database during every update. Upgrading schemas and whatnot. I still use Debian at work and I note that it is still prone to building and rebuilding initrd during an update when it should only be built once. On a recent update initrd was built for the kernel that was being _uninstalled_ which was awesome.
  - kasabali 11y ago
    consider using eatmydata. living on the edge but it is worth it. https://packages.debian.org/jessie/eatmydata https://packages.debian.org/jessie/eatmydata
- newman314 11y ago
  Apt is quite slow on a Pi running OSMC so I'm hoping this makes it downstream at some point
- kasabali 11y ago
  > I noticed that it ran painfully slow on devices with slower disks. I suppose that is going to change now No, most of the time is spent fsync'ing and it is a problem at a lower layer (related to dpkg), but ot apt. Too many bug reports to list but see [0] for the latest one. You can use apt with eatmydata as a workaround. [0] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=613428 https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=613428
orf 11y ago
This is crazy, apt has been reading diffs a byte at a time? Think of the millions of hours that have been wasted due to this.
- grandinj 11y ago
  No, they made the right choices. (1)Make it work. (2)Make it correct. (3)Make it fast. Can take a long time to get to step 3 with something as safety critical as an update tool.
  - deleted 11y ago
    [deleted]
  - k__ 11y ago
    > implying apt is a young tool and the maintainers didn't have many years to go from 1 to 3
    - baghira 11y ago
      According to the developer the bug was present only in the 1.1 series, which is just a few months old (it was pre-released at debconf 2015, and is not in Jessie if i'm not mistaken).
      - r0muald 11y ago
        Furthermore pdiffs were introduced in ~2006: https://www.debian-administration.org/article/439/Avoiding_slow_package_updates_with_package_diffs https://www.debian-administration.org/article/439/Avoiding_s...
  - deleted 11y ago
    [deleted]
  - rektide 11y ago
    Sometime between the start and the end, there's often a mandatory burn it all down step required to more fully satisfy either (2) or (3). Watching hundreds of MB of data getting written to my HD for an apt-get update makes me 90% certain that Debian indeed needs to burn it all down. To their credit, they started really early. And burning it all down seems to be an increasingly better option for purely extrinsic reasons; the late mover advantage keeps increasing, and better and better options keep emerging. A LMDB-based refactor perhaps? This is probably a pipe dream, alas: Debian developers must have a hundred different programs that all build and extend forward the original "make it work" technology, to make it survivable. And that's really my final counter to your cute linear notion of ongoing improvement: the mold is set, and there are dozens of things bound up in what has happened.
saurik 11y ago
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/ http://svn.telesphoreo.org/trunk/data/_apt7/
aidos 11y ago
This is great. Even more so because after gem, or pip, or something (can't remember) had a similar issue a while ago (think they had an n2 algorithm) a lot of people jumped on it as being bad computer science. There were all sorts of calls about how web people were not real computer scientists. Either way, good useful products were made and they've been further optimised. That's great. More of that more of the time.
- shadeless 11y ago
  You're probably thinking of this, rubygems was optimized using a linked list: https://news.ycombinator.com/item?id=9195847 https://news.ycombinator.com/item?id=9195847
abrowne 11y ago
Another (fairly) recent improvement for apt, but on the UI side, is the apt command [1]. It "combines the most commonly used commands from apt-get and apt-cache. The commands are the same as their apt-get/apt-cache counterparts but with slightly different configuration options." So no need to remember that it's apt-cache search, and it's a shorter command. (I know you can set aliases, but this works by default, so on a live USB or another user's machine.) Bash completion didn't work at first, at least on Ubuntu, but as of 15.10 it's working. [1]: https://mvogt.wordpress.com/2014/04/04/apt-1-0/ https://mvogt.wordpress.com/2014/04/04/apt-1-0/
- fistfuck 11y ago
  Ugh can't even count how many times this happens: Apt search somepackage sigh Apt-cache search somepackage
  - malux85 11y ago
    then: sigh apt-cache search somepackage | grep '^somepackage'
  - leeoniya 11y ago
    apt-cache policy <somepackage> does that work better?
  - asjo 11y ago
    wajig(1) is your unifying interface friend in this space.
- mixmastamyk 11y ago
  This does the same I believe, if you'd like to try something like this right now: https://pypi.python.org/pypi/apt-wrapper https://pypi.python.org/pypi/apt-wrapper It also runs sudo for you when needed. The wrapper part is only for the package name as it was already taken on pypi.
- dilap 11y ago
  this is good! i'm mostly homebrew on mac these days, but every once in a while i find myself on an apt-based linux system, and i've always blown away at how obscure and unintuitive apt is.
legulere 11y ago
> The reason for this is that our I/O is unbuffered, and we were reading one byte at a time in order to read lines. This changed on December 24, by adding read buffering for reading lines, vastly improving the performance of rred. Why not use memory mapped files and let the operating system deal with caching in a way that is most efficient for that specific case?
- ars 11y ago
  I believe mmap is not fully portable without extra work, so they avoid it - debian runs on a LOT of different systems.
  - legulere 11y ago
    It was developed inside the original BSD and is part of POSIX. So it's supported on all unixes today. The only place it isn't supported is Windows.
    - icefox 11y ago
      It is everywhere even Windows. There is a little bit of weirdness on some older versions of Windows CE and some undefined behavior with edge conditions on some OS's if I recall, but you can find the capability everywhere. I added the map API to QFile back in the day and went through checking different OS's for compatibility. A quick google search here is a link to the windows method: https://github.com/radekp/qt/blob/master/src/corelib/io/qfsfileengine_win.cpp#L1948 https://github.com/radekp/qt/blob/master/src/corelib/io/qfsf... unix version: https://github.com/radekp/qt/blob/master/src/corelib/io/qfsfileengine_unix.cpp#L1238 https://github.com/radekp/qt/blob/master/src/corelib/io/qfsf...
- julian-klode 11y ago
  Not all our files are uncompressed, so directly using mmap does not make sense for us, because we also need to be able to use files compressed with gzip, bzip2, xz (and soonish probably lz4).
k_bx 11y ago
It's great to see apt improving. I am still waiting for "apt-get update" to become git-pull-like thing to have much faster update (especially when no recent changes were made) though.

172 points by edward 11y ago

I am really surprised that something as frequently used as apt had these obvious performance issues. Was there a technical reason for it? I noticed that it ran painfully slow on devices with slower disks. I suppose that is going to change now.

devit 11y ago
Based on the sort of issues fixed, it looks like no one ever bothered to benchmark it until now.
- buster 11y ago
  As a Debian user, i find that updating can be slow, but it looks like spending much of its time on network traffic. Also 30 or 40 seconds is not large enough to be _really_ annoying. Nevertheless, i'm looking forward to this!
jzwinck 11y ago
A 20x speedup as reported here is not that unusual in my experience. If I work on optimizing something which has never had detailed performance analysis, I expect to achieve 3x to 10x speedups in most cases. Even 100x is not really rare. I once found a similar thing in a commercial setting. A program had been written which could set one bit in a shared memory region for use as a feature flag. It was slowly expanded in use until it was being run thousands of times a day on hundreds of very expensive computers. I wrote a replacement program which read commands from a file and set all the bits in one invocation. This saved well over 100k USD per year if you just added up the cost of computer time without staffing. I imagine this APT fix is worth more than that.
deleted 11y ago
[deleted]
thrownaway2424 11y ago
I doubt this is by any means the most important performance issue that Debian package installation faces. It looks like the speedup discussed here is in the no-update case, which is nice, but not the only case. I stopped using Debian at home several years ago, and one of the main reasons was the incredible slowness of groping around in GNOME's moronic XML settings database during every update. Upgrading schemas and whatnot. I still use Debian at work and I note that it is still prone to building and rebuilding initrd during an update when it should only be built once. On a recent update initrd was built for the kernel that was being _uninstalled_ which was awesome.
- kasabali 11y ago
  consider using eatmydata. living on the edge but it is worth it. https://packages.debian.org/jessie/eatmydata https://packages.debian.org/jessie/eatmydata
newman314 11y ago
Apt is quite slow on a Pi running OSMC so I'm hoping this makes it downstream at some point
kasabali 11y ago
> I noticed that it ran painfully slow on devices with slower disks. I suppose that is going to change now No, most of the time is spent fsync'ing and it is a problem at a lower layer (related to dpkg), but ot apt. Too many bug reports to list but see [0] for the latest one. You can use apt with eatmydata as a workaround. [0] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=613428 https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=613428

orf 11y ago

This is crazy, apt has been reading diffs a byte at a time? Think of the millions of hours that have been wasted due to this.

grandinj 11y ago
No, they made the right choices. (1)Make it work. (2)Make it correct. (3)Make it fast. Can take a long time to get to step 3 with something as safety critical as an update tool.
- deleted 11y ago
  [deleted]
- k__ 11y ago
  > implying apt is a young tool and the maintainers didn't have many years to go from 1 to 3
  - baghira 11y ago
    According to the developer the bug was present only in the 1.1 series, which is just a few months old (it was pre-released at debconf 2015, and is not in Jessie if i'm not mistaken).
    - r0muald 11y ago
      Furthermore pdiffs were introduced in ~2006: https://www.debian-administration.org/article/439/Avoiding_slow_package_updates_with_package_diffs https://www.debian-administration.org/article/439/Avoiding_s...
- deleted 11y ago
  [deleted]
- rektide 11y ago
  Sometime between the start and the end, there's often a mandatory burn it all down step required to more fully satisfy either (2) or (3). Watching hundreds of MB of data getting written to my HD for an apt-get update makes me 90% certain that Debian indeed needs to burn it all down. To their credit, they started really early. And burning it all down seems to be an increasingly better option for purely extrinsic reasons; the late mover advantage keeps increasing, and better and better options keep emerging. A LMDB-based refactor perhaps? This is probably a pipe dream, alas: Debian developers must have a hundred different programs that all build and extend forward the original "make it work" technology, to make it survivable. And that's really my final counter to your cute linear notion of ongoing improvement: the mold is set, and there are dozens of things bound up in what has happened.

saurik 11y ago

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/ http://svn.telesphoreo.org/trunk/data/_apt7/

aidos 11y ago

This is great. Even more so because after gem, or pip, or something (can't remember) had a similar issue a while ago (think they had an n2 algorithm) a lot of people jumped on it as being bad computer science. There were all sorts of calls about how web people were not real computer scientists. Either way, good useful products were made and they've been further optimised. That's great. More of that more of the time.

shadeless 11y ago
You're probably thinking of this, rubygems was optimized using a linked list: https://news.ycombinator.com/item?id=9195847 https://news.ycombinator.com/item?id=9195847

abrowne 11y ago

Another (fairly) recent improvement for apt, but on the UI side, is the apt command [1]. It "combines the most commonly used commands from apt-get and apt-cache. The commands are the same as their apt-get/apt-cache counterparts but with slightly different configuration options." So no need to remember that it's apt-cache search, and it's a shorter command. (I know you can set aliases, but this works by default, so on a live USB or another user's machine.) Bash completion didn't work at first, at least on Ubuntu, but as of 15.10 it's working. [1]: https://mvogt.wordpress.com/2014/04/04/apt-1-0/ https://mvogt.wordpress.com/2014/04/04/apt-1-0/

fistfuck 11y ago
Ugh can't even count how many times this happens: Apt search somepackage sigh Apt-cache search somepackage
- malux85 11y ago
  then: sigh apt-cache search somepackage | grep '^somepackage'
- leeoniya 11y ago
  apt-cache policy <somepackage> does that work better?
- asjo 11y ago
  wajig(1) is your unifying interface friend in this space.
mixmastamyk 11y ago
This does the same I believe, if you'd like to try something like this right now: https://pypi.python.org/pypi/apt-wrapper https://pypi.python.org/pypi/apt-wrapper It also runs sudo for you when needed. The wrapper part is only for the package name as it was already taken on pypi.
dilap 11y ago
this is good! i'm mostly homebrew on mac these days, but every once in a while i find myself on an apt-based linux system, and i've always blown away at how obscure and unintuitive apt is.

legulere 11y ago

> The reason for this is that our I/O is unbuffered, and we were reading one byte at a time in order to read lines. This changed on December 24, by adding read buffering for reading lines, vastly improving the performance of rred. Why not use memory mapped files and let the operating system deal with caching in a way that is most efficient for that specific case?

ars 11y ago
I believe mmap is not fully portable without extra work, so they avoid it - debian runs on a LOT of different systems.
- legulere 11y ago
  It was developed inside the original BSD and is part of POSIX. So it's supported on all unixes today. The only place it isn't supported is Windows.
  - icefox 11y ago
    It is everywhere even Windows. There is a little bit of weirdness on some older versions of Windows CE and some undefined behavior with edge conditions on some OS's if I recall, but you can find the capability everywhere. I added the map API to QFile back in the day and went through checking different OS's for compatibility. A quick google search here is a link to the windows method: https://github.com/radekp/qt/blob/master/src/corelib/io/qfsfileengine_win.cpp#L1948 https://github.com/radekp/qt/blob/master/src/corelib/io/qfsf... unix version: https://github.com/radekp/qt/blob/master/src/corelib/io/qfsfileengine_unix.cpp#L1238 https://github.com/radekp/qt/blob/master/src/corelib/io/qfsf...
julian-klode 11y ago
Not all our files are uncompressed, so directly using mmap does not make sense for us, because we also need to be able to use files compressed with gzip, bzip2, xz (and soonish probably lz4).

k_bx 11y ago

It's great to see apt improving. I am still waiting for "apt-get update" to become git-pull-like thing to have much faster update (especially when no recent changes were made) though.