C: Cấu trúc dữ liệu căn chỉnh

Question

Tôi đang làm việc với các cấu trúc và có một số câu hỏi về chúng. Khi tôi hiểu các biến cấu trúc sẽ được đặt ở bộ nhớ tuần tự. Độ dài của khối (từ) phụ thuộc vào kiến ​​trúc máy (32 bit - 4 byte, 64 bit - 8 byte).

phép nói rằng chúng tôi có 2 cấu trúc dữ liệu:

struct ST1 { 
    char c1; 
    short s; 
    char c2; 
    double d; 
    int i; 
}; 

Trong bộ nhớ nó sẽ là:

32 bit - 20 bytes  
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 
------------------------------------------------------------------------------------------ 
c1| PB| s | s | c1| PB| PB| PB| d | d | d | d | d | d | d | d | i | i | i | i | 

64 bit - 24 bytes | 20 | 21 | 22 | 23 | 
previous sequence + --------------------- 
        | PB | PB | PB | PB | 

Nhưng chúng ta có thể sắp xếp lại nó, để làm cho dữ liệu này phù hợp vào từ máy. Như thế này:

struct ST2 { 
    double d; 
    int i; 
    short s; 
    char c1; 
    char c2; 
}; 

Trong trường hợp này cho cả 32 và 64 bit nó sẽ được biểu diễn tại cùng một cách (16 byte):

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 
---------------------------------------------------------------------- 
d | d | d | d | d | d | d | d | i | i | i | i | s | s | ch1| ch2| 

Tôi có một vài câu hỏi:

• Giống như dự đoán hoang dã nhưng quy tắc chính cho struct là xác định các biến có kích thước lớn hơn lúc đầu?
• Vì tôi hiểu nó không hoạt động với các biến độc lập. Thích char str[] = "Hello";?
• byte đệm, mã nào có? Nó ở đâu đó tại bảng ASCII? Xin lỗi, không thể tìm thấy nó.
• 2 cấu trúc với tất cả các thành viên được đại diện ở bộ nhớ theo các địa chỉ khác nhau và chúng có thể được đặt không tuần tự ở bộ nhớ?
• Cấu trúc như vậy: struct ST3 { char c1; char c2; char c3;} st3; Có size = 3, tôi hiểu rằng nếu chúng tôi sẽ thêm thành viên có loại khác vào nó, nó sẽ được căn chỉnh. Nhưng tại sao nó không liên kết trước nó?

Answer 1

Hãy cẩn thận, bạn không chắc chắn rằng các biến của bạn được căn chỉnh (nhưng thường là). Nếu bạn sử dụng GCC, bạn có thể sử dụng thuộc tính để đảm bảo rằng dữ liệu của bạn được căn chỉnh.

Ví dụ:

struct foo { 
    char c; 
    int x; 
} __attribute__((packed)); 

Theo tôi được biết nó không làm việc với các biến độc lập. Giống như char str [] = "Hello" ;?

Bảng này sẽ được căn chỉnh trong bộ nhớ của bạn.

Answer 2

Trả lời câu hỏi của bạn như được đặt ra (bỏ qua hình ảnh rất đẹp của bạn về cấu trúc)

Nó giống như đoán hoang dã nhưng quy tắc chính cho struct là để xác định các biến với kích thước lớn hơn ngay từ đầu?

Luôn đặt những thứ yêu cầu căn chỉnh nhiều nhất trước. Tôi sẽ không đặt một ví dụ char[99] trước. Nói chung điều này hoạt động như con trỏ, các kiểu bản địa 64 bit, các kiểu bản địa 32 bit, vv, nhưng bạn phải rất cẩn thận nếu cấu trúc của bạn chứa các thành viên là các cấu trúc khác.

Vì tôi hiểu nó không hoạt động với các biến độc lập. Giống như char str[] = "Hello";

Tôi không thực sự hiểu điều này. Nếu bạn định nghĩa một mảng char trên stack, nó có sự liên kết char. Nếu bạn xác định một mảng char theo sau là một int, có thể sẽ có đệm trên ngăn xếp, bạn chỉ không thể tìm thấy nó.

byte đệm, mã nào? Nó ở đâu đó tại bảng ASCII? Xin lỗi, không thể tìm thấy nó.

Nó không có mã và dữ liệu. Nó là trình đệm chèn vào trình biên dịch và có thể chứa bất kỳ giá trị nào, có thể hoặc không thể khác nhau giữa các cá thể khác nhau của cấu trúc trong các hoạt động giống nhau hoặc khác nhau của chương trình.

2 cấu trúc với tất cả các thành viên được đại diện tại bộ nhớ theo các địa chỉ khác nhau và chúng có thể được đặt không tuần tự ở bộ nhớ?

