¿BitArray es más rápido en C#para obtener un valor de bit que una simple conjunción con cambio de bit a bit?

performance bit-shift

Question

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

2). utilizando System.Collections.BitArray con un método Get(int index)

• ¿Qué es más rápido?
• ¿En qué situaciones para los proyectos .NET BitArray podría ser más útil que una simple conjunción con el cambio a nivel de bits?

Answer 1

@Jonathon Reinhart,

su punto de referencia es, lamentablemente, no concluyente. No tiene en cuenta los efectos de la posible carga diferida, el almacenamiento en caché y / o la captura previa (por parte de la CPU, el sistema operativo host y / o el tiempo de ejecución .NET).

Baraje el orden de las pruebas (o llame a los métodos de prueba varias veces) y es posible que note diferentes medidas de tiempo.

Hice su punto de referencia original creado con el objetivo de plataforma "Cualquier CPU" y el perfil de cliente .NET 4.0, ejecutándome en mi máquina con una CPU i7-3770 y Windows 7 de 64 bits.

Lo que obtuve fue esto:

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

que está bastante en línea con sus observaciones.

Sin embargo, la ejecución de la prueba de BitArray antes de la prueba de UInt32 produjo esto:

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

Al observar los tiempos de las pruebas UInt32 y BitArray, notará que el tiempo medido no parece estar conectado a las pruebas en sí, sino al orden en que se ejecutan las pruebas.

Para aliviar estos efectos secundarios al menos un poco, ejecuté los métodos de prueba dos veces en cada programa ejecutado con los siguientes resultados.

Orden de prueba 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.

Orden de prueba 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.

Al observar las segundas invocaciones de los métodos de prueba, parece que al menos en las CPU i7 con tiempo de ejecución .NET actualizado, la prueba UInt32 es más rápida que la prueba BitArray , mientras que la prueba BoolArray sigue siendo la más rápida.

(Me disculpo por tener que escribir mi respuesta al punto de referencia de Jonathon como respuesta, pero como nuevo usuario de SO no puedo comentar ...)

EDITAR:

En lugar de barajar el orden de los métodos de prueba, puede intentar poner un Thread.Sleep (5000) o algo similar justo antes de llamar a la primera prueba ...

Además, la prueba original parece poner la prueba UInt32 en desventaja, ya que incluye una verificación de límites " if (bitnum <0 || bitnum> 31) ", que se ejecuta 30 millones de veces. Ninguna de las otras dos pruebas incluye tal verificación de límites. Sin embargo, esto realmente no es toda la verdad, ya que tanto BitArray como la matriz bool realizan comprobaciones de límites internamente.

Aunque no realicé pruebas, espero que al eliminar los controles de límites, las pruebas UInt32 y BoolArray se realicen de manera similar, pero eso no sería una buena propuesta para una API pública.

Answer 2

BitArray podrá manejar un número arbitrario de valores booleanos, mientras que un byte solo tendrá 8, int solo 32, etc. Esta será la mayor diferencia entre los dos.

Además, BitArray implementa IEnumerable , donde obviamente no lo hace un tipo integral. Así que todo depende de los requisitos de su proyecto; Si necesita una IEnumerable o IEnumerable una matriz, vaya con BitArray .

De hecho, usaría un bool[] en cualquiera de las soluciones, simplemente porque es más explícito en qué tipo de datos está realizando un seguimiento. T

BitArray o bitfield utilizará aproximadamente BitArray del espacio de un bool[] porque "empaquetan" 8 valores booleanos en un solo byte, mientras que un bool por sí mismo ocupará todo el byte de 8 bits. La ventaja de espacio de usar un campo de bits o BitArray no va a importar hasta que estés almacenando muchos bools . (La matemática se deja al lector :-))

Punto de referencia

Resultados: para mi entorno de prueba primitivo, parece que BitArray es un poco más rápido, pero está en el mismo orden de magnitud que hacerlo usted mismo con un tipo integral. También se probó un bool[] , que sorprendentemente fue el más rápido. El acceso a los bytes individuales en la memoria será menos complejo que el acceso a los bits individuales en bytes diferentes.

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

Código:

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;
    }
}