Reordering instance variables to save space

[HertzDevil]

Instance variables in a type are laid out in the order the compiler calls Crystal::Type#declare_instance_var on the type. Roughly speaking, TypeDeclarations and UninitializedVars go first, followed by other things like plain assignments. We can write this:

struct Foo
  @a = uninitialized Int64
  @b = uninitialized Bool
  @c = uninitialized Int64
  @d = uninitialized Bool
  @e = uninitialized Int64
  @f = uninitialized Bool
  @g = uninitialized Int64
  @h = uninitialized Bool
end

offsetof(Foo, @a) # => 0
offsetof(Foo, @b) # => 8
offsetof(Foo, @c) # => 16
offsetof(Foo, @d) # => 24
offsetof(Foo, @e) # => 32
offsetof(Foo, @f) # => 40
offsetof(Foo, @g) # => 48
offsetof(Foo, @h) # => 56
sizeof(Foo)       # => 64

We can also rearrange those instance variables to produce a smaller struct:

struct Foo
  @a = uninitialized Int64
  @c = uninitialized Int64
  @e = uninitialized Int64
  @g = uninitialized Int64
  @b = uninitialized Bool
  @d = uninitialized Bool
  @f = uninitialized Bool
  @h = uninitialized Bool
end

offsetof(Foo, @a) # => 0
offsetof(Foo, @c) # => 8
offsetof(Foo, @e) # => 16
offsetof(Foo, @g) # => 24
offsetof(Foo, @b) # => 32
offsetof(Foo, @d) # => 33
offsetof(Foo, @f) # => 34
offsetof(Foo, @h) # => 35
sizeof(Foo)       # => 40

By reordering the instance variables, we have reduced the amount of padding between them and, therefore, the total byte size occupied by a Foo instance.

I propose that the compiler should do this automatically for every type that isn't a primitive type or an extern type. All instance variables within a struct, not including its supertypes or subtypes, would be sorted in descending order by their alignments. For classes the situation is a bit different:

class Foo
  @a = uninitialized Int64
  @c = uninitialized Int64
  @e = uninitialized Int64
  @g = uninitialized Int64
  @b = uninitialized Bool
  @d = uninitialized Bool
  @f = uninitialized Bool
  @h = uninitialized Bool
end

offsetof(Foo, @a)    # => 8
offsetof(Foo, @c)    # => 16
offsetof(Foo, @e)    # => 24
offsetof(Foo, @g)    # => 32
offsetof(Foo, @b)    # => 40
offsetof(Foo, @d)    # => 41
offsetof(Foo, @f)    # => 42
offsetof(Foo, @h)    # => 43
instance_sizeof(Foo) # => 48

class Foo
  @b = uninitialized Bool
  @d = uninitialized Bool
  @f = uninitialized Bool
  @h = uninitialized Bool
  @a = uninitialized Int64
  @c = uninitialized Int64
  @e = uninitialized Int64
  @g = uninitialized Int64
end

offsetof(Foo, @b)    # => 4
offsetof(Foo, @d)    # => 5
offsetof(Foo, @f)    # => 6
offsetof(Foo, @h)    # => 7
offsetof(Foo, @a)    # => 8
offsetof(Foo, @c)    # => 16
offsetof(Foo, @e)    # => 24
offsetof(Foo, @g)    # => 32
instance_sizeof(Foo) # => 40

Because all reference types start with a type ID, which is an Int32 with an alignment of 4 bytes, it would be more efficient if instance variables with an alignment of 4, 2, or 1 byte are placed first, followed by other variables with an alignment larger than 4. This applies to classes whose entire inheritance chain up to Reference does not define any instance variables, in particular classes inheriting directly from Reference; subsequent subclasses are free to continue placing the most strictly aligned instance variables first.

A consequence is that the same generic type may order its instance variables differently depending on the generic arguments:

struct Foo(T)
  @x = uninitialized Int32
  @y = uninitialized T
end

offsetof(Foo(Int64), @x) # => 8
offsetof(Foo(Int64), @y) # => 0
sizeof(Foo(Int64)        # => 16

offsetof(Foo(Int8), @x) # => 0
offsetof(Foo(Int8), @y) # => 4
sizeof(Foo(Int8)        # => 8

The instance variables are never reordered across types; an instance variable in a subclass will never be moved before any instance variable in its superclasses. Thus, a pointer to a subclass is implicitly also a pointer to any of its superclasses. However, the same need not apply to included modules:

module Foo
  @x = uninitialized Int32
end

# `@x` and `@y` may be reordered
struct Bar(T)
  include Foo
  @y = uninitialized T
end

Here it is assumed that Foo#@x will always perform some kind of dynamic dispatch similar to union-typed variables.

String and Log::Metadata are special since they do not have a fixed instance size. Instead, String#@c and Log::Metadata#@first are flexible array members that must be the last instance variable, although the rest of their instance variables can still be reordered. (For String this requires a bit of extra effort when defining its constants too.) There should be a special annotation for these special instance variables.

[beta-ziliani]

It makes a lot of sense. Great analysis, Quinton! 👏

[straight-shoota]

There should be a special annotation for these special instance variables.

One idea could be to repurpose @[Extern] for this because it's a bit of a similar situation. But then it's not really because we actually just need to pin a specific ivar to be the last one and everything else can be reordered as pleased.
So probably a dedicated annotation for the ivar specifically would be better.

There is some similarity to #7773 which proposes annotations for ivars regarding alignment and packing.

For String this requires a bit of extra effort when defining its constants too.

I noticed that as well while working on #12020 (which introduces an additional ivar): The memory layout of String is hard coded in three different places or so in the compiler (and prior to #13335 even in stdlib).

[Blacksmoke16]

Given this is at the codegen level, macros would all be expanded already before the reordering happens yea? I.e. TypeNode#instance_vars would still return them in the same order as they do now?

[straight-shoota]

@Blacksmoke16 Yeah, this is all limited to codegen.
I don't think we could reasonably change the order of instance variables in the semantic phase / reflection (like TypeNode#instance_vars). That would break a lot of things.

[funny-falcon]

But struct could be used for fast protocols: casting pointer to bytes into pointer to struct, and you're ready to read values.

So, there should be not only @[Extern], but @[Packet] as well.

Probably @[Extern] is a good name as well for this case, since we “externalize through raw serialization to bytes which are written to external storage/network”. Though I don’t know current it’s semantics.

[HertzDevil]

@[Extern] only guarantees a struct has the same layout as if it were declared inside a lib, I don't think what you mention is related

[funny-falcon]

@HertzDevil by the effect (fixed field order and offsets, ie fixed layout) it is the same. But by meaning, it is not.