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