Hiệu suất của std :: bitset là gì?

Question

Gần đây tôi đã hỏi một câu hỏi về Programmers liên quan đến lý do để sử dụng thao tác bit tay loại nguyên thủy trên std::bitset.

Từ thảo luận mà tôi đã kết luận rằng nguyên nhân chính là hiệu suất, mặc dù tôi không biết về bất kỳ cơ sở đo cho ý kiến ​​này. Vì vậy, câu hỏi tiếp theo của tôi là; gì là đạt hiệu suất, nếu có, nhiều khả năng sẽ được phát sinh bằng cách sử dụng std::bitset trên một nguyên thủy?

Câu hỏi là cố ý rộng, bởi vì sau khi tìm kiếm trực tuyến, tôi không thể tìm thấy bất cứ điều gì, vì vậy tôi sẽ lấy những gì tôi có thể nhận được. Về cơ bản tôi là sau khi một nguồn tài nguyên cung cấp một số hồ sơ của std::bitset vs 'pre-bitet' lựa chọn thay thế cho các vấn đề tương tự trên một số kiến ​​trúc máy phổ biến bằng cách sử dụng GCC, Clang và/hoặc VC + +. Có một bài báo rất toàn diện mà attemtps để trả lời câu hỏi này cho vectơ bit:

http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

Đáng tiếc là nó xảy ra trước một trong hai hoặc coi ra khỏi phạm vi std::bitset, vì vậy nó tập trung vào vectơ/triển khai mảng động để thay thế.

Tôi thực sự chỉ muốn biết liệu std::bitset là tốt hơn so với các lựa chọn thay thế cho các trường hợp sử dụng mà nó có ý định giải quyết. Tôi đã biết rằng đó là dễ dàng hơn và rõ ràng hơn hơn bit-fiddling trên một số nguyên, nhưng có phải là nhanh?

Answer 1

Cập nhật

Đó là lứa tuổi kể từ khi tôi đăng một này, nhưng:

Tôi đã biết rằng đó là dễ dàng hơn và rõ ràng hơn so với bit không quan trọng trên một số nguyên , nhưng nó như là Nhanh?

Nếu bạn đang sử dụng bitset theo một cách mà không thực sự làm cho nó rõ ràng hơn và sạch hơn so với bit không quan trọng, như kiểm tra một chút tại một thời điểm thay vì sử dụng một mặt nạ bit, sau đó chắc chắn bạn sẽ mất tất cả những lợi ích mà các hoạt động bitwise cung cấp, như có thể kiểm tra xem 64 bit được đặt cùng một lúc với một mặt nạ hay sử dụng hướng dẫn FFS để nhanh chóng xác định bit nào được đặt trong 64 bit.

Tôi không chắc rằng bitset gánh chịu một hình phạt để sử dụng trong tất cả các cách có thể (ví dụ: sử dụng Bitwise nó operator&), nhưng nếu bạn sử dụng nó như một kích thước cố định mảng boolean đó là khá nhiều cách tôi luôn thấy mọi người sử dụng nó, sau đó bạn thường mất tất cả những lợi ích được mô tả ở trên. Thật không may, chúng tôi không thể có được mức độ biểu đạt của việc chỉ truy cập một bit tại một thời điểm với operator[] và có trình tối ưu hóa tất cả các thao tác bitwise và FFS và FFZ và tiếp tục cho chúng tôi, ít nhất là không kể từ lần cuối cùng tôi được kiểm tra (nếu không, bitset sẽ là một trong những cấu trúc yêu thích của tôi).

Bây giờ nếu bạn định sử dụng bitset<N> bits thay thế cho nhau, ví dụ như, uint64_t bits[N/64] như truy cập cả hai cách tương tự bằng cách sử dụng bitwise, nó có thể là ngang hàng (chưa kiểm tra từ bài đăng cũ này). Nhưng sau đó bạn mất nhiều lợi ích khi sử dụng bitset ngay từ đầu.

for_each phương pháp

