mksizeclasses.go

Documentation: runtime

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