allocators.go

     1  // Copyright 2022 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  package main
     6  
     7  // TODO: should we share backing storage for similarly-shaped types?
     8  // e.g. []*Value and []*Block, or even []int32 and []bool.
     9  
    10  import (
    11  	"bytes"
    12  	"fmt"
    13  	"go/format"
    14  	"io"
    15  	"log"
    16  	"os"
    17  )
    18  
    19  type allocator struct {
    20  	name     string // name for alloc/free functions
    21  	typ      string // the type they return/accept
    22  	mak      string // code to make a new object (takes power-of-2 size as fmt arg)
    23  	capacity string // code to calculate the capacity of an object. Should always report a power of 2.
    24  	resize   string // code to shrink to sub-power-of-two size (takes size as fmt arg)
    25  	clear    string // code for clearing object before putting it on the free list
    26  	minLog   int    // log_2 of minimum allocation size
    27  	maxLog   int    // log_2 of maximum allocation size
    28  }
    29  
    30  type derived struct {
    31  	name string // name for alloc/free functions
    32  	typ  string // the type they return/accept
    33  	base string // underlying allocator
    34  }
    35  
    36  func genAllocators() {
    37  	allocators := []allocator{
    38  		{
    39  			name:     "ValueSlice",
    40  			typ:      "[]*Value",
    41  			capacity: "cap(%s)",
    42  			mak:      "make([]*Value, %s)",
    43  			resize:   "%s[:%s]",
    44  			clear:    "clear(%s)",
    45  			minLog:   5,
    46  			maxLog:   32,
    47  		},
    48  		{
    49  			name:     "LimitSlice",
    50  			typ:      "[]limit", // the limit type is basically [4]uint64.
    51  			capacity: "cap(%s)",
    52  			mak:      "make([]limit, %s)",
    53  			resize:   "%s[:%s]",
    54  			clear:    "clear(%s)",
    55  			minLog:   3,
    56  			maxLog:   30,
    57  		},
    58  		{
    59  			name:     "SparseSet",
    60  			typ:      "*sparseSet",
    61  			capacity: "%s.cap()",
    62  			mak:      "newSparseSet(%s)",
    63  			resize:   "", // larger-sized sparse sets are ok
    64  			clear:    "%s.clear()",
    65  			minLog:   5,
    66  			maxLog:   32,
    67  		},
    68  		{
    69  			name:     "SparseMap",
    70  			typ:      "*sparseMap",
    71  			capacity: "%s.cap()",
    72  			mak:      "newSparseMap(%s)",
    73  			resize:   "", // larger-sized sparse maps are ok
    74  			clear:    "%s.clear()",
    75  			minLog:   5,
    76  			maxLog:   32,
    77  		},
    78  		{
    79  			name:     "SparseMapPos",
    80  			typ:      "*sparseMapPos",
    81  			capacity: "%s.cap()",
    82  			mak:      "newSparseMapPos(%s)",
    83  			resize:   "", // larger-sized sparse maps are ok
    84  			clear:    "%s.clear()",
    85  			minLog:   5,
    86  			maxLog:   32,
    87  		},
    88  	}
    89  	if splitPhase >= phase0Export {
    90  		allocators[1].typ = "[]Limit"
    91  		allocators[1].mak = "make([]Limit, %s)"
    92  		allocators[2].typ = "*SparseSet"
    93  		allocators[2].mak = "NewSparseSet(%s)"
    94  		allocators[2].clear = "%s.Clear()"
    95  		allocators[3].mak = "NewSparseMap(%s)"
    96  		allocators[3].clear = "%s.Clear()"
    97  		allocators[4].typ = "*SparseMapPos"
    98  		allocators[4].clear = "%s.Clear()"
    99  	}
   100  	deriveds := []derived{
   101  		{
   102  			name: "BlockSlice",
   103  			typ:  "[]*Block",
   104  			base: "ValueSlice",
   105  		},
   106  		{
   107  			name: "Int64",
   108  			typ:  "[]int64",
   109  			base: "LimitSlice",
   110  		},
   111  		{
   112  			name: "IntSlice",
   113  			typ:  "[]int",
   114  			base: "LimitSlice",
   115  		},
   116  		{
   117  			name: "Int32Slice",
   118  			typ:  "[]int32",
   119  			base: "LimitSlice",
   120  		},
   121  		{
   122  			name: "Int8Slice",
   123  			typ:  "[]int8",
   124  			base: "LimitSlice",
   125  		},
   126  		{
   127  			name: "BoolSlice",
   128  			typ:  "[]bool",
   129  			base: "LimitSlice",
   130  		},
   131  		{
   132  			name: "IDSlice",
   133  			typ:  "[]ID",
   134  			base: "LimitSlice",
   135  		},
   136  		{
   137  			name: "UintSlice",
   138  			typ:  "[]uint",
   139  			base: "LimitSlice",
   140  		},
   141  		{
   142  			name: "KnownBitsEntriesSlice",
   143  			typ:  "[]knownBitsEntry",
   144  			base: "LimitSlice",
   145  		},
   146  	}
   147  
   148  	w := new(bytes.Buffer)
   149  	fmt.Fprintf(w, "// Code generated from _gen/allocators.go using 'go generate'; DO NOT EDIT.\n")
   150  	fmt.Fprintln(w)
   151  	fmt.Fprintf(w, "package %s\n", splitCorePkg)
   152  
   153  	fmt.Fprintln(w, "import (")
   154  	fmt.Fprintln(w, "\"internal/unsafeheader\"")
   155  	fmt.Fprintln(w, "\"math/bits\"")
   156  	fmt.Fprintln(w, "\"sync\"")
   157  	fmt.Fprintln(w, "\"unsafe\"")
   158  	fmt.Fprintln(w, ")")
   159  	for _, a := range allocators {
   160  		genAllocator(w, a)
   161  	}
   162  	for _, d := range deriveds {
   163  		for _, base := range allocators {
   164  			if base.name == d.base {
   165  				genDerived(w, d, base)
   166  				break
   167  			}
   168  		}
   169  	}
   170  	// gofmt result
   171  	b := w.Bytes()
   172  	var err error
   173  	b, err = format.Source(b)
   174  	if err != nil {
   175  		fmt.Printf("%s\n", w.Bytes())
   176  		panic(err)
   177  	}
   178  
   179  	mkdirOutFile(allocatorsFile)
   180  	if err := os.WriteFile(outFile(allocatorsFile), b, 0666); err != nil {
   181  		log.Fatalf("can't write output: %v\n", err)
   182  	}
   183  }
   184  func genAllocator(w io.Writer, a allocator) {
   185  	fmt.Fprintf(w, "var poolFree%s [%d]sync.Pool\n", a.name, a.maxLog-a.minLog)
   186  	fmt.Fprintf(w, "func (c *Cache) %s%s(n int) %s {\n", splitTitle("alloc"), a.name, a.typ)
   187  	fmt.Fprintf(w, "var s %s\n", a.typ)
   188  	fmt.Fprintf(w, "n2 := n\n")
   189  	fmt.Fprintf(w, "if n2 < %d { n2 = %d }\n", 1<<a.minLog, 1<<a.minLog)
   190  	fmt.Fprintf(w, "b := bits.Len(uint(n2-1))\n")
   191  	fmt.Fprintf(w, "v := poolFree%s[b-%d].Get()\n", a.name, a.minLog)
   192  	fmt.Fprintf(w, "if v == nil {\n")
   193  	fmt.Fprintf(w, "  s = %s\n", fmt.Sprintf(a.mak, "1<<b"))
   194  	fmt.Fprintf(w, "} else {\n")
   195  	if a.typ[0] == '*' {
   196  		fmt.Fprintf(w, "s = v.(%s)\n", a.typ)
   197  	} else {
   198  		fmt.Fprintf(w, "sp := v.(*%s)\n", a.typ)
   199  		fmt.Fprintf(w, "s = *sp\n")
   200  		fmt.Fprintf(w, "*sp = nil\n")
   201  		fmt.Fprintf(w, "c.hdr%s = append(c.hdr%s, sp)\n", a.name, a.name)
   202  	}
   203  	fmt.Fprintf(w, "}\n")
   204  	if a.resize != "" {
   205  		fmt.Fprintf(w, "s = %s\n", fmt.Sprintf(a.resize, "s", "n"))
   206  	}
   207  	fmt.Fprintf(w, "return s\n")
   208  	fmt.Fprintf(w, "}\n")
   209  	fmt.Fprintf(w, "func (c *Cache) %s%s(s %s) {\n", splitTitle("free"), a.name, a.typ)
   210  	fmt.Fprintf(w, "%s\n", fmt.Sprintf(a.clear, "s"))
   211  	fmt.Fprintf(w, "b := bits.Len(uint(%s) - 1)\n", fmt.Sprintf(a.capacity, "s"))
   212  	if a.typ[0] == '*' {
   213  		fmt.Fprintf(w, "poolFree%s[b-%d].Put(s)\n", a.name, a.minLog)
   214  	} else {
   215  		fmt.Fprintf(w, "var sp *%s\n", a.typ)
   216  		fmt.Fprintf(w, "if len(c.hdr%s) == 0 {\n", a.name)
   217  		fmt.Fprintf(w, "  sp = new(%s)\n", a.typ)
   218  		fmt.Fprintf(w, "} else {\n")
   219  		fmt.Fprintf(w, "  sp = c.hdr%s[len(c.hdr%s)-1]\n", a.name, a.name)
   220  		fmt.Fprintf(w, "  c.hdr%s[len(c.hdr%s)-1] = nil\n", a.name, a.name)
   221  		fmt.Fprintf(w, "  c.hdr%s = c.hdr%s[:len(c.hdr%s)-1]\n", a.name, a.name, a.name)
   222  		fmt.Fprintf(w, "}\n")
   223  		fmt.Fprintf(w, "*sp = s\n")
   224  		fmt.Fprintf(w, "poolFree%s[b-%d].Put(sp)\n", a.name, a.minLog)
   225  	}
   226  	fmt.Fprintf(w, "}\n")
   227  }
   228  func genDerived(w io.Writer, d derived, base allocator) {
   229  	fmt.Fprintf(w, "func (c *Cache) %s%s(n int) %s {\n", splitTitle("alloc"), d.name, d.typ)
   230  	if d.typ[:2] != "[]" || base.typ[:2] != "[]" {
   231  		panic(fmt.Sprintf("bad derived types: %s %s", d.typ, base.typ))
   232  	}
   233  	fmt.Fprintf(w, "var base %s\n", base.typ[2:])
   234  	fmt.Fprintf(w, "var derived %s\n", d.typ[2:])
   235  	fmt.Fprintf(w, "if unsafe.Sizeof(base)%%unsafe.Sizeof(derived) != 0 { panic(\"bad\") }\n")
   236  	fmt.Fprintf(w, "scale := unsafe.Sizeof(base)/unsafe.Sizeof(derived)\n")
   237  	fmt.Fprintf(w, "b := c.%s%s(int((uintptr(n)+scale-1)/scale))\n", splitTitle("alloc"), base.name)
   238  	fmt.Fprintf(w, "s := unsafeheader.Slice {\n")
   239  	fmt.Fprintf(w, "  Data: unsafe.Pointer(&b[0]),\n")
   240  	fmt.Fprintf(w, "  Len: n,\n")
   241  	fmt.Fprintf(w, "  Cap: cap(b)*int(scale),\n")
   242  	fmt.Fprintf(w, "  }\n")
   243  	fmt.Fprintf(w, "return *(*%s)(unsafe.Pointer(&s))\n", d.typ)
   244  	fmt.Fprintf(w, "}\n")
   245  	fmt.Fprintf(w, "func (c *Cache) %s%s(s %s) {\n", splitTitle("free"), d.name, d.typ)
   246  	fmt.Fprintf(w, "var base %s\n", base.typ[2:])
   247  	fmt.Fprintf(w, "var derived %s\n", d.typ[2:])
   248  	fmt.Fprintf(w, "scale := unsafe.Sizeof(base)/unsafe.Sizeof(derived)\n")
   249  	fmt.Fprintf(w, "b := unsafeheader.Slice {\n")
   250  	fmt.Fprintf(w, "  Data: unsafe.Pointer(&s[0]),\n")
   251  	fmt.Fprintf(w, "  Len: int((uintptr(len(s))+scale-1)/scale),\n")
   252  	fmt.Fprintf(w, "  Cap: int((uintptr(cap(s))+scale-1)/scale),\n")
   253  	fmt.Fprintf(w, "  }\n")
   254  	fmt.Fprintf(w, "c.%s%s(*(*%s)(unsafe.Pointer(&b)))\n", splitTitle("free"), base.name, base.typ)
   255  	fmt.Fprintf(w, "}\n")
   256  }
   257
View as plain text