BitMagic Library / News: Recent posts

1. Implemented const iterator for bm::sparse_vector<>
2. Implemented back inserter for bm::sparse_vector<>
3. Implemented new search algorithm utility class (bm::sparse_vector_scanner) for unordered sets stored in bm::sparse_vector<>
4. Performance optimizations of common logical operations, construction and destruction of bm::bvector<>
5. New bit-vector method to find relative bit position for the specified rank bm::bvector<>::find_rank(...)
6. SIMD performance optimizations (minor) for AVX2 and SSE4.2
7. Improved test code coverage, fixed a few rare bugs
8. Improved build environment, cmake files and settings

9. define BMCOUNTOPT deprecated (potential thread safety issues)

10. Added a few new examples

1. Performance optimizations (minor) for SSE4.2 and AVX2.
2. Improved C-library (language mapping) to support CPU identification.
3. Improved C-library to buils DLLs for various SIMD targets.
4. bm::sparse_vector - optimizations to set/get single elements without full decode.
5. bm::sparse_vector added support of NULL (unassigned) values for memory efficient construction of columnar databases.
6. New algorithm: memory efficient sparse_vector<> algorithm for Theory of Groups Image operation (set to set transformation / remapping / etc). (svsample05.cpp)
7. Reworked some memory management for better compiler compatibility, cleaner code, less warnings.
8. bm::bvector<> - added methods to find index of last set bit to determine dynamic range. (sample15.cpp)
9. bm::bvector<>, bm::sparse_vector<> - added method inc() for binary increment of an element.
10. New example: implementation of counting sort / histogram build using sparse_vector<>, performance and memory benchmarks. (xsample02.cpp)... read more

1. BitMagic Library now licensed under Apache 2.0 license.
2. Improved performance of enumerators.
3. Added new algorithms to traverse bit-vector. Works a few times faster than enumerator.
4. Improved memory management of serializations, fixed potential security vulnerabilities (buffer overrun).
   5.New AVX2 and SSE4.2 optimizations.
5. Improved performance of sparse_vector<> extraction algorithms.

6. Added new examples for some common use cases for bit-vectors.
7. Continued improvement of BitMagic C library (libbm).
8. Improved build environment for cmake to make various SIMD configurations easier.

• added AVX2 optimization option (#define BMAVX2OPT)
• improved SIMD vectorization computational kernels for SSE2, SSE4.2
• faster testing for bits in compressed vectors
• bit-vector enumerator (bvector<>::enumerator) added random positioning, can now go to any arbitrary start point and traverse bits from it
• added bvector<>::count_to() to efficiently work with range bit counting and bit-vector based prefix sums
• new samples
• optimizations to bit counting, sparse vector extraction, bit testing, etc

• improved C++11 compatibility, added move constructors, assignmnets.
• improved performance of bm::sparse_vector<> container, faster import and export
• added libbm C library based on top of C++, but can be compiled without exceptions, RTTI, STL and C++ runtime dependency

- Fixed logical bug in deserialization
- Performance optimization count_and(), bvector destruction, etc
- Simplified template arguments for bvector<>

Release 3.6.4 significantly improves performance of deserialization.

Release 3.6.3 fixes critical bug for 64-bit mode and improves performance of bit-counting dependent operations.

New features: optimizations for 64-bit SSE 4.2, new algorithm for random subset generation, configuration for MacOS-X

BitMagic Library v.3.6.1 features optimized de-compression (Gamma Encoding). Added support for SSE 4.2 (Intel Nehalem).

BitMagic Library v.3.6.0 features improved bit-vector serialization
with bit-set compression. New serialization adds Gamma encoding
on top of D-Gap compression. New serialization should significantly
reduce IO for databases and search systems using serialized bit-vectors.

BitMagic Library version 3.5.4: this release features SSE2 and GCC compatibility. Now all SSE2 optimization options are available for Intel C++, GCC and MSVC.

BitMagic Library version 3.5.3:
- improved performance of AND logical operations and derived
DOT product algorithms (cound_and(), any_and())
- improved compression of serialized bvectors
(serialization format remains backward compatible)
- fixed compatibility issues with MSVC8 and Intel C++ 11 .1
(SSE2 optimization mode)
- improved automatic variables disambiguation using 'restrict'

Please see BitMagic Library BLOG at
http://bvector.blogspot.com/

BitMagic library v.3.5.2 improves size and performance of serialization. Short bit-vectors are taking less space.
New algorithm for bit iteration improves performance by 10-20% (enumerator). Few minor bug fixes.

This release fixes several coding bugs (some of them should be considered important). Code has been cleaned up in many places, eliminating some compilation warnings. Improved compatibility with WIN64 platform.
Bitset serialization improved to work faster and in many cases compress bitsets better.

BitMagic Librarry Release 3.3.0 fixes several compilation
incompatibilities. The major fix is GCC 3.4. Incorporated several improvements contributed by Apple Mac users.

API change: serialization functions are now
separated into an separate group of utilities (see bmserial.h)

BitMagic - compressed bitvectors library gets new features:

- New function bvector<>::set_range, performance optimized when you need to set or clear many bits in one call

- New set algorithms (bmalgo.h)
count_intervals - compute number of bit intervals (GAPs) in bitvector
combine_and, combine_or, combine_xor, combine_sub - performance optized recombination of bitvector and an arbitrary set sequence (iterator) (works well with STL containers and other iterable containers)

- Made bvector<> architecture more open.
Some internal access functions now are public.
It makes possible to create external functions and algorithms based on bvector, but not part of it. Over time bvector<> template became an example of a swiss-army knife class, slowing down compilation and hard to supportand and understand. This design change will make possible migration of some methods (like serialize/deserialize) into a separate place.... read more

More information on memory bandwidth issues and bitset distances (on example of Hamming distance).
http://bmagic.sourceforge.net/bmsse2opt.html

Distance optimization is work in progress for the next version of the BM library.

BitMagic library of compressed bitsets releases v. 3.1.4.
After a serious testing several critical bugs were found and fixed. It's strongly suggested to start using this new version.
Also we made one important change to the code structure. All platform dependent SSE2 code now migrated into an optional header. This change is supposed to facilitate creation of new modules for other SIMD architectures(3DNow!, Altivec, etc). Developers with experience in SIMD programming are very welcome to paticipate in this activity.

Changes in version 3.1.3

- Improved compatibility between bvector<> and STL algorithms and containers. enumerator can now be used as an argument of std::set_intersection, etc. Added inserter class to copy data from containers to bvector. See sample8.cpp for more details

- New function: bvector<>::count_range - counts number of 1 bits in a given range of bits.

- New function: bvector<>::set_gap_levels - to change possible GAP sizes after bvector construction... read more

BitMagic is a C++ library implementing dynamic bitvectors with several types of on-the-fly, adaptive compression. Designed for use in databases, search systems, scientific projects. Version 3.1.2 primarily focuses on memory consumption issues. Additional parameters added to save memory in situations when thousands of bitsets are used.
(see http://bmagic.sourceforge.net/memsave.html\); several build environment problems were fixed; added support file for AIX; improved performance of logical operations.

Compressed bitsets C++ template library v. 3.1.1 released. This version implements optimization for SSE2 arithmetic (Pentium 4). Optimization principles are described in accompanying article (http://bmagic.sourceforge.net/bmsse2opt.html).

- performance optimization of bvector<>::enumerator;
- lexicographical comparison of bitsets
reimplemented for better performance;
- additional optimization of bitcounting procedures to employ out-of-order execution on some processors;
- added several functions making bvector<> look more like standard std::bitset;
- fixed several minor bugs and problems