BitMagic v.9.1.0

This update to the BitMagic library adds the sparse_vector_float container, designed to store both sparse and dense floating-point data in a succinct format that reduces memory overhead, with additional compression when serialized to disk. Alongside this new container, the update adds support for serialization and deserialization of this new container, as well as optimized search capabilities integrated directly into the existing sparse_vector_scanner class. Some use cases for a sparse_vector_float include storing geospatial data such as elevations or temperatures, machine learning, sparse graphs, and storing time-series such as financial data.

New Classes:

In this update the following classes have been added

• sparse_vector_float
• sparse_vector_float_serial_layout
• sparse_vector_float_serializer
• sparse_vector_float_deserializer
  These are wrapper classes for the sparse vector class type, and allow for the storage of 32-bit floats.

As floats do not have an unsigned version, they cannot be stored in a normal sparse vector. The sparse_vector_float series of classes allows for the storage of these floats by splitting received floats into their sign, exponent, and mantissa. The exponent and mantissa are stored in two sparse vectors, the type of which is given by the user, and the sign is stored in a bit vector of the same type as the given sparse vectors.

This allows for the storage of floats in a single sparse vector object, and instead of the user having to split a float and store it in 3 separate containers themselves, they can instead store it in a single sparse_vector_float object and have operations on that sparse_vector_float affect all 3 inner containers simultaneously.

The sparse_vector_float_serial_layout, sparse_vector_float_serializer, and the sparse_vector_float_deserializer are used for serialization and deserialization of sparse_vector_float objects, and are largely used in the same way as the sparse vector version of the classes.

New Functions:

The following functions have been added:
sparse_vector_float_serialize()
sparse_vector_float_deserialize()
These functions are the same as their sparse vector counterparts but use the sparse_vector_float serializer/deserializer’s

New Methods:

The following methods have been added:

• sparse_vector_scanner::find_gt_float
• sparse_vector_scanner::find_lt_float
• sparse_vector_scanner::find_ge_float
• sparse_vector_scanner::find_le_float
• sparse_vector_scanner::find_range_float

These methods allow for a scanner to find the greater than, less than, greater than or equal to, less than or equal to, and a specific range of values in a sparse_vector_float object, allowing easier parsing of sparse_vector_floats.

New Samples:

The following samples have been created on how to use the sparse_vector_float class

• svfsample01 - Basic operations(import, set, get, optimize, etc.)
• svfsample02 - Serialization and Const iterator operations
• svfsample03 - Range methods(clear, compare, equal, join, merge)
• svfsample04 - Extracting from a sparse_vector_float(decode, extract, gather, extract_range)

Comparing a std::vector to sparse_vector_float objects:

Memory Size Comparison between
Calculated using Bitmagic’s calc_stat::memory_used

• std::vector
• SVF - sparse_vector_float using a sparse_vector
  • With Linear data going from -N/2 * .00123 to N/2 * .00123
  • With Random data going from -1,000,000 to 1,000,000
• RSC SVF - sparse_vector_float using an rsc_sparse_vector with 35% NULL’s
  • With Linear data going from -N/2 * .00123 to N/2 * .00123
  • With Random data going from -1,000,000 to 1,000,000

Container	100,000 Elements(bytes)	1,000,000 Elements(bytes)	10,000,000 Elements(bytes)
std::vector	400,024	4,000,024	40,000,024
SVF Linear	338,176	1,819,648	12,703,488
SVF Random	539,232	3,870,464	36,430,080
RSC SVF Linear	266,256	1,558,288	11,536,280
RSC SVF Random	351,344	2,765,584	26,786,576

Serialized Memory Size Comparison

Container	100,000 Elements(bytes)	1,000,000 Elements(bytes)	10,000,000 Elements(bytes)
std::vector	400,024	4,000,024	40,000,024
SVF Linear	191,310	956,513	6,890,859
SVF Random	375,352	3,470,964	34,693,378
RSC SVF Linear	149,633	1,166,626	9,122,900
RSC SVF Random	254,964	2,546,823	25,480,286

Search Comparison between Data structures with 10,000,000 elements

