[Pre-RFC] Improved Unsizing

language design
17

Assuming I understood the problem correctly, here's an algorithmic proof:

Suppose the type's alignment requirement is B.

for A in [1,2,4,...,B/4,B/2]:

  1. Gather the fields with alignment A together.
  2. If their total size is not a multiple of the next alignment (2A), add one A-byte padding element to fix that
  3. Reorder these fields arbitrarily (they have the same alignment)
  4. Replace these fields (including the possible padding element) with a single tuple with 2A-alignment (this will be included in step 1 on the next iteration)

When done you only have fields of the maximum alignment B, so no more padding is required. Total padding added is at most 1+2+4+...+B/4+B/2 = B-1 bytes, so it is minimal as the padded size must be a multiple of B. Any specific field can be made the last in the struct by doing so in every step 3. (You can get much more freedom in step 4 by pairing the fields into multiple chunks, each a multiple of 2A in size.)

1 Like