xsample01.cpp
Go to the documentation of this file.
/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/** \example xsample01.cpp
Demo and a benchmark on memory consumption control and logical operation
*/
/*! \file xsample01.cpp
\brief Example: Example: memory consumption techniques
*/
#include <iostream>
#include <memory>
#include <map>
#include <vector>
#include <chrono>
#include <algorithm>
#include <stdexcept>
using namespace std;
#include "bm.h"
#include "bmalgo.h"
#include "bmtimer.h"
#include "bmserial.h"
#include "bmsparsevec.h"
#include "bmsparsevec_algo.h"
#include "bmsparsevec_serial.h"
#include "bmalgo_similarity.h"
#include "bmdbg.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
// ----------------------------------------------------
// Global parameters and types
// ----------------------------------------------------
// Number of vectors generated for the test
const unsigned index_size = 1000000;
// Dynamic range for constructed sets
const unsigned max_size = 2000000;
// Number of bits per one vector
const unsigned bits_per_vect = 5;
// benchmark operation count
const unsigned benchmark_ops = 1000;
// subset of vectors used as a sample
const unsigned sample_cnt = 250;
// index values to extract
const unsigned result_set_cnt = 200;
// bit-vector type for this example
typedef bm::bvector<> TBVector;
// timing storage for benchmarking
bm::chrono_taker<>::duration_map_type timing_map;
/* BitMagic provides two GAP length tables for situations when we have
standard or embarassingly sparse vectors.
bm::gap_len_table - default standard
bm::gap_len_table_min - option for smaller vectors
Here we define an alternative table for very sparse vectors
*/
template<bool T> struct gap_len_table_sparse
{
static const bm::gap_word_t _len[bm::gap_levels];
};
template<bool T>
const bm::gap_word_t gap_len_table_sparse<T>::_len[bm::gap_levels] =
{ 8, 32, 128, 512 };
// simple bit-vector class factory for the project
//
static
TBVector* construct_bvector()
{
// in this example we plan to keep lots of vectors in memory, thus
// use parameters to minimize memory consumption
//
TBVector* bv =
new TBVector(bm::BM_GAP, // use GAP compressed mode
gap_len_table_sparse<true>::_len, // custom lens for super sparse vectors
max_size // limit the maximum size
);
return bv;
}
// Generic utility to destroy map of pointers
template<typename TM>
void destroy_map(TM& id_map)
{
for (typename TM::iterator it = id_map.begin();
it != id_map.end();
++it)
{
typename TM::mapped_type mp = it->second;
delete mp;
} // for
id_map.clear();
}
// ------------------------------------------------------------------
// Sample data structures
// ------------------------------------------------------------------
// Sample index structure to keep a map of in-memory bit-vectors
//
struct bv_index
{
typedef std::map<unsigned, TBVector*> map_type;
~bv_index()
{
destroy_map(idx_);
}
map_type idx_;
};
// Sample index structure to keep map of in-memory serialized/compressed bit-vectors
//
struct bvs_index
{
typedef std::vector<unsigned char> buffer_type;
typedef std::map<unsigned, buffer_type> map_type;
map_type idx_;
};
// Sample index structure to keep map of in-memory vector<unsigned int>
//
struct vect_index
{
typedef std::vector<unsigned int> buffer_type;
typedef std::map<unsigned, buffer_type> map_type;
map_type idx_;
};
// Sample index structure as in-memory sparse_vector
//
struct sparse_vect_index
{
struct vect_addr
{
unsigned offset;
unsigned size;
};
typedef bm::sparse_vector<unsigned, bm::bvector<> > sparse_vector_type;
typedef std::map<unsigned, vect_addr> map_type;
typedef std::vector< std::pair<uint64_t, unsigned> > delta_sum_map_type;
void get_vector(unsigned id, std::vector<unsigned>& vect) const;
sparse_vector_type sv_storage_;
sparse_vector_type sv_storage1_;
map_type idx_;
};
void sparse_vect_index::get_vector(unsigned id, std::vector<unsigned>& vect) const
{
map_type::const_iterator it = idx_.find(id);
if (it != idx_.end())
{
const sparse_vect_index::vect_addr& vaddr = it->second;
vect.resize(vaddr.size+1);
vect[0] = sv_storage1_.get(id);
for (unsigned j = 1; j < vect.size(); ++j)
{
unsigned a = sv_storage_.get(j + vaddr.offset - 1);
a += (vect[j-1] + 1);
vect[j] = a;
} // for j
}
else
{
vect.resize(0);
}
}
// --------------------------------------------------------------------
// set bits in a vector using various methods picked at random
///
// one method will generate a plato of non-random integers,
// another random integers of near neighbors
// the other adds ints randomly without following any system
//
static
void generate_random_vector(TBVector* bv)
{
unsigned method = rand() % 5; // pick a generation method
if (method == 0) // generate a incremental linear sequence at random location
{
unsigned seed_id = unsigned(rand()) % max_size;
for (unsigned i = seed_id; i < seed_id+bits_per_vect; ++i)
{
if (i >= max_size)
break;
bv->set_bit(i);
} // for i
}
else
if (method == 1) // generate near neighbors
{
unsigned seed_id = unsigned(rand()) % max_size;
unsigned id = seed_id;
for (unsigned i = 0; i < bits_per_vect; ++i)
{
if (id >= max_size)
break;
bv->set_bit(id);
id += (rand() % 10);
if (id >= max_size)
id = unsigned(rand()) % max_size;
} // for i
}
else // generate completely random bits
{
for (unsigned i = 0; i < bits_per_vect; ++i)
{
unsigned id = unsigned(rand()) % max_size;
if (i >= max_size) // paranoiya check
break;
bv->set_bit(id);
} // for i
}
}
// generate map of bit-vectors, each filled with just a few bits
//
static
void generate_bv_index(bv_index& bvi)
{
for (unsigned i = 0; i < index_size; ++i)
{
std::unique_ptr<TBVector> ap(construct_bvector());
generate_random_vector(ap.get());
if (!ap->any()) // integrity check
{
// this should never happen
std::cerr << "Warning. Empty vector generated!" << std::endl;
}
bvi.idx_[i] = ap.release();
}
}
// calculate memory footprint for in memory index
//
static
size_t calc_memory_footprint(const bv_index& bvi)
{
size_t mem_total = 0;
for (bv_index::map_type::const_iterator it = bvi.idx_.begin();
it != bvi.idx_.end();
++it)
{
const TBVector* mp = it->second;
TBVector::statistics st;
mp->calc_stat(&st);
mem_total += st.memory_used;
mem_total += sizeof(void*);
} // for
return mem_total;
}
// convert bit-vector index to bit-vector serialized index
//
static
size_t convert_bv2bvs(const bv_index& bvi, bvs_index& bvs)
{
size_t mem_total = 0;
std::vector<unsigned char> buf; // prepare a temporary buffer
buf.reserve(1024);
// bit-vector serializer
// (keep it out of the serialization loop to minimize buffers re-allocations)
//
bm::serializer<TBVector> bvsr;
bvsr.byte_order_serialization(false);
bvsr.gap_length_serialization(false);
bvsr.set_compression_level(4);
for (bv_index::map_type::const_iterator it = bvi.idx_.begin();
it != bvi.idx_.end();
++it)
{
unsigned id = it->first;
const TBVector* bvp = it->second;
TBVector::statistics st;
bvp->calc_stat(&st); // calculate max. serialized size
buf.resize(st.max_serialize_mem); // prepare the temp buffer
// run serialization, actual serialization size is expacted to be smaller
//
unsigned bvs_size = bvsr.serialize(*bvp, buf.data(), st.max_serialize_mem);
// move from temp serialization buffer to compressed in-memory index
//
bvs_index::buffer_type& vbuf = bvs.idx_[id];
vbuf.resize(bvs_size);
::memcpy(vbuf.data(), buf.data(), bvs_size);
mem_total += bvs_size;
mem_total += sizeof(std::vector<unsigned char>::size_type);
// paranoia check compare source and desirialized vectors
//
#ifdef DEBUG
{
TBVector bv1;
bm::deserialize(bv1, vbuf.data());
if (bv1.compare(*bvp) !=0 )
{
throw std::runtime_error("deserialization check failed");
}
}
#endif
} // for
return mem_total;
}
// convert bit-vector index to vector<usingned>
//
static
size_t convert_bv2vect(const bv_index& bvi, vect_index& vidx)
{
size_t mem_total = 0;
for (bv_index::map_type::const_iterator it = bvi.idx_.begin();
it != bvi.idx_.end();
++it)
{
unsigned id = it->first;
const TBVector* bvp = it->second;
unsigned count = bvp->count(); // population count
vect_index::buffer_type& vect = vidx.idx_[id];
vect.resize(count);
for (TBVector::enumerator en = bvp->first(); en.valid(); ++en)
{
vect.push_back(*en);
}
mem_total +=
sizeof(vect_index::buffer_type::value_type) * vect.size() +
sizeof(vect_index::buffer_type::size_type);
} // for
return mem_total;
}
static
void bv2delta(const TBVector& bv, std::vector<unsigned>& vect)
{
// convert into a plain vector first
//
vect.resize(0);
for (TBVector::enumerator en = bv.first(); en.valid(); ++en)
{
vect.push_back(*en);
}
// convert into delta-vector
//
{
for (size_t k = vect.size()-1; k >= 1; --k)
{
vect[k] -= vect[k-1];
--vect[k];
} // for
}
}
// convert bit-vector index to bm::sparse_vector
//
static
size_t convert_bv2sv(const bv_index& bvi, sparse_vect_index& sv_idx)
{
size_t mem_total = 0;
std::vector<unsigned> vect;
sparse_vect_index::delta_sum_map_type delta_map;
for (bv_index::map_type::const_iterator it = bvi.idx_.begin();
it != bvi.idx_.end();
++it)
{
unsigned id = it->first;
const TBVector* bvp = it->second;
bv2delta(*bvp, vect);
// compute sum of the delta-vector elements add to the sort map
{
uint64_t sum = 0;
for (unsigned k = 1; k < vect.size(); ++k)
{
sum += vect[k];
} // for
delta_map.push_back(std::make_pair(sum, id));
}
} // for
// sort by "enthropy" (sort of)
//
std::sort(delta_map.begin(), delta_map.end());
if (delta_map.size() != bvi.idx_.size()) // paranoia check
{
throw std::runtime_error("delta map size is incorrect");
}
unsigned sv_pos = 0; // current position in sparse vector
for (unsigned j = 0; j < delta_map.size(); ++j)
{
unsigned id = delta_map[j].second;
bv_index::map_type::const_iterator it = bvi.idx_.find(id);
if (it == bvi.idx_.end())
continue;
const TBVector& bv = *(it->second);
// convert into a plain delta vector again
bv2delta(bv, vect);
sparse_vect_index::vect_addr vaddr;
vaddr.offset = sv_pos;
vaddr.size = (unsigned)(vect.size() - 1);
sv_idx.sv_storage1_.set(id, vect[0]);
if (vaddr.size)
{
sv_idx.sv_storage_.import(&vect[1], vaddr.size, vaddr.offset);
sv_pos += vaddr.size;
}
sv_idx.idx_[id] = vaddr;
} // for
// optimize sparse vector storage, compute memory consumption
{
sparse_vect_index::sparse_vector_type::statistics st;
BM_DECLARE_TEMP_BLOCK(tb)
sv_idx.sv_storage_.optimize(tb, TBVector::opt_compress, &st);
mem_total += st.memory_used;
sv_idx.sv_storage1_.optimize(tb, TBVector::opt_compress, &st);
mem_total += st.memory_used;
}
// check
for (bv_index::map_type::const_iterator it = bvi.idx_.begin();
it != bvi.idx_.end();
++it)
{
unsigned id = it->first;
const TBVector* bvp = it->second;
// convert into a plain vector first
//
vect.resize(0);
for (TBVector::enumerator en = bvp->first(); en.valid(); ++en)
{
vect.push_back(*en);
}
std::vector<unsigned> svect;
sv_idx.get_vector(id, svect);
if (svect.size() != vect.size())
{
std::cerr << "Size check failed! id = " << id
<< "size() = " << svect.size()
<< std::endl;
throw std::runtime_error("sparse vector content check failed");
}
for (unsigned k = 0; k < vect.size(); ++k)
{
if (vect[k] != svect[k])
{
std::cerr << "SV content check failed! id = " << id
<< " i=" << k << std::endl;
for (unsigned h = 0; h < vect.size(); ++h)
{
std::cout << "[" << vect[h] << "=" << svect[h] << "], ";
} // for h
std::cout << std::endl;
throw std::runtime_error("sparse vector content check failed");
}
} // for k
} // for
#ifdef DEBUG
bm::print_svector_stat(sv_idx.sv_storage_, true);
bm::print_svector_stat(sv_idx.sv_storage1_, true);
#endif
return mem_total;
}
// speed test for in-memory bit vectors
// benchmark performs a mix of logical operations
//
static
void speed_test_bv_index(const bv_index& bvi)
{
TBVector bv_join; // OR join vector
bm::chrono_taker tt1(cout, "1. bm::bvector<> index", 1, &timing_map);
// join all vectors using OR operation
for (bv_index::map_type::const_iterator it = bvi.idx_.begin();
it != bvi.idx_.end();
++it)
{
const TBVector* bvp = it->second;
bv_join |= *bvp;
} // for
bv_join.optimize();
// a group of random vectors from the index map, compute OR
// then compute AND with the join vector
//
TBVector bv_res(bm::BM_GAP);
std::vector<unsigned> result_set;
result_set.reserve(result_set_cnt); // memory reservation to avoid reallocs
for (unsigned i = 0; i < benchmark_ops; ++i)
{
bv_res.clear(true); // free all blocks
result_set.resize(0);
for (unsigned j = 0; j < sample_cnt; ++j)
{
unsigned id = unsigned(rand()) % index_size;
bv_index::map_type::const_iterator it = bvi.idx_.find(id);
if (it == bvi.idx_.end())
continue;
const TBVector& bv = *(it->second);
bv_res |= bv;
}
bv_res &= bv_join;
// enumerate the final result set, extract first N elements
//
TBVector::enumerator en = bv_res.first();
for (unsigned k = 0; en.valid() && k < result_set_cnt; ++k, ++en)
{
result_set.push_back(*en);
}
} // for i
tt1.add_repeats(benchmark_ops + 1);
}
// speed test for in-memory serialized bit vectors
// this function uses bm::operation_deserializer
// to perform logical operation between a BLOB and bvector<> in memory
// and avoids extra decompression overhead
//
static
void speed_test_bvs_index(const bvs_index& bvs)
{
TBVector bv_join; // OR join vector
BM_DECLARE_TEMP_BLOCK(tb)
bm::operation_deserializer<TBVector> des;
bm::chrono_taker tt1(cout, "2. serialized bvector", 1, &timing_map);
// join all vectors using OR operation
for (bvs_index::map_type::const_iterator it = bvs.idx_.begin();
it != bvs.idx_.end();
++it)
{
const bvs_index::buffer_type& svect = it->second;
if (svect.size() == 0)
{
throw std::runtime_error("empty buffer error");
}
const unsigned char* buf = it->second.data();
des.deserialize(bv_join, buf, tb, bm::set_OR);
} // for
bv_join.optimize();
// a group of random vectors from the index map, compute OR
// then compute AND with the join vector
//
TBVector bv_res(bm::BM_GAP);
std::vector<unsigned> result_set;
result_set.reserve(result_set_cnt); // memory reservation to avoid reallocs
for (unsigned i = 0; i < benchmark_ops; ++i)
{
bv_res.clear(true); // free all blocks
result_set.resize(0);
for (unsigned j = 0; j < sample_cnt; ++j)
{
unsigned id = unsigned(rand()) % index_size;
bvs_index::map_type::const_iterator it = bvs.idx_.find(id);
if (it == bvs.idx_.end())
continue;
const unsigned char* buf = it->second.data();
des.deserialize(bv_res, buf, tb, bm::set_OR);
} // for j
bv_res &= bv_join;
// enumerate the final result set, extract first N elements
//
TBVector::enumerator en = bv_res.first();
for (unsigned k = 0; en.valid() && k < result_set_cnt; ++k, ++en)
{
result_set.push_back(*en);
}
} // for i
tt1.add_repeats(benchmark_ops + 1);
}
static
void speed_test_vect_index(const vect_index& vecti)
{
TBVector bv_join; // OR join vector
bm::chrono_taker tt1(cout, "3. std::vector<unsigned> ", 1, &timing_map);
// join all vectors using OR operation
for (vect_index::map_type::const_iterator it = vecti.idx_.begin();
it != vecti.idx_.end();
++it)
{
const vect_index::buffer_type& vect = it->second;
if (vect.size() == 0)
{
throw std::runtime_error("empty buffer error");
}
bm::combine_or(bv_join, vect.begin(), vect.end());
} // for
bv_join.optimize();
// a group of random vectors from the index map, compute OR
// then compute AND with the join vector
//
TBVector bv_res(bm::BM_GAP);
std::vector<unsigned> result_set;
result_set.reserve(result_set_cnt); // memory reservation to avoid reallocs
for (unsigned i = 0; i < benchmark_ops; ++i)
{
bv_res.clear(true); // free all blocks
result_set.resize(0);
for (unsigned j = 0; j < sample_cnt; ++j)
{
unsigned id = unsigned(rand()) % index_size;
vect_index::map_type::const_iterator it = vecti.idx_.find(id);
if (it == vecti.idx_.end())
continue;
const vect_index::buffer_type& vect = it->second;
bm::combine_or(bv_join, vect.begin(), vect.end());
} // for j
bv_res &= bv_join;
// enumerate the final result set, extract first N elements
//
TBVector::enumerator en = bv_res.first();
for (unsigned k = 0; en.valid() && k < result_set_cnt; ++k, ++en)
{
result_set.push_back(*en);
}
} // for i
tt1.add_repeats(benchmark_ops + 1);
}
static
void speed_test_sv_index(const sparse_vect_index& svi)
{
TBVector bv_join; // OR join vector
bm::chrono_taker tt1(cout, "4. bm::sparse_vector<unsigned> ", 1, &timing_map);
std::vector<unsigned> vect;
// join all vectors using OR operation
for (sparse_vect_index::map_type::const_iterator it = svi.idx_.begin();
it != svi.idx_.end();
++it)
{
unsigned id = it->first;
svi.get_vector(id, vect);
bm::combine_or(bv_join, vect.begin(), vect.end());
} // for
bv_join.optimize();
// a group of random vectors from the index map, compute OR
// then compute AND with the join vector
//
TBVector bv_res(bm::BM_GAP);
std::vector<unsigned> result_set;
result_set.reserve(result_set_cnt); // memory reservation to avoid reallocs
for (unsigned i = 0; i < benchmark_ops; ++i)
{
bv_res.clear(true); // free all blocks
result_set.resize(0);
for (unsigned j = 0; j < sample_cnt; ++j)
{
unsigned id = unsigned(rand()) % index_size;
svi.get_vector(id, vect);
if (vect.size() == 0)
continue;
bm::combine_or(bv_join, vect.begin(), vect.end());
} // for j
bv_res &= bv_join;
// enumerate the final result set, extract first N elements
//
TBVector::enumerator en = bv_res.first();
for (unsigned k = 0; en.valid() && k < result_set_cnt; ++k, ++en)
{
result_set.push_back(*en);
}
} // for i
tt1.add_repeats(benchmark_ops + 1);
}
int main(void)
{
try
{
bv_index bvi; // regular in-memory index id to bvector<>
bvs_index bvs; // compressed in-memory index id to bvector<> BLOB
vect_index vecti; // index based on plain uncompressed vector<unsigned>
sparse_vect_index svi; // all ids in a sparse vector
// experiments generation, measuring memory footprints
//
generate_bv_index(bvi);
size_t bv_mem_total = calc_memory_footprint(bvi);
size_t bv_mem_total_MB = bv_mem_total / (1024*1024);
std::cout << "bm::bvector<> memory footprint = "
<< bv_mem_total << " (" << bv_mem_total_MB << "MB)"
<< std::endl;
size_t bvs_mem_total = convert_bv2bvs(bvi, bvs);
size_t bvs_mem_total_MB = bvs_mem_total / (1024*1024);
std::cout << "bm::bvector<> BLOB memory footprint = "
<< bvs_mem_total << " (" << bvs_mem_total_MB << "MB)"
<< std::endl;
size_t vecti_mem_total = convert_bv2vect(bvi, vecti);
size_t vecti_mem_total_MB = vecti_mem_total / (1024*1024);
std::cout << "std::vector<unsigned> memory footprint = "
<< vecti_mem_total << " (" << vecti_mem_total_MB << "MB)"
<< std::endl;
size_t svi_mem_total = convert_bv2sv(bvi, svi);
size_t svi_mem_total_MB = svi_mem_total / (1024*1024);
std::cout << "bm::sparse_vector<> memory footprint = "
<< svi_mem_total << " (" << svi_mem_total_MB << "MB)"
<< std::endl;
// run performance tests
//
speed_test_bv_index(bvi);
speed_test_bvs_index(bvs);
speed_test_vect_index(vecti);
speed_test_sv_index(svi);
std::cout << std::endl << "Performance (ops/sec):" << std::endl;
bm::chrono_taker<>::print_duration_map(cout, timing_map, bm::chrono_taker<>::ct_ops_per_sec);
//getchar(); // uncomment to check memory consumption at the OS level
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
BM_DECLARE_TEMP_BLOCK
#define BM_DECLARE_TEMP_BLOCK(x)
Definition bm.h:47
bmalgo.h
Algorithms for bvector<> (main include).
bmalgo_similarity.h
bmserial.h
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs.
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bmsparsevec_algo.h
Algorithms for bm::sparse_vector.
bmsparsevec_serial.h
Serialization for sparse_vector<>.
bmtimer.h
Timing utilities for benchmarking (internal).
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::bvector::enumerator
Constant iterator designed to enumerate "ON" bits.
Definition bm.h:603
bm::bvector::iterator_base::valid
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Definition bm.h:283
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:115
bm::bvector::opt_compress
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition bm.h:137
bm::bvector::count
size_type count() const BMNOEXCEPT
population count (count of ON bits)
Definition bm.h:2401
bm::bvector::optimize
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
Definition bm.h:3635
bm::bvector::set_bit
bool set_bit(size_type n, bool val=true)
Sets bit n.
Definition bm.h:4227
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition bm.h:1871
bm::bvector::clear
void clear(const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN)
clear list of bits in this bitset
Definition bm.h:4149
bm::bvector::compare
int compare(const bvector< Alloc > &bvect) const BMNOEXCEPT
Lexicographical comparison with a bitvector.
Definition bm.h:3744
bm::bvector::end
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition bm.h:1877
bm::bvector::calc_stat
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const BMNOEXCEPT
Calculates bitvector statistics.
Definition bm.h:3978
bm::chrono_taker
Utility class to collect performance measurements and statistics.
Definition bmtimer.h:41
bm::chrono_taker::duration_map_type
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition bmtimer.h:66
bm::chrono_taker::ct_ops_per_sec
@ ct_ops_per_sec
Definition bmtimer.h:60
bm::chrono_taker::add_repeats
void add_repeats(unsigned inc)
Definition bmtimer.h:125
bm::chrono_taker::print_duration_map
static void print_duration_map(TOut &tout, const duration_map_type &dmap, format fmt=ct_time)
Definition bmtimer.h:150
bm::operation_deserializer
Deserializer, performs logical operations between bit-vector and serialized bit-vector.
Definition bmserial.h:927
bm::operation_deserializer::deserialize
size_type deserialize(bvector_type &bv, const unsigned char *buf, set_operation op, bool exit_on_one=false)
Deserialize bvector using buffer as set operation argument.
Definition bmserial.h:6581
bm::serializer
Bit-vector serialization class.
Definition bmserial.h:76
bm::serializer::gap_length_serialization
void gap_length_serialization(bool value) BMNOEXCEPT
Set GAP length serialization (serializes GAP levels of the original vector).
Definition bmserial.h:1272
bm::serializer::set_compression_level
void set_compression_level(unsigned clevel) BMNOEXCEPT
Set compression level.
Definition bmserial.h:1251
bm::serializer::byte_order_serialization
void byte_order_serialization(bool value) BMNOEXCEPT
Set byte-order serialization (for cross platform compatibility).
Definition bmserial.h:1278
bm::serializer::serialize
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
Definition bmserial.h:2703
bm::sparse_vector
succinct sparse vector with runtime compression using bit-slicing / transposition method
Definition bmsparsevec.h:87
bm::sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition bmsparsevec.h:1849
bm::sparse_vector::import
void import(const value_type *arr, size_type arr_size, size_type offset=0, bool set_not_null=true)
Import list of elements from a C-style array.
Definition bmsparsevec.h:1172
bm::sparse_vector::optimize
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector planes
Definition bmsparsevec.h:2148
bm::set_OR
@ set_OR
Definition bmconst.h:170
bm::BM_GAP
@ BM_GAP
GAP compression is ON.
Definition bmconst.h:148
bm::deserialize
size_t deserialize(BV &bv, const unsigned char *buf, bm::word_t *temp_block=0, const bm::bv_ref_vector< BV > *ref_vect=0)
Bitvector deserialization from a memory BLOB.
Definition bmserial.h:3137
bm::combine_or
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition bmalgo_impl.h:1080
bm::gap_levels
const unsigned gap_levels
Definition bmconst.h:85
bm::gap_word_t
unsigned short gap_word_t
Definition bmconst.h:78
timing_map
bm::chrono_taker ::duration_map_type timing_map
Definition sample11.cpp:46
bm::bv_statistics::max_serialize_mem
size_t max_serialize_mem
estimated maximum memory for serialization
Definition bmfunc.h:61
bm::bv_statistics::memory_used
size_t memory_used
memory usage for all blocks and service tables
Definition bmfunc.h:62
bm::bvector::statistics
Statistical information about bitset's memory allocation details.
Definition bm.h:125
bv_index
Definition xsample01.cpp:135
bv_index::~bv_index
~bv_index()
Definition xsample01.cpp:137
bv_index::map_type
std::map< unsigned, TBVector * > map_type
Definition xsample01.cpp:136
bv_index::idx_
map_type idx_
Definition xsample01.cpp:141
bvs_index
Definition xsample01.cpp:147
bvs_index::map_type
std::map< unsigned, buffer_type > map_type
Definition xsample01.cpp:149
bvs_index::buffer_type
std::vector< unsigned char > buffer_type
Definition xsample01.cpp:148
bvs_index::idx_
map_type idx_
Definition xsample01.cpp:151
gap_len_table_sparse
Definition xsample01.cpp:90
gap_len_table_sparse::_len
static const bm::gap_word_t _len[bm::gap_levels]
Definition xsample01.cpp:91
sparse_vect_index::vect_addr
Definition xsample01.cpp:170
sparse_vect_index::vect_addr::size
unsigned size
Definition xsample01.cpp:172
sparse_vect_index::vect_addr::offset
unsigned offset
Definition xsample01.cpp:171
sparse_vect_index
Definition xsample01.cpp:168
sparse_vect_index::idx_
map_type idx_
Definition xsample01.cpp:185
sparse_vect_index::sv_storage1_
sparse_vector_type sv_storage1_
Definition xsample01.cpp:184
sparse_vect_index::sparse_vector_type
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_type
Definition xsample01.cpp:175
sparse_vect_index::map_type
std::map< unsigned, vect_addr > map_type
Definition xsample01.cpp:176
sparse_vect_index::delta_sum_map_type
std::vector< std::pair< uint64_t, unsigned > > delta_sum_map_type
Definition xsample01.cpp:177
sparse_vect_index::get_vector
void get_vector(unsigned id, std::vector< unsigned > &vect) const
Definition xsample01.cpp:188
sparse_vect_index::sv_storage_
sparse_vector_type sv_storage_
Definition xsample01.cpp:183
vect_index
Definition xsample01.cpp:157
vect_index::map_type
std::map< unsigned, buffer_type > map_type
Definition xsample01.cpp:159
vect_index::idx_
map_type idx_
Definition xsample01.cpp:161
vect_index::buffer_type
std::vector< unsigned int > buffer_type
Definition xsample01.cpp:158
generate_random_vector
static void generate_random_vector(TBVector *bv)
Definition xsample01.cpp:219
TBVector
bm::bvector TBVector
Definition xsample01.cpp:74
generate_bv_index
static void generate_bv_index(bv_index &bvi)
Definition xsample01.cpp:262
index_size
const unsigned index_size
Definition xsample01.cpp:55
speed_test_vect_index
static void speed_test_vect_index(const vect_index &vecti)
Definition xsample01.cpp:678
benchmark_ops
const unsigned benchmark_ops
Definition xsample01.cpp:64
bits_per_vect
const unsigned bits_per_vect
Definition xsample01.cpp:61
main
int main(void)
Definition xsample01.cpp:800
speed_test_bv_index
static void speed_test_bv_index(const bv_index &bvi)
Definition xsample01.cpp:555
calc_memory_footprint
static size_t calc_memory_footprint(const bv_index &bvi)
Definition xsample01.cpp:283
bv2delta
static void bv2delta(const TBVector &bv, std::vector< unsigned > &vect)
Definition xsample01.cpp:397
convert_bv2bvs
static size_t convert_bv2bvs(const bv_index &bvi, bvs_index &bvs)
Definition xsample01.cpp:305
destroy_map
void destroy_map(TM &id_map)
Definition xsample01.cpp:116
result_set_cnt
const unsigned result_set_cnt
Definition xsample01.cpp:70
speed_test_sv_index
static void speed_test_sv_index(const sparse_vect_index &svi)
Definition xsample01.cpp:740
convert_bv2vect
static size_t convert_bv2vect(const bv_index &bvi, vect_index &vidx)
Definition xsample01.cpp:367
sample_cnt
const unsigned sample_cnt
Definition xsample01.cpp:67
convert_bv2sv
static size_t convert_bv2sv(const bv_index &bvi, sparse_vect_index &sv_idx)
Definition xsample01.cpp:421
construct_bvector
static TBVector * construct_bvector()
Definition xsample01.cpp:101
max_size
const unsigned max_size
Definition xsample01.cpp:58
speed_test_bvs_index
static void speed_test_bvs_index(const bvs_index &bvs)
Definition xsample01.cpp:614