Tôi không hiểu điều này. Bạn có hỏi liệu trình biên dịch có thể chèn đệm giữa các cấu trúc không? Nếu không, xin vui lòng làm rõ, bởi vì câu trả lời này sẽ không được nhiều giúp đỡ;

Khi trình biên dịch tạo cấu trúc, nó phải giúp bạn có thể tạo một mảng cấu trúc như vậy một cách an toàn. Xem xét việc này:

struct S { 
    int wibble; 
    char wobble; 
}; 

S stuff[2]; 

Nếu trình biên dịch không chèn 3 byte đệm sau khi dao động, truy cập để stuff[1].wobble sẽ không được sắp xếp đúng cách, sẽ dẫn đến sự cố trên một số phần cứng (và hiệu suất tồi tệ trên phần cứng khác) . Về cơ bản, trình biên dịch phải đảm bảo đệm ở cuối để đảm bảo rằng thành viên được căn chỉnh nhất của cấu trúc luôn được căn chỉnh chính xác cho một mảng các cấu trúc như vậy.

Cấu trúc như vậy: struct ST3 { char c1; char c2; char c3;} st3; Có kích thước = 3, tôi hiểu rằng nếu chúng tôi thêm thành viên có loại khác vào nó, nó sẽ được căn chỉnh. Nhưng tại sao nó không liên kết trước nó?

Bạn có nghĩa là 'Tại sao trình biên dịch không đặt nó ở vị trí được căn chỉnh chính xác'? Bởi vì ngôn ngữ không cho phép nó. Trình biên dịch không được phép sắp xếp lại các thành viên của cấu trúc của bạn. Nó chỉ được phép chèn đệm.

Answer 3

Căn chỉnh thành viên của cấu trúc (và các lớp) phụ thuộc vào nền tảng, đúng, nhưng trên trình biên dịch. Lý do sắp xếp thành viên với kích thước của nó là vì lý do hiệu suất. Làm cho tất cả các loại tích phân phù hợp với kích thước của nó làm giảm khả năng truy cập bộ nhớ.

Bạn thường có thể buộc trình biên dịch giảm căn chỉnh, nhưng không phải là ý tưởng hay, ngoại trừ các lý do cụ thể (ví dụ, để tương thích dữ liệu giữa các nền tảng khác nhau, dưới dạng dữ liệu liên lạc). Trong Visual C++ tồn tại #pragma pack cho điều đó, ví dụ:

#pragma pack(1) 
struct ST1 { 
    char c1; 
    short s; 
    char c2; 
    double d; 
    int i; 
}; 

assert(sizeof(ST1) == 16); 

Nhưng như tôi đã nói trước đây thường không phải là một ý kiến ​​hay.

