share/doc/papers/malloc/performance.ms

   1 .\"
   2 .\" ----------------------------------------------------------------------------
   3 .\" "THE BEER-WARE LICENSE" (Revision 42):
   4 .\" <phk@login.dknet.dk> wrote this file.  As long as you retain this notice you
   5 .\" can do whatever you want with this stuff. If we meet some day, and you think
   6 .\" this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
   7 .\" ----------------------------------------------------------------------------
   8 .\"
   9 .\" $FreeBSD: src/share/doc/papers/malloc/performance.ms,v 1.6 1999/08/28 00:18:11 peter Exp $
  10 .\" $DragonFly: src/share/doc/papers/malloc/performance.ms,v 1.2 2003/06/17 04:36:56 dillon Exp $
  11 .\"
  12 .ds RH Performance
  13 .NH
  14 Performance
  15 .PP
  16 Performance for a malloc(3) implementation comes as two variables:
  17 .IP
  18 A: How much time does it use for searching and manipulating data structures.
  19 We will refer to this as ``overhead time''.
  20 .IP
  21 B: How well does it manage the storage.
  22 This rather vague metric we call ``quality of allocation''.
  23 .PP
  24 The overhead time is easy to measure, just to a lot of malloc/free calls
  25 of various kinds and combination, and compare the results.
  26 .PP
  27 The quality of allocation is not quite as simple as that.
  28 One measure of quality is the size of the process, that should obviously
  29 be minimized.
  30 Another measure is the execution time of the process.
  31 This is not an obvious indicator of quality, but people will generally
  32 agree that it should be minimized as well, and if malloc(3) can do
  33 anything to do so, it should.
  34 Explanation why it is still a good metric follows:
  35 .PP
  36 In a traditional segment/swap kernel, the desirable behaviour of a process
  37 is to keep the brk(2) as low as possible, thus minimizing the size of the
  38 data/bss/heap segment, which in turn translates to a smaller process and
  39 a smaller probability of the process being swapped out, qed: faster
  40 execution time as an average.
  41 .PP
  42 In a paging environment this is not a bad choice for a default, but
  43 a couple of details needs to be looked at much more carefully.
  44 .PP
  45 First of all, the size of a process becomes a more vague concept since
  46 only the pages that are actually used need to be in primary storage
  47 for execution to progress, and they only need to be there when used.
  48 That implies that many more processes can fit in the same amount of
  49 primary storage, since most processes have a high degree of locality
  50 of reference and thus only need some fraction of their pages to actually
  51 do their job.
  52 .PP
  53 From this it follows that the interesting size of the process, is some
  54 subset of the total amount of virtual memory occupied by the process.
  55 This number isn't a constant, it varies depending on the whereabouts
  56 of the process, and it may indeed fluctuate wildly over the lifetime
  57 of the process.
  58 .PP
  59 One of the names for this vague concept is ``current working set''.
  60 It has been defined many different ways over the years, mostly to
  61 satisfy and support claims in marketing or benchmark contexts.
  62 .PP
  63 For now we can simply say that it is the number of pages the process
  64 needs in order to run at a sufficiently low paging rate in a congested
  65 primary storage.
  66 (If primary storage isn't congested, this is not really important
  67 of course, but most systems would be better off using the pages for
  68 disk-cache or similar functions, so from that perspective it will
  69 always be congested.)
  70 If the number of pages is too small, the process will wait for its
  71 pages to be read from secondary storage much of the time, if it's too
  72 big, the space could be used better for something else.
  73 .PP
  74 From the view of any single process, this number of pages is
  75 "all of my pages", but from the point of view of the OS it should
  76 be tuned to maximise the total throughput of all the processes on
  77 the machine at the time.
  78 This is usually done using various kinds of least-recently-used
  79 replacement algorithms to select page candidates for replacement.
  80 .PP
  81 With this knowledge, can we decide what the performance goal is for
  82 a modern malloc(3) ?
  83 Well, it's almost as simple as it used to be:
  84 .B
  85 Minimize the number of pages accessed.
  86 .R
  87 .PP
  88 This really is the core of it all.
  89 If the number of accessed pages is smaller, then locality of reference is
  90 higher, and all kinds of caches (which is essentially what the
  91 primary storage is in a VM system) work better.
  92 .PP
  93 It's interesting to notice that the classical malloc fails on this one
  94 because the information about free chunks is kept with the free
  95 chunks themselves.  In some of the benchmarks this came out as all the
  96 pages being paged in every time a malloc call was made, because malloc
  97 had to traverse the free list to find a suitable chunk for the allocation.
  98 If memory is not in use, then you shouldn't access it.
  99 .PP
 100 The secondary goal is more evident:
 101 .B
 102 Try to work in pages.
 103 .R
 104 .PP
 105 That makes it easier for the kernel, and wastes less virtual memory.
 106 Most modern implementations do this when they interact with the
 107 kernel, but few try to avoid objects spanning pages.
 108 .PP
 109 If an object's size
 110 is less than or equal to a page, there is no reason for it to span two pages.
 111 Having objects span pages means that two pages must be
 112 paged in, if that object is accessed.
 113 .PP
 114 With this analysis in the luggage, we can start coding.