c++ - ¿Cuál es el rendimiento de std:: bitset?

performance

Question

Hace poco hice una pregunta a los Programmers sobre las razones para usar la manipulación manual de bits de los tipos primitivos sobre std::bitset .

De esa discusión, he concluido que la razón principal es su desempeño comparativamente más pobre, aunque no conozco ninguna base mesurada para esta opinión. Así que la siguiente pregunta es:

¿ std::bitset es el impacto de rendimiento, si es que hay alguno, en el que se incurrirá al usar std::bitset sobre la manipulación de bits de un primitivo?

La pregunta es intencionalmente amplia, porque después de buscar en línea no he podido encontrar nada, así que tomo lo que puedo obtener. Básicamente, busco un recurso que proporcione un perfil de las alternativas std::bitset vs ''pre-bitset'' a los mismos problemas en algunas arquitecturas de máquinas comunes utilizando GCC, Clang y / o VC ++. Hay un documento muy completo que intenta responder esta pregunta para vectores de bits:

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

Desafortunadamente, es anterior o se considera fuera de alcance std::bitset , por lo que se enfoca en implementaciones de vectores / arreglos dinámicos en su lugar.

Realmente solo quiero saber si std::bitset es mejor que las alternativas para los casos de uso que se pretende resolver. Ya sé que es más fácil y más claro que manipular bits en un entero, pero ¿es tan rápido ?

Answer 1

Además de lo que dicen las otras respuestas sobre el rendimiento del acceso, también puede haber una gran sobrecarga de espacio: las bitset<> típicas de conjuntos de bitset<> simplemente usan el tipo de entero más largo para respaldar sus bits. Así, el siguiente código

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

produce la siguiente salida en mi máquina:

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

Como puede ver, mi compilador asigna la friolera de 64 bits para almacenar uno solo, con el enfoque de campo de bits, solo necesito redondear hasta ocho bits.

Este factor ocho en el uso del espacio puede llegar a ser importante si tiene muchos conjuntos de bits pequeños.

Answer 2

Hice una prueba corta de perfiles std :: bitset vs bool arrays para acceso secuencial y aleatorio, usted también puede:

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

Tenga en cuenta que: la salida de la suma total es necesaria para que el compilador no optimice el bucle for, lo que algunos lo hacen si no se usa el resultado del bucle.

Bajo GCC x64 con los siguientes indicadores: -O2; -Wall; -march = native; -fomit-frame-pointer; -std = c ++ 11; Obtengo los siguientes resultados:

Bool array: tiempo de acceso aleatorio = 4695, tiempo de acceso secuencial = 390

Conjunto de bits: tiempo de acceso aleatorio = 5382, tiempo de acceso secuencial = 749

Answer 3

No es una gran respuesta aquí, sino una anécdota relacionada:

Hace unos años, estaba trabajando en software en tiempo real y tuvimos problemas de programación. Había un módulo que superaba el presupuesto de tiempo, y esto era muy sorprendente porque el módulo solo era responsable de algunos mapeos y empaquetamientos / desempaquetados de bits en / desde palabras de 32 bits.

Resultó que el módulo estaba usando std :: bitset. Reemplazamos esto con operaciones manuales y el tiempo de ejecución disminuyó de 3 milisegundos a 25 microsegundos. Ese fue un problema de rendimiento significativo y una mejora significativa.

El punto es que los problemas de rendimiento causados ​​por esta clase pueden ser muy reales.

Answer 4

Pregunta retórica: ¿Por qué std::bitset está escrito de esa manera std::bitset ? Respuesta: No lo es.

Otra pregunta retórica: ¿Cuál es la diferencia entre:

std::bitset<128> a = src;
a[i] = true;
a = a << 64;

y

std::bitset<129> a = src;
a[i] = true;
a = a << 63;

Respuesta: 50 veces la diferencia en el rendimiento http://quick-bench.com/iRokweQ6JqF2Il-T-9JSmR0bdyw

bitset ser muy cuidadoso con lo que pide, muchas cosas bitset compatibles con cada una de ellas pero cada una tiene su propio costo. Con el manejo correcto, tendrá exactamente el mismo comportamiento que el código en bruto:

void f(std::bitset<64>& b, int i)
{
    b |= 1L << i;
    b = b << 15;
}
void f(unsigned long& b, int i)
{
    b |= 1L << i;
    b = b << 15;
}