• Linear Data
  • Data in Data Structures
    • 10,000,000 linear elements
    • Range of -6150 to 6150 or ( -N/2 * .00123 to N/2 * .00123)
  • Search Info
    • 1000 searches performed on 1000 ranges
    • Ranges are 2 random numbers from -6150 to 6150
  • Legend
    • Linearly search on an std::vector
    • sparse_vector_scanner on a sparse_vector_float using a sparse_vector
    • Using the Const Iterator of a sparse_vector_float using a sparse_vector
    • sparse_vector_scanner on a sparse_vector_float using an rsc_sparse_vector
    • Using the Const Iterator of a sparse_vector_float using an rsc_sparse_vector
• Random data
  • Data in Data structures
    • 10,000,000 random numbers
    • Range of -1,000,000 to 1,000,000
  • Search Info
    • 1000 searches performed on 1000 ranges
    • Ranges are 2 random numbers from -1,000,000 to 1,000,000
  • Legend
    • Same as Linear Data

Query Method / Dataset	Linear Data(sec)	Random Data(sec)
std::vector	18.6000 s	41.1800 s
sparse_vector_scanner	0.8433 s	5.1880 s
Const Iterator	112.8000 s	239.2800 s
std::vector(35% NaN)	24.0400 s	32.9500 s
RSC sparse_vector_scanner(35% Null)	106.6200 s	230.5200 s
RSC Const Iterator(35% Null)	172.3200 s	268.3200 s

Fixes:

General:

• Fixed the use of chrono_taker<> in the perf.cpp and t.cpp as it was used without the <>, causing errors.
• Fixed compilation warnings in bmaggregator.h, bmblocks.h, bmfunc.h, bmserial.h, perf.cpp, and t.cpp
• Updated CMakeLists.txt to not use -march=native by default for non-x86 builds, and to instead use -O2

sparse_vector_scanner

• Fixed an error where in the find_gt_horizontal() method a duplicate of a given bvector was created, but if the given bvector was read only it would copy the read only, causing an error. Changed how it was copying the bvector to using bit_or()

t.cpp:

• Fixed an error in the TestCompressSparseVector() test where in the Compressed load() stress test cmp 3 was testing csv2 instead of csv1
• Fixed an error where in DetailedCheckCompressedDecode() where an assert would fail if given an empty rsc_sparse_vector, despite some tests being an empty rsc_sparse_vector

BitMagic v.8.0.1

1. Enhanced Bit-Vector Serialization & Compression

Introduced a new, more efficient serialization format for bit-vectors, significantly improving compression.
Note: This change is not backward compatible, but forward compatibility is maintained—new versions can read and deserialize older bit-vectors.
Optimized Succinct Vectors Serialization
Succinct vectors serialization now benefits from the improved bit-vector compression, reducing storage and improving performance.
2.Improved Error Handling & Robustness

Serialization error handling has been improved, with better exception-based reporting for corrupted or malformed serialized objects.
Previously, deserialization failures could lead to crashes—now, errors are properly detected and reported (via exceptions).
Code Cleanup & Static Analysis Fixes
3.Addressed compiler warnings and refined code based on static analysis, improving maintainability and stability.

BitMagic v.7.13.4

1. Improved str_sparse_vector<>::clear_all()  - added parameter to reset remap matrix by default, which is safer (less surprises for the user). Method signature changed, this may cause some minor incompatibility issues.



2. New method bm::sparse_vector<>::get_unsigned_bits() - to extract partial value (only a few bits)

3. Optimizations of bm::bvector<>::inc() (minor)



4. Added bm::bvector<>::swap() - method to swap two bit positions - basis for implementing sort or shuffle algorithms on compressive memory structures

5. Added bm::sparse_vector<>::swap() - to help implement swap of shuffle algorithms on succinct vectors

6. Added new example strsvsample09 to showcase sort algorithm in compressive memory space.

7. Optimization for bit-vector deserialization algorithm to avoid frequent reallocations of top-level memory table. Especially important for large 48/64-bit mode bit-vectors.

