packing structures and numbers
I've been reading btrfs's on-disk format, and two things caught my eye
- attribute((packed)) structures everywhere, often with misaligned fields. This conserves space, but can be harmful to in-memory performance on some archs.
- le64's everywhere. This scales nicely, but wastes space. My home directory is unlikely to have more than 4G objects or 4GB extents (let alone >2 devices).
I think the two issues can be improved by separating the on-disk format and the in-memory structure, and by using uleb128 as the on-disk format for numbers. uleb128 is a variable-length format that encodes 7 bits of a number in each byte, using the eighth bit as a stop bit.
So, for example
struct btrfs_disk_key {
__le64 objectid;
u8 type;
__le64 offset;
} __attribute__ ((__packed__));
With 1M objectids, and 1T offsets, this reduces in size from 17 bytes to 10 bytes. Most other structures show similar gains. We can also have more than 256 types if the need arises.
There are, off course, disadvantages to switching to uleb128:
- need to write encode and decode functions, which is tedious. This can be automated a la xdr.
- increased cpu utilization for decoding and encoding
- can no longer know the size of the in-memory structures in advance
- it's just wonderful to rewrite the entire disk format so close to freezing it
The advantages, IMO, outweigh the disadvantages:
- better packing reduces tree depth and therefore seekage, the most important cost on rotating media
- the disk format is infinitely growable
- in-memory format is more efficient for archs which prefer aligned accesses
I'm not volunteering to do this, but please consider this proposal.
Signature · 2 lines
I have a truly marvellous patch that fixes the bug which this signature is too narrow to contain.
Quoted 5 lines · Avi Kivity
I've been reading btrfs's on-disk format, and two things caught my eye
- attribute((packed)) structures everywhere, often with misaligned fields. This conserves space, but can be harmful to in-memory performance on some archs.
packed is important to make sure that a given field takes exactly the same amount of space everywhere, regardless of compiler optimization or arch.
Quoted 9 lines
- le64's everywhere. This scales nicely, but wastes space. My home
directory is unlikely to have more than 4G objects or 4GB extents (let alone >2 devices).I think the two issues can be improved by separating the on-disk format and the in-memory structure, and by using uleb128 as the on-disk format for numbers. uleb128 is a variable-length format that encodes 7 bits of a number in each byte, using the eighth bit as a stop bit.
This couldn't be used everywhere, as the array of items headers and keys need to be a fixed sized the current bin_search code. The items can be variable sized but in general they don't have as many le64s.
The place we're really suffering from poor packing is in the extent allocation tree.
But, most of the space being wasted there is in the item headers and keys ;) I'd prefer to address that by consolidating the items stored, especially for the btree block extents.
-chris
Quoted 4 lines · Chris Mason
Quoted 2 lines · Avi Kivity
I've been reading btrfs's on-disk format, and two things caught my eye
Quoted 8 lines
Quoted 3 lines
- attribute((packed)) structures everywhere, often with misaligned
fields. This conserves space, but can be harmful to in-memory performance on some archs.packed is important to make sure that a given field takes exactly the same amount of space everywhere, regardless of compiler optimization or arch.
Yes, of course.
Quoted 12 lines
Quoted 6 lines
- le64's everywhere. This scales nicely, but wastes space. My home
directory is unlikely to have more than 4G objects or 4GB extents (let alone >2 devices).I think the two issues can be improved by separating the on-disk format and the in-memory structure, and by using uleb128 as the on-disk format for numbers. uleb128 is a variable-length format that encodes 7 bits of a number in each byte, using the eighth bit as a stop bit.
This couldn't be used everywhere, as the array of items headers and keys need to be a fixed sized the current
bin_searchcode. The items can be variable sized but in general they don't have as many le64s.
You'd decode the keys and headers before searching. This of couse negates the idea behind a binary search, unless you cache the decoded nodes.
Signature · 2 lines
I have a truly marvellous patch that fixes the bug which this signature is too narrow to contain.
Quoted 10 lines · Chris Mason
Quoted 5 lines · Avi Kivity
I've been reading btrfs's on-disk format, and two things caught my eye
- attribute((packed)) structures everywhere, often with misaligned fields. This conserves space, but can be harmful to in-memory performance on some archs.
packed is important to make sure that a given field takes exactly the same amount of space everywhere, regardless of compiler optimization or arch.
Amen. Are we sure that attribute ((packed)) works the same on all arches?
And what about bitfields, does GCC pack them to the same size on all arches in this case or take the easy way out as permitted by the standard?
Regards,
Daniel
Quoted 8 lines · Daniel Phillips
Quoted 7 lines · Chris Mason
Quoted 5 lines · Avi Kivity
I've been reading btrfs's on-disk format, and two things caught my eye
- attribute((packed)) structures everywhere, often with misaligned fields. This conserves space, but can be harmful to in-memory performance on some archs.
Quoted 6 lines
Quoted 3 lines
packed is important to make sure that a given field takes exactly the same amount of space everywhere, regardless of compiler optimization or arch.
Amen. Are we sure that attribute ((packed)) works the same on all arches?
As long as you use types with strictly defined size, yes.
Quoted 4 lines
And what about bitfields, does GCC pack them to the same size on all arches in this case or take the easy way out as permitted by the standard?
I'm not sure, I believe a bit field on a strictly defined size will be packed the same everywhere. But bitfields + endian conversion are messy, so I avoid them.
-chris
Quoted 8 lines · Chris Mason
Quoted 3 lines · Daniel Phillips
And what about bitfields, does GCC pack them to the same size on all arches in this case or take the easy way out as permitted by the standard?
I'm not sure, I believe a bit field on a strictly defined size will be packed the same everywhere. But bitfields + endian conversion are messy, so I avoid them.
Likewise, sigh. On the other hand, packed + endian can't really be avoided.
Regards,
Daniel
Quoted 5 lines · Chris Mason
Quoted 2 lines · Daniel Phillips
...Are we sure that attribute ((packed)) works the same on all arches?
As long as you use types with strictly defined size, yes.
Just to be a language lawyer about that... int does not have a strictly defined size, yet we define uint32_t as a typedef of int on 32 bit arches do we not?
Regards,
Daniel
Quoted 7 lines · Daniel Phillips
Quoted 5 lines · Chris Mason
Quoted 3 lines · Daniel Phillips
...Are we sure that attribute ((packed)) works the same on all arches?
Quoted 7 lines
Quoted 2 lines
As long as you use types with strictly defined size, yes.
Just to be a language lawyer about that... int does not have a strictly defined size, yet we define
uint32_tas a typedef of int on 32 bit arches do we not?
What else would you define it to?
Signature · 2 lines
I have a truly marvellous patch that fixes the bug which this signature is too narrow to contain.
Quoted 5 lines · Avi Kivity
I've been reading btrfs's on-disk format, and two things caught my eye
- attribute((packed)) structures everywhere, often with misaligned fields. This conserves space, but can be harmful to in-memory performance on some archs.
How harmful? Do you have any profiles that can even pick this out of the noise?
- z
Quoted 4 lines · Zach Brown
Quoted 2 lines · Avi Kivity
I've been reading btrfs's on-disk format, and two things caught my eye
Quoted 8 lines
Quoted 4 lines
- attribute((packed)) structures everywhere, often with misaligned fields. This conserves space, but can be harmful to in-memory performance on some archs.
How harmful? Do you have any profiles that can even pick this out of the noise?
On those archs that take faults on unaligned accesses it's unlikely to be in the noise. But we could (and should) stick a get_unaligned() in the accessor functions.
uleb128 encoding is orthogonal to this issue, however. It's only about getting better density.
Signature · 2 lines
I have a truly marvellous patch that fixes the bug which this signature is too narrow to contain.
Quoted 10 lines · Avi Kivity
Quoted 9 lines · Zach Brown
Quoted 6 lines · Avi Kivity
I've been reading btrfs's on-disk format, and two things caught my eye
- attribute((packed)) structures everywhere, often with misaligned fields. This conserves space, but can be harmful to in-memory performance on some archs.
Quoted 7 lines
Quoted 3 lines
How harmful? Do you have any profiles that can even pick this out of the noise?
On those archs that take faults on unaligned accesses it's unlikely to be in the noise. But we could (and should) stick a
get_unaligned()in the accessor functions.
Normally the compiler on such architectures generates special load/store code for known unaligned types that does not actually fault, but just uses multiple instructions. That is slower than a normal memory access, but still much faster than a exception.
You only really get the full exception fault penalty when the compiler cannot figure out at compile time that a given variable is unaligned. But with packed it normally assumes that (I think).
-Andi
Signature · 1 line
[email protected]
Quoted 5 lines · Andi Kleen
Quoted 4 lines
On those archs that take faults on unaligned accesses it's unlikely to be in the noise. But we could (and should) stick a
get_unaligned()in the accessor functions.
Quoted 8 lines
Normally the compiler on such architectures generates special load/store code for known unaligned types that does not actually fault, but just uses multiple instructions. That is slower than a normal memory access, but still much faster than a exception.
You only really get the full exception fault penalty when the compiler cannot figure out at compile time that a given variable is unaligned. But with packed it normally assumes that (I think)
Sounds reasonable. In which case the unaligned access issue I raised is a red herring. So using uleb128 or not is down to whether the improved packing efficiency is worth the increased complexity; it seems unlikely that it is.
Signature · 2 lines
I have a truly marvellous patch that fixes the bug which this signature is too narrow to contain.