BitMagic-C++
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.

/*
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
{
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;
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;
}
main
int main(void)
Definition: xsample02.cpp:238
print_sorted
static void print_sorted(const sparse_vector_u32 &sv)
Definition: xsample02.cpp:170
bm::sparse_vector
sparse vector with runtime compression using bit transposition method
Definition: bmsparsevec.h:81
bm::chrono_taker
Utility class to collect performance measurements and statistics.
Definition: bmtimer.h:39
timing_map
bm::chrono_taker::duration_map_type timing_map
Definition: xsample02.cpp:71
BM_DECLARE_TEMP_BLOCK
#define BM_DECLARE_TEMP_BLOCK(x)
Definition: bm.h:47
value_max
const unsigned value_max
Definition: xsample02.cpp:54
bm::bvector<>::enumerator
friend class enumerator
Definition: bm.h:823
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
build_histogram
static void build_histogram(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition: xsample02.cpp:211
sparse_vector_u32
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_u32
Definition: xsample02.cpp:66
counting_sort
static void counting_sort(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition: xsample02.cpp:116
rand_dev
std::random_device rand_dev
Definition: xsample02.cpp:61
sort_map
static void sort_map(map_u32 &hmap, const std::vector< unsigned > &vin)
Definition: xsample02.cpp:79
counting_sort_parallel
static void counting_sort_parallel(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition: xsample02.cpp:145
bm::bvector<>
bm::use_null
@ use_null
support "non-assigned" or "NULL" logic
Definition: bmconst.h:215
rand_dis
std::uniform_int_distribution rand_dis(1, value_max)
test_size
const unsigned test_size
Definition: xsample02.cpp:55
bm::bvector<>::opt_compress
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition: bm.h:134
counting_sort_naive
static void counting_sort_naive(sparse_vector_u32 &sv_out, const std::vector< unsigned > &vin)
Definition: xsample02.cpp:96
bmtimer.h
Timing utilities for benchmarking (internal)
bm::chrono_taker::ct_ops_per_sec
@ ct_ops_per_sec
Definition: bmtimer.h:59
bm::sparse_vector::get
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
Definition: bmsparsevec.h:1451
bm::chrono_taker::duration_map_type
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition: bmtimer.h:65
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:1825
bm::chrono_taker::print_duration_map
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
Definition: bmtimer.h:127
gen
std::mt19937 gen(rand_dev())
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1784
counting_sort_subbatch
unsigned counting_sort_subbatch(sparse_vector_u32 *sv_out, const std::vector< unsigned > *vin)
Definition: xsample02.cpp:128
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
map_u32
std::map< unsigned, unsigned > map_u32
Definition: xsample02.cpp:67
bm::sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition: bmsparsevec.h:1475
bm::sparse_vector::inc
void inc(size_type idx)
increment specified element by one
Definition: bmsparsevec.h:1667
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:329