Field alignment
A processor reads a number fastest if it lies at an address that is a multiple of its size. So the Go compiler places each field of a struct at an address that is a multiple of its alignment, leaving empty bytes before the field if necessary. The struct itself is aligned by the strictest of its fields, and its size is rounded up to a multiple of that alignment, so that in an array of structs every field also lies correctly.
Sizes and alignments on a 64-bit machine:
| Types | Size | Alignment |
|---|---|---|
bool, int8, uint8, byte | 1 | 1 |
int16, uint16 | 2 | 2 |
int32, uint32, rune, float32 | 4 | 4 |
int64, uint64, int, uint, uintptr, float64, a pointer *T, map[K]V | 8 | 8 |
string, any, error, complex128 | 16 | 8 |
a slice []T | 24 | 8 |
an array [k]T | k · the size of T | as for T |
| a struct described earlier in the input | its size | its alignment |
For each struct find its size with the fields in the order described, and the smallest size that can be achieved by reordering its fields (nested structs stay as they are).
Input
The first line holds q (1 ≤ q ≤ 1000), the number of structs. Then the structs in order: a line with the name and the number of fields k (1 ≤ k ≤ 12), then k lines “name type”. A type is written without spaces and refers only to types from the table and to structs described above; the size of any struct is at most 10⁹.
Output
For each struct, its name, its size in the order described and the smallest size.
Examples
Example 1
2 Event 6 Done bool Mag float64 Deep bool Year int32 Felt bool Count int64 Quake 7 Time string Lat float64 Lon float64 Depth float64 Mag float64 MagType string Place string
Event 40 24 Quake 80 80
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The size of every type is a multiple of its alignment. What happens if the fields are laid from the most strictly aligned to the least?
2The idea
The size in the order described is a direct simulation: the offset grows, before each field it is rounded up to a multiple of its alignment, and at the end to a multiple of the largest alignment. For the smallest size, sort the fields by alignment from largest to smallest and compute the same way. Nested structs, arrays and compound types reduce to a pair “size, alignment” recursively.
3Walkthrough
Why sorting by alignment is optimal. The size of any order is at least the sum of the field sizes rounded up to a multiple of the largest alignment A: all the fields lie in it, and the size of the struct is a multiple of A. And the order by decreasing alignment reaches this bound. Alignments are powers of two, and while fields of alignment a are being laid, the offset is a multiple of a: all the previous fields had alignment at least a, and their sizes are multiples of their alignments, hence of a. No empty bytes are left between fields, only a tail at the end.
Sorting by size is a common mistake that usually works. It fails when the size is not equal to the alignment: the array [3]int32 weighs 12 bytes with alignment 4. Placed before an int64, it shifts it by 4 bytes: in the second test the struct Pixel comes out at 48 bytes instead of 40.
In the example from the article on memory, the fields bool, float64, bool, int32, bool, int64 take 40 bytes, 17 of them empty. From largest to smallest, 24. All answers to this problem match what unsafe.Sizeof shows in real Go; the fieldalignment analyser from golang.org/x/tools looks for exactly such structs.
3+Solution
4Complexity
O(k log k) per struct plus parsing the types: the sizes of described structs are remembered in a dictionary.
5Common mistakes
- Sorting by size. Breaks on arrays whose size is larger than their alignment.
- Forgetting the tail. The size of a struct is rounded up to its alignment:
float32,bool,float32is 12 bytes, not 9. - Reordering the fields of a nested struct. A nested struct is one field with its own size; only the fields of the current struct may be reordered.
Algorithms behind it
the estimate is bytes per record × the number of records
1 problem
PAR
Technique
Greedy algorithms
The best step now with no looking back: when it is optimal, when almost, and how to prove it.
usually O(n log n): a sort or a heap
2 problems