why this re-arrange algorithm works?

[cuiweixie]

structslop/structslop.go

Lines 246 to 267 in 13637e2

	sort.Slice(fields, func(i, j int) bool {
	ti, tj := fields[i].Type(), fields[j].Type()
	si, sj := sizes.Sizeof(ti), sizes.Sizeof(tj)
	if si == 0 && sj != 0 {
	return true
	}
	if sj == 0 && si != 0 {
	return false
	}
	ai, aj := sizes.Alignof(ti), sizes.Alignof(tj)
	if ai != aj {
	return ai > aj
	}
	if si != sj {
	return si > sj
	}
	return false
	})

why sort by <align of field, size of field> can minimize the sizeof struct?
is there some formal prove?

[kirbyquerby]

This isn't quite a formal proof, but:

If a struct field would be placed at an offset from the beginning of the struct not divisible by its align, then padding will be inserted between it and the previous field. Because alignments will be to a number of bytes that is a power of 2, a field with an alignment <= the alignment of the previous field will not require padding, since the larger field's alignment is a multiple of the smaller field's alignment. Therefore, sorting by descending alignment should guarantee that there will be no padding between the struct's fields.

There could still be padding at the end of the struct (for example if the last field in a struct has a size smaller than the overall struct's alignment). Interestingly, this means there might still be padding between struct fields if the fields themselves have padding included at the end. Thus, it could be possible to get further savings (at the cost of readability and probably other things) by flattening a struct. For instance: https://go.dev/play/p/ALZhIBGTKbQ

I'm less certain whether having the secondary sorting key be the size of the field, but at the very least, it makes it clear which fields in a struct take up the most space :)

See:

• https://go.dev/ref/spec#System_considerations
• https://go.dev/ref/spec#Size_and_alignment_guarantees
• https://en.wikipedia.org/wiki/Data_structure_alignment#Default_packing_and_#pragma_pack