...
Run Format

Source file src/runtime/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  // +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  	"io/ioutil"
    39  	"log"
    40  	"os"
    41  )
    42  
    43  // Generate msize.go
    44  
    45  var stdout = flag.Bool("stdout", false, "write to stdout instead of sizeclasses.go")
    46  
    47  func main() {
    48  	flag.Parse()
    49  
    50  	var b bytes.Buffer
    51  	fmt.Fprintln(&b, "// Code generated by mksizeclasses.go; DO NOT EDIT.")
    52  	fmt.Fprintln(&b, "//go:generate go run mksizeclasses.go")
    53  	fmt.Fprintln(&b)
    54  	fmt.Fprintln(&b, "package runtime")
    55  	classes := makeClasses()
    56  
    57  	printComment(&b, classes)
    58  
    59  	printClasses(&b, classes)
    60  
    61  	out, err := format.Source(b.Bytes())
    62  	if err != nil {
    63  		log.Fatal(err)
    64  	}
    65  	if *stdout {
    66  		_, err = os.Stdout.Write(out)
    67  	} else {
    68  		err = ioutil.WriteFile("sizeclasses.go", out, 0666)
    69  	}
    70  	if err != nil {
    71  		log.Fatal(err)
    72  	}
    73  }
    74  
    75  const (
    76  	// Constants that we use and will transfer to the runtime.
    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  	mul    int
    92  	shift  uint
    93  	shift2 uint
    94  	mask   int
    95  }
    96  
    97  func powerOfTwo(x int) bool {
    98  	return x != 0 && x&(x-1) == 0
    99  }
   100  
   101  func makeClasses() []class {
   102  	var classes []class
   103  
   104  	classes = append(classes, class{}) // class #0 is a dummy entry
   105  
   106  	align := 8
   107  	for size := align; size <= maxSmallSize; size += align {
   108  		if powerOfTwo(size) { // bump alignment once in a while
   109  			if size >= 2048 {
   110  				align = 256
   111  			} else if size >= 128 {
   112  				align = size / 8
   113  			} else if size >= 16 {
   114  				align = 16 // required for x86 SSE instructions, if we want to use them
   115  			}
   116  		}
   117  		if !powerOfTwo(align) {
   118  			panic("incorrect alignment")
   119  		}
   120  
   121  		// Make the allocnpages big enough that
   122  		// the leftover is less than 1/8 of the total,
   123  		// so wasted space is at most 12.5%.
   124  		allocsize := pageSize
   125  		for allocsize%size > allocsize/8 {
   126  			allocsize += pageSize
   127  		}
   128  		npages := allocsize / pageSize
   129  
   130  		// If the previous sizeclass chose the same
   131  		// allocation size and fit the same number of
   132  		// objects into the page, we might as well
   133  		// use just this size instead of having two
   134  		// different sizes.
   135  		if len(classes) > 1 && npages == classes[len(classes)-1].npages && allocsize/size == allocsize/classes[len(classes)-1].size {
   136  			classes[len(classes)-1].size = size
   137  			continue
   138  		}
   139  		classes = append(classes, class{size: size, npages: npages})
   140  	}
   141  
   142  	// Increase object sizes if we can fit the same number of larger objects
   143  	// into the same number of pages. For example, we choose size 8448 above
   144  	// with 6 objects in 7 pages. But we can well use object size 9472,
   145  	// which is also 6 objects in 7 pages but +1024 bytes (+12.12%).
   146  	// We need to preserve at least largeSizeDiv alignment otherwise
   147  	// sizeToClass won't work.
   148  	for i := range classes {
   149  		if i == 0 {
   150  			continue
   151  		}
   152  		c := &classes[i]
   153  		psize := c.npages * pageSize
   154  		new_size := (psize / (psize / c.size)) &^ (largeSizeDiv - 1)
   155  		if new_size > c.size {
   156  			c.size = new_size
   157  		}
   158  	}
   159  
   160  	if len(classes) != 67 {
   161  		panic("number of size classes has changed")
   162  	}
   163  
   164  	for i := range classes {
   165  		computeDivMagic(&classes[i])
   166  	}
   167  
   168  	return classes
   169  }
   170  
   171  // computeDivMagic computes some magic constants to implement
   172  // the division required to compute object number from span offset.
   173  // n / c.size is implemented as n >> c.shift * c.mul >> c.shift2
   174  // for all 0 <= n < c.npages * pageSize
   175  func computeDivMagic(c *class) {
   176  	// divisor
   177  	d := c.size
   178  	if d == 0 {
   179  		return
   180  	}
   181  
   182  	// maximum input value for which the formula needs to work.
   183  	max := c.npages*pageSize - 1
   184  
   185  	if powerOfTwo(d) {
   186  		// If the size is a power of two, heapBitsForObject can divide even faster by masking.
   187  		// Compute this mask.
   188  		if max >= 1<<16 {
   189  			panic("max too big for power of two size")
   190  		}
   191  		c.mask = 1<<16 - d
   192  	}
   193  
   194  	// Compute pre-shift by factoring power of 2 out of d.
   195  	for d%2 == 0 {
   196  		c.shift++
   197  		d >>= 1
   198  		max >>= 1
   199  	}
   200  
   201  	// Find the smallest k that works.
   202  	// A small k allows us to fit the math required into 32 bits
   203  	// so we can use 32-bit multiplies and shifts on 32-bit platforms.
   204  nextk:
   205  	for k := uint(0); ; k++ {
   206  		mul := (int(1)<<k + d - 1) / d //  ⌈2^k / dβŒ‰
   207  
   208  		// Test to see if mul works.
   209  		for n := 0; n <= max; n++ {
   210  			if n*mul>>k != n/d {
   211  				continue nextk
   212  			}
   213  		}
   214  		if mul >= 1<<16 {
   215  			panic("mul too big")
   216  		}
   217  		if uint64(mul)*uint64(max) >= 1<<32 {
   218  			panic("mul*max too big")
   219  		}
   220  		c.mul = mul
   221  		c.shift2 = k
   222  		break
   223  	}
   224  
   225  	// double-check.
   226  	for n := 0; n <= max; n++ {
   227  		if n*c.mul>>c.shift2 != n/d {
   228  			fmt.Printf("d=%d max=%d mul=%d shift2=%d n=%d\n", d, max, c.mul, c.shift2, n)
   229  			panic("bad multiply magic")
   230  		}
   231  		// Also check the exact computations that will be done by the runtime,
   232  		// for both 32 and 64 bit operations.
   233  		if uint32(n)*uint32(c.mul)>>uint8(c.shift2) != uint32(n/d) {
   234  			fmt.Printf("d=%d max=%d mul=%d shift2=%d n=%d\n", d, max, c.mul, c.shift2, n)
   235  			panic("bad 32-bit multiply magic")
   236  		}
   237  		if uint64(n)*uint64(c.mul)>>uint8(c.shift2) != uint64(n/d) {
   238  			fmt.Printf("d=%d max=%d mul=%d shift2=%d n=%d\n", d, max, c.mul, c.shift2, n)
   239  			panic("bad 64-bit multiply magic")
   240  		}
   241  	}
   242  }
   243  
   244  func printComment(w io.Writer, classes []class) {
   245  	fmt.Fprintf(w, "// %-5s  %-9s  %-10s  %-7s  %-10s  %-9s\n", "class", "bytes/obj", "bytes/span", "objects", "tail waste", "max waste")
   246  	prevSize := 0
   247  	for i, c := range classes {
   248  		if i == 0 {
   249  			continue
   250  		}
   251  		spanSize := c.npages * pageSize
   252  		objects := spanSize / c.size
   253  		tailWaste := spanSize - c.size*(spanSize/c.size)
   254  		maxWaste := float64((c.size-prevSize-1)*objects+tailWaste) / float64(spanSize)
   255  		prevSize = c.size
   256  		fmt.Fprintf(w, "// %5d  %9d  %10d  %7d  %10d  %8.2f%%\n", i, c.size, spanSize, objects, tailWaste, 100*maxWaste)
   257  	}
   258  	fmt.Fprintf(w, "\n")
   259  }
   260  
   261  func printClasses(w io.Writer, classes []class) {
   262  	fmt.Fprintln(w, "const (")
   263  	fmt.Fprintf(w, "_MaxSmallSize = %d\n", maxSmallSize)
   264  	fmt.Fprintf(w, "smallSizeDiv = %d\n", smallSizeDiv)
   265  	fmt.Fprintf(w, "smallSizeMax = %d\n", smallSizeMax)
   266  	fmt.Fprintf(w, "largeSizeDiv = %d\n", largeSizeDiv)
   267  	fmt.Fprintf(w, "_NumSizeClasses = %d\n", len(classes))
   268  	fmt.Fprintf(w, "_PageShift = %d\n", pageShift)
   269  	fmt.Fprintln(w, ")")
   270  
   271  	fmt.Fprint(w, "var class_to_size = [_NumSizeClasses]uint16 {")
   272  	for _, c := range classes {
   273  		fmt.Fprintf(w, "%d,", c.size)
   274  	}
   275  	fmt.Fprintln(w, "}")
   276  
   277  	fmt.Fprint(w, "var class_to_allocnpages = [_NumSizeClasses]uint8 {")
   278  	for _, c := range classes {
   279  		fmt.Fprintf(w, "%d,", c.npages)
   280  	}
   281  	fmt.Fprintln(w, "}")
   282  
   283  	fmt.Fprintln(w, "type divMagic struct {")
   284  	fmt.Fprintln(w, "  shift uint8")
   285  	fmt.Fprintln(w, "  shift2 uint8")
   286  	fmt.Fprintln(w, "  mul uint16")
   287  	fmt.Fprintln(w, "  baseMask uint16")
   288  	fmt.Fprintln(w, "}")
   289  	fmt.Fprint(w, "var class_to_divmagic = [_NumSizeClasses]divMagic {")
   290  	for _, c := range classes {
   291  		fmt.Fprintf(w, "{%d,%d,%d,%d},", c.shift, c.shift2, c.mul, c.mask)
   292  	}
   293  	fmt.Fprintln(w, "}")
   294  
   295  	// map from size to size class, for small sizes.
   296  	sc := make([]int, smallSizeMax/smallSizeDiv+1)
   297  	for i := range sc {
   298  		size := i * smallSizeDiv
   299  		for j, c := range classes {
   300  			if c.size >= size {
   301  				sc[i] = j
   302  				break
   303  			}
   304  		}
   305  	}
   306  	fmt.Fprint(w, "var size_to_class8 = [smallSizeMax/smallSizeDiv+1]uint8 {")
   307  	for _, v := range sc {
   308  		fmt.Fprintf(w, "%d,", v)
   309  	}
   310  	fmt.Fprintln(w, "}")
   311  
   312  	// map from size to size class, for large sizes.
   313  	sc = make([]int, (maxSmallSize-smallSizeMax)/largeSizeDiv+1)
   314  	for i := range sc {
   315  		size := smallSizeMax + i*largeSizeDiv
   316  		for j, c := range classes {
   317  			if c.size >= size {
   318  				sc[i] = j
   319  				break
   320  			}
   321  		}
   322  	}
   323  	fmt.Fprint(w, "var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv+1]uint8 {")
   324  	for _, v := range sc {
   325  		fmt.Fprintf(w, "%d,", v)
   326  	}
   327  	fmt.Fprintln(w, "}")
   328  }
   329  

View as plain text