Ambos generan el mismo ensamblaje: https://godbolt.org/g/PUUUyd (64 bit GCC)

Otra cosa es que el conjunto de bitset es más portátil pero esto también tiene un costo:

void h(std::bitset<64>& b, unsigned i)
{
    b = b << i;
}
void h(unsigned long& b, unsigned i)
{
    b = b << i;
}

Si i > 64 entonces el bit set será cero y en caso de que no esté firmado tenemos UB.

void h(std::bitset<64>& b, unsigned i)
{
    if (i < 64) b = b << i;
}
void h(unsigned long& b, unsigned i)
{
    if (i < 64) b = b << i;
}

Con la comprobación de UB ambos generan el mismo código.

Se establece otro lugar y [] , el primero es seguro y significa que nunca obtendrá UB, pero esto le costará una sucursal. [] tiene UB si usas un valor incorrecto pero es rápido como var |= 1L<< i; . Por supuesto, si std::bitset no necesita tener más bits que el mayor int disponible en el sistema porque de otra manera necesita un valor dividido para obtener el elemento correcto en la tabla interna. Esta media para std::bitset<N> tamaño N es muy importante para el rendimiento. Si es mayor o menor que el óptimo, pagará el costo de la misma.

En general me parece que la mejor manera es usar algo así:

constexpr size_t minBitSet = sizeof(std::bitset<1>)*8;

template<size_t N>
using fasterBitSet = std::bitset<minBitSet * ((N  + minBitSet - 1) / minBitSet)>;

Esto eliminará el costo de recortar los bits excedentes: http://quick-bench.com/Di1tE0vyhFNQERvucAHLaOgucAY

Answer 5

Actualizar

Han pasado años desde que publiqué este, pero:

Ya sé que es más fácil y más claro que manipular bits en un entero, pero ¿es tan rápido?

Si está utilizando el conjunto de bitset de una manera que lo hace más claro y limpio que la bitset de bits, como comprobar un bit a la vez en lugar de usar una máscara de bits, inevitablemente perderá todos los beneficios que brindan las operaciones a nivel de bits, como ser capaz de verificar si se establecen 64 bits a la vez contra una máscara, o usar las instrucciones de FFS para determinar rápidamente qué bit se establece entre 64 bits.

No estoy seguro de que el conjunto de bitset incurra en una penalización para usarlo de todas las formas posibles (por ejemplo, usar su operator& bits operator& ), pero si lo usa como una matriz booleana de tamaño fijo, que es prácticamente la misma forma en que siempre veo a las personas que lo usan. entonces generalmente pierdes todos los beneficios descritos anteriormente. Desafortunadamente, no podemos obtener el nivel de expresividad de solo acceder un bit a la vez con el operator[] y hacer que el optimizador descubra todas las manipulaciones de bits y FFS y FFZ y así sucesivamente, al menos no desde la última el tiempo que revisé (de lo contrario el conjunto de bitset sería una de mis estructuras favoritas).

Ahora, si va a utilizar bitset<N> bits intercambiable con like, por ejemplo, uint64_t bits[N/64] como para acceder a ambos de la misma manera utilizando operaciones a nivel de bits, podría estar a la par (no lo he comprobado desde esta antigua publicación ). Pero luego pierdes muchos de los beneficios de usar bitset en primer lugar.

método for_each

En el pasado tuve algunos malentendidos, creo, cuando propuse un método for_each para iterar a través de cosas como vector<bool> , deque y bitset . El objetivo de tal método es utilizar el conocimiento interno del contenedor para recorrer los elementos de manera más eficiente al invocar un funtor, al igual que algunos contenedores asociativos ofrecen un método de find propio en lugar de usar std::find para hacer un mejor trabajo. Búsqueda en tiempo lineal.

Por ejemplo, puede iterar a través de todos los bits establecidos de un vector<bool> o conjunto de bits si tenía conocimiento interno de estos contenedores al verificar 64 elementos a la vez usando una máscara de 64 bits cuando están ocupados 64 índices contiguos, y de igual manera usar Instrucciones de FFS cuando ese no es el caso.

Pero un diseño de iterador que tenga que hacer este tipo de lógica escalar en el operator++ inevitablemente tendría que hacer algo considerablemente más caro, solo por la naturaleza en la que se diseñan los iteradores en estos casos peculiares. bitset carece de iteradores en forma directa y eso a menudo hace que las personas deseen usarlo para evitar manejar la lógica a nivel de bits para usar el operator[] para verificar cada bit individualmente en un bucle secuencial que solo quiere averiguar qué bits están establecidos. Eso tampoco es tan eficiente como lo que podría hacer una implementación del método for_each .

