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