Hãy nhớ rằng trình biên dịch không chỉ thêm byte đệm sau một số trường. Nó cũng đảm bảo cấu trúc được cấp phát trong bộ nhớ cho tất cả các trường được căn phải.Ý tôi là, trong mẫu ST1 của bạn, bởi vì các loại lĩnh vực lớn hơn gấp đôi, trình biên dịch sẽ được đảm bảo d lĩnh vực sẽ được sắp xếp ở mức 8 byte (trừ nếu sử dụng #pragma pack hoặc tương tự tùy chọn):

ST1 st1; 

assert(&st1.d % 8 == 0); 

Về câu hỏi của bạn:

• Nếu bạn muốn tiết kiệm dung lượng, có, là một trường thứ tự lừa tốt theo kích thước, trước tiên hãy viết lớn hơn. Trong trường hợp các cấu trúc được tạo thành, sử dụng kích thước của trường lớn hơn của cấu trúc bên trong, thay vì kích thước của cấu trúc.
• Nó hoạt động trên các biến độc lập. Nhưng trình biên dịch có thể đặt các biến trong bộ nhớ (trái ngược với thành viên của các cấu trúc và các lớp).

Ví dụ:

short s[27]; 
int32_t i32[34]; 
int64_t i64[45]; 

assert(s % 2 == 0); 
assert(i32 % 4 == 0); 
assert(i64 % 8 == 0); 

• Padding byte có thể chứa bất cứ điều gì. Thường được khởi tạo dữ liệu (ít nhất bạn khởi tạo nó). Một số lần có thể chứa mẫu byte cụ thể bởi trình biên dịch, vì lý do gỡ lỗi.
• Giới thiệu về cấu trúc với tất cả các thành viên đại diện ở bộ nhớ theo các địa chỉ khác nhau: xin lỗi, tôi không hiểu rõ những gì bạn hỏi.
• Tiêu chuẩn C++ cho biết địa chỉ của cấu trúc/lớp phải giống với địa chỉ của trường đầu tiên của cấu trúc/lớp đó. Sau đó, chỉ có thể đệm sau c3, nhưng không bao giờ trước c1.

Từ N3337 (C++ 11) [9.2 class.menu, p.20]:

Một con trỏ tới một đối tượng struct tiêu chuẩn bố trí, phù hợp chuyển đổi sử dụng một reinterpret_cast, trỏ tới thành viên ban đầu của nó (hoặc nếu thành viên đó là một trường bit, sau đó đến đơn vị mà nó cư trú) và ngược lại. [ Lưu ý: Do đó, có thể có phần đệm không tên trong một đối tượng cấu trúc bố cục tiêu chuẩn , nhưng không phải ở đầu của nó, khi cần thiết để đạt được căn chỉnh phù hợp. lưu ý end]

Answer 4

Các quy tắc cơ bản rất đơn giản:

• thành viên phải có mặt ở đó để (trừ khi trong C++ bạn sử dụng riêng: public: ... phần)
• đệm là cho phép giữa các thành viên và sau khi người cuối cùng

đó là về nó. Phần còn lại còn lại để triển khai: bộ nhớ được lấy theo loại, số lượng đệm. Thông thường bạn có thể mong đợi nó được ghi lại chính xác trong ABI hoặc trực tiếp trong trình biên dịch, và thậm chí có các công cụ để thao tác.

Trong thực tế đệm là cần thiết về một số kiến ​​trúc, nói SPARC đòi hỏi 32-bit "ints" xếp trên địa chỉ chia hết cho 4. Trên người khác nó không phải là yêu cầu nhưng thực thể lệch có thể mất nhiều thời gian để xử lý, nói một Bộ xử lý 80286 mất thêm một chu kỳ để đọc thực thể 16 bit từ một địa chỉ lẻ. (Trước khi tôi quên: đại diện của các loại chính nó là khác nhau!)

Thông thường yêu cầu căn chỉnh hoặc hiệu suất tốt nhất khớp chính xác: bạn sẽ căn chỉnh trên cùng một đường viền với kích thước. Một ví dụ phản đối tốt là số 80-bit số dấu phẩy động (có sẵn dưới dạng gấp đôi hoặc dài gấp đôi trong một số trình biên dịch) giống như liên kết 8 hoặc 16 byte thay vì 10.

Để fiddle với trình biên dịch đệm thường cung cấp cho bạn chuyển sang đặt mặc định. Điều đó thay đổi từ phiên bản sang phiên bản, vì vậy tốt hơn nên được tính vào nâng cấp. Và thiết bị ghi đè mã bên trong như _attribute__(packed) trong gcc và #pragma gói trong MS và nhiều loại khác. Đó là tất cả các phần mở rộng tiêu chuẩn rõ ràng.

Điểm mấu chốt là, nếu bạn muốn fiddle với bố trí, bạn bắt đầu đọc dox của tất cả các trình biên dịch bạn nhắm mục tiêu, bây giờ và trong tương lai, để biết những gì họ làm và làm thế nào để kiểm soát nó. Cũng có thể đọc dox của nền tảng đích, tùy thuộc vào lý do bạn quan tâm đến bố cục ở vị trí đầu tiên.

Một động lực thông thường là có bố cục ổn định khi bạn ghi bộ nhớ thô vào tệp và mong muốn đọc lại. Có lẽ trên nền tảng khác nhau bằng cách sử dụng trình biên dịch khác nhau. Đó là dễ dàng hơn cho đến khi một loại nền tảng mới đi vào hiện trường.

Động lực khác là hiệu suất. Đó là một trong những cách khôn lanh hơn, như các quy tắc thay đổi nhanh chóng, và hiệu quả là khó dự đoán ngay lập tức. Nói về intel, hình phạt "lệch hướng" cơ bản đã biến mất trong thời gian dài, thay vào đó số lượng đếm được nằm trong một dòng bộ nhớ cache. Trường hợp kích thước dòng bộ nhớ cache thay đổi tùy theo bộ xử lý. Ngoài ra sử dụng nhiều padding có thể tạo ra cá nhân tốt hơn trong khi các cấu trúc được đóng gói đầy đủ sẽ tiết kiệm hơn trong việc sử dụng bộ nhớ cache.

Và một số thao tác yêu cầu căn chỉnh thích hợp, nhưng không được trình biên dịch trực tiếp thực thi, bạn có thể cần áp dụng các loại pragma liên kết đặc biệt (như đối với một số cụ thể SSE liên quan).

Dòng dưới cùng được lặp lại: dừng đoán, quyết định mục tiêu của bạn và đọc dox thích hợp. (Btw cho tôi đọc hướng dẫn sử dụng kiến ​​trúc cho SPARC, IA32 và những người khác là niềm vui to lớn và đạt được trong nhiều khía cạnh.)

Answer 5

cho một gcc trên kiến ​​trúc intel nó có thêm hướng dẫn và chu kỳ để truy cập (đọc/ghi) địa chỉ bộ nhớ số lẻ. do đó đệm được thêm vào địa chỉ bộ nhớ số chẵn thậm chí