BitMagic-C++
xsample02.cpp

Counting sort using bit-vector and sparse vector to build histogram of unsigned ints.

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.

/*
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>
#include "bm.h"
#include "bmtimer.h"
#include "bmsparsevec.h"
// ----------------------------------------------------
// 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 std::map<unsigned, unsigned> map_u32;
// timing storage for benchmarking
// -------------------------------------------
// 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)
{
// 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
{
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,
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;
map_u32 h_map;
{
bm::chrono_taker tt1("1. counting sort ", 1, &timing_map);
counting_sort(r_sv, v);
}
{
bm::chrono_taker tt1("3. counting sort (naive) ", 1, &timing_map);
}
{
bm::chrono_taker tt1("4. counting sort (parallel) ", 1, &timing_map);
}
{
bm::chrono_taker tt1("5. counting sort (map) ", 1, &timing_map);
sort_map(h_map, v);
}
{
bm::chrono_taker tt1("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;
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;
}
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
#define BM_DECLARE_TEMP_BLOCK(x)
Definition bm.h:47
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Timing utilities for benchmarking (internal)
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values or NULL (if not constructed that way)
Definition bmbmatrix.h:329
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:108
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition bm.h:1770
Utility class to collect performance measurements and statistics.
Definition bmtimer.h:40
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
Definition bmtimer.h:127
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition bmtimer.h:65
sparse vector with runtime compression using bit transposition method
Definition bmsparsevec.h:82
void inc(size_type idx)
increment specified element by one
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
sparse_vector< Val, BV > & merge(sparse_vector< Val, BV > &sv)
merge with another sparse vector using OR operation Merge is different from join(),...
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:215
std::random_device rand_dev
Definition sample11.cpp:49
bm::chrono_taker::duration_map_type timing_map
Definition sample11.cpp:44
std::uniform_int_distribution rand_dis(1, int(vector_max))
std::mt19937 gen(rand_dev())
int main(void)
Definition sample1.cpp:38
const unsigned test_size
Definition xsample02.cpp:55
static void counting_sort_parallel(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
std::map< unsigned, unsigned > map_u32
Definition xsample02.cpp:67
static void counting_sort(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
static void build_histogram(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_u32
Definition xsample02.cpp:66
static void counting_sort_naive(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition xsample02.cpp:96
static void sort_map(map_u32 &hmap, const std::vector< unsigned > &vin)
Definition xsample02.cpp:79
unsigned counting_sort_subbatch(sparse_vector_u32 *sv_out, const std::vector< unsigned > *vin)
static void print_sorted(const sparse_vector_u32 &sv)
const unsigned value_max
Definition xsample02.cpp:54