fieldalignment.go

Documentation: golang.org/x/tools/go/analysis/passes/fieldalignment

     1  // Copyright 2020 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 fieldalignment defines an Analyzer that detects structs that would use less
     6  // memory if their fields were sorted.
     7  package fieldalignment
     8  
     9  import (
    10  	"bytes"
    11  	"fmt"
    12  	"go/ast"
    13  	"go/format"
    14  	"go/token"
    15  	"go/types"
    16  	"sort"
    17  
    18  	"golang.org/x/tools/go/analysis"
    19  	"golang.org/x/tools/go/analysis/passes/inspect"
    20  	"golang.org/x/tools/go/ast/inspector"
    21  )
    22  
    23  const Doc = `find structs that would use less memory if their fields were sorted
    24  
    25  This analyzer find structs that can be rearranged to use less memory, and provides
    26  a suggested edit with the most compact order.
    27  
    28  Note that there are two different diagnostics reported. One checks struct size,
    29  and the other reports "pointer bytes" used. Pointer bytes is how many bytes of the
    30  object that the garbage collector has to potentially scan for pointers, for example:
    31  
    32  	struct { uint32; string }
    33  
    34  have 16 pointer bytes because the garbage collector has to scan up through the string's
    35  inner pointer.
    36  
    37  	struct { string; *uint32 }
    38  
    39  has 24 pointer bytes because it has to scan further through the *uint32.
    40  
    41  	struct { string; uint32 }
    42  
    43  has 8 because it can stop immediately after the string pointer.
    44  
    45  Be aware that the most compact order is not always the most efficient.
    46  In rare cases it may cause two variables each updated by its own goroutine
    47  to occupy the same CPU cache line, inducing a form of memory contention
    48  known as "false sharing" that slows down both goroutines.
    49  `
    50  
    51  var Analyzer = &analysis.Analyzer{
    52  	Name:     "fieldalignment",
    53  	Doc:      Doc,
    54  	URL:      "https://pkg.go.dev/golang.org/x/tools/go/analysis/passes/fieldalignment",
    55  	Requires: []*analysis.Analyzer{inspect.Analyzer},
    56  	Run:      run,
    57  }
    58  
    59  func run(pass *analysis.Pass) (interface{}, error) {
    60  	inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
    61  	nodeFilter := []ast.Node{
    62  		(*ast.StructType)(nil),
    63  	}
    64  	inspect.Preorder(nodeFilter, func(node ast.Node) {
    65  		var s *ast.StructType
    66  		var ok bool
    67  		if s, ok = node.(*ast.StructType); !ok {
    68  			return
    69  		}
    70  		if tv, ok := pass.TypesInfo.Types[s]; ok {
    71  			fieldalignment(pass, s, tv.Type.(*types.Struct))
    72  		}
    73  	})
    74  	return nil, nil
    75  }
    76  
    77  var unsafePointerTyp = types.Unsafe.Scope().Lookup("Pointer").(*types.TypeName).Type()
    78  
    79  func fieldalignment(pass *analysis.Pass, node *ast.StructType, typ *types.Struct) {
    80  	wordSize := pass.TypesSizes.Sizeof(unsafePointerTyp)
    81  	maxAlign := pass.TypesSizes.Alignof(unsafePointerTyp)
    82  
    83  	s := gcSizes{wordSize, maxAlign}
    84  	optimal, indexes := optimalOrder(typ, &s)
    85  	optsz, optptrs := s.Sizeof(optimal), s.ptrdata(optimal)
    86  
    87  	var message string
    88  	if sz := s.Sizeof(typ); sz != optsz {
    89  		message = fmt.Sprintf("struct of size %d could be %d", sz, optsz)
    90  	} else if ptrs := s.ptrdata(typ); ptrs != optptrs {
    91  		message = fmt.Sprintf("struct with %d pointer bytes could be %d", ptrs, optptrs)
    92  	} else {
    93  		// Already optimal order.
    94  		return
    95  	}
    96  
    97  	// Flatten the ast node since it could have multiple field names per list item while
    98  	// *types.Struct only have one item per field.
    99  	// TODO: Preserve multi-named fields instead of flattening.
   100  	var flat []*ast.Field
   101  	for _, f := range node.Fields.List {
   102  		// TODO: Preserve comment, for now get rid of them.
   103  		//       See https://github.com/golang/go/issues/20744
   104  		f.Comment = nil
   105  		f.Doc = nil
   106  		if len(f.Names) <= 1 {
   107  			flat = append(flat, f)
   108  			continue
   109  		}
   110  		for _, name := range f.Names {
   111  			flat = append(flat, &ast.Field{
   112  				Names: []*ast.Ident{name},
   113  				Type:  f.Type,
   114  			})
   115  		}
   116  	}
   117  
   118  	// Sort fields according to the optimal order.
   119  	var reordered []*ast.Field
   120  	for _, index := range indexes {
   121  		reordered = append(reordered, flat[index])
   122  	}
   123  
   124  	newStr := &ast.StructType{
   125  		Fields: &ast.FieldList{
   126  			List: reordered,
   127  		},
   128  	}
   129  
   130  	// Write the newly aligned struct node to get the content for suggested fixes.
   131  	var buf bytes.Buffer
   132  	if err := format.Node(&buf, token.NewFileSet(), newStr); err != nil {
   133  		return
   134  	}
   135  
   136  	pass.Report(analysis.Diagnostic{
   137  		Pos:     node.Pos(),
   138  		End:     node.Pos() + token.Pos(len("struct")),
   139  		Message: message,
   140  		SuggestedFixes: []analysis.SuggestedFix{{
   141  			Message: "Rearrange fields",
   142  			TextEdits: []analysis.TextEdit{{
   143  				Pos:     node.Pos(),
   144  				End:     node.End(),
   145  				NewText: buf.Bytes(),
   146  			}},
   147  		}},
   148  	})
   149  }
   150  
   151  func optimalOrder(str *types.Struct, sizes *gcSizes) (*types.Struct, []int) {
   152  	nf := str.NumFields()
   153  
   154  	type elem struct {
   155  		index   int
   156  		alignof int64
   157  		sizeof  int64
   158  		ptrdata int64
   159  	}
   160  
   161  	elems := make([]elem, nf)
   162  	for i := 0; i < nf; i++ {
   163  		field := str.Field(i)
   164  		ft := field.Type()
   165  		elems[i] = elem{
   166  			i,
   167  			sizes.Alignof(ft),
   168  			sizes.Sizeof(ft),
   169  			sizes.ptrdata(ft),
   170  		}
   171  	}
   172  
   173  	sort.Slice(elems, func(i, j int) bool {
   174  		ei := &elems[i]
   175  		ej := &elems[j]
   176  
   177  		// Place zero sized objects before non-zero sized objects.
   178  		zeroi := ei.sizeof == 0
   179  		zeroj := ej.sizeof == 0
   180  		if zeroi != zeroj {
   181  			return zeroi
   182  		}
   183  
   184  		// Next, place more tightly aligned objects before less tightly aligned objects.
   185  		if ei.alignof != ej.alignof {
   186  			return ei.alignof > ej.alignof
   187  		}
   188  
   189  		// Place pointerful objects before pointer-free objects.
   190  		noptrsi := ei.ptrdata == 0
   191  		noptrsj := ej.ptrdata == 0
   192  		if noptrsi != noptrsj {
   193  			return noptrsj
   194  		}
   195  
   196  		if !noptrsi {
   197  			// If both have pointers...
   198  
   199  			// ... then place objects with less trailing
   200  			// non-pointer bytes earlier. That is, place
   201  			// the field with the most trailing
   202  			// non-pointer bytes at the end of the
   203  			// pointerful section.
   204  			traili := ei.sizeof - ei.ptrdata
   205  			trailj := ej.sizeof - ej.ptrdata
   206  			if traili != trailj {
   207  				return traili < trailj
   208  			}
   209  		}
   210  
   211  		// Lastly, order by size.
   212  		if ei.sizeof != ej.sizeof {
   213  			return ei.sizeof > ej.sizeof
   214  		}
   215  
   216  		return false
   217  	})
   218  
   219  	fields := make([]*types.Var, nf)
   220  	indexes := make([]int, nf)
   221  	for i, e := range elems {
   222  		fields[i] = str.Field(e.index)
   223  		indexes[i] = e.index
   224  	}
   225  	return types.NewStruct(fields, nil), indexes
   226  }
   227  
   228  // Code below based on go/types.StdSizes.
   229  
   230  type gcSizes struct {
   231  	WordSize int64
   232  	MaxAlign int64
   233  }
   234  
   235  func (s *gcSizes) Alignof(T types.Type) int64 {
   236  	// For arrays and structs, alignment is defined in terms
   237  	// of alignment of the elements and fields, respectively.
   238  	switch t := T.Underlying().(type) {
   239  	case *types.Array:
   240  		// spec: "For a variable x of array type: unsafe.Alignof(x)
   241  		// is the same as unsafe.Alignof(x[0]), but at least 1."
   242  		return s.Alignof(t.Elem())
   243  	case *types.Struct:
   244  		// spec: "For a variable x of struct type: unsafe.Alignof(x)
   245  		// is the largest of the values unsafe.Alignof(x.f) for each
   246  		// field f of x, but at least 1."
   247  		max := int64(1)
   248  		for i, nf := 0, t.NumFields(); i < nf; i++ {
   249  			if a := s.Alignof(t.Field(i).Type()); a > max {
   250  				max = a
   251  			}
   252  		}
   253  		return max
   254  	}
   255  	a := s.Sizeof(T) // may be 0
   256  	// spec: "For a variable x of any type: unsafe.Alignof(x) is at least 1."
   257  	if a < 1 {
   258  		return 1
   259  	}
   260  	if a > s.MaxAlign {
   261  		return s.MaxAlign
   262  	}
   263  	return a
   264  }
   265  
   266  var basicSizes = [...]byte{
   267  	types.Bool:       1,
   268  	types.Int8:       1,
   269  	types.Int16:      2,
   270  	types.Int32:      4,
   271  	types.Int64:      8,
   272  	types.Uint8:      1,
   273  	types.Uint16:     2,
   274  	types.Uint32:     4,
   275  	types.Uint64:     8,
   276  	types.Float32:    4,
   277  	types.Float64:    8,
   278  	types.Complex64:  8,
   279  	types.Complex128: 16,
   280  }
   281  
   282  func (s *gcSizes) Sizeof(T types.Type) int64 {
   283  	switch t := T.Underlying().(type) {
   284  	case *types.Basic:
   285  		k := t.Kind()
   286  		if int(k) < len(basicSizes) {
   287  			if s := basicSizes[k]; s > 0 {
   288  				return int64(s)
   289  			}
   290  		}
   291  		if k == types.String {
   292  			return s.WordSize * 2
   293  		}
   294  	case *types.Array:
   295  		return t.Len() * s.Sizeof(t.Elem())
   296  	case *types.Slice:
   297  		return s.WordSize * 3
   298  	case *types.Struct:
   299  		nf := t.NumFields()
   300  		if nf == 0 {
   301  			return 0
   302  		}
   303  
   304  		var o int64
   305  		max := int64(1)
   306  		for i := 0; i < nf; i++ {
   307  			ft := t.Field(i).Type()
   308  			a, sz := s.Alignof(ft), s.Sizeof(ft)
   309  			if a > max {
   310  				max = a
   311  			}
   312  			if i == nf-1 && sz == 0 && o != 0 {
   313  				sz = 1
   314  			}
   315  			o = align(o, a) + sz
   316  		}
   317  		return align(o, max)
   318  	case *types.Interface:
   319  		return s.WordSize * 2
   320  	}
   321  	return s.WordSize // catch-all
   322  }
   323  
   324  // align returns the smallest y >= x such that y % a == 0.
   325  func align(x, a int64) int64 {
   326  	y := x + a - 1
   327  	return y - y%a
   328  }
   329  
   330  func (s *gcSizes) ptrdata(T types.Type) int64 {
   331  	switch t := T.Underlying().(type) {
   332  	case *types.Basic:
   333  		switch t.Kind() {
   334  		case types.String, types.UnsafePointer:
   335  			return s.WordSize
   336  		}
   337  		return 0
   338  	case *types.Chan, *types.Map, *types.Pointer, *types.Signature, *types.Slice:
   339  		return s.WordSize
   340  	case *types.Interface:
   341  		return 2 * s.WordSize
   342  	case *types.Array:
   343  		n := t.Len()
   344  		if n == 0 {
   345  			return 0
   346  		}
   347  		a := s.ptrdata(t.Elem())
   348  		if a == 0 {
   349  			return 0
   350  		}
   351  		z := s.Sizeof(t.Elem())
   352  		return (n-1)*z + a
   353  	case *types.Struct:
   354  		nf := t.NumFields()
   355  		if nf == 0 {
   356  			return 0
   357  		}
   358  
   359  		var o, p int64
   360  		for i := 0; i < nf; i++ {
   361  			ft := t.Field(i).Type()
   362  			a, sz := s.Alignof(ft), s.Sizeof(ft)
   363  			fp := s.ptrdata(ft)
   364  			o = align(o, a)
   365  			if fp != 0 {
   366  				p = o + fp
   367  			}
   368  			o += sz
   369  		}
   370  		return p
   371  	}
   372  
   373  	panic("impossible")
   374  }
   375
View as plain text