BitMagia
v.7.13.4
BitMagic se creó como un conjunto de herramientas de álgebra de conjuntos para la recuperación de información, pero actualmente evolucionó hasta convertirse en una biblioteca de componentes de ciencia de datos más general para estructuras compactas de memoria y algoritmos en vectores de datos concisos. BitMagic implementa contenedores y vectores de bits comprimidos (vectores) basados en ideas de transformación de corte de bits, compresión Rank-Select y computación lógica en modelos de memoria comprimida.
Todos los contenedores sucintos de BitMagic son serializables (con compresión utilizando codificación interpolativa binaria de última generación) para un almacenamiento y transferencia de red eficientes. Todos los contenedores se pueden buscar rápidamente en forma comprimida.
BitMagic ofrece conjuntos de métodos y herramientas para diseñar sus aplicaciones para utilizar técnicas HPC para ahorrar memoria sobre la marcha (y así poder incluir más datos en una unidad informática), mejorar los patrones de almacenamiento y tráfico al almacenar vectores y modelos de datos en archivos u objetos. almacena (SQL o noSQL), optimiza el ancho de banda de los sistemas desde el nivel bajo (cachés de CPU) hasta el intercambio de red y almacenamiento.
BitMagic facilita dos grandes clases de escenarios:
BitMagic se utilizó como base para:
Visite nuestras notas de casos de uso: http://bitmagic.io/use-case.html
La biblioteca BitMagic es una biblioteca de alto rendimiento que implementa optimizaciones para una variedad de plataformas y objetivos de compilación:
BitMagic utiliza un diseño vectorizado de datos paralelos con el objetivo no solo de proporcionar el mejor rendimiento de un solo subproceso, sino también de facilitar la computación altamente paralela en sistemas de muchos núcleos.
BitMagic utiliza un conjunto de algoritmos de compresión, filtros y transformaciones para reducir el uso de memoria, los costos de almacenamiento y la transferencia de datos de red. http://bitmagic.io/design.html
Visite nuestras notas técnicas: http://bitmagic.io/articles.html
BitMagic admite la reinterpretación de vectores de bits como colecciones de rangos no superpuestos de unos flanqueados por ceros (por ejemplo: 011110110). Las funciones de conjuntos regulares proporcionan operaciones de intervalos de intersecciones/uniones establecidas, implementan iteradores de intervalos y buscan límites de intervalos. Los rangos e intervalos tienen gran utilidad en bioinformática, porque los datos genómicos a menudo se anotan como rangos de coordenadas. BitMagic ofrece bloques de construcción para operaciones eficientes en intervalos codificados como vectores de bits (buscar el inicio/final del intervalo, verificar si el rango es un intervalo, iterar intervalos
BitMagic implementa operaciones lógicas para lógica de 3 valores de Verdadero/Falso/Desconocido (también lógica trinaria, trivalente, ternaria) en una representación compacta de dos vectores de bits, admitiendo operaciones de inversión, Y y O siguiendo las definiciones de Kleene. https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic
BitMagic utiliza el concepto de serialización-deserialización de dos etapas. La atención se centra en la deserialización rápida. BitMagic implementa una API para una deserialización rápida de rangos vectoriales y una deserialización de recopilación de BLOB comprimidos. La característica definitiva de BitMagic es la capacidad de trabajar con datos comprimidos.
Este es el estado operativo principal en RAM, donde los vectores se mantienen en forma compacta de memoria. Sucinto NO es una compresión. Es posible acceder a elementos aleatorios en contenedores, decodificar bloques, iterar vectores, realizar actualizaciones, ejecutar algoritmos de búsqueda. Stage One ofrece un uso transparente, sus vectores se parecen mucho a STL. Sucinto es una memoria compacta pero no completamente comprimida.
BitMagic puede serializar todos los contenedores y vectores con compresión adicional basada en bloques de heurísticas y códecs. Las técnicas de codificación más utilizadas son: codificación interpolativa binaria (BIC) y Elias Gamma.
Los contenedores de BitMagic se denominan vectores "dispersos", pero de hecho sus esquemas de compresión funcionan bien tanto para datos dispersos como para datos densos.
BitMagic se prueba en el conjunto de referencia Gov2 de listas invertidas y una cantidad de conjuntos de datos propietarios. http://bitmagic.io/bm5-cmpr.html
La deserialización siempre vuelve a la Etapa Uno, por lo que los datos no se decodifican por completo, sino que
sucinto en RAM. Nuestro objetivo aquí es reducir el uso de memoria de la aplicación y mejorar la latencia de deserialización. Los algoritmos de descompresión admiten la deserialización de rangos arbitrarios o incluso recopilan la deserialización de elementos.
BitMagic admite vectores sucintos (memoria compacta) basados en transformación de transposición de bits
también conocida como compresión de plano de bits (BPC) (también conocida como corte de bits) más compresión Rank-Select. Los vectores sucintos de BitMagic están etiquetados de manera algo engañosa como "escasos", pero funcionan bien para vectores densos.
La transposición de bits resuelve dos propósitos: liberar planos de bits no utilizados y aislar la regularidad y la entropía en vectores de bits separados (dispersos). La compresión en planos de bits ofrece un rendimiento de memoria superior y una búsqueda rápida. Uno de los objetivos del diseño es realizar búsquedas sin índice en vectores sucintos utilizando operaciones lógicas vectorizadas rápidas.
Los vectores sucintos de BitMagic se pueden buscar sin índice en forma comprimida en memoria. ¡Es rápido!
La implementación sucinta de transposición de bits funciona bien tanto para vectores enteros (con o sin signo) como para vectores de cadena. Compite con otros esquemas concisos como los árboles de prefijos. Los vectores sucintos pueden estar tanto ordenados como sin clasificar. La idea aquí es similar a Apache Arrow-Parquet, pero va más allá con la compresión de plano de bits y el uso extensivo de la compresión acelerada Rank-Select.
BitMagic admite la evolución de la serialización (protocolo): si el formato de serialización cambia, los datos antiguos guardados siguen siendo legibles con el nuevo código. El código antiguo NO podrá leer BLOB nuevos. BitMagic cambia el número de versión principal cuando cambia el formato de serialización.
BitMagic implementa llamadas de perfiles de memoria para todos los vectores. Se puede tomar muestras de cualquier vector para determinar la huella de memoria, de modo que el sistema de nivel superior pueda adaptar la administración de la memoria en función del perfil de memoria en tiempo de ejecución. El caso de uso típico es la memoria caché de objetos con compresión en RAM y luego desalojo al disco en función del consumo de recursos y los costos (equilibrio dinámico de oferta y demanda).
¡Sí! BitMagic admite 64 bits, se puede utilizar con un espacio de direcciones de 32 bits (menos gastos generales) o con un espacio de direcciones completo de 64 bits. El espacio de direcciones de 32 bits es el modo predeterminado. Los elementos 2^31-1 deberían ser una buena opción para sistemas de ciencia de datos e IR de corto a mediano alcance. El modo de dirección de 64 bits está disponible usando #define BM64ADDR o #include "bm64.h". La implementación actual de 64 bits permite elementos vectoriales 2^48-1 para sistemas a gran escala.
BitMagic compila y trabaja con WebAssmbly (emscripten). Las últimas versiones incluyen múltiples ajustes específicos para la plataforma. Las cifras de rendimiento se aproximan a las del código nativo sin SIMD (a veces después). La línea de compilación de muestra se vería así:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...
WebAssembly SIMD es compatible pero no está activado de forma predeterminada. Utilice: #define BMWASMSIMDOPT para habilitarlo. Ejemplo de cmd de Emscripten:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -msse4.2 -msimd128 -D BMWASMSIMDOPT -s WASM=1 -s DISABLE_EXCEPTION_CATCHING=0 -fno-rtti
La implementación actual utiliza la transcompilación SSE4.2 (a través de intrínsecos), por lo que -msse4.2 es necesario.
BitMagic es totalmente compatible con CPU ARM. Todas las versiones se prueban con Raspberry Pi 4. BitMagic implementa algunos ajustes algorítmicos y mejoras específicas para ARM (como el uso de la instrucción LZCNT). Los contenedores sucintos de BitMagic pueden ser muy útiles en sistemas integrados para computación de vanguardia con una cantidad limitada de memoria disponible.
La compatibilidad con Arm Neon SIMD está disponible (a través de la biblioteca SSE2NEON).
BitMagic C++ es una biblioteca de solo encabezado (fácil de construir y usar en su proyecto) y viene con un conjunto de ejemplos. NO se recomienda utilizar pruebas como ejemplo de código para estudiar el uso de la biblioteca. Las pruebas no ilustran los mejores patrones y modelos de uso y, a menudo, son intencionadamente ineficientes.
Documentación API y ejemplos: http://www.bitmagic.io/apis.html
Tutorial de Álgebra de Conjuntos: http://bitmagic.io/set-algebra.html
Casos de uso y notas de aplicación: http://bitmagic.io/use-case.html
Notas técnicas sobre optimización del rendimiento: http://bitmagic.io/articles.html
Doxygen: http://bitmagic.io/doxygen/html/modules.html
Apache 2.0.
¡Importante! Le pedimos que mencione explícitamente el proyecto BitMagic en cualquier trabajo derivado o en nuestros materiales publicados. La referencia adecuada en la página de su producto/proyecto es un REQUISITO para usar la Biblioteca BitMagic.
La biblioteca BitMagic presta mucha atención a la calidad del código y la cobertura de las pruebas.
Como biblioteca de componentes básicos, BitMagic debe ser estable y compatible para ser útil.
No confiamos únicamente en las pruebas unitarias, nuestras pruebas a menudo utilizan "pruebas de caos" (también conocidas como fuzzing) donde las pruebas de estrés se basan en conjuntos generados aleatorios y operaciones aleatorias. Regularmente creamos y ejecutamos trajes de prueba para los modos de lanzamiento y depuración para varias combinaciones de optimizaciones SIMD.
Todas las variantes de las compilaciones de prueba tardan días en ejecutarse, por lo que NO se garantiza que la rama maestra en funcionamiento sea perfecta todo el tiempo. Para producción, utilice distribuciones o ramas de lanzamiento estables de github de SourceForge: https://sourceforge.net/projects/bmagic/files/
GitHub master acepta solicitudes de parches. Nuestra política de ramificación es que master no puede considerarse completamente estable entre las versiones. (para estabilidad de producción, utilice versiones de lanzamiento)
Necesita ayuda con asignaciones a Python y otros lenguajes (BitMagic tiene enlaces C)
BitMagic C++ es un paquete de software de solo encabezado y probablemente puedas tomar las fuentes e insertarlas directamente en tu proyecto. Todas las fuentes/encabezados de la biblioteca C++ están en el directorio src.
Sin embargo, si desea utilizar nuestros archivos MAKE, debe seguir las siguientes instrucciones sencillas:
Aplique algunas variables de entorno ejecutando bmenv.sh en el directorio raíz del proyecto:
$ source ./bmenv.sh
(utilice "." "./bmenv.sh" para aplicar la variable de entorno raíz)
use GNU make (gmake) para construir la instalación.
$make rebuild
o (versión DEBUG)
$gmake DEBUG=YES rebuild
El compilador predeterminado en Unix y CygWin es g++. Si desea cambiar el valor predeterminado, puede hacerlo en makefile.in (debería ser bastante fácil de hacer)
Si utiliza la instalación de cygwin, siga las recomendaciones generales de Unix. MSVC: la solución y los proyectos están disponibles a través de CMAKE.
Xcode: los archivos del proyecto están disponibles a través de CMAKE.
Biblioteca BitMagic para asignaciones C y JNI.
La biblioteca BitMagic está disponible para lenguaje C (este es un trabajo en progreso). El objetivo principal de la compilación C es unir BitMagic con otros lenguajes de programación. La compilación C está en el subdirectorio "lang-maps".
La compilación C crea versiones de la compilación BitMagic para SSE y AVX y agrega identificación de CPU, por lo que el sistema de nivel superior puede admitir la identificación dinámica de CPU y el envío de código.
La compilación de C usa el compilador de C++, pero no usa RTTI, excepciones (simuladas con salto de longitud) ni administración de memoria de C++, por lo que es neutral en el lenguaje C++, sin dependencias de tiempo de ejecución. Los algoritmos y el comportamiento se comparten entre C y C++.
Estado actual de desarrollo:
El soporte de Python está pendiente y necesitamos ayuda aquí. Si está entusiasmado con Python y cree que puede ayudar, comuníquese con: anatoliy.kuznetsov @ yahoo dot com
La biblioteca BitMagic requiere CXX-11. Utiliza semántica de movimiento, noexept, listas de inicializadores, subprocesos. La próxima versión pública utilizará CXX-17 (constexpr ifs, etc.).
###Ajustes y optimizaciones:
Todos los parámetros de ajuste fino de BitMagic están controlados por las definiciones del preprocesador (y las claves del compilador específicas del arco de destino para la generación de código).
| #definir | Descripción | Ancho |
|---|---|---|
| BMSSE2OPT | Optimizaciones del código SSE2 | 128 bits |
| BMSSE42OPT | Optimizaciones de código SSE4.2 más POPCNT, BSF, etc. | 128 bits |
| BMAVX2OPT | Optimizaciones AVX2, POPCNT, LZCNT, BMI1, BMI2 | 256 bits |
| BMAVX512OPT | AVX-512, (experimental) | 512 bits |
| BMWASMSIMDOPT | Optimizaciones SIMD de WebAssembly (a través de SSE4.2) | 128 bits |
| DBMNEONOPT | Optimizaciones de Arm Neon SIMD (a través de traducción SSE2) | 128 bits |
####Limitaciones:
Las definiciones de optimización SIMD son mutuamente excluyentes, NO puede tener BMSSE42OPT y BMAVX2OPT al mismo tiempo. Elige sólo uno.
La biblioteca BM NO admite múltiples rutas de código ni identificación de CPU en tiempo de ejecución. Debe compilar específicamente para su sistema de destino o utilizar la compilación portátil predeterminada.
####Ejemplos:
Los ejemplos y pruebas de BitMagic se pueden crear con GCC usando la configuración de la línea cmd:
make BMOPTFLAGS=-DBMAVX2OPT rebuild
o
make BMOPTFLAGS=-DBMSSE42OPT rebuild
Aplica automáticamente el conjunto correcto de indicadores del compilador (GCC) para la compilación de destino.
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
O
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
La biblioteca BM admite la palabra clave "restringir", algunos compiladores (por ejemplo, Intel C++) generan un mejor código (almacenamiento de carga fuera de orden) cuando la palabra clave restringir es útil. Esta opción está desactivada de forma predeterminada ya que la mayoría de los compiladores de C++ no la admiten. Para activarlo, #defina BM_HASRESTRICT en su proyecto. Algunos compiladores utilizan la palabra clave "__restrict" para este propósito. Para corregirlo, defina la macro BMRESTRICT para corregir la palabra clave.
Si desea utilizar la biblioteca BM en un "proyecto sin STL" (como sistemas integrados), defina BM_NO_STL.
Esta regla solo se aplica a los métodos principales bm::bvector<>. Los algoritmos auxiliares, ejemplos, etc. seguirían usando STL.
Síguenos en twitter: https://twitter.com/bitmagicio
¡Gracias por usar la biblioteca BitMagic!
correo electrónico: [email protected]
Sitio WEB: http://bitmagic.io
GitHub: https://github.com/tlk00/BitMagic