8. optimizations of bm::bvector<>::import(), implemented memory reservation (important for large 48/64-bit imports).

9. Fixed bug with collaborative XOR compression, causing debug level asserts and inability to decode compressed vectors.

Various code-cleanups to reduce warnings in different compilers, improves MSVC compatibility.

10. Fixed bug in incorrect binary search in compressive string vector (bm::sparse_vector_scanner<>)

11. Improved build system to better support Apple M2

BitMagic release v7.12.3

Release Notes: BitMagic 7.12.3

Bug fixes:

1. Fixed bugs related to handling of immutable bit-vectors
2. Fixed bug in Rank-Select index assisted bvector<>::count_to()

New features, optinmizations, improvements:

1. Implemented sparse vector read-only deserialization.
   bm::sparse_vector_deserializer<>::set_finalization(bm::finalization::READONLY);
   https://github.com/tlk00/BitMagic/tree/master/samples/svsample02

2. Optimizations: for bvector<>::test( ) membership testing (and changing)
   for GAP compressed blocks. BM implementation uses binary search (ONlogN) for this operation
   with SIMD optimizations (hybrid binary search). The algorithms around this problem were
   reviewed to minimize number of comparisons, better use L1 cache and improve speed.
   Performance gain of 10-20% measured on synthetic tests.

3.Optimizations: bm::aggregator<> SIMD and general purpose optimizations
of aggregate AND-SUB operations. Group AND-SUB operation is at the core of succinct vector
searches, inspired by Bloom filters but uses "data as an index approach"
(works well for bit-sliced succinct vectors).
Latest version adds various optimizations related to SIMD, parallel memory reads,
algorithmically better detection of search reductions.

4. Optimizations: bm::sparse_vector_scanner<>::bfind_eq_str() -
   binary search in compressive memory vectors of strings.
   Implemented a new index for approximating the search using binary index.
   BM allows to setup a binding between bm::sparse_vector_scanner and a sperse
vector itself, defining the fraction of elements to keep decompressed for the fast approximated
search. Maintenance of a index fractionally reduces a memory efficiency, but significantly
improves the search speed.
New example was added to the code repo to illustrate the new API.
https://github.com/tlk00/BitMagic/tree/master/samples/strsvsample08.

Release notes:
http://bitmagic.io/bm-7.12.3.html

BitMagic release v7.11.2

Bug fixes:

1. Fixed bug in rank-select index assisted compute of rank (affecting compressive sparse vector)
2. Fixed bug with potential misaligned reads in SIMD mode
3. Fixed bug in deserialization of empty sparse vector

New features and improvements:

1. Improved read-only mode for bm::bvector<> to allocate one contiguos memory block for the arena to
   better reduce memory fragmentation. This improvement also affects read-only mode memory allocation
   for bit-vector based succinct vectors.

2. succinct vector for strings (bm::str_sparse_vector) remap() method improved to use less memory
   in the process

3. Added bit-vector immutability methods into C-language mappings

Release notes:
http://bitmagic.io/bm-7.11.2.html

BitMagic release v7.10.3

Release Notes: BitMagic 7.10.3

Bug fixes:

1. Fixed bug in serialization/deserialization of empty null-able bm::str_sparse_vector<> (could case crashes and assertion faults)
2. Fixed corner case bug in XOR compression of empty succinct vectors
3. C language interface (libbm) – fixed incorrect handling of CPU SIMD capabilities (AVX2)

New features and improvements:

1. Implemented immutable (read-only) bit-vectors.
   New version of BitMagic library first introduces an API for making vectors immutable.
   Immutable mode has two advantages: better memory footprint and faster analytical operations.

