Thực thi hiệu quả biểu thức boolean trên bitmap trong C hoặc C++

Question

Cách hiệu quả nhất để thực thi biểu thức boolean trên bitmap trong C hoặc C++ là gì? Ví dụ: giả sử tôi có bitmap 4 bit (a, b, c, d). Bây giờ, hãy nói rằng tôi có một biểu thức boolean đơn giản như (a AND b) OR (c AND d). Làm thế nào tôi nên đại diện cho biểu thức boolean để tôi có thể áp dụng hiệu quả nó vào bitmap của tôi? Tôi đang tìm một giải pháp chung có thể được áp dụng cho bất kỳ biểu thức boolean, không chỉ là một trong những ví dụ. Nói cách khác, tôi đang tìm một cách nào đó để "biên dịch" biểu thức boolean thành một cấu trúc dữ liệu khác có thể được sử dụng để giảm hiệu quả bitmap của tôi thành một boolean.

Cấu trúc bitmap là kết quả của hoạt động lọc trên bản ghi của cơ sở dữ liệu. Mỗi bản ghi có bitmap riêng và mỗi bit trong bitmap là kết quả của một quy tắc lọc riêng lẻ. Biểu thức boolean được sử dụng để kết hợp các quy tắc lọc này để quyết định xem bản ghi có nên được bao gồm trong các kết quả của truy vấn cơ sở dữ liệu hay không. Có thể có tối đa 64 quy tắc lọc riêng lẻ có thể được kết hợp bởi thao tác boolean, do đó bitmap có thể được biểu diễn dưới dạng unsigned long long int nếu cần.

Giải pháp phải hiệu quả về tốc độ và không được thay đổi cấu trúc bitmap. Việc chuyển đổi biểu thức boolean thành một cấu trúc khác không phải là bộ nhớ hiệu quả cũng không nhanh, bởi vì nó có thể được lưu trữ (ít nhất là trong trường hợp sử dụng hiện tại của tôi). Việc giảm bitmap với biểu thức boolean được chuyển đổi phải nhanh và hiệu quả về bộ nhớ.

Ghi chú:

• Biểu thức boolean chỉ sử dụng lồng nhau AND và OR hoạt động (không IF báo cáo).
• Giải pháp nên giả định tính khả dụng của CPU 64 bit.
• Giải pháp không nên phụ thuộc vào CPU (bên cạnh địa chỉ 64 bit).
• Giải pháp không được giả định tính khả dụng của bất kỳ phần cứng cụ thể nào khác (ví dụ: GPU).
• Tất cả các bitmap đều có trong bộ nhớ.
• Có thể có rất nhiều bitmap (tỷ).
• Các ảnh bitmap được cập nhật từng cái một.

Answer 1

Bạn có thể biểu diễn biểu thức dưới dạng cây nhị phân và cũng có thể sử dụng hai lớp cho hai loại nút. Bạn cũng có thể tham số hóa mỗi nút với thao tác nhưng nó hầu như không đáng giá trong khi đó. Có lẽ bạn cũng tạo một nút Không với một đầu vào. Đầu vào cho các nút là một trong hai vị trí trong bitmap của bạn hoặc các nút khác, vì vậy tôi đang tạo một lớp con cho trường hợp trước đó, lấy chỉ mục trong bitmap làm tham số. Bạn hoàn thành mã này bằng cách viết hàm giá trị cho nút Và và hoàn tất nút Or.

typedef unsigned long long Bitmap; 
Bitmap bitmap; 

struct Node { 
    virtual bool value()=0; 
}; 

struct AbsNode : public Node { 
    int bit; 
    bool value() {return (bitmap>>bit)&1; } 
} 

struct AndNode : public Node { 
    Node *operandA, *operandB; 
    etc. 
} 

Answer 2

Phương pháp hiệu quả nhất khi sử dụng các hoạt động AND hoặc OR trên bitmap là sử dụng hỗ trợ phần cứng. Nhiều bộ xử lý đồ họa có thể thực hiện các thao tác trên hai bitmap. Không có hoạt động thư viện chuẩn C++ nào cho việc này.

Bạn cần thực hiện thao tác trên từng bit, byte, từ hoặc từ kép trong bitmap.

Phương pháp hiệu quả tốc độ tiếp theo là hủy vòng lặp. Hướng dẫn chi nhánh các chu kỳ thực thi chất thải (có thể được sử dụng cho các hướng dẫn dữ liệu) và có thể xóa bỏ đường dẫn lệnh lãng phí thời gian nạp lại nó.

Bạn cũng có thể đạt được một số hiệu quả bằng cách sử dụng một cách hiệu quả bộ nhớ cache dữ liệu của bộ xử lý. Tải lên một loạt các biến, thực hiện các hoạt động, lưu trữ kết quả, lặp lại.

Bạn cũng nên lấy trong nhóm sử dụng kích thước chữ của bộ xử lý. Bộ vi xử lý 32 bit thích tìm nạp 32 bit mỗi lần. Vì vậy, điều này sẽ cung cấp cho bạn 8 bộ pixel 4 bit được tải bằng một lần tìm nạp. Nếu không, bạn sẽ phải lấy 8 bit tại một thời điểm, mà kết quả trong 4 fetches 8 bit so với 1 lấy 32-bit.

Dưới đây là các thuật toán cốt lõi:

uint8_t * p_bitmap_a = &Bitmap_A[0]; 
uint8_t * p_bitmap_b = &Bitmap_B[0]; 
uint8_t * p_bitmap_c = &Bitmap_C[0]; 

// C = A AND B 

for (unsigned int i = 0; i < bitmap_size/4; ++i) 
{ 
    uint32_t a = *((uint32_t*) p_bitmap_a); 
    uinte2_t b = *((uint32_t*) p_bitmap_b); 
    uint32_t c = a & b; 
    *((uint32_t *) p_bitmap_c) = c; 
    p_bitmap_a += sizeof(uint32_t); 
    p_bitmap_b += sizeof(uint32_t); 
    p_bitmap_c += sizeof(uint32_t); 
} 

Sửa 1:
vi xử lý của bạn có thể có hướng dẫn mà có thể hỗ trợ các hoạt động. Ví dụ, bộ vi xử lý ARM7 có thể tải nhiều thanh ghi từ bộ nhớ bằng một lệnh. Nghiên cứu bộ hướng dẫn bộ vi xử lý của bạn. Bạn có thể phải sử dụng ngôn ngữ lắp ráp nội tuyến để tận dụng các hướng dẫn cụ thể của bộ xử lý.

Chỉnh sửa 2: Luồng & Xử lý song song.

Trừ bitmap của bạn là rất lớn, các nguyên cần thiết của việc duy trì nhiều đề thi hay thực hiện song song có thể lớn hơn lợi ích. Ví dụ, nếu overhead của đồng bộ với lõi CPU khác là 200ms và xử lý bitmap mà không bị gián đoạn là 1000ms, bạn đã lãng phí thời gian bằng cách sử dụng xử lý song song trên bitmap đơn (1200 ms để có một tiến trình lõi khác bitmap).

Nếu bạn có nhiều bitmap, bạn có thể đạt được một số thời gian bằng cách sử dụng xử lý song song hoặc nhiều chủ đề:

1. Một chủ đề lấy về bitmap từ cơ sở dữ liệu vào bộ nhớ (bộ đệm).
2. chủ đề khác xử lý bitmap và lưu trữ vào một đệm đi.
3. Một quá trình thứ ba viết các bitmap đệm cơ sở dữ liệu.

Nếu bạn đang tìm nạp bitmap từ nguồn bên ngoài, chẳng hạn như cơ sở dữ liệu, I/O này sẽ là nút cổ chai của bạn. Đây là phần bạn nên tối ưu hóa hoặc spool.

Answer 3

Nếu bitmap là GUARANTEED luôn là 4 bit, thì chúng sẽ vừa với 4 bit thấp hơn của một char và sẽ chỉ có 16 giá trị có thể cho bất kỳ bitmap nào.

Đối với một biểu thức boolean cụ thể, sau đó bạn đánh giá nó cho mỗi trong số mười sáu kết hợp bit có thể, cung cấp cho bạn một bộ mười sáu bit kết quả. Lắp ráp chúng vào một int mười sáu bit: false, false, false, false bằng bit không, false, false, false, true trong bit 1, v.v.

Bây giờ cho một bitmap tùy ý so với một boolean tùy ý, séc của bạn trở thành:

1. Hãy đối xử với bitmap như một int 4 bit, đánh giá 1 << (4 bit int).
2. Lấy kết quả của ca làm việc đó và sử dụng toán tử C++ & để kiểm tra đối với giá trị int 16 bit được lưu trong bộ đệm của hoạt động boolean.

Điều đó sẽ trở == 0 cho sai và != 0 cho đúng.

Giảm thành hai hướng dẫn: shift và and là về tốc độ nhanh nhất mà tôi có thể thấy khi thực hiện.

này giả định rằng có một số lượng khá nhỏ hoạt động boolean rằng bạn đang áp dụng trên một kết thúc, các thiết lập mỗi boolean kiểm tra sẽ thể tốn kém, nhưng kể từ khi bạn đang nói hàng tỷ bitmap, tôi giả định rằng bạn sẽ sử dụng cùng một phép toán boolean trên nhiều bitmap.