Source file src/runtime/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	// +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
   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