Mutable writable vectors in BitMagic are implemented using block allocation strategy (that is why sparse vectors). To facilitate edits in compressive mode vectors do space reservations to avoid frequent re-allocations which otherwise be a performance killer in multi-threaded scenarios. Such memory reservations is obviously not free and goes against the idea of memory succinct operations.
New version adds APIs to freeze vectors to read-only mode, which assembles all blocks together into one memory arena (heap defragmentation, which can reduce memory footprint for your program) and drops any reservations made for editing (reduce RAM consumption).
An additional extra benefit is that immutable mode now uses contiguous arena of memory, giving CPU a better chance for cache memory reuse and more efficient hardware prefetch. Performance benchmarking shows that this factor can give 1 to 5 percent performance improvements on data-science operations like binary distance functions (Dice). The performance advantage is not super-significant, but it is a nice bonus for applications which can use and benefit from read-only mode.
Special note: current implementation still turns read-write mode back on deserialization of vectors because current serialization format remains without changes for this release.
https://github.com/tlk00/BitMagic/tree/master/samples/bvsample26

2. New method for random access read from the Rank-Select succinct vector bm::rsc_sparse_vector<>::gather() – new method can give you 10% and better performance improvement comparing to naïve random access. Actual performance improvement depends on the access pattern and data pattern.
   https://github.com/tlk00/BitMagic/tree/master/samples/rscsample06

3. Improved performance of Rank-Select index. The most notisable performance improvement is for Arm and configurations without efficient SIMD acceleration. SSE4.2 and AVX2 builds show minor improvement or parity with the previous version

4. Improved “noexcept” declarations in the code (improved WASM target performance)

5. Improved bm::bvector<>insert()/shift_right() to avoid unnecessary deoptimization of compressed blocks

Release notes:
http://bitmagic.io/bm-7.10.3.html

BitMagic release v7.9.3

Release Notes: BitMagic 7.9.3

1. Improved bm::sparse_vector_scanner<>::pipeline::set_search_mask()
   with ability to specify AND mask. Search mask is very useful optimization tool
   for cases when search can be limited/prunned by a prior knoweledge or a prior search on a more selective index.
   SQL example: Field1 = 10 AND Field2 IN ('value1', 'value2')
   One side of an SQL expression Field1 = 10 as a bit-vector can now be fed into a
   pipeline index-free search scanner to potentially make search significantly faster.
   Example: https://github.com/tlk00/BitMagic/tree/master/samples/strsvsample07

2. bm::str_sparse_vector<> - fixed a few bugs related to processing of succinct vectors with NULL values.

3. New API bm::str_sparse_vector<>::compare() - optimized comparison for construction of sort
   method taking two indexes of elements to perform comparison.

4. Optimizations for SSE2, SSE4.2 code for logical set subtraction (AND NOT).

5. Minor optimizations of bm::aggregator<> - collection of algorithms for logical expression search.

6. All succinct vectors: Implemented new API functions for bulk
   set_null() and clear() of vector elements.
   New methods take bm::bvector<> as an input to set/clear marked elements.
   New operations are significantly faster than random access element assignments.
   https://github.com/tlk00/BitMagic/tree/master/samples/strsvsample04

7. All succinct vectors: New method try_get() for conditional access
   to not NULL elements. New method is somewhat faster than separate is_null()/get() calls.
   https://github.com/tlk00/BitMagic/tree/master/samples/rscsample01

8. Integer succinct vectors: optimizations of random element access (10% gain in some cases).

9. New example on how to use algorithms for bit-vector traversal: bm::for_each_bit(),
   bm::for_each_bit_range(), bm::visit_each_bit(), bm::visit_each_bit_range().
   https://github.com/tlk00/BitMagic/tree/master/samples/bvsample25

10. Minor optimizations for Rank-Select index construction and search.

Release notes:
http://bitmagic.io/bm-7.9.3.html

BitMagic release v7.8.0

Release Notes: BitMagic 7.8.0

1. Implemented complete set of index-free search methods on compressive memory vectors with
   bm::sparse_vector_scanner<>: GT, GE, LT, LE, RANGE fast search functions.
   New search logic uses fast bit-vector operations without de-compressing the succinct models
   to solve search logic problems fast and without external indexes overhead
   New functionality is important for both search systems and columnar databases.

2. New example on how to use the new scanner search functions:
   https://github.com/tlk00/BitMagic/tree/master/samples/svsample10

3. SSE2 improvements: added more SSE2 kernels and optimizations.