Trong quá khứ tôi đã vào một số hiểu lầm, tôi nghĩ rằng, khi tôi đề xuất một phương pháp for_each để lặp qua những thứ như vector<bool>, deque, và bitset. Điểm của phương thức như vậy là sử dụng kiến ​​thức nội bộ của container để lặp qua các phần tử hiệu quả hơn khi gọi một hàm, giống như một số thùng chứa liên kết cung cấp phương thức của riêng mình thay vì sử dụng std::find để làm tốt hơn thời gian tuyến tính. Tìm kiếm. Ví dụ, bạn có thể lặp qua tất cả các bit thiết lập của vector<bool> hoặc bitset nếu bạn có kiến ​​thức nội bộ về các vùng chứa này bằng cách kiểm tra 64 phần tử cùng một lúc bằng cách sử dụng mặt nạ 64 bit khi 64 chỉ mục liền kề bị chiếm đóng và tương tự như vậy sử dụng hướng dẫn FFS khi không phải như vậy.

Nhưng một thiết kế vòng lặp phải làm loại logic vô hướng trong operator++ chắc chắn sẽ phải làm một cái gì đó đáng kể tốn kém hơn, chỉ bởi bản chất mà các vòng lặp được thiết kế trong những trường hợp đặc biệt này. bitset thiếu các trình vòng lặp hoàn toàn và thường làm cho những người muốn sử dụng nó để tránh xử lý bitwise logic để sử dụng operator[] để kiểm tra từng bit riêng lẻ trong một vòng tuần tự chỉ muốn tìm ra các bit nào được đặt. Điều đó cũng không hiệu quả như những gì thực hiện phương pháp for_each có thể thực hiện.

Double/Nested Vòng lặp

Một thay thế cho phương pháp for_each container cụ thể đề xuất trên sẽ được sử dụng lặp kép/lồng nhau: đó là, một iterator bên ngoài mà chỉ vào một tiểu phạm vi của một khác nhau loại trình lặp. Ví dụ về mã khách hàng:

for (auto outer_it = bitset.nbegin(); outer_it != bitset.nend(); ++outer_it) 
{ 
    for (auto inner_it = outer_it->first; inner_it != outer_it->last; ++inner_it) 
      // do something with *inner_it (bit index) 
} 

Mặc dù không phù hợp với loại thiết kế lặp có sẵn trong thùng chứa tiêu chuẩn, điều này có thể cho phép một số tối ưu hóa rất thú vị. Như một ví dụ, hãy tưởng tượng một trường hợp như thế này:

bitset<64> bits = 0x1fbf; // 0b1111110111111; 

