[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: apt-file performance characterization

nick black left as an exercise for the reader:
> I've written up a performance characterization of apt-file(1) as stands. The
> preliminary version is available here:
> 	http://nick-black.com/raptorial-file

OK, finished this writeup. I've updated the file at the link above, and
included it below. I'm going to go ahead and knock out bugs 705[0] and
698[1], which will together implement everything described herein.
Hopefully that'll be done by tomorrow morningish, EDT.

Hack on!

--rigorously, nick

[0] https://www.sprezzatech.com/bugs/show_bug.cgi?id=705
[1] https://www.sprezzatech.com/bugs/show_bug.cgi?id=698

Optimizing apt-file

All timings were taken on a quadcore Core i7 2600K overclocked to 5.0GHz,
reading files from an Intel 320 SSD. All data sets fit within main memory.

apt-file has a more complex performance space than did apt-show-versions.
Understanding this space is critical to optimizing apt-file, and evaluating
any optimizations made. apt-file doesn't perform string searches itself; it
uses grep, zgrep and zfgrep. Furthermore, while apt-file is not multithreaded,
it does run multiple processes (apt-file -> gzip | grep), and thus natively
takes advantage of multiple cpus within a given Contents file. In this top(1)
output, the last column is the CPU number:

 8529 dank   7952  848  688 R  21.9  0:00.66 grep                3 
 8522 dank  66508  17m 3436 S  11.6  0:00.35 apt-file            0 
 8528 dank   8840  668  508 R  10.6  0:00.32 gzip                2 

Of course, on a unicore machine, this use of three different processes will
provide no computational benefit (it might provide I/O benefit).

It is worth noting that the -x (regex) functionality of apt-file appears to be
broken or at least incomplete. Neither of the following searches, for instance,
yield any matches for "compiz" (or indeed all of the matches for "frog"):

	[skynet](0) $ apt-file search -x frog\|compiz
	frog: /usr/bin/frog
	wmfrog: /usr/bin/wmfrog
	[skynet](0) $ apt-file search -x \(frog\)\|\(compiz\)
	frog: /usr/bin/frog
	wmfrog: /usr/bin/wmfrog
	[skynet](0) $ 

Running "apt-file frog compiz" finds all of the frog matches, but none of the
compiz matches. It appears that apt-file cannot use multiple patterns off the
command line, but it doesn't bother to warn the user about that. We can create
a pattern file, however, and that works:

	[skynet](0) $ echo -e "frog\ncompiz" > searches 
	[skynet](0) $ apt-file -f search searches  | wc -l
	[skynet](0) $ apt-file search compiz  | wc -l
	[skynet](0) $ apt-file search frog | wc -l
	[skynet](0) $ echo $((3874 - 1112))
	[skynet](0) $ 

Characterizing apt-file performance

Background material:

	"Flexible Pattern Matching in Strings" by Navarro et al
	"Introduction to Algorithms" by Cormen et al

String search algorithms tend to be optimized for one use or another. Searching
within DNA, for instance, is a very different game than searching within
UTF-32, which is very different from searching within UTF-8. We will consider
only exact string matching, and not "fuzzy" string matching (i.e., matching
within some string distance). Parameterizing the problem space under this
condition yields:

 - alphabet size
 - needle length
 - haystack length
 - number of needles
 - needle heterogeneity
 - frequency of occurrence

Note that in the presence of Kleene closure, there might be an infinite number
of needles. In the case of an online algorithm, the haystack is of infinite
size. All other parameters are finite. The alphabet size and haystack length
are independent of apt-file(1). Let's explore performance when we vary the
other parameters:

Varying needle length

It would be nice to have short needles of various length which held the
frequency of occurrence constant, but that'll have to come another day. It'll
be easy, as we'll see, to vary frequency without varying length.

[skynet](0) $ for i in compizabd compizab compiza compiz compi comp com co c ; do time apt-file search $i | wc -l ; done

real	0m1.655s

real	0m1.673s

real	0m1.654s

real	0m1.854s

real	0m2.850s

real	0m4.971s

real	0m7.667s

real	0m22.491s

real	1m30.639s
[skynet](0) $ 

apt-file(1) clearly performs better for longer strings, although this could be
due to their lesser frequency of occurrence. Times are approximately equal for
the three longest strings, but they also have equal frequency (0 occurrences).
This points to a backwards-skipping algorithm such as Boyer-Moore (with longer
strings, we get longer skips, and the ratio of skipped text for different
string lengths (N, N-1) converges towards 1 as N grows large (i.e., there's
a much bigger difference between skipping 1 vs 2 than skipping 10 vs 11). This
could all be due to I/O, though. To check, we comment out the print command in
the innermost loop of print_winners(); I'll spare you the block of timings and
just assert that the absolute timings fell, but not by much. It does indeed
appear that a backwards-skipping algorithm is in use.

Needle heterogeneity

We'll hold length and frequency constant, and vary the homogeneity:

[skynet](0) $ for i in abcd aaaa aaaa abcd  ; do time apt-file search $i | wc -l ; done

real	0m1.739s
user	0m2.047s
sys	0m0.163s

real	0m1.827s
user	0m2.227s
sys	0m0.117s

real	0m1.813s
user	0m2.157s
sys	0m0.167s

real	0m1.715s
user	0m2.003s
sys	0m0.167s
[skynet](0) $ 

The slightly longer times on "aaaa" vs "abcd", despite nearly equal frequency,
suggest that a backwards-skipping rather than a forwards-skipping algorithm is
in use, as a homogeneous needle will affect the former more (questionable!).

Number of needles

Frequency of occurrence

We'll hold length constant, and vary the number of matches:

[skynet](0) $ for i in th gh es zz ; do time apt-file search $i | wc -l ; done

real	0m14.883s
user	0m20.290s
sys	0m0.953s

real	0m7.139s
user	0m10.440s
sys	0m0.453s

real	0m36.047s
user	0m43.220s
sys	0m2.497s

real	0m2.698s
user	0m3.927s
sys	0m0.200s
[skynet](0) $ 

All things being equal, we'd expect that more matches would be faster, as it
would allow more text to be skipped (we can stop matching a given haystack as
soon as we find a match). That it does not suggests that the postprocessing
step of apt-file(1) (a perl "uniq sort") probably has crap running time. Once
again, I tested this with no output, and got very similar numbers.

Speeding it up

First, a constraint: we're going to use unmodified zlib to inflate the files,
which precludes matching as we inflate (there is no way to insert such a
function into zlib 1.2.7). There will thus necessarily be a strong dependency
between chunk inflation and chunk processing. This has two effects, both
negative: we can't process a chunk in parallel with that chunk's inflation, and
we are likely to suffer both a write-miss (during deflation) and a read-miss
(during processing) rather than merely a write-miss, or possibly no cache miss
at all for non-matching text (if we inflated and processed non-matches wholly
within registers).

Let's first look at how to best parallelize this, as that tends to affect
program organization overall, forcing shape on the other code.

There is one Contents file per |repository X architecture| (the "source"
pseudo-architecture does not currently provide a Contents file). Most
installations are likely to have between one and three Contents files ("main",
"contrib", and "non-free" for some primary repository), where one of these
files is very much larger than the other two. As an example:

[skynet](0) $ ls -l /var/cache/apt/apt-file/
    82015 ftp.us.debian.org_debian_dists_unstable_contrib_Contents-amd64.gz
 25868596 ftp.us.debian.org_debian_dists_unstable_main_Contents-amd64.gz
   794733 ftp.us.debian.org_debian_dists_unstable_non-free_Contents-amd64.gz
     1330 www.sprezzatech.com_apt_dists_unstable_contrib_Contents-amd64.gz
  4551278 www.sprezzatech.com_apt_dists_unstable_main_Contents-amd64.gz
    28211 www.sprezzatech.com_apt_dists_unstable_non-free_Contents-amd64.gz
[skynet](0) $ 

Ratios of length are: 5.68, 5.73, 9.69, 2.91, 21.21. Leaving out the second set
of repositories, they're 32.55 and 9.69 for Debian and 161.33 and 21.21 for
SprezzOS. Either way, there's about three orders of magnitude difference
between the smallest and the largest. Remember that these are compressed
versions of the files -- we'll be scanning proportionately more text.

So, we can parallelize across the files, but that's of limited utility; the
largest file(s) are likely to strongly dominate total execution time.
Nonetheless, we have gone ahead and done this. This has the added benefit that
if there is a problem reading any particular file (i.e. I/O delay due to a bad
sector), the other files can still be processed.

Much more benefit can be had by parallelizing within a file (recall that
apt-file(1) already enjoys producer:consumer parallelism within a file by its
multiprocess approach). Remembering that we never want more threads in the
running state than there are available processors, there's three major
approaches we could pursue:

 (a) one thread inflates to multiple buffers in succession. worker threads
      start in stepwise fashion as buffers become available.
 (b) worker threads lock on the file being inflated; upon taking ownership,
      they inflate a chunk to their own buffer, and work on it.
 (c) worker threads statically chunk up the file to be inflated, then seek out
      the first zlib breakpoint following the start of their chunk. this is
      similar to how apt-show-versions works, since it doesn't know stanza
      boundaries ahead of time.

Options (a) and (b) are very similar -- they are equivalent for small files
("small" here meaning less than the product of chunk size and processor count).
The difference is that when all worker threads are occupied in (a), the
inflating thread continues to run, whereas inflation pauses when all worker
threads are running in (b). A fundamental advantage of (b) is that it uses a
fixed amount of memory small relative to large files, whereas (a) can require
up to the full inflated size (this occurs if the inflating thread runs ahead of
the worker threads). Option (b) has threads waiting whenever they finish at the
same time. Option (a) has threads waiting whenever any thread finishes before
the inflation thread has made a chunk available. It seems clear that (b) is the
better choice of the two.

Option (c) is interesting. It does a bit more work than (b), but eliminates all
delays (most importantly the compulsory startup delays) provided a friendly
chunk size during deflation. Should processing time be similar to inflation
time, this could become important. Currently, processing time is roughly
characterized as at least twice inflation time, and I'm not very knowledgeable
regarding zlib chunking characteristics, so this added complexity is not
planned. It's worth considering later, though, especially as the serial nature
of inflation will become more and more apparent as processor count increases.

Finally, we want to ensure we launch an optimal number of threads -- we don't
want to launch 8 threads on either a dual-core, power-limited tablet or a
1024-core supercomputer. Libblossom allows us to launch a thread per processing
unit. Rather than parallelizing directly within a directory or within a file,
then, we parallelize on a queue of file-offset objects. This queue has a fixed
upper size: one descriptor per thread (we'll never have 9 files open if we have
only 8 threads), where a descriptor is a map, a total map length, and the
offset through which processing has been scheduled. Once a map is fully
scheduled, its descriptor is removed. If there are no descriptors on the queue,
perform a readdir_r() on the DIR pointer (serialized by the kernel), and
possibly add a new descriptor to the queue (if the file returned by readdir_r()
is too large to process in one chunk).

We need unlock before calling readdir_r(), but in this case we have to relock
to add a new queue element. We could eliminate this by always performing a
readdir_r(), and simply adding the new element if there's an element to work on
already when we acquire the queue, cutting some overhead. This would violate
our assumption that we never have more files open than we have threads,
however, meaning that we'd no longer have a fixed queue size. This is no great
loss, however; the fixed size was more a nice property that fell out of our
design than a real goal. We can use a dynamic array and indices rather than
pointers, or even dynamically-allocated queue nodes, without much cost.

Let's take this idea further (d): rather than adding the new descriptor to the
queue and taking the front work element, the thread could immediately begin
working on the new descriptor. Enqueue a new node if the new descriptor is not
completely processed, and repeat this process until readdir_r() is exhausted.
This implies state equal to the aggregate length of the files, but means that
there is never delay blocking on another thread within a file.

Of course, we achieved this in (c) anyway, at the cost of a bit extra work.
Option (d) only improves on (c) in the fairly unlikely event that there are
more files than there are threads, burns probably at least as much extra work
with all those extraneous readdir_r() calls, and eats up more memory when it
does provide a benefit. We will go with (c).

Within a thread, we will use Boyer-Moore-Galil or perhaps Apostolico–Giancarlo
or Volnitsky (the cases for which AG beats BMG can be considered pathological
for apt-file(1), but hey, completion is good. Volnitsky is Wu-Manber-ish (read:
hash-based) and difficult to characterize. BMG is well-adapted to large
alphabets and low repetition of letters within a search term, which accurately
describes our search space.

Closing note

This has all assumed purely ASCII needles and haystacks, which seems valid
from what I've seen of the Contents files. This seems a pretty shortsighted
policy, though. If someone wants to point out chapter and verse where packages
are restricted to ASCII filenames in Debian, that'd comfort me a bit. I'd go
look it up, but I've been writing this for like four hours.

nick black     http://www.sprezzatech.com -- unix and hpc consulting
to make an apple pie from scratch, you need first invent a universe.

Attachment: signature.asc
Description: Digital signature

Reply to: