Tự động sắp xếp lại trường trong các cấu trúc C để tránh đệm

Question

Tôi đã dành một vài phút sắp xếp lại các trường theo cách thủ công trong cấu trúc để giảm hiệu ứng đệm [1], cảm giác như một vài phút quá nhiều. Cảm giác ruột của tôi nói rằng thời gian của tôi có lẽ tốt hơn nên viết một kịch bản Perl hoặc không nên làm loại tối ưu hóa này cho tôi.

Câu hỏi của tôi là liệu điều này có quá thừa hay không; đã có một số công cụ mà tôi không nhận thức được, hoặc một số tính năng biên dịch mà tôi sẽ có thể bật [2] để đóng gói cấu trúc?

Vấn đề thậm chí còn phức tạp hơn vì thực tế điều này cần phải được tối ưu hóa liên tục trên một vài kiến ​​trúc khác nhau, vì vậy bất cứ công cụ nào cũng cần có khả năng tính toán các cấu trúc và kích cỡ con trỏ khác nhau.

EDIT: Làm rõ nhanh - những gì tôi muốn làm là sắp xếp lại trường trong mã nguồn để tránh đệm, không "đóng gói" cấu trúc như được biên dịch mà không có đệm.

EDIT # 2: Một biến chứng khác: tùy thuộc vào cấu hình, kích thước của một số loại dữ liệu cũng có thể thay đổi. Những cái rõ ràng là con trỏ và con trỏ khác biệt cho các kiến ​​trúc khác nhau, nhưng cũng có các loại dấu phẩy động (16, 32 hoặc 64 bit tùy thuộc vào độ chính xác), tổng kiểm tra (8 hoặc 16 bit tùy thuộc vào 'tốc độ') và một số những thứ không rõ ràng khác.

ngàn [1] struct trong câu hỏi là instantiated lần trên một thiết bị nhúng, vì vậy mỗi giảm 4-byte của struct có thể có nghĩa là sự khác biệt giữa một đi và không-go cho dự án này.

[2] Trình biên dịch có sẵn là GCC 3. * và 4. *, Visual Studio, TCC, ARM ADS 1.2, RVCT 3. * và một số ít người khác mơ hồ hơn.

Answer 1

Nếu mỗi từ duy nhất bạn có thể bóp ra khỏi lưu trữ là rất quan trọng, sau đó tôi phải khuyên bạn nên tối ưu hóa cấu trúc bằng tay. Một công cụ có thể sắp xếp các thành viên tối ưu cho bạn, nhưng nó không biết, ví dụ, giá trị này ở đây mà bạn đang lưu trữ trong 16 bit thực sự không bao giờ vượt quá 1024, vì vậy bạn có thể ăn cắp 6 bit trên cho này giá trị trên tại đây ...

Vì vậy, con người gần như chắc chắn sẽ đánh bại một rô bốt trong công việc này.

[Chỉnh sửa] Nhưng có vẻ như bạn thực sự không muốn tự tối ưu hóa cấu trúc của mình cho mỗi kiến ​​trúc. Có lẽ bạn thực sự có nhiều kiến ​​trúc tuyệt vời để hỗ trợ?

Tôi nghĩ vấn đề này không phải là giải pháp chung, nhưng bạn có thể mã hóa kiến ​​thức miền của mình thành tập lệnh Perl/Python/something tùy chỉnh tạo định nghĩa cấu trúc cho mỗi kiến ​​trúc.

Ngoài ra, nếu tất cả các thành viên của bạn có kích thước là sức mạnh của hai, thì bạn sẽ nhận được đóng gói tối ưu bằng cách sắp xếp thành viên theo kích thước (lớn nhất trước tiên.) Trong trường hợp đó, bạn chỉ có thể sử dụng tốt vĩ mô dựa trên cấu trúc xây dựng kiểu cũ - một cái gì đó như thế này:

#define MYSTRUCT_POINTERS  \ 
    Something* m_pSomeThing; \ 
    OtherThing* m_pOtherThing; 

#define MYSTRUCT_FLOATS  \ 
    FLOAT m_aFloat;   \ 
    FLOAT m_bFloat; 

#if 64_BIT_POINTERS && 64_BIT_FLOATS 
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_POINTERS MYSTRUCT_FLOATS 
#else if 64_BIT_POINTERS 
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_POINTERS 
#else if 64_BIT_FLOATS 
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_FLOATS 
#else 
    #define MYSTRUCT_64_BIT_MEMBERS 
#endif 

// blah blah blah 

struct MyStruct 
{ 
    MYSTRUCT_64_BIT_MEMBERS 
    MYSTRUCT_32_BIT_MEMBERS 
    MYSTRUCT_16_BIT_MEMBERS 
    MYSTRUCT_8_BIT_MEMBERS 
}; 

Answer 2

Hãy xem gói #pragma. Điều này thay đổi cách trình biên dịch căn chỉnh các phần tử trong cấu trúc. Bạn có thể sử dụng nó để buộc họ phải được đóng gói chặt chẽ với nhau mà không có không gian.

See more details here

Answer 3

Hầu hết các trình biên dịch C sẽ không làm được điều này dựa trên thực tế là bạn có thể làm những thứ kỳ lạ (như lấy địa chỉ của một phần tử trong cấu trúc và sau đó sử dụng phép thuật con trỏ để truy cập phần còn lại, bỏ qua trình biên dịch). Một ví dụ nổi tiếng là các danh sách liên kết đôi trong AmigaOS sử dụng các nút của người giám hộ làm đầu và đuôi của danh sách (điều này có thể tránh được ifs khi duyệt qua danh sách). Nút đầu người giám hộ sẽ luôn có pred == null và nút đuôi sẽ có next == null, các nhà phát triển đã cuộn hai nút thành một cấu trúc ba con trỏ duy nhất head_next null tail_pred. Bằng cách sử dụng địa chỉ head_next hoặc null làm địa chỉ của nút đầu và đuôi, họ đã lưu bốn byte và một cấp phát bộ nhớ (vì chúng chỉ cần toàn bộ cấu trúc một lần).

Vì vậy, đặt cược tốt nhất của bạn có lẽ là viết các cấu trúc như mã giả và sau đó viết một kịch bản tiền xử lý tạo cấu trúc thực từ đó.

Answer 4

Có một tập lệnh Perl được gọi là pstruct thường được bao gồm trong cài đặt Perl. Kịch bản lệnh sẽ loại bỏ các kích thước và kích thước của thành viên cấu trúc. Bạn có thể sửa đổi pstruct hoặc sử dụng đầu ra của nó như là một điểm khởi đầu để tạo một tiện ích đóng gói các cấu trúc của bạn theo cách bạn muốn.

$ cat foo.h 
struct foo { 
    int x; 
    char y; 
    int b[5]; 
    char c; 
}; 

$ pstruct foo.h 
struct foo { 
    int    foo.x      0  4 
    char    foo.y      4  1 
        foo.b      8  20 
    char    foo.c      28  1 
} 

Answer 5

Nó cũng phụ thuộc vào nền tảng/trình biên dịch. Như đã đề cập, hầu hết các trình biên dịch pad tất cả mọi thứ đến một sự liên kết 4-byte (hoặc tồi tệ hơn!), Do đó giả định một cấu trúc với 2 quần short và dài:

short 
long 
short 

sẽ mất 12 byte (2 * 2 byte đệm).

sắp xếp lại nó được

short 
short 
long 

vẫn sẽ chiếm 12 byte như pad trình biên dịch sẽ nó để thực hiện truy cập dữ liệu nhanh hơn (đó là mặc định cho hầu hết các máy tính để bàn, như họ thích truy cập nhanh hơn sử dụng bộ nhớ) . Hệ thống nhúng của bạn có các nhu cầu khác nhau, vì vậy bạn sẽ phải sử dụng gói #pragma bất kể.

Đối với một công cụ để sắp xếp lại, tôi sẽ chỉ đơn giản là (thủ công) sắp xếp lại bố trí cấu trúc của bạn để các loại khác nhau được đặt cùng nhau. Đặt tất cả các quần short trong đầu tiên, sau đó đặt tất cả các longs in, vv Nếu bạn đang đi để có được đóng gói thực hiện, đó là những gì một công cụ sẽ làm anyway. Bạn có thể có 2 byte đệm ở giữa tại các điểm chuyển tiếp giữa các loại, nhưng tôi sẽ không coi đó là đáng lo ngại.

Answer 6

Trình biên dịch không thể sắp xếp lại các trường trong cấu trúc bằng đầu của chính nó. Các nhiệm vụ tiêu chuẩn mà các trường cần được sắp xếp theo thứ tự chúng được định nghĩa. Làm điều gì khác có thể phá vỡ mã theo những cách tinh tế.

Khi bạn viết, tất nhiên là hoàn toàn có thể làm cho một số loại trình tạo mã phát triển xung quanh các trường theo cách hiệu quả. Nhưng tôi thích làm điều này bằng tay.

Answer 7

Suy nghĩ về cách tôi muốn tạo một công cụ như vậy ... Tôi nghĩ tôi sẽ bắt đầu với thông tin gỡ lỗi.

Lấy kích thước của mỗi cấu trúc từ nguồn là một cơn đau. Nó chồng lên rất nhiều công việc mà trình biên dịch đã làm. Tôi không quen thuộc với ELF để nói chính xác cách trích xuất thông tin kích thước cấu trúc từ một nhị phân gỡ lỗi, nhưng tôi biết rằng thông tin tồn tại vì các trình gỡ rối có thể hiển thị nó.Có lẽ objdump hoặc cái gì khác trong gói binutils có thể nhận được điều này cho bạn tầm thường (đối với nền tảng sử dụng ELF, ít nhất).

Sau khi bạn có thông tin, phần còn lại khá đơn giản. Đặt hàng các thành viên từ lớn nhất đến nhỏ nhất, cố gắng giữ càng nhiều càng tốt thứ tự của cấu trúc ban đầu càng tốt. Với perl hoặc python nó thậm chí sẽ dễ dàng để vượt qua nó với phần còn lại của nguồn và thậm chí có thể bảo vệ ý kiến ​​hoặC#ifdefs tùy thuộc vào cách chúng được sử dụng một cách rõ ràng. Nỗi đau lớn nhất sẽ thay đổi tất cả các khởi tạo của cấu trúc trong toàn bộ codebase. Yikes.

Đây là điều. Nghe có vẻ rất hay, nhưng tôi không biết bất kỳ công cụ nào hiện có như vậy, và vào thời điểm bạn tự viết ... Tôi nghĩ bạn sẽ có thể sắp xếp lại theo cách thủ công hầu hết các cấu trúc trong chương trình.

Answer 8

Tôi gặp sự cố tương tự. Như được đề xuất trong một câu trả lời khác, pstruct có thể giúp đỡ. Nhưng, nó đưa ra chính xác những gì chúng ta cần. Trong thực tế pstruct sử dụng thông tin gỡ lỗi được cung cấp bởi gcc. Tôi đã viết một kịch bản khác dựa trên cùng một ý tưởng.

Bạn phải tạo tệp lắp ráp với thông tin gỡ lỗi STUBS (-gstubs). (Nó sẽ có thể có được thông tin tương tự từ lùn, nhưng tôi đã sử dụng cùng một phương pháp hơn pstruct). Một cách tốt để làm điều này mà không cần sửa đổi quá trình biên dịch là thêm "-gstubs -save-temps=obj" vào các tùy chọn biên dịch của bạn.

Kịch bản sau đó đọc các file lắp ráp và phát hiện khi một byte thêm được thêm vào trong một cấu trúc:

#!/usr/bin/perl -n 

    if (/.stabs[\t ]*"([^:]*):T[()0-9,]*=s([0-9]*)(.*),128,0,0,0/) { 
     my $struct_name = $1; 
     my $struct_size = $2; 
     my $desc = $3; 
     # Remove unused information from input 
     $desc =~ s/=ar\([0-9,]*\);[0-9]*;[-0-9]*;\([-0-9,]*\)//g; 
     $desc =~ s/=[a-zA-Z_0-9]+://g; 
     $desc =~ s/=[\*f]?\([0-9,]*\)//g; 
     $desc =~ s/:\([0-9,]*\)*//g; 
     my @members = split /;/, $desc; 
     my ($prev_size, $prev_offset, $prev_name) = (0, 0, ""); 
     for $i (@members) { 
      my ($name, $offset, $size) = split /,/, $i; 
      my $correct_offset = $prev_offset + $prev_size; 
      if ($correct_offset < $offset) { 
      my $diff = ($offset - $correct_offset)/8; 
      print "$struct_name.$name looks misplaced: $prev_offset + $prev_size = $correct_offset < $offset (diff = $diff bytes)\n"; 
      } 
      # Skip static members 
      if ($offset != 0 || $size != 0) { 
      ($prev_name, $prev_offset, $prev_size) = ($name, $offset, $size); 
      } 
     } 
    } 

Cách tốt nhất để gọi nó:

find . -name *.s | xargs ./detectPaddedStructs.pl | sort | un