Iteradores dobles / anidados

Otra alternativa al método específico para el contenedor de for_each propuesto anteriormente sería utilizar iteradores dobles / anidados: es decir, un iterador externo que apunta a un sub-rango de un tipo diferente de iterador. Ejemplo de código de cliente:

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

Si bien no se ajusta al tipo plano de diseño de iterador disponible ahora en contenedores estándar, esto puede permitir algunas optimizaciones muy interesantes. Como ejemplo, imagina un caso como este:

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

En ese caso, el iterador externo puede, con solo unas pocas iteraciones a nivel de bits ((FFZ / o / complemento), deducir que el primer rango de bits a procesar sería bits [0, 6), en cuyo punto podemos iterar a través de eso sub-rango muy barato a través del iterador interno / anidado (solo incrementaría un entero, haciendo que ++inner_it equivalente a solo ++int ). Luego, cuando incrementamos el iterador externo, puede entonces muy rápidamente, y nuevamente con unas pocas instrucciones a nivel de bits, determinar que el siguiente rango sería [7, 13). Después de que iteramos a través de ese sub-rango, hemos terminado. Toma esto como otro ejemplo:

bitset<16> bits = 0xffff;

En tal caso, el primer y último sub-rango sería [0, 16) , y el conjunto de bits podría determinar eso con una sola instrucción a nivel de bits en qué punto podemos recorrer todos los bits establecidos y luego hemos terminado.

Este tipo de diseño de iterador anidado se asignaría particularmente bien a vector<bool> , deque y bitset , así como a otras estructuras de datos que la gente podría crear como listas desenrolladas.

Lo digo de una manera que va más allá de la especulación del sillón, ya que tengo un conjunto de estructuras de datos que se asemejan a los gustos de deque que en realidad están a la par con la iteración secuencial del vector (todavía notablemente más lento para el acceso aleatorio, especialmente si simplemente almacenando un montón de primitivas y haciendo un procesamiento trivial). Sin embargo, para lograr los tiempos comparables con el vector para la iteración secuencial, tuve que usar estos tipos de técnicas (para for_each método y los iteradores dobles / anidados) para reducir la cantidad de procesamiento y ramificación en cada iteración. No podría competir con los tiempos, de lo contrario utilizaría solo el diseño del iterador plano y / o el operator[] . Y ciertamente no soy más inteligente que los implementadores de bibliotecas estándar, pero se me ocurrió un contenedor similar a deque que puede iterarse secuencialmente mucho más rápido, y eso me sugiere fuertemente que es un problema con el diseño de interfaz estándar de los iteradores en este caso. vienen con un poco de sobrecarga en estos casos peculiares que el optimizador no puede optimizar.

Respuesta antigua

Soy uno de los que te daría una respuesta de desempeño similar, pero intentaré darte un poco más de profundidad que "just because" . Es algo que encontré a través de perfiles y tiempos reales, no simplemente de desconfianza y paranoia.

Uno de los mayores problemas con el conjunto de bitset y el vector<bool> es que su diseño de interfaz es "demasiado conveniente" si desea usarlos como un conjunto de valores booleanos. Los optimizadores son excelentes para eliminar toda la estructura que usted establece para proporcionar seguridad, reducir los costos de mantenimiento, hacer cambios menos intrusivos, etc. Hacen un trabajo especialmente bueno con la selección de instrucciones y la asignación del número mínimo de registros para que dicho código se ejecute tan rápido como el no tan seguro, no tan fácil de mantener / cambiar alternativas.

La parte que hace que la interfaz del conjunto de bits sea "demasiado conveniente" al costo de la eficiencia es el operator[] acceso aleatorio operator[] , así como el diseño del iterador para vector<bool> . Cuando accede a uno de estos en el índice n , el código debe determinar primero a qué byte pertenece el bit nth, y luego el subíndice del bit dentro de ese. La primera fase generalmente implica una división / rshifts contra un lvalue junto con modulo / bitwise y que es más costoso que la operación de bit real que está intentando realizar.

El diseño del iterador para vector<bool> enfrenta un dilema incómodo similar en el que tiene que derivar en un código diferente cada 8+ veces que lo itere o pague ese tipo de costo de indexación descrito anteriormente. Si se hace lo primero, hace que la lógica sea asimétrica en todas las iteraciones, y los diseños de iteradores tienden a tener un impacto en el rendimiento en esos casos raros. Para ejemplificar, si el vector tuviera su propio método for_each , podría recorrer, por ejemplo, un rango de 64 elementos a la vez simplemente enmascarando los bits contra una máscara de 64 bits para el vector<bool> si todos los bits se configuran sin Comprobando cada bit individualmente. Incluso podría usar FFS para calcular el rango de una vez. Un diseño de iterador tendería a tener que hacerlo inevitablemente de forma escalar o almacenar más estados, lo que debe comprobarse de forma redundante en cada iteración.

Para el acceso aleatorio, parece que los optimizadores no pueden optimizar esta sobrecarga de indexación para determinar a qué byte y qué bit relativo acceder (quizás un poco demasiado dependiente del tiempo de ejecución) cuando no es necesario, y usted tiende a ver ganancias significativas en el rendimiento con más. código de procesamiento manual de bits secuencialmente con conocimiento avanzado de qué byte / palabra / dword / qword está trabajando. Es algo así como una comparación injusta, pero la dificultad con std::bitset es que no hay manera de hacer una comparación justa en tales casos donde el código sabe a qué byte quiere acceder por adelantado, y la mayoría de las veces, tiende a tener esta información por adelantado. Es una comparación de manzanas con naranjas en el caso de acceso aleatorio, pero a menudo solo se necesitan naranjas.

Quizás ese no sería el caso si el diseño de la interfaz involucrara un conjunto de bitset donde el operator[] devolviera un proxy, requiriendo un patrón de acceso de dos índices para su uso. Por ejemplo, en tal caso, tendría acceso al bit 8 escribiendo el conjunto de bitset[0][6] = true; bitset[0][7] = true; bitset[0][6] = true; bitset[0][7] = true; con un parámetro de plantilla para indicar el tamaño del proxy (64 bits, por ejemplo). Un buen optimizador puede ser capaz de tomar tal diseño y hacerlo rivalizar con la forma manual, de la vieja escuela, de hacer la manipulación manual de los bits traduciéndolos a: bitset |= 0x60;

Otro diseño que podría ayudar es si los conjuntos de bitsets proporcionaran un tipo de método for_each_bit , pasando un proxy de bits al functor que usted proporciona. Eso podría ser capaz de rivalizar con el método manual.

std::deque tiene un problema de interfaz similar. Su rendimiento no debería ser tan lento como std::vector para el acceso secuencial. Sin embargo, desafortunadamente, accedemos a él de forma secuencial utilizando el operator[] que está diseñado para un acceso aleatorio o mediante un iterador, y el representante interno de deques simplemente no se asigna de manera muy eficiente a un diseño basado en iteradores. Si Deque proporcionó un tipo de método propio para for_each , entonces potencialmente podría comenzar a acercarse mucho más al rendimiento de acceso secuencial de std::vector''s . Estos son algunos de los casos raros en los que el diseño de la interfaz de Secuencia viene con una sobrecarga de eficiencia que los optimizadores a menudo no pueden borrar. A menudo, los buenos optimizadores pueden hacer que la conveniencia no tenga costo de tiempo de ejecución en una generación de producción, pero desafortunadamente no en todos los casos.

¡Lo siento!

También lo siento, en retrospectiva, vagué un poco con esta publicación hablando sobre vector<bool> y deque además de bitset . Es porque teníamos una base de código donde el uso de estos tres, y en particular iterando a través de ellos o usándolos con acceso aleatorio, a menudo eran puntos de acceso.

Manzanas a las naranjas

Como se enfatizó en la respuesta anterior, comparar el uso directo de bitset de bitset con tipos primitivos con lógica bitwise de bajo nivel es comparar manzanas con naranjas. No es como que el conjunto de bitset se implementa de manera muy ineficiente por lo que hace. Si realmente necesita acceder a un grupo de bits con un patrón de acceso aleatorio que, por alguna razón u otra, necesita verificar y configurar solo un bit por vez, entonces podría implementarse idealmente para tal propósito. Pero mi punto es que casi todos los casos de uso que he encontrado no lo requieren, y cuando no es necesario, la forma de la vieja escuela que involucra operaciones bitwise tiende a ser significativamente más eficiente.