On Thu, Mar 21, 2024 at 09:25:47PM +0100, Julian Andres Klode wrote:
On Thu, Mar 21, 2024 at 06:01:12PM +0200, Laurențiu Nicola wrote:
Package: apt
Version: 2.7.12
I noticed that searching for packages is very slow if the package lists are compressed. To reproduce, remove `/var/lib/apt/lists`, enable
Acquire::GzipIndexes "true"; Acquire::CompressionTypes::Order:: "gz";
, run `apt update`. This enables LZ4 compression on my systems, but I don't think the exact method matters. You can then run `apt search librust`, which takes about 19 seconds in a Debian 12 container (docker.io/debian:12 has compression already set
up), compared to 0.4 seconds without compression.
Also tested on Ubuntu 22.04 and 24.04, so the exact APT version shouldn't matter too much.
I tried to look into it, and `strace -e trace=openat apt-cache search librust` shows it reopen and re-read one of the package lists:
openat(AT_FDCWD, "/var/lib/apt/lists/archive.ubuntu.com_ubuntu_dists_jammy_universe_binary-amd64_Packages.lz4", O_RDONLY) = 16
librust-addr2line+default-dev - Cross-platform symbolication library - feature "default"
openat(AT_FDCWD, "/var/lib/apt/lists/archive.ubuntu.com_ubuntu_dists_jammy_universe_binary-amd64_Packages.lz4", O_RDONLY) = 16
librust-addr2line+object-dev - Cross-platform symbolication library - feature "object"
openat(AT_FDCWD, "/var/lib/apt/lists/archive.ubuntu.com_ubuntu_dists_jammy_universe_binary-amd64_Packages.lz4", O_RDONLY) = 16
librust-addr2line+rustc-demangle-dev - Cross-platform symbolication library - feature "rustc-demangle"
openat(AT_FDCWD, "/var/lib/apt/lists/archive.ubuntu.com_ubuntu_dists_jammy_universe_binary-amd64_Packages.lz4", O_RDONLY) = 16
librust-addr2line+std-dev - Cross-platform symbolication library - feature "std"
(you can use -e trace=openat,read to confirm that it's actually reading the file)
I believe it's quadratic in the number of search results, and this is related to the pseudo-indexing mechanism used by APT (see `pkgRecords::Lookup` in apt-pkg). Each lookup call will have to decompress the file in order to seek to the destination.
Unfortunately, I suspect this isn't exactly an easy fix, given the current design.
Going to respond to this but also including responses to your followup email which has a broken Subject:
Searching works by ordering the packages based on file, offset
and then iterating over them and looking them up. Seeking forward
to a higher offset does not involve a reopen, we just skip content
in betwene.
Full-text search is inside the description in the section parsed
for each package.
It's not clear why this fails on bookworm - I can reproduce that -
t certainly is fine in git main on my Ubuntu 24.04 system.
This should be fixed in
https://salsa.debian.org/apt-team/apt/-/merge_requests/336
What happened was that we got called for the same offset twice, e.g.
let's say 42.
Now our section size is let's say 7.
So what happened is that we did:
- Jump to 42 => offset = 42
- Parse => offset = 49
- Jump to 42 => ugh gotta go back
Luckily we still have the currently used section in the Buffer; i.e.
we only looked at bytes 49...<something> but our buffer still starts
at 42, so we can just look back to find our section again.
Sadly we can't avoid the reparse of the section here, because the
pkgTagSection passed to pkgTagFile::Jump() could be a different one
than the last one.
I have a patch to avoid the reparse by storing offset a level higher
where the pkgTagSection is fixed but I'm in favour of not shipping that
- those would only be marginal gains and we want to exercise this code
path.
--
debian developer - deb.li/jak | jak-linux.org - free software dev
ubuntu core developer i speak de, en
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)