share/doc/papers/malloc/performance.ms

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