BitArray có nhanh hơn trong C# để nhận được một giá trị bit hơn một kết hợp đơn giản với sự dịch chuyển bitwise không?

Question

1). var bitValue = (byteValue & (1 << bitNumber)) != 0;

2). sử dụng System.Collections.BitArray với phương thức Get(int index)

• Điều gì sẽ nhanh hơn?
• Trong trường hợp nào cho các dự án .NET BitArray có thể hữu ích hơn so với kết hợp đơn giản với thay đổi bitwise?

Answer 1

BitArray đang xảy ra để có thể xử lý một số tùy ý các giá trị boolean, trong khi một byte sẽ tổ chức chỉ có 8, int chỉ 32, vv Điều này sẽ là sự khác biệt lớn nhất giữa hai người.

Ngoài ra, BitArray thực hiện IEnumerable, trong đó một loại tích phân rõ ràng là không. Vì vậy, tất cả phụ thuộc vào yêu cầu của dự án của bạn; nếu bạn cần IEnumerable hoặc giao diện giống như mảng, hãy đi theo số BitArray.

Tôi thực sự sẽ sử dụng bool[] trên một trong hai giải pháp, đơn giản vì nó rõ ràng hơn trong loại dữ liệu bạn đang theo dõi. T

BitArray hoặc bitfield sẽ sử dụng khoảng 1/8 không gian của một bool[] vì họ "gói" 8 giá trị boolean thành một byte duy nhất, trong khi một bool bởi chính nó sẽ mất toàn bộ byte 8-bit. Lợi thế không gian của việc sử dụng một bitfield hoặc BitArray sẽ không quan trọng cho đến khi bạn đang lưu trữ lô của bools. (Toán học là trái lên đến người đọc :-))

---

Benchmark

Kết quả: Đối với môi trường thử nghiệm nguyên thủy của tôi, dường như là một BitArraychút nhanh hơn, nhưng là trên cùng một thứ tự độ lớn khi tự làm nó với một loại tích phân. Ngoài ra thử nghiệm là một bool[], mà không ngạc nhiên là nhanh nhất. Việc truy cập các byte đơn trong bộ nhớ sẽ ít phức tạp hơn việc truy cập các bit riêng lẻ trong các byte khác nhau.

Testing with 10000000 operations: 
    A UInt32 bitfield took 808 ms. 
    A BitArray (32) took 574 ms. 
    A List<bool>(32) took 436 ms. 

Code:

class Program 
{ 
    static void Main(string[] args) 
    { 
     Random r = new Random(); 
     r.Next(1000); 

     const int N = 10000000; 

     Console.WriteLine("Testing with {0} operations:", N); 

     Console.WriteLine(" A UInt32 bitfield took {0} ms.", TestBitField(r, N)); 
     Console.WriteLine(" A BitArray (32) took {0} ms.", TestBitArray(r, N)); 
     Console.WriteLine(" A List<bool>(32) took {0} ms.", TestBoolArray(r, N)); 

     Console.Read(); 
    } 


    static long TestBitField(Random r, int n) 
    { 
     UInt32 bitfield = 0; 

     var sw = Stopwatch.StartNew(); 
     for (int i = 0; i < n; i++) { 

      SetBit(ref bitfield, r.Next(32), true); 
      bool b = GetBit(bitfield, r.Next(32)); 
      SetBit(ref bitfield, r.Next(32), b); 
     } 
     sw.Stop(); 
     return sw.ElapsedMilliseconds; 
    } 

    static bool GetBit(UInt32 x, int bitnum) { 
     if (bitnum < 0 || bitnum > 31) 
      throw new ArgumentOutOfRangeException("Invalid bit number"); 

     return (x & (1 << bitnum)) != 0; 
    } 

    static void SetBit(ref UInt32 x, int bitnum, bool val) 
    { 
     if (bitnum < 0 || bitnum > 31) 
      throw new ArgumentOutOfRangeException("Invalid bit number"); 

     if (val) 
      x |= (UInt32)(1 << bitnum); 
     else 
      x &= ~(UInt32)(1 << bitnum); 
    } 



    static long TestBitArray(Random r, int n) 
    { 
     BitArray b = new BitArray(32, false);  // 40 bytes 

     var sw = Stopwatch.StartNew(); 
     for (int i = 0; i < n; i++) { 

      b.Set(r.Next(32), true); 
      bool v = b.Get(r.Next(32)); 
      b.Set(r.Next(32), v); 
     } 
     sw.Stop(); 
     return sw.ElapsedMilliseconds; 
    } 



