xsample02.cpp
Go to the documentation of this file.
/*
Copyright(c) 2018 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 xsample02.cpp
Counting sort using bit-vector and sparse vector to build histogram of unsigned ints.
Benchmark compares different histogram buiding techniques using BitMagic and std::sort()
Histogram construction, based on integer events is a common problem,
this demo studies different approaches, potential for parallelization and other
aspects.
*/
/*! \file xsample02.cpp
\brief Example: sparse_vector<> used for counting sort / historgam construction
*/
#include <iostream>
#include <memory>
#include <map>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <stdexcept>
#include <future>
#include <thread>
using namespace std;
#include "bm.h"
#include "bmtimer.h"
#include "bmsparsevec.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
// ----------------------------------------------------
// Global parameters and types
// ----------------------------------------------------
const unsigned value_max = 1250000; // range of variants of events [0..max]
const unsigned test_size = 250000000; // number of events (ints) to generate
// -------------------------------------------
// Random generator
// -------------------------------------------
std::random_device rand_dev;
std::mt19937 gen(rand_dev());
std::uniform_int_distribution<> rand_dis(1, value_max); // generate uniform numebrs for [1, vector_max]
typedef bm::sparse_vector<unsigned, bm::bvector<> > sparse_vector_u32;
typedef std::map<unsigned, unsigned> map_u32;
// timing storage for benchmarking
bm::chrono_taker<>::duration_map_type timing_map;
// -------------------------------------------
// Counting sort / histogram construction (std::map)
// -------------------------------------------
static
void sort_map(map_u32& hmap, const std::vector<unsigned>& vin)
{
for (auto v : vin)
{
hmap[v]++;
}
}
// -------------------------------------------
// Counting sort / histogram construction (naive)
// -------------------------------------------
// This sorting method uses sparse_vector<> as a storage but implements increment
// as an get-inc-put operations (decoding-encoding every value in the sum)
//
static
void counting_sort_naive(sparse_vector_u32& sv_out, const std::vector<unsigned>& vin)
{
for (auto v : vin)
{
auto count = sv_out.get(v);
sv_out.set(v, count + 1);
}
}
// -------------------------------------------
// Counting sort / histogram construction
// -------------------------------------------
// This sorting method uses sparse_vector<> as a storage but implements increment
// but increment was implemented as a bm::sparse_vector::inc() method
// which in turn is based on uses bvector<>::inc()
//
// This approach is faster than decoding-encoding used in naive counting sort
//
static
void counting_sort(sparse_vector_u32& sv_out, const std::vector<unsigned>& vin)
{
for(auto v : vin)
sv_out.inc(v);
}
// --------------------------------------------------
// Counting sort / histogram construction (parallel)
// --------------------------------------------------
// parallel subproblem for all even numbers: (v & 1) == 0
inline
unsigned counting_sort_subbatch(sparse_vector_u32* sv_out, const std::vector<unsigned>* vin)
{
for (size_t i = 0; i < vin->size(); i++)
{
auto v = (*vin)[i];
if ((v & 1) == 0)
sv_out->inc(v);
}
return 0;
}
// Parallel histogram construction uses a very simple divide and conquer technique
// splitting by even/odd numbers, uses std::async() for parallelization
//
// (should be possible to do a lot better than that)
//
static
void counting_sort_parallel(sparse_vector_u32& sv_out, const std::vector<unsigned>& vin)
{
sparse_vector_u32 sv_out2(bm::use_null);
// process evens in parallel
std::future<unsigned> f1 = std::async(std::launch::async, counting_sort_subbatch, &sv_out2, &vin);
// process all odd elements
for (size_t i = 0; i < vin.size(); i++)
{
auto v = vin[i];
if (v & 1)
sv_out.inc(v);
}
f1.wait();
// merge effectively performs logical OR on all plains, only it
// borrows memory blocks from the argument vector, so it gets changed
// (which is ok here, since sv_out2 is a temporary)
//
sv_out.merge(sv_out2);
}
// Test utility. It also illustrates histogram access method
//
static
void print_sorted(const sparse_vector_u32& sv)
{
const sparse_vector_u32::bvector_type* bv_null = sv.get_null_bvector();
sparse_vector_u32::bvector_type::enumerator en = bv_null->first();
for (; en.valid(); ++en)
{
unsigned v = *en;
unsigned cnt = sv.get(v);
for (unsigned j = 0; j < cnt; ++j)
{
std::cout << v << ", ";
} // for
} // for en
std::cout << std::endl;
}
// Test utility for std::map
//
static
void print_sorted(const map_u32& hmap)
{
map_u32::const_iterator it = hmap.begin();
map_u32::const_iterator it_end = hmap.end();
for (; it != it_end; ++it)
{
unsigned v = it->first;
unsigned cnt = it->second;
for (unsigned j = 0; j < cnt; ++j)
{
std::cout << v << ", ";
} // for
} // for en
std::cout << std::endl;
}
// build histogram using sorted vector
//
static
void build_histogram(sparse_vector_u32& sv_out, const std::vector<unsigned>& vin)
{
if (vin.empty())
return;
unsigned start = vin[0];
unsigned count = 0; // histogram counter
for (auto v : vin)
{
if (v == start)
{
++count;
}
else
{
sv_out.set(start, count);
start = v; count = 1;
}
}
if (count)
{
sv_out.set(start, count);
}
}
int main(void)
{
try
{
// try simple input vector as a model
//
{
std::vector<unsigned> v {10, 1, 5, 4, 8, 8, 8} ;
sparse_vector_u32 r_sv(bm::use_null); // result vector
counting_sort(r_sv, v);
print_sorted(r_sv); // 1, 4, 5, 8, 8, 8, 10,
sparse_vector_u32 p_sv(bm::use_null);
counting_sort_parallel(p_sv, v);
print_sorted(r_sv);
map_u32 h_map;
sort_map(h_map, v);
print_sorted(h_map);
std::sort(v.begin(), v.end());
sparse_vector_u32 h_sv(bm::use_null); // histogram vector
build_histogram(h_sv, v);
if (!r_sv.equal(h_sv))
{
std::cerr << "Error: Histogram comparison failed!" << std::endl;
print_sorted(h_sv);
return 1;
}
}
// run benchmarks
//
std::vector<unsigned> v;
// generate vector of random numbers
for (unsigned i = 0; i < test_size; ++i)
{
v.push_back(unsigned(rand_dis(gen)));
}
std::cout << "test vector generation ok" << std::endl;
sparse_vector_u32 r_sv(bm::use_null);
sparse_vector_u32 h_sv(bm::use_null);
sparse_vector_u32 n_sv(bm::use_null);
sparse_vector_u32 p_sv(bm::use_null);
map_u32 h_map;
{
bm::chrono_taker tt1(cout, "1. counting sort ", 1, &timing_map);
counting_sort(r_sv, v);
}
{
bm::chrono_taker tt1(cout, "3. counting sort (naive) ", 1, &timing_map);
counting_sort_naive(n_sv, v);
}
{
bm::chrono_taker tt1(cout, "4. counting sort (parallel) ", 1, &timing_map);
counting_sort_parallel(p_sv, v);
}
{
bm::chrono_taker tt1(cout, "5. counting sort (map) ", 1, &timing_map);
sort_map(h_map, v);
}
{
bm::chrono_taker tt1(cout, "2. std::sort() + histogram", 1, &timing_map);
std::sort(v.begin(), v.end());
build_histogram(h_sv, v);
}
// quality assurance checks
//
if (!r_sv.equal(h_sv) || !n_sv.equal(h_sv))
{
std::cerr << "Error: Histogram comparison failed!" << std::endl;
return 1;
}
if (!r_sv.equal(p_sv))
{
std::cerr << "Error: Histogram comparison failed for parallel sort!" << std::endl;
return 1;
}
// compute memory consumption of sparse vector
{
std::cout << std::endl;
BM_DECLARE_TEMP_BLOCK(tb);
sparse_vector_u32::statistics st;
r_sv.optimize(tb, sparse_vector_u32::bvector_type::opt_compress, &st);
std::cout << "Sparse vector memory usage:" << st.memory_used / (1024*1024)<< "MB" << std::endl;
std::cout << "vector<unsigned> usage:" << v.size() * sizeof(v[0]) / (1024 * 1024) << "MB" << std::endl << std::endl;
}
bm::chrono_taker<>::print_duration_map(cout, timing_map, bm::chrono_taker<>::ct_ops_per_sec);
}
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
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bmtimer.h
Timing utilities for benchmarking (internal).
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::base_sparse_vector::get_null_bvector
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values or NULL (if not constructed that way).
Definition bmbmatrix.h:451
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition bm.h:1871
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::print_duration_map
static void print_duration_map(TOut &tout, const duration_map_type &dmap, format fmt=ct_time)
Definition bmtimer.h:150
bm::sparse_vector
succinct sparse vector with runtime compression using bit-slicing / transposition method
Definition bmsparsevec.h:87
bm::sparse_vector::inc
void inc(size_type idx)
increment specified element by one
Definition bmsparsevec.h:2052
bm::sparse_vector::get
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
Definition bmsparsevec.h:1758
bm::sparse_vector::equal
bool equal(const sparse_vector< Val, BV > &sv, bm::null_support null_able=bm::use_null) const BMNOEXCEPT
check if another sparse vector has the same content and size
Definition bmsparsevec.h:2300
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::merge
sparse_vector< Val, BV > & merge(sparse_vector< Val, BV > &sv)
merge with another sparse vector using OR operation Merge is different from join(),...
Definition bmsparsevec.h:2208
bm::sparse_vector< unsigned, bm::bvector<> >::bvector_type
bm::bvector<> bvector_type
Definition bmsparsevec.h:90
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::use_null
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:230
rand_dev
std::random_device rand_dev
Definition sample11.cpp:51
timing_map
bm::chrono_taker ::duration_map_type timing_map
Definition sample11.cpp:46
gen
std::mt19937 gen(rand_dev())
test_size
const unsigned test_size
Definition xsample02.cpp:57
counting_sort_parallel
static void counting_sort_parallel(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition xsample02.cpp:147
map_u32
std::map< unsigned, unsigned > map_u32
Definition xsample02.cpp:69
counting_sort
static void counting_sort(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition xsample02.cpp:118
rand_dev
std::random_device rand_dev
Definition xsample02.cpp:63
build_histogram
static void build_histogram(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition xsample02.cpp:213
sparse_vector_u32
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_u32
Definition xsample02.cpp:68
main
int main(void)
Definition xsample02.cpp:240
counting_sort_naive
static void counting_sort_naive(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition xsample02.cpp:98
sort_map
static void sort_map(map_u32 &hmap, const std::vector< unsigned > &vin)
Definition xsample02.cpp:81
counting_sort_subbatch
unsigned counting_sort_subbatch(sparse_vector_u32 *sv_out, const std::vector< unsigned > *vin)
Definition xsample02.cpp:130
gen
std::mt19937 gen(rand_dev())
print_sorted
static void print_sorted(const sparse_vector_u32 &sv)
Definition xsample02.cpp:172
value_max
const unsigned value_max
Definition xsample02.cpp:56
rand_dis
std::uniform_int_distribution rand_dis(1, value_max)