BitMagic
v.7.13.4
BitMagic foi criado como um kit de ferramentas de Álgebra de Conjuntos para Recuperação de Informações, mas atualmente evoluiu para uma biblioteca de componentes de Ciência de Dados mais geral para estruturas compactas de memória e algoritmos em vetores de dados sucintos. BitMagic implementa vetores de bits compactados e contêineres (vetores) com base em ideias de transformação de fatiamento de bits, compactação Rank-Select e computação lógica em modelos de memória compactada.
Todos os contêineres sucintos BitMagic são serializáveis (com compactação usando codificação interpolativa binária de última geração) para armazenamento eficiente e transferência de rede. Todos os contêineres podem ser pesquisados rapidamente em formato compactado.
BitMagic oferece conjuntos de métodos e ferramentas para arquitetar seus aplicativos para usar técnicas de HPC para economizar memória em tempo real (assim, ser capaz de acomodar mais dados em uma unidade de computação), melhorar padrões de armazenamento e tráfego ao armazenar vetores e modelos de dados em arquivos ou objetos armazenamentos (SQL ou noSQL), otimizam a largura de banda dos sistemas, desde caches de CPU de baixo nível até troca de rede e armazenamento.
BitMagic facilita duas grandes classes de cenários:
BitMagic foi usado como bloco de construção para:
Visite nossas notas de casos de uso: http://bitmagic.io/use-case.html
A biblioteca BitMagic é uma biblioteca de alto desempenho, implementando otimizações para diversas plataformas e alvos de construção:
BitMagic usa um design vetorizado de dados paralelos com o objetivo não apenas de fornecer o melhor desempenho de thread único, mas também de facilitar a computação altamente paralela em sistemas com vários núcleos.
BitMagic usa um conjunto de algoritmos de compressão, filtros e transformações para reduzir o consumo de memória, custos de armazenamento e transferência de dados de rede. http://bitmagic.io/design.html
Por favor, visite nossas notas técnicas: http://bitmagic.io/articles.html
BitMagic suporta a reinterpretação de vetores de bits como coleções de intervalos não sobrepostos de 1s flanqueados por 0s (por exemplo: 011110110). Funções de conjunto regulares fornecem operações de intervalo de interseção / união de conjunto, implementam iterador de intervalo e pesquisas por limites de intervalo. Intervalos e intervalos têm grande utilidade em bioinformática, porque os dados genômicos são frequentemente anotados como intervalos de coordenadas. BitMagic oferece blocos de construção para operações eficientes em intervalos codificados como vetores de bits (encontre o início/fim do intervalo, verifique se o intervalo é um inetrval, itere intervalos
BitMagic implementa operações lógicas para lógica de 3 valores de Verdadeiro/Falso/Desconhecido (também lógica trinária, trivalente, ternária) em representação compacta de dois vetores de bits, suportando operações Invert, AND, OR seguindo as definições de Kleene. https://github.com/tlk00/BitMagic/tree/master/samples/bv3vlogic
BitMagic usa o conceito de serialização-desserialização em dois estágios. O foco está na desserialização rápida. BitMagic implementa API para desserialização rápida de intervalo vetorial e desserialização de coleta de BLOBs compactados. O recurso definitivo do BitMagic é a capacidade de trabalhar com dados compactados.
Este é o principal estado operacional da RAM, onde os vetores são mantidos em formato compacto de memória. Sucinto NÃO é uma compressão. É possível acessar elementos aleatórios em contêineres, decodificar blocos, iterar vetores, fazer atualizações, executar algoritmos de busca. O Stage One oferece uso transparente, seus vetores se parecem muito com STL. Sucinto é uma memória compacta, mas não totalmente compactada.
BitMagic pode serializar todos os contêineres e vetores com compactação adicional baseada em blocos de heurísticas e codecs. As técnicas de codificação robustas são: Codificação Interpolativa Binária (BIC) e Elias Gamma.
Os contêineres BitMagic são chamados de vetores "esparsos", mas na verdade seus esquemas de compactação funcionam bem para dados esparsos e densos.
BitMagic é testado no conjunto de benchmark Gov2 de listas invertidas e número de conjuntos de dados proprietários. http://bitmagic.io/bm5-cmpr.html
A desserialização sempre volta ao Estágio Um, então os dados não são completamente decodificados, mas sim
sucinto na RAM. Nosso objetivo aqui é reduzir o consumo de memória do aplicativo e melhorar a latência de desserialização. Algoritmos de descompressão suportam a desserialização de intervalos arbitrários ou até mesmo coletam a desserialização de elementos.
BitMagic suporta vetores sucintos (compactos de memória) baseados em transformação de transposição de bits
também conhecida como compactação de plano de bits (BPC) (também conhecida como fatiamento de bits) mais compactação Rank-Select. Vetores sucintos BitMagic rotulados de maneira enganosa como "esparsos", mas funcionam perfeitamente para vetores densos.
A transposição de bits resolve dois propósitos: liberar planícies de bits não utilizadas e isolar a regularidade e a entropia em vetores de bits separados (esparsos). A compactação em planos de bits oferece desempenho de memória superior e pesquisa rápida. Um dos objetivos do projeto é realizar pesquisas sem índice em vectros sucintos usando operações lógicas vetorizadas rápidas.
Os vetores sucintos BitMagic são pesquisáveis sem índice em formato compactado de memória. É rápido!
A implementação sucinta de transposição de bits funciona bem para vetores inteiros (com ou sem sinal), bem como para vetores de string. Ele rivaliza com outros esquemas sucintos, como árvores de prefixos. Vetores sucintos podem ser classificados e não classificados. A ideia aqui é semelhante à do Apache Arrow-Parquet, mas vai além com a compactação de plano de bits e o uso extensivo da compactação Rank-Select acelerada.
BitMagic suporta evolução de serialização (protocolo) - se o formato de serialização mudar, os dados antigos salvos permanecerão legíveis pelo novo código. O código antigo NÃO será capaz de ler novos BLOBs. BitMagic altera o número da versão principal quando o formato de serialização muda.
BitMagic implementa chamadas de perfil de memória para todos os vetores. Qualquer vetor pode ser amostrado quanto ao consumo de memória para que o sistema de nível superior possa adaptar o gerenciamento de memória com base no perfil de memória de tempo de execução. O caso de uso típico é cache de memória de objetos com compactação em RAM e depois despejo para disco com base no consumo e custos de recursos (equilíbrio dinâmico de demanda e oferta).
Sim! BitMagic suporta 64 bits, pode ser usado com espaço de endereço de 32 bits (menos sobrecarga) ou espaço de endereço completo de 64 bits. O espaço de endereço de 32 bits é o modo padrão. Os elementos 2 ^ 31-1 devem ser uma boa opção para sistemas de IR e ciência de dados de curto e médio alcance. O modo de endereço de 64 bits está disponível usando #define BM64ADDR ou #include "bm64.h". A implementação atual de 64 bits permite elementos vetoriais 2 ^ 48-1 para sistemas de grande escala.
BitMagic compila e trabalha com WebAssmbly (em script). As versões mais recentes incluem vários ajustes, específicos para a plataforma. Os números de desempenho estão próximos do código nativo sem SIMD (às vezes depois). A linha de compilação de exemplo seria semelhante a:
emcc -std=c++17 -s ALLOW_MEMORY_GROWTH=1 -O2 -s WASM=1 ...
WebAssembly SIMD é compatível, mas não está ativado por padrão. Use: #define BMWASMSIMDOPT para habilitá-lo. Exemplo de script cmd:
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
A implementação atual usa transcompilação SSE4.2 (via intrínsecos), portanto -msse4.2 é necessário.
BitMagic suporta totalmente CPU ARM. Todas as versões são testadas quanto ao estresse com Raspberry Pi 4. BitMagic implementa alguns ajustes algorítmicos e melhorias específicas para ARM (como o uso de instruções LZCNT). Os contêineres sucintos BitMagic podem ser muito úteis em sistemas embarcados para computação de ponta com quantidade limitada de memória disponível.
O suporte Arm Neon SIMD está disponível (via biblioteca SSE2NEON).
BitMagic C++ é uma biblioteca apenas de cabeçalho (fácil de construir e usar em seu projeto) e vem com um conjunto de exemplos. NÃO é aconselhável usar testes como exemplo de código para estudar o uso da biblioteca. Os testes não ilustram os melhores padrões e modelos de uso e muitas vezes são intencionalmente ineficientes.
Documentação e exemplos da API: http://www.bitmagic.io/apis.html
Tutorial para Álgebra de Conjuntos: http://bitmagic.io/set-algebra.html
Casos de uso e notas de aplicação: http://bitmagic.io/use-case.html
Notas técnicas sobre otimização de desempenho: http://bitmagic.io/articles.html
Doxygen: http://bitmagic.io/doxygen/html/modules.html
Apache 2.0.
Importante! Pedimos que você mencione explicitamente o projeto BitMagic em qualquer trabalho derivado ou em nossos materiais publicados. A referência adequada na página do seu produto/projeto é um REQUISITO para usar a Biblioteca BitMagic.
A biblioteca BitMagic presta muita atenção à qualidade do código e à cobertura dos testes.
Como uma biblioteca de blocos de construção, o BitMagic precisa ser estável e compatível para ser útil.
Não confiamos apenas em testes unitários, nossos testes geralmente usam "testes de caos" (também conhecidos como fuzzing), onde os testes de estresse são baseados em conjuntos gerados e aleatórios e operações aleatórias. Construímos e executamos regularmente conjuntos de testes para o modo Release e Debug para várias combinações de otimizações SIMD.
Todas as variantes de compilações de teste levam dias para serem executadas, portanto, NÃO é garantido que o branch master funcional seja perfeito o tempo todo. Para produção, use ramificações de lançamento estáveis do github ou distribuições do SourceForge: https://sourceforge.net/projects/bmagic/files/
O mestre do GitHub aceita solicitações de patch Nossa política de ramificação é que o mestre não pode ser considerado totalmente estável entre os lançamentos. (para estabilidade da produção, use versões de lançamento)
Precisa de ajuda com mapeamentos para Python e outras linguagens (BitMagic possui ligações C)
BitMagic C++ é um pacote de software somente de cabeçalho e você provavelmente pode simplesmente pegar os fontes e colocá-los diretamente em seu projeto. Todas as fontes/cabeçalhos da biblioteca C++ estão no diretório src.
No entanto, se você quiser usar nossos makefiles, você precisa seguir as próximas instruções simples:
Aplique algumas variáveis de ambiente executando bmenv.sh no diretório raiz do projeto:
$ source ./bmenv.sh
(use "." "./bmenv.sh" para aplicar a variável de ambiente raiz)
use GNU make (gmake) para construir a instalação.
$make rebuild
ou (versão DEBUG)
$gmake DEBUG=YES rebuild
O compilador padrão no Unix e CygWin é g++. Se você quiser alterar o padrão, você pode fazer isso em makefile.in (deve ser bem fácil de fazer)
Se você usar a instalação do cygwin, siga as recomendações gerais do Unix. MSVC - solução e projetos estão disponíveis via CMAKE.
Xcode - os arquivos do projeto estão disponíveis via CMAKE.
Biblioteca BitMagic para mapeamentos C e JNI.
A biblioteca BitMagic está disponível para linguagem C (este é um trabalho em andamento). O principal objetivo da construção C é conectar o BitMagic a outras linguagens de programação. A compilação C está no subdiretório "lang-maps".
A compilação C cria versões da compilação BitMagic para SSE e AVX e adiciona identificação de CPU, para que o sistema de nível superior possa suportar identificação dinâmica de CPU e envio de código.
A compilação C usa compilador C++, mas não usa RTTI, exceções (simuladas com salto em distância) e gerenciamento de memória C++, portanto é neutra em linguagem C++, sem dependências de tempo de execução. Algoritmos e comportamento são compartilhados entre C e C++.
Estado atual de desenvolvimento:
O suporte ao Python está pendente e precisamos de ajuda aqui. Se você está entusiasmado com Python e acha que pode ajudar, entre em contato: anatoliy.kuznetsov @ yahoo ponto com
A biblioteca BitMagic requer CXX-11. Ele usa semântica de movimentação, noexept, listas de inicializadores, threads. A próxima versão pública usará CXX-17 (constexpr ifs, etc).
###Ajuste fino e otimizações:
Todos os parâmetros de ajuste fino do BitMagic são controlados pelas definições do pré-processador (e chaves do compilador específicas do arco de destino para geração de código).
| #definir | Descrição | Largura |
|---|---|---|
| BMSSE2OPT | Otimizações de código SSE2 | 128 bits |
| BMSSE42OPT | Otimizações de código SSE4.2 mais POPCNT, BSF, etc. | 128 bits |
| BMAVX2OPT | Otimizações AVX2, POPCNT, LZCNT, IMC1, IMC2 | 256 bits |
| BMAVX512OPT | AVX-512, (experimental) | 512 bits |
| BMWASMSIMDOPT | Otimizações SIMD do WebAssembly (via SSE4.2) | 128 bits |
| DBMNEONOPT | Otimizações Arm Neon SIMD (via tradução SSE2) | 128 bits |
####Limitações:
As definições de otimização SIMD são mutuamente exclusivas, você NÃO pode ter BMSSE42OPT e BMAVX2OPT ao mesmo tempo. Escolha apenas um.
A biblioteca BM NÃO suporta vários caminhos de código e identificação de CPU em tempo de execução. Você deve compilar especificamente para o seu sistema de destino ou usar a compilação portátil padrão.
####Exemplos:
Exemplos e testes BitMagic podem ser construídos com GCC usando configurações de linha cmd:
make BMOPTFLAGS=-DBMAVX2OPT rebuild
ou
make BMOPTFLAGS=-DBMSSE42OPT rebuild
Ele aplica automaticamente o conjunto correto de sinalizadores do compilador (GCC) para a compilação de destino.
CMAKE
cd build
cmake -DBMOPTFLAGS:STRING=BMSSE42OPT ..
make
OU
cmake -DBMOPTFLAGS:STRING=BMAVX2OPT ..
A biblioteca BM suporta a palavra-chave "restrict", alguns compiladores (por exemplo Intel C++) geram código melhor (lojas de carga fora de ordem) quando a palavra-chave restrita está ajudando. Esta opção está desativada por padrão, pois a maioria dos compiladores C++ não a suporta. Para ativá-lo, #define BM_HASRESTRICT em seu projeto. Alguns compiladores usam a palavra-chave "__restrict" para essa finalidade. Para corrigi-lo, defina a macro BMRESTRICT para corrigir a palavra-chave.
Se você quiser usar a biblioteca BM em um "projeto não-STL" (como sistemas embarcados), defina BM_NO_STL.
Esta regra se aplica apenas aos métodos principais bm::bvector<>. Algoritmos auxiliares, exemplos, etc. ainda usariam STL.
Siga-nos no Twitter: https://twitter.com/bitmagicio
Obrigado por usar a biblioteca BitMagic!
e-mail: [email protected]
Site: http://bitmagic.io
GitHub: https://github.com/tlk00/BitMagic
