That memory alignment thing
This is the second day of my participation in the August Text Challenge.More challenges in August
Introduction: When I read the source code of Redis SDS and explain it before, I often see that memory alignment can improve efficiency, but I don’t know how to achieve it. Recently, WHEN REVIEWING the underlying data structure of Redis, I took a look at memory alignment.
1. Definition of memory alignment
Wikipedia defines memory alignment as follows:
A memory address a is said to be n-byte aligned when a is a multiple of n bytes (where n is a power of 2). In this context, a byte is the smallest unit of memory access, i.e. each memory address specifies a different byte. An n-byte aligned address would have a minimum of log2(n) least-significant zeros when expressed in binary.
When A is A multiple of n bytes (where n is A power of 2), the storage address A is said to be n-byte aligned. In this context, a byte is the smallest unit of memory access, that is, each memory address specifies a different byte. When represented in binary, an n-byte aligned address has at least log2(n) least significant zeros.
Wikipedia may be a little confusing, but memory alignment is simply a way to improve code efficiency by sacrificing space.
Memory alignment is required for several aspects
- Base type alignment, memory address alignment. The alignment factor for the base type may differ on different architecture CPU platforms.
- The alignment of cache lines between CPU and memory is a pseudo-sharing problem.
2. Why memory alignment
If the memory is not aligned, the number of accesses will increase due to hardware limitations, affecting efficiency. Although memory is measured in bytes, most processors do not measure memory in bytes. They typically measure memory in double, four, eight, 16, and 32 bytes, which we call memory granularity.
Suppose the system is now 32-bit and can only read data from memory at multiples of 4. If no memory alignment, arbitrary data storage, so if a type int data starts stored address 2 (occupy 2 5-tetrafluorobenzoic) so there are addressing in the need to read two bytes, and the need to eliminate 0,1,6,7 four addresses, and the address 2, 5-tetrafluorobenzoic merged into together, reduces the efficiency, increase the cost. So you have memory alignment.
Specific reference is as follows:
3. Memory alignment rules
Each compiler on a particular platform has its own default “alignment coefficient” (also known as the alignment modulus).
Valid alignment values are the “alignment coefficient” of a given value and the smaller of the longest data type length in the data structure. Valid alignment values are also called alignment units.
Alignment rules:
- The offset for a member in the structure is 0, and each member’s offset from the first address of the structure is an integer multiple of the smaller of the member’s size and the valid alignment value. The compiler adds padding bytes between the members if necessary.
- The total size of the structure is an integer multiple of the valid aligned value, and the compiler adds a padding byte after the last member if necessary.
Example:
// 64-bit system
#include<stdio.h>
struct{
int a,
char b,
double c,
}s1;
struct{
int a,
double c,
char b,
}s2;
struct{
char b,
int a,
double c,
}s3;
int main(a){
printf("%d\n".sizeof(s1)); / / 16
printf("%d\n".sizeof(s2)); / / 24
printf("%d\n".sizeof(s3)); / / 16
}
Copy the codeUse the two rules above to calculate the number of bytes each of the three data structures takes up.
| S1 Memory usage (8 bytes) | S2 Memory usage (8 bytes) | S3 Memory usage (8 bytes) |
|---|---|---|
| A 4 bytes B 1 byte (8 bytes) | A 4 bytes (8 bytes) | B 1 byte A 4 byte (8 bytes) |
| C 8 bytes (8 bytes) | C 8 bytes (8 bytes) | C 1 byte (8 bytes) |
| B 1 byte (8 bytes) | ||
| Total: 8 + 8 = 16 | Total: 8 + 8 + 8 = 24 | Total: 8 + 8 = 16 |
Take S1 as an example for analysis:
The number of bytes of a is 4<=8 bytes, aligned with 4 bytes, occupying unit 0,1,2,3;
The number of bytes of B is 1<=8 bytes, aligned according to 1 byte, and the offset relative to the first address should be a multiple of four, occupying the fourth unit;
The number of bytes of C is 8<=8 bytes, and it should be aligned according to 8 bytes. The offset relative to the first address of the structure should be a multiple of 8, occupying 8-15 cells.
Similarly, the other two data structures occupy bytes.
From the analysis of this example, you should have a little understanding of memory alignment.
4. Memory alignment on 32-bit and 64-bit systems
1.64 a
#include<stdio.h>
struct A
{
int a; / / 4 bytes
char b; / / 1 byte
double c; / / 8 bytes
char d; / / 1 byte
};
struct B
{
char a;
double b;
char c;
};
int main(a)
{
Int =4,char=1,double=8
printf("int =%lu,char=%lu,double=%lu\n".sizeof(int),sizeof(char),sizeof(double));
// result: structA=24 structB=24
printf("structA=%lu structB=%lu\n".sizeof(struct A),sizeof(struct B));
return 0;
}
Copy the codeIt is easy to calculate according to the rules in Section 3:
StructA: 4+1+3(alignment)+8+1+7(alignment) =24
StructB: 1+7(alignment)+8+1+7(alignment) = 24
2.32 a
#include<stdio.h>
struct A
{
int a; / / 4
char b; / / 1
double c; / / 8
char d; / / 1
};
struct B
{
char a;
double b;
char c;
};
int main(a)
{
// result: int=4 char=1 double=8
printf("int =%u,char=%u,double=%u\n".sizeof(int),sizeof(char),sizeof(double));
// result: structA=20 structB=16
printf("structA=%u structB=%u\n".sizeof(struct A),sizeof(struct B));
return 0;
}
Copy the codeThe reason why 32-bit and 64-bit systems calculate bytes differently is that the alignment modulus in 32-bit systems is 4 bytes, while in 64-bit systems the alignment model is 8 bytes.
structA:
structB:
