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