Layout analysis of Rust's structs

README.md

Struct layout: total space occupied by padding

(including drop flags and tail padding)

total padding (bytes)	number of structs
0	641
1	6
2	7
3	15
4	57
5	13
6	34
7	192
8	3
10	4
11	44
12	4
13	8
14	33
15	5
17	3
18	14
19	1
21	18
22	6
24	2
25	4
26	1
27	1
28	4
29	1
31	2
32	2
33	6
35	1
40	2
42	2
44	3
47	2
53	2
55	5
92	1
106	1
110	1
631	1
675	2
963	1

After HashMap's optimizations

total padding (bytes)	number of structs
0	813
1	12
2	28
3	130
4	48
5	17
6	53
7	130
8	3
9	17
10	1
11	15
12	7
13	1
14	20
15	1
16	2
17	2
18	5
19	1
21	11
22	1
23	2
24	2
32	1
42	1
48	4
83	1

in "librustc", "rustc", "libcore", "liblibc", "liballoc", "libstd", "librand", "libcollections", "libsync", "liblog", "libterm", "libserialize", "libfmt_macros", "libsyntax", "libflate", "libarena", "libgetopts", "libtime", "libgraphviz", "libnative", "libgreen", "librustuv", "libglob", "libsemver", "libuuid", "libnum", "libregex", "libtest", "libworkcache", "liburl", "librlibc"

layout.rb

s = File.read(ARGV.first || 'layout.txt')

crates = {}
s.split(/(?=oxidize)/).drop(1).each do |crate|
   lib = crate[/\/(\w+)$/, 1]
   structs = crate.scan(/struct DefId {.*node:(.+)} size (\d+)-(\d+): \[(.*)\]/)
         .map do |id, sz, pad, fsz|
      # struct DefId { krate: 2, node: 133725 } size 96-3: [8, 4, 1, 16, 16, 16, 16, 16]
      [id, sz.to_i, pad.to_i, fsz.split(', ').map(&:to_i)]
   end
   crates[lib] = structs
end

pad_stats = {}
pad_stats.default = 0

p crates.size, crates.map{|lib,_|lib}

crates.map do |_, st|
   st && st.map {|*head, fsizes| [*head, fsizes.inject(&:+) || 0] }
end.flatten(1)
   .compact
   .uniq
   .each do |_, sz, pad, fsz|
   pad_stats[pad] += 1
end

rust.diff

diff --git a/src/librustc/middle/trans/adt.rs b/src/librustc/middle/trans/adt.rs
index 9cea6d0..2c0d2cc 100644
--- a/src/librustc/middle/trans/adt.rs
+++ b/src/librustc/middle/trans/adt.rs
@@ -147,7 +147,39 @@ pub fn represent_type(cx: &CrateContext, t: ty::t) -> Rc<Repr> {
     repr
 }
 
+fn deep_padding(cx: &CrateContext, fields: &[ty::t]) -> uint {
+    use std::iter::AdditiveIterator;
+    fields.iter().map(|&ty|
+        match ty::get(ty).sty {
+            ty::ty_tup(ref elems) => {
+                deep_padding(cx, elems.as_slice())
+            }
+            ty::ty_struct(def_id, ref substs) => {
+                let fields = ty::lookup_struct_fields(cx.tcx(), def_id);
+                let mut ftys = fields.iter().map(|field| {
+                    ty::lookup_field_type(cx.tcx(), def_id, field.id, substs)
+                }).collect::<Vec<_>>();
+
+                if ty::ty_dtor(cx.tcx(), def_id).has_drop_flag() {
+                    ftys.push(ty::mk_bool());
+                }
+
+                let lltys = ftys.iter().map(|&ty| {
+                    type_of::sizing_type_of(cx, ty)
+                }).collect::<Vec<_>>();
+
+                let llty_rec = Type::struct_(cx, lltys.as_slice(), ty::lookup_packed(cx.tcx(), def_id));
+                let field_sizes = lltys.iter().map(|&typ| machine::llsize_of_alloc(cx, typ)).collect::<Vec<u64>>();
+                let size = machine::llsize_of_alloc(cx, llty_rec) as uint;
+                size - field_sizes.move_iter().sum() as uint + deep_padding(cx, ftys.as_slice())
+            }
+            _ => 0
+        }
+    ).sum()
+}
+
 fn represent_type_uncached(cx: &CrateContext, t: ty::t) -> Repr {
+    use std::iter::AdditiveIterator;
     match ty::get(t).sty {
         ty::ty_tup(ref elems) => {
             return Univariant(mk_struct(cx, elems.as_slice(), false), false)
@@ -161,6 +193,17 @@ fn represent_type_uncached(cx: &CrateContext, t: ty::t) -> Repr {
             let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
             if dtor { ftys.push(ty::mk_bool()); }
 
+            let lltys = ftys.iter().map(|&ty| type_of::sizing_type_of(cx, ty)).collect::<Vec<_>>();
+            let llty_rec = Type::struct_(cx, lltys.as_slice(), packed);
+            let field_sizes = lltys.iter().map(|&typ| machine::llsize_of_alloc(cx, typ)).collect::<Vec<u64>>();
+            let size = machine::llsize_of_alloc(cx, llty_rec) as uint;
+            println!("struct {} size {}-{}: {}",
+                def_id,
+                size,
+                deep_padding(cx, ftys.as_slice()) + size - field_sizes.clone().move_iter().sum() as uint,
+                field_sizes
+            );
+
             return Univariant(mk_struct(cx, ftys.as_slice(), packed), dtor)
         }
         ty::ty_enum(def_id, ref substs) => {