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.
7 // Generate tables for small malloc size classes.
9 // See malloc.go for overview.
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).
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
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
45 var stdout
= flag
.Bool("stdout", false, "write to stdout instead of sizeclasses.go")
51 fmt
.Fprintln(&b
, "// Code generated by mksizeclasses.go; DO NOT EDIT.")
52 fmt
.Fprintln(&b
, "//go:generate go run mksizeclasses.go")
54 fmt
.Fprintln(&b
, "package runtime")
55 classes
:= makeClasses()
57 printComment(&b
, classes
)
59 printClasses(&b
, classes
)
61 out
, err
:= format
.Source(b
.Bytes())
66 _
, err
= os
.Stdout
.Write(out
)
68 err
= ioutil
.WriteFile("sizeclasses.go", out
, 0666)
76 // Constants that we use and will transfer to the runtime.
77 maxSmallSize
= 32 << 10
84 pageSize
= 1 << pageShift
89 npages
int // number of pages
97 func powerOfTwo(x
int) bool {
98 return x
!= 0 && x
&(x
-1) == 0
101 func makeClasses() []class
{
104 classes
= append(classes
, class
{}) // class #0 is a dummy entry
107 for size
:= align
; size
<= maxSmallSize
; size
+= align
{
108 if powerOfTwo(size
) { // bump alignment once in a while
111 } else if size
>= 128 {
113 } else if size
>= 16 {
114 align
= 16 // required for x86 SSE instructions, if we want to use them
117 if !powerOfTwo(align
) {
118 panic("incorrect alignment")
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
128 npages
:= allocsize
/ pageSize
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
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
139 classes
= append(classes
, class
{size
: size
, npages
: npages
})
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
{
153 psize
:= c
.npages
* pageSize
154 new_size
:= (psize
/ (psize
/ c
.size
)) &^ (largeSizeDiv
- 1)
155 if new_size
> c
.size
{
160 if len(classes
) != 67 {
161 panic("number of size classes has changed")
164 for i
:= range classes
{
165 computeDivMagic(&classes
[i
])
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
) {
182 // maximum input value for which the formula needs to work.
183 max
:= c
.npages
*pageSize
- 1
186 // If the size is a power of two, heapBitsForObject can divide even faster by masking.
187 // Compute this mask.
189 panic("max too big for power of two size")
194 // Compute pre-shift by factoring power of 2 out of d.
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.
205 for k
:= uint(0); ; k
++ {
206 mul
:= (int(1)<<k
+ d
- 1) / d
// ā2^k / dā
208 // Test to see if mul works.
209 for n
:= 0; n
<= max
; n
++ {
217 if uint64(mul
)*uint64(max
) >= 1<<32 {
218 panic("mul*max too big")
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")
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")
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")
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")
247 for i
, c
:= range classes
{
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
)
256 fmt
.Fprintf(w
, "// %5d %9d %10d %7d %10d %8.2f%%\n", i
, c
.size
, spanSize
, objects
, tailWaste
, 100*maxWaste
)
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
)
271 fmt
.Fprint(w
, "var class_to_size = [_NumSizeClasses]uint16 {")
272 for _
, c
:= range classes
{
273 fmt
.Fprintf(w
, "%d,", c
.size
)
277 fmt
.Fprint(w
, "var class_to_allocnpages = [_NumSizeClasses]uint8 {")
278 for _
, c
:= range classes
{
279 fmt
.Fprintf(w
, "%d,", c
.npages
)
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")
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
)
295 // map from size to size class, for small sizes.
296 sc
:= make([]int, smallSizeMax
/smallSizeDiv
+1)
298 size
:= i
* smallSizeDiv
299 for j
, c
:= range classes
{
306 fmt
.Fprint(w
, "var size_to_class8 = [smallSizeMax/smallSizeDiv+1]uint8 {")
307 for _
, v
:= range sc
{
308 fmt
.Fprintf(w
, "%d,", v
)
312 // map from size to size class, for large sizes.
313 sc
= make([]int, (maxSmallSize
-smallSizeMax
)/largeSizeDiv
+1)
315 size
:= smallSizeMax
+ i
*largeSizeDiv
316 for j
, c
:= range classes
{
323 fmt
.Fprint(w
, "var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv+1]uint8 {")
324 for _
, v
:= range sc
{
325 fmt
.Fprintf(w
, "%d,", v
)