4. First version of ARM NEON optizations (as SSE2 to NEON translation).
   Tested on R-Pi, it adds up to 25% performance gain in some logic search benchmarks.

Release notes:
http://bitmagic.io/bm-7.8.0.html

BitMagic release v7.7.7

1.Fixed a bug in bm::bvector<>::merge() - destructive OR operation, when arg vectors is empty and uninitialized
function did not implement a correct logical OR (serious issue!)

2.Implemented a new logical idiom bvector<>::bit_or_and()
as
C := C OR (A AND B)
Fused OR+AND is an often used idiom in query systems, implementations of SQL and operation on memory compressed
structures. Fused implementation uses multiple optimizations and does not require a temporary vector, avoiding
allocations and memory copy.
New idiom is 2x times faster in synthetic tests of uncompressed bit-vectors.

3. bm::aggregator::pipeline now implements a fast mode to run multiple AND-SUB queries with an optional
   aggregation of results via an OR function.

Aggregator logical pipeline implements fast idioms used in BitMagic succinct vectors to implement
sparse/dense vector search or query requests.

bm::aggregator::pipeline uses cache memory bandwidth and optimizations to implement
series of AND-SUB as: (bv1 AND bv2 AND bv3…) AND NOT (bvS1 OR bvS2 OR … ) with an optional final
accumulation of multiple search requests using OR logical function.

Aggregator pipeline is used internally in BitMagic to implement succinct bit-sliced vector searches
(bm::scanner<>) 2-3 times faster. The speed achieved in 7.7.7 release demonstrates performance levels
otherwise specific to systems using indexes.
Fast index-free searches can significantly reduce both the systems footprint (RAM and disk) and
complexity of implementation.

4. Algebra of Sets tutorial (bvsetalgebra.cpp) example reworked to illustrate use of new fused OR-AND
   operations and aggregator pipeline (AND-SUB-OR).

https://github.com/tlk00/BitMagic/tree/master/samples/bvsetalgebra

5. bm:scanner::pipeline implements fast multiple string search in memory compressed string vector with an
   optional OR stage (under the hood uses bm::aggregator<>).
   Latest version makes a change in semantics to use compile-time options to configure pipeline,
   new options result in faster code due to compile-time specialization (C++-17 is very useful there).

OR stage helps to implement a SQL idiom: Field1 IN (value1, value2… valueN) for cases where list of
search values is in the tens of thousands or more or Field1 IN (SELECT FieldN FROM…) idiom using
memory compressed index-free search.

New version adds important optimizations of the algorithms to automatically tune-up for a typical
L2 cache size, but also adds a manual override (batch_size) to tune and tweak the system for a specific
HW configuration and data distribution statistics. The auto-tune topic definitely deserves more optimization
in the future.

New usage modes and benchmarks are available at:
https://github.com/tlk00/BitMagic/tree/master/samples/strsvsample07

Release notes:
http://bitmagic.io/bm-7.7.7.html

BitMagic release v7.6.0

• fixed regression bug from 7.5.0 in dynamic matrix allocation algorithms of succinct vectors

• bm::aggregator<> reworked to support new pipeline mode for AND-MINUS ("all this but not that" queries)
  aggregation, using L1/L2 cache and algorithmic optimizations to run thousands of coordinated aggregations times
  faster than it was possible in previous versions

• bm::scanner<> implements string new string search method for bulk search with bm::aggregator<>::pipeline under the hood. New bm::scanner<>::pipeline can run multiple string searches in unordered succinct string vectors times faster.
  It also implements new search methods which can be used to run massive queries and construct results
  (inverted list bit-vectors) or run stat analysis computing results population count without materializing the vectors
  (effectively histogram construction).

-New example: strsvsample07
added to illustrate use of fast scanner and scanner pipeline 3x times, with synthetic benchmarks showing 3x better
performance for bulk search cases.

• Parallel compute engine and thread pools reworked to use Modern C++ approach based on lambdas rather than function pointers. New development lays the internal foundation for BitMagic parallel algorithms to unfold its potential
  on multi-threaded systems.

Release notes:
http://bitmagic.io/bm-7.6.0.html