    static long TestBoolArray(Random r, int n) 
    { 
     bool[] ba = new bool[32]; 

     var sw = Stopwatch.StartNew(); 
     for (int i = 0; i < n; i++) { 

      ba[r.Next(32)] = true; 
      bool v = ba[r.Next(32)]; 
      ba[r.Next(32)] = v; 
     } 
     sw.Stop(); 
     return sw.ElapsedMilliseconds; 
    } 
} 

Answer 2

@Jonathon Reinhart,

benchmark của bạn là tiếc không thuyết phục. Nó không tính đến tác động của việc tải xuống, lưu vào bộ nhớ đệm và/hoặc tìm nạp trước (bởi CPU, hệ điều hành máy chủ và/hoặc thời gian chạy .NET).

Trộn thứ tự các phép thử (hoặc gọi phương thức thử nhiều lần) và bạn có thể nhận thấy các phép đo thời gian khác nhau.

Tôi đã làm điểm chuẩn ban đầu của bạn được xây dựng với mục tiêu nền tảng "Bất kỳ CPU" và cấu hình máy khách .NET 4.0, chạy trên máy tính của tôi với CPU i7-3770 và Windows 7 64 bit.

gì tôi đã nhận được điều này:

Testing with 10000000 operations: 
    A UInt32 bitfield took 484 ms. 
    A BitArray (32) took 459 ms. 
    A List<bool>(32) took 393 ms. 

đó là khá nhiều phù hợp với quan sát của bạn.

Tuy nhiên, thực hiện các bài kiểm tra BitArray trước khi thử nghiệm UInt32 mang lại điều này:

Testing with 10000000 operations: 
    A BitArray (32) took 513 ms. 
    A UInt32 bitfield took 456 ms. 
    A List<bool>(32) took 417 ms. 

Bằng cách nhìn vào những thời điểm cho UInt32 và BitArray bài kiểm tra bạn sẽ nhận thấy rằng thời gian đo dường như không được kết nối với tự kiểm tra, nhưng đúng hơn là thứ tự các bài kiểm tra được chạy.

Để giảm bớt những tác dụng phụ này ít nhất một chút, tôi đã thực hiện các phương pháp thử nghiệm hai lần trong mỗi chương trình chạy với các kết quả sau.

Kiểm tra trật tự UInt32, BitArray, BoolArray, UInt32, BitArray, BoolArray:

Testing with 10000000 operations: 
    A UInt32 bitfield took 476 ms. 
    A BitArray (32) took 448 ms. 
    A List<bool>(32) took 367 ms. 

    A UInt32 bitfield took 419 ms. <<-- Watch this. 
    A BitArray (32) took 444 ms. <<-- Watch this. 
    A List<bool>(32) took 388 ms. 

để thử nghiệm BitArray, UInt32, BoolArray, BitArray, UInt32, BoolArray:

Testing with 10000000 operations: 
    A BitArray (32) took 514 ms. 
    A UInt32 bitfield took 413 ms. 
    A List<bool>(32) took 379 ms. 

    A BitArray (32) took 444 ms. <<-- Watch this. 
    A UInt32 bitfield took 413 ms. <<-- Watch this. 
    A List<bool>(32) took 381 ms. 

Nhìn vào lời gọi thứ hai của các phương pháp thử nghiệm, có vẻ như ít nhất trên các CPU i7 với thời gian chạy .NET cập nhật, kiểm tra UI132 nhanh hơn thử nghiệm BitArray, trong khi thử nghiệm BoolArray vẫn là nhanh nhất.

(Tôi xin lỗi mà tôi đã phải viết câu trả lời của tôi để chuẩn Jonathon như một câu trả lời, nhưng như một SO người dùng mới tôi không cho phép bình luận ...)

EDIT:

Thay vì xáo trộn thứ tự của phương pháp thử, bạn có thể thử đặt một Thread.Sleep (5000) hoặc tương tự ngay trước khi gọi thử nghiệm đầu tiên ...

Ngoài ra thử nghiệm ban đầu dường như đặt thử nghiệm UInt32 ở bất lợi, bởi vì nó bao gồm một ranh giới kiểm tra "nếu (bitnum < 0 || bitnum> 31)", whic h được thực hiện 30 triệu lần. Không có hai thử nghiệm nào khác bao gồm kiểm tra ranh giới như vậy. Tuy nhiên, đây thực sự không phải là toàn bộ sự thật, vì cả hai mảng BitArray và bool đều thực hiện kiểm tra ranh giới nội bộ.

Mặc dù tôi không kiểm tra, tôi hy vọng rằng việc loại bỏ kiểm tra biên sẽ làm cho các thử nghiệm UInt32 và BoolArray hoạt động tương tự, nhưng đó không phải là một đề xuất tốt cho API công khai.