Trong trường hợp đó, các iterator bên ngoài có thể, chỉ với một vài lần lặp Bitwise ((FFZ/hoặc/bổ sung), suy ra rằng phạm vi đầu tiên của các bit để xử lý sẽ là bit [0, 6), tại thời điểm đó chúng ta có thể lặp qua tiểu phạm vi đó rất rẻ thông qua trình vòng lặp bên trong/lồng nhau (nó sẽ tăng số nguyên, làm cho ++inner_it tương đương với chỉ ++int). Sau đó, khi chúng ta tăng vòng lặp bên ngoài, nó có thể sau đó rất nhanh chóng, và một lần nữa với một vài hướng dẫn bitwise, xác định rằng phạm vi tiếp theo sẽ là [7, 13]. Sau khi chúng tôi lặp qua tiểu phạm vi đó, chúng tôi đã hoàn tất. Thực hiện việc này như một ví dụ khác:

bitset<16> bits = 0xffff; 

Trong trường hợp này, các tiểu phạm vi đầu tiên và cuối cùng sẽ là [0, 16), và bitset có thể xác định rằng với một hướng dẫn Bitwise duy nhất tại thời điểm đó chúng tôi có thể lặp qua tất cả các bit bộ và sau đó chúng ta đã xong.

Loại thiết kế vòng lặp lồng nhau này sẽ ánh xạ đặc biệt tốt đến vector<bool>, deque và bitset cũng như các cấu trúc dữ liệu khác mà mọi người có thể tạo như danh sách chưa được kiểm soát.

Tôi nói rằng theo cách vượt xa chỉ là suy đoán về ghế bành, vì tôi có một tập hợp các cấu trúc dữ liệu giống như số deque thực sự ngang bằng với lặp tuần tự vector (vẫn chậm hơn một cách ngẫu nhiên để truy cập ngẫu nhiên, đặc biệt là nếu chúng ta chỉ lưu trữ một loạt các nguyên thủy và xử lý tầm thường). Tuy nhiên, để đạt được thời gian tương đương với vector cho lặp tuần tự, tôi phải sử dụng các loại kỹ thuật này (phương pháp for_each và các trình vòng lặp đôi/lồng nhau) để giảm số lượng xử lý và phân nhánh đang diễn ra trong mỗi lần lặp. Tôi không thể cạnh tranh thời gian bằng cách khác chỉ sử dụng thiết kế lặp vòng lặp phẳng và/hoặc operator[]. Và tôi chắc chắn không thông minh hơn những người triển khai thư viện chuẩn nhưng đã đưa ra một vùng chứa deque giống như có thể được lặp tuần tự nhanh hơn nhiều và điều đó gợi ý cho tôi rằng đó là vấn đề với thiết kế giao diện chuẩn của trình lặp trong trường hợp này đi kèm với một số chi phí trong những trường hợp đặc biệt mà trình tối ưu hóa không thể tối ưu hóa.

Old trả lời

Tôi là một trong những người sẽ cung cấp cho bạn một câu trả lời thực hiện tương tự, nhưng tôi sẽ cố gắng cung cấp cho bạn một cái gì đó nhiều hơn một chút sâu hơn "just because". Đó là điều tôi đã trải qua qua việc định hình và định thời gian thực tế, không chỉ là sự ngờ vực và hoang tưởng.

Một trong những vấn đề lớn nhất với bitset và vector<bool> là thiết kế giao diện của họ "quá tiện lợi" nếu bạn muốn sử dụng chúng như một mảng các boolean. Tối ưu hóa tất cả cấu trúc mà bạn thiết lập để cung cấp an toàn, giảm chi phí bảo trì, thay đổi ít xâm nhập, v.v. Họ làm một công việc đặc biệt tốt với việc chọn hướng dẫn và phân bổ số lượng đăng ký tối thiểu để làm cho mã chạy nhanh như các lựa chọn thay thế không an toàn, không dễ bảo trì/thay đổi.

Phần làm giao diện bitet "quá tiện lợi" với chi phí hiệu quả là truy cập ngẫu nhiên operator[] cũng như thiết kế trình lặp cho vector<bool>. Khi bạn truy cập vào một trong các chỉ mục này tại chỉ mục n, trước tiên, mã phải tìm ra byte thứ n thuộc về, và sau đó chỉ mục phụ tới bit trong đó. Giai đoạn đầu tiên thường liên quan đến một bộ phận/rshifts chống lại một lvalue cùng với modulo/bitwise và đó là tốn kém hơn so với hoạt động bit thực tế bạn đang cố gắng thực hiện.

Thiết kế iterator cho vector<bool> phải đối mặt với tình trạng khó xử vụng về tương tự nơi nó hoặc có chi nhánh thành mã khác nhau mỗi 8 + lần bạn lặp qua nó hoặc trả tiền rằng loại chi phí lập chỉ mục mô tả ở trên. Nếu trước đây được thực hiện, nó làm cho logic không đối xứng trên lặp đi lặp lại, và thiết kế lặp có xu hướng để có một hit hiệu suất trong những trường hợp hiếm hoi. Để minh họa, nếu vector có phương thức for_each của riêng nó, bạn có thể lặp qua, bao gồm 64 phần tử cùng một lúc bằng cách chỉ che các bit dựa vào mặt nạ 64 bit cho vector<bool> nếu tất cả các bit được đặt mà không kiểm tra từng bit riêng. Nó thậm chí có thể sử dụng FFS để tìm ra phạm vi tất cả cùng một lúc. Một thiết kế iterator sẽ có xu hướng chắc chắn phải làm điều đó trong một thời trang vô hướng hoặc lưu trữ nhiều tiểu bang mà phải được redundantly kiểm tra mỗi iteration. Để truy cập ngẫu nhiên, trình tối ưu hóa dường như không thể tối ưu hóa chi phí lập chỉ mục này để tìm ra byte và bit tương đối nào cần truy cập (có lẽ hơi phụ thuộc vào thời gian chạy) khi không cần thiết và bạn có xu hướng thấy hiệu suất đáng kể đạt được với các bit xử lý mã thủ công hơn theo tuần tự với kiến ​​thức nâng cao về byte/từ/dword/qword mà nó đang làm việc.Đó là một sự so sánh không công bằng, nhưng khó khăn với std::bitset là không có cách nào để so sánh công bằng trong những trường hợp như vậy, nơi mã biết byte nào nó muốn truy cập trước, và thường xuyên hơn không, bạn có xu hướng có thông tin này trước. Đó là một quả táo để so sánh màu cam trong trường hợp truy cập ngẫu nhiên, nhưng bạn thường chỉ cần cam.

Có lẽ sẽ không xảy ra nếu thiết kế giao diện liên quan đến bitset trong đó operator[] trả về proxy, yêu cầu mẫu truy cập hai chỉ mục để sử dụng. Ví dụ, trong trường hợp này, bạn sẽ truy cập bit 8 bằng cách viết bitset[0][6] = true; bitset[0][7] = true; với tham số mẫu để biểu thị kích thước của proxy (64 bit, ví dụ). Một ưu tốt có thể mất một thiết kế như vậy và làm cho nó cạnh tranh với, loại trường cũ tay cách để thực hiện các thao tác bit bằng tay bằng cách dịch đó vào: bitset |= 0x60;

Một thiết kế có thể giúp là nếu bitsets cung cấp một for_each_bit loại phương thức, chuyển một proxy bit tới hàm functor mà bạn cung cấp. Điều đó thực sự có thể có khả năng cạnh tranh với phương pháp thủ công.

std::deque có vấn đề về giao diện tương tự. Hiệu suất của nó không được là mà chậm hơn nhiều so với std::vector để truy cập tuần tự. Tuy nhiên, thật không may, chúng tôi truy cập nó theo tuần tự sử dụng operator[] được thiết kế để truy cập ngẫu nhiên hoặc thông qua một trình lặp, và đại diện nội bộ của deques chỉ đơn giản là không ánh xạ rất hiệu quả cho một thiết kế dựa trên vòng lặp. Nếu deque cung cấp một phương thức riêng của mình là for_each thì có khả năng nó sẽ có khả năng bắt đầu gần hơn với hiệu suất truy cập tuần tự std::vector's. Đây là một số trường hợp hiếm hoi mà thiết kế giao diện trình tự đi kèm với một số chi phí hiệu quả mà các trình tối ưu hóa thường không thể xóa bỏ. Thường thì các trình tối ưu hóa tốt có thể làm cho tiện ích trở nên miễn phí với chi phí thời gian chạy trong một bản dựng sản xuất, nhưng tiếc là không phải trong mọi trường hợp.

Xin lỗi!

Cũng xin lỗi, khi nhìn lại tôi lang thang một chút với bài đăng này nói về vector<bool> và deque ngoài bitset. Đó là bởi vì chúng tôi đã có một codebase, nơi sử dụng ba, và đặc biệt là lặp đi lặp lại thông qua họ hoặc sử dụng chúng với truy cập ngẫu nhiên, thường là các điểm nóng.

táo để cam

Như đã nhấn mạnh trong câu trả lời cũ, so sánh việc sử dụng đơn giản của bitset để loại nguyên thủy với logic bitwise ở mức độ thấp được so sánh táo để cam. Nó không giống như bitset được thực hiện rất không hiệu quả cho những gì nó làm. Nếu bạn thực sự cần truy cập một loạt các bit với một mẫu truy cập ngẫu nhiên, vì một lý do nào đó, cần kiểm tra và thiết lập một chút thời gian, thì nó có thể được thực hiện lý tưởng cho một mục đích như vậy. Nhưng quan điểm của tôi là hầu như tất cả các trường hợp sử dụng tôi gặp phải không yêu cầu điều đó, và khi nó không được yêu cầu, cách học cũ liên quan đến hoạt động bitwise có xu hướng hiệu quả hơn đáng kể.

Answer 2

Đã làm một bài kiểm tra ngắn profiling std :: bitset vs mảng bool cho truy cập tuần tự và ngẫu nhiên - bạn có thể quá:

#include <iostream> 
#include <bitset> 
#include <cstdlib> // rand 
#include <ctime> // timer 

inline unsigned long get_time_in_ms() 
{ 
    return (unsigned long)((double(clock())/CLOCKS_PER_SEC) * 1000); 
} 


void one_sec_delay() 
{ 
    unsigned long end_time = get_time_in_ms() + 1000; 

    while(get_time_in_ms() < end_time) 
    { 
    } 
} 



int main(int argc, char **argv) 
{ 
    srand(get_time_in_ms()); 

    using namespace std; 

    bitset<5000000> bits; 
    bool *bools = new bool[5000000]; 

    unsigned long current_time, difference1, difference2; 
    double total; 

    one_sec_delay(); 

    total = 0; 
    current_time = get_time_in_ms(); 

    for (unsigned int num = 0; num != 200000000; ++num) 
    { 
     bools[rand() % 5000000] = rand() % 2; 
    } 

    difference1 = get_time_in_ms() - current_time; 
    current_time = get_time_in_ms(); 

    for (unsigned int num2 = 0; num2 != 100; ++num2) 
    { 
     for (unsigned int num = 0; num != 5000000; ++num) 
     { 
      total += bools[num]; 
     } 
    } 

    difference2 = get_time_in_ms() - current_time; 

    cout << "Bool:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl; 


    one_sec_delay(); 

    total = 0; 
    current_time = get_time_in_ms(); 

    for (unsigned int num = 0; num != 200000000; ++num) 
    { 
     bits[rand() % 5000000] = rand() % 2; 
    } 

    difference1 = get_time_in_ms() - current_time; 
    current_time = get_time_in_ms(); 

    for (unsigned int num2 = 0; num2 != 100; ++num2) 
    { 
     for (unsigned int num = 0; num != 5000000; ++num) 
     { 
      total += bits[num]; 
     } 
    } 

    difference2 = get_time_in_ms() - current_time; 

    cout << "Bitset:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl; 

    delete [] bools; 

    cin.get(); 

    return 0; 
} 

Xin lưu ý: xuất ra tổng số tiền là cần thiết để trình biên dịch không tối ưu hóa vòng lặp for - mà một số sẽ thực hiện nếu kết quả của vòng lặp không được sử dụng.

Dưới GCC x64 với các cờ sau: -O2; -Bán; -march = gốc; -fomit-frame-pointer; -std = C++ 11; tôi nhận được kết quả như sau:

Bool mảng: truy cập ngẫu nhiên time = 4695, thời gian truy cập tuần tự = 390

BitSet: thời gian truy cập ngẫu nhiên = 5382, thời gian truy cập tuần tự = 749

Answer 3

Ngoài những gì các câu trả lời khác nói về hiệu suất truy cập, cũng có thể có một không gian đáng kể trên không: Các triển khai điển hình bitset<> chỉ đơn giản là sử dụng kiểu số nguyên dài nhất để trả về các bit của chúng. Do đó, đoạn code sau

#include <bitset> 
#include <stdio.h> 

struct Bitfield { 
    unsigned char a:1, b:1, c:1, d:1, e:1, f:1, g:1, h:1; 
}; 

struct Bitset { 
    std::bitset<8> bits; 
}; 

int main() { 
    printf("sizeof(Bitfield) = %zd\n", sizeof(Bitfield)); 
    printf("sizeof(Bitset) = %zd\n", sizeof(Bitset)); 
    printf("sizeof(std::bitset<1>) = %zd\n", sizeof(std::bitset<1>)); 
} 

xuất ra như sau trên máy tính của tôi:

sizeof(Bitfield) = 1 
sizeof(Bitset) = 8 
sizeof(std::bitset<1>) = 8 

Như bạn thấy, trình biên dịch của tôi phân bổ một con số khổng lồ 64 bit để lưu trữ một duy nhất, với cách tiếp cận bitfield, tôi chỉ cần làm tròn tới tám bit.

Yếu tố này tám trong sử dụng không gian có thể trở nên quan trọng nếu bạn có nhiều bit nhỏ.

Answer 4

Không phải là một câu trả lời tuyệt vời ở đây, mà là một giai thoại liên quan:

Một vài năm trước, tôi đã làm việc trên phần mềm thời gian thực và chúng tôi chạy vào vấn đề lập kế hoạch. Có một mô-đun đã vượt quá thời gian ngân sách, và điều này rất đáng ngạc nhiên vì mô-đun này chỉ chịu trách nhiệm cho một số ánh xạ và đóng gói/giải nén các bit vào/từ các từ 32 bit.

Hóa ra là mô-đun đã sử dụng std :: bitset. Chúng tôi đã thay thế điều này bằng các thao tác thủ công và thời gian thực hiện giảm từ 3 mili giây xuống 25 micro giây. Đó là một vấn đề hiệu suất đáng kể và một sự cải thiện đáng kể.

Vấn đề là các vấn đề hiệu suất do lớp này gây ra có thể rất thực tế.