mksizeclasses.go

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Generate tables for small malloc size classes.
     6  //
     7  // See malloc.go for overview.
     8  //
     9  // The size classes are chosen so that rounding an allocation
    10  // request up to the next size class wastes at most 12.5% (1.125x).
    11  //
    12  // Each size class has its own page count that gets allocated
    13  // and chopped up when new objects of the size class are needed.
    14  // That page count is chosen so that chopping up the run of
    15  // pages into objects of the given size wastes at most 12.5% (1.125x)
    16  // of the memory. It is not necessary that the cutoff here be
    17  // the same as above.
    18  //
    19  // The two sources of waste multiply, so the worst possible case
    20  // for the above constraints would be that allocations of some
    21  // size might have a 26.6% (1.266x) overhead.
    22  // In practice, only one of the wastes comes into play for a
    23  // given size (sizes < 512 waste mainly on the round-up,
    24  // sizes > 512 waste mainly on the page chopping).
    25  // For really small sizes, alignment constraints force the
    26  // overhead higher.
    27  
    28  package main
    29  
    30  import (
    31  	"bytes"
    32  	"flag"
    33  	"fmt"
    34  	"io"
    35  	"math"
    36  	"math/bits"
    37  )
    38  
    39  // Generate internal/runtime/gc/msize.go
    40  
    41  func generateSizeClasses(classes []class) []byte {
    42  	flag.Parse()
    43  
    44  	var b bytes.Buffer
    45  	fmt.Fprintln(&b, "// Code generated by mksizeclasses.go; DO NOT EDIT.")
    46  	fmt.Fprintln(&b, "//go:generate go -C ../../../runtime/_mkmalloc run mksizeclasses.go")
    47  	fmt.Fprintln(&b)
    48  	fmt.Fprintln(&b, "package gc")
    49  
    50  	printComment(&b, classes)
    51  
    52  	printClasses(&b, classes)
    53  
    54  	return b.Bytes()
    55  }
    56  
    57  type class struct {
    58  	size   int // max size
    59  	npages int // number of pages
    60  }
    61  
    62  func powerOfTwo(x int) bool {
    63  	return x != 0 && x&(x-1) == 0
    64  }
    65  
    66  func makeClasses() []class {
    67  	var classes []class
    68  
    69  	classes = append(classes, class{}) // class #0 is a dummy entry
    70  
    71  	align := minHeapAlign
    72  	for size := align; size <= maxSmallSize; size += align {
    73  		if powerOfTwo(size) { // bump alignment once in a while
    74  			if size >= 2048 {
    75  				align = 256
    76  			} else if size >= 128 {
    77  				align = size / 8
    78  			} else if size >= 32 {
    79  				align = 16 // heap bitmaps assume 16 byte alignment for allocations >= 32 bytes.
    80  			}
    81  		}
    82  		if !powerOfTwo(align) {
    83  			panic("incorrect alignment")
    84  		}
    85  
    86  		// Make the allocnpages big enough that
    87  		// the leftover is less than 1/8 of the total,
    88  		// so wasted space is at most 12.5%.
    89  		allocsize := pageSize
    90  		for allocsize%size > allocsize/8 {
    91  			allocsize += pageSize
    92  		}
    93  		npages := allocsize / pageSize
    94  
    95  		// If the previous sizeclass chose the same
    96  		// allocation size and fit the same number of
    97  		// objects into the page, we might as well
    98  		// use just this size instead of having two
    99  		// different sizes.
   100  		if len(classes) > 1 && npages == classes[len(classes)-1].npages && allocsize/size == allocsize/classes[len(classes)-1].size {
   101  			classes[len(classes)-1].size = size
   102  			continue
   103  		}
   104  		classes = append(classes, class{size: size, npages: npages})
   105  	}
   106  
   107  	// Increase object sizes if we can fit the same number of larger objects
   108  	// into the same number of pages. For example, we choose size 8448 above
   109  	// with 6 objects in 7 pages. But we can well use object size 9472,
   110  	// which is also 6 objects in 7 pages but +1024 bytes (+12.12%).
   111  	// We need to preserve at least largeSizeDiv alignment otherwise
   112  	// sizeToClass won't work.
   113  	for i := range classes {
   114  		if i == 0 {
   115  			continue
   116  		}
   117  		c := &classes[i]
   118  		psize := c.npages * pageSize
   119  		new_size := (psize / (psize / c.size)) &^ (largeSizeDiv - 1)
   120  		if new_size > c.size {
   121  			c.size = new_size
   122  		}
   123  	}
   124  
   125  	if len(classes) != 68 {
   126  		panic("number of size classes has changed")
   127  	}
   128  
   129  	for i := range classes {
   130  		computeDivMagic(&classes[i])
   131  	}
   132  
   133  	return classes
   134  }
   135  
   136  // computeDivMagic checks that the division required to compute object
   137  // index from span offset can be computed using 32-bit multiplication.
   138  // n / c.size is implemented as (n * (^uint32(0)/uint32(c.size) + 1)) >> 32
   139  // for all 0 <= n <= c.npages * pageSize
   140  func computeDivMagic(c *class) {
   141  	// divisor
   142  	d := c.size
   143  	if d == 0 {
   144  		return
   145  	}
   146  
   147  	// maximum input value for which the formula needs to work.
   148  	max := c.npages * pageSize
   149  
   150  	// As reported in [1], if n and d are unsigned N-bit integers, we
   151  	// can compute n / d as ⌊n * c / 2^F⌋, where c is ⌈2^F / d⌉ and F is
   152  	// computed with:
   153  	//
   154  	// 	Algorithm 2: Algorithm to select the number of fractional bits
   155  	// 	and the scaled approximate reciprocal in the case of unsigned
   156  	// 	integers.
   157  	//
   158  	// 	if d is a power of two then
   159  	// 		Let F ← log₂(d) and c = 1.
   160  	// 	else
   161  	// 		Let F ← N + L where L is the smallest integer
   162  	// 		such that d ≤ (2^(N+L) mod d) + 2^L.
   163  	// 	end if
   164  	//
   165  	// [1] "Faster Remainder by Direct Computation: Applications to
   166  	// Compilers and Software Libraries" Daniel Lemire, Owen Kaser,
   167  	// Nathan Kurz arXiv:1902.01961
   168  	//
   169  	// To minimize the risk of introducing errors, we implement the
   170  	// algorithm exactly as stated, rather than trying to adapt it to
   171  	// fit typical Go idioms.
   172  	N := bits.Len(uint(max))
   173  	var F int
   174  	if powerOfTwo(d) {
   175  		F = int(math.Log2(float64(d)))
   176  		if d != 1<<F {
   177  			panic("imprecise log2")
   178  		}
   179  	} else {
   180  		for L := 0; ; L++ {
   181  			if d <= ((1<<(N+L))%d)+(1<<L) {
   182  				F = N + L
   183  				break
   184  			}
   185  		}
   186  	}
   187  
   188  	// Also, noted in the paper, F is the smallest number of fractional
   189  	// bits required. We use 32 bits, because it works for all size
   190  	// classes and is fast on all CPU architectures that we support.
   191  	if F > 32 {
   192  		fmt.Printf("d=%d max=%d N=%d F=%d\n", c.size, max, N, F)
   193  		panic("size class requires more than 32 bits of precision")
   194  	}
   195  
   196  	// Brute force double-check with the exact computation that will be
   197  	// done by the runtime.
   198  	m := ^uint32(0)/uint32(c.size) + 1
   199  	for n := 0; n <= max; n++ {
   200  		if uint32((uint64(n)*uint64(m))>>32) != uint32(n/c.size) {
   201  			fmt.Printf("d=%d max=%d m=%d n=%d\n", d, max, m, n)
   202  			panic("bad 32-bit multiply magic")
   203  		}
   204  	}
   205  }
   206  
   207  func printComment(w io.Writer, classes []class) {
   208  	fmt.Fprintf(w, "// %-5s  %-9s  %-10s  %-7s  %-10s  %-9s  %-9s\n", "class", "bytes/obj", "bytes/span", "objects", "tail waste", "max waste", "min align")
   209  	prevSize := 0
   210  	var minAligns [pageShift + 1]int
   211  	for i, c := range classes {
   212  		if i == 0 {
   213  			continue
   214  		}
   215  		spanSize := c.npages * pageSize
   216  		objects := spanSize / c.size
   217  		tailWaste := spanSize - c.size*(spanSize/c.size)
   218  		maxWaste := float64((c.size-prevSize-1)*objects+tailWaste) / float64(spanSize)
   219  		alignBits := bits.TrailingZeros(uint(c.size))
   220  		if alignBits > pageShift {
   221  			// object alignment is capped at page alignment
   222  			alignBits = pageShift
   223  		}
   224  		for i := range minAligns {
   225  			if i > alignBits {
   226  				minAligns[i] = 0
   227  			} else if minAligns[i] == 0 {
   228  				minAligns[i] = c.size
   229  			}
   230  		}
   231  		prevSize = c.size
   232  		fmt.Fprintf(w, "// %5d  %9d  %10d  %7d  %10d  %8.2f%%  %9d\n", i, c.size, spanSize, objects, tailWaste, 100*maxWaste, 1<<alignBits)
   233  	}
   234  	fmt.Fprintf(w, "\n")
   235  
   236  	fmt.Fprintf(w, "// %-9s  %-4s  %-12s\n", "alignment", "bits", "min obj size")
   237  	for bits, size := range minAligns {
   238  		if size == 0 {
   239  			break
   240  		}
   241  		if bits+1 < len(minAligns) && size == minAligns[bits+1] {
   242  			continue
   243  		}
   244  		fmt.Fprintf(w, "// %9d  %4d  %12d\n", 1<<bits, bits, size)
   245  	}
   246  	fmt.Fprintf(w, "\n")
   247  }
   248  
   249  func maxObjsPerSpan(classes []class) int {
   250  	most := 0
   251  	for _, c := range classes[1:] {
   252  		n := c.npages * pageSize / c.size
   253  		most = max(most, n)
   254  	}
   255  	return most
   256  }
   257  
   258  func maxNPages(classes []class) int {
   259  	most := 0
   260  	for _, c := range classes[1:] {
   261  		most = max(most, c.npages)
   262  	}
   263  	return most
   264  }
   265  
   266  func printClasses(w io.Writer, classes []class) {
   267  	sizeToSizeClass := func(size int) int {
   268  		for j, c := range classes {
   269  			if c.size >= size {
   270  				return j
   271  			}
   272  		}
   273  		panic("unreachable")
   274  	}
   275  
   276  	fmt.Fprintln(w, "const (")
   277  	fmt.Fprintf(w, "MinHeapAlign = %d\n", minHeapAlign)
   278  	fmt.Fprintf(w, "MaxSmallSize = %d\n", maxSmallSize)
   279  	fmt.Fprintf(w, "SmallSizeDiv = %d\n", smallSizeDiv)
   280  	fmt.Fprintf(w, "SmallSizeMax = %d\n", smallSizeMax)
   281  	fmt.Fprintf(w, "LargeSizeDiv = %d\n", largeSizeDiv)
   282  	fmt.Fprintf(w, "NumSizeClasses = %d\n", len(classes))
   283  	fmt.Fprintf(w, "PageShift = %d\n", pageShift)
   284  	fmt.Fprintf(w, "MaxObjsPerSpan = %d\n", maxObjsPerSpan(classes))
   285  	fmt.Fprintf(w, "MaxSizeClassNPages = %d\n", maxNPages(classes))
   286  	fmt.Fprintf(w, "TinySize = %d\n", tinySize)
   287  	fmt.Fprintf(w, "TinySizeClass = %d\n", sizeToSizeClass(tinySize))
   288  	fmt.Fprintln(w, ")")
   289  
   290  	fmt.Fprint(w, "var SizeClassToSize = [NumSizeClasses]uint16 {")
   291  	for _, c := range classes {
   292  		fmt.Fprintf(w, "%d,", c.size)
   293  	}
   294  	fmt.Fprintln(w, "}")
   295  
   296  	fmt.Fprint(w, "var SizeClassToNPages = [NumSizeClasses]uint8 {")
   297  	for _, c := range classes {
   298  		fmt.Fprintf(w, "%d,", c.npages)
   299  	}
   300  	fmt.Fprintln(w, "}")
   301  
   302  	fmt.Fprint(w, "var SizeClassToDivMagic = [NumSizeClasses]uint32 {")
   303  	for _, c := range classes {
   304  		if c.size == 0 {
   305  			fmt.Fprintf(w, "0,")
   306  			continue
   307  		}
   308  		fmt.Fprintf(w, "^uint32(0)/%d+1,", c.size)
   309  	}
   310  	fmt.Fprintln(w, "}")
   311  
   312  	// map from size to size class, for small sizes.
   313  	sc := make([]int, smallSizeMax/smallSizeDiv+1)
   314  	for i := range sc {
   315  		size := i * smallSizeDiv
   316  		sc[i] = sizeToSizeClass(size)
   317  	}
   318  	fmt.Fprint(w, "var SizeToSizeClass8 = [SmallSizeMax/SmallSizeDiv+1]uint8 {")
   319  	for _, v := range sc {
   320  		fmt.Fprintf(w, "%d,", v)
   321  	}
   322  	fmt.Fprintln(w, "}")
   323  
   324  	// map from size to size class, for large sizes.
   325  	sc = make([]int, (maxSmallSize-smallSizeMax)/largeSizeDiv+1)
   326  	for i := range sc {
   327  		size := smallSizeMax + i*largeSizeDiv
   328  		sc[i] = sizeToSizeClass(size)
   329  	}
   330  	fmt.Fprint(w, "var SizeToSizeClass128 = [(MaxSmallSize-SmallSizeMax)/LargeSizeDiv+1]uint8 {")
   331  	for _, v := range sc {
   332  		fmt.Fprintf(w, "%d,", v)
   333  	}
   334  	fmt.Fprintln(w, "}")
   335  }
   336
View as plain text