本例是<C++ 性能优化指南>一书STL容器部分的代码。
着重比较了STL各种操作的性能。
代码比较长。
conanfile.txt
[requires]
boost/1.72.0
[generators]
cmake
CMakeLists.txt
cmake_minimum_required(VERSION 2.6)
project(optimize)
set(ENV{PKG_CONFIG_PATH} "$ENV{PKG_CONFIG_PATH}:/usr/local/lib/pkgconfig/")
set ( CMAKE_CXX_FLAGS "-pthread")
set(CMAKE_CXX_STANDARD 17)
add_definitions(-g)
include(${CMAKE_BINARY_DIR}/conanbuildinfo.cmake)
conan_basic_setup()
include_directories(${CMAKE_CURRENT_SOURCE_DIR}/include)
LINK_DIRECTORIES(${LINK_DIRS})
file( GLOB main_file_list ${CMAKE_CURRENT_SOURCE_DIR}/*.cpp)
file( GLOB source_file_list ${CMAKE_CURRENT_SOURCE_DIR}/impl/*.cpp)
foreach( main_file ${main_file_list} )
file(RELATIVE_PATH filename ${CMAKE_CURRENT_SOURCE_DIR} ${main_file})
string(REPLACE ".cpp" "" file ${filename})
add_executable(${file} ${main_file} ${source_file_list})
target_link_libraries(${file} ${CONAN_LIBS} pthread)
endforeach( main_file ${main_file_list})
stopwatch.h
#ifndef _STOPWATCH_H_
#define _STOPWATCH_H_
#include <iostream>
template <class T>
class basic_stopwatch: public T {
public:
using BaseTimer = T;
using tick_t = typename T::tick_t;
// 创建可选的，开始对一个行为计时
explicit basic_stopwatch(bool start);
explicit basic_stopwatch(char const* activity="Stopwatch",
bool start=true);
basic_stopwatch(std::ostream& log,
char const* activtity="Stopwatch",
bool start=true);
~basic_stopwatch();
// 获取上次stop以后lap的时间
tick_t LapGet() const;
bool IsStarted() const;
tick_t Show(char const* event="show");
tick_t Start(char const* event_name="start");
tick_t Stop(char const* event_name="stop");
private:
char const* m_activity;
tick_t m_lap;
std::ostream& m_log;
};
template <class T>
inline basic_stopwatch<T>::basic_stopwatch(bool start_now):
m_activity("StopWatch"),
m_lap(0),
m_log(std::cout) {
if(start_now) {
Start();
}
}
template <class T>
inline basic_stopwatch<T>::basic_stopwatch(char const* activity,
bool start):
m_activity(activity&&activity[0]? activity: nullptr),
m_lap(0),
m_log(std::cout) {
if(start) {
if(m_activity) {
Start();
}else {
// 没有activity，连事件名都没有
Start(nullptr);
}
}
}
template <typename T>
inline basic_stopwatch<T>::basic_stopwatch(std::ostream& log,
char const* activtity,
bool start):
m_activity(activtity&&activtity[0]? activtity: nullptr),
m_lap(0),
m_log(log) {
if(start) {
Start();
} else {
Start(nullptr);
}
}
template <class T>
inline basic_stopwatch<T>::~basic_stopwatch() {
if(IsStarted()) {
if(m_activity) {
Stop();
} else {
Stop(nullptr);
}
}
}
template <class T>
inline bool basic_stopwatch<T>::IsStarted() const {
return BaseTimer::IsStarted();
}
template <class T>
inline typename basic_stopwatch<T>::tick_t basic_stopwatch<T>::LapGet() const {
return m_lap;
}
template <class T>
inline typename basic_stopwatch<T>::tick_t basic_stopwatch<T>::Show(char const* event_name) {
if(IsStarted()) {
m_lap = BaseTimer::GetMs();
if(event_name && event_name[0]) {
if(m_activity) {
m_log << m_activity << ": ";
}
m_log << event_name << " at " << m_lap << " mS" << std::endl << std::flush;
}
}else {
if(m_activity) {
m_log << m_activity << ": not started" << std::endl << std::flush;
}
}
return m_lap;
}
template <class T>
inline typename basic_stopwatch<T>::tick_t basic_stopwatch<T>::Start(char const* event_name) {
if(IsStarted()) {
Stop(event_name);
} else {
if(event_name && event_name[0]) {
if(m_activity) {
m_log << m_activity << ": ";
}
m_log << event_name << std::endl << std::flush;
}
}
BaseTimer::Start();
return m_lap;
}
template <class T>
inline typename basic_stopwatch<T>::tick_t basic_stopwatch<T>::Stop(char const* event_name) {
if(IsStarted()) {
m_lap = BaseTimer::GetMs();
if(event_name && event_name[0]) {
if(m_activity) {
m_log << m_activity << ": ";
}
m_log << event_name << " " << m_lap << "mS" << std::endl << std::flush;
}
}
BaseTimer::Clear();
return m_lap;
}
#endif
stopwatch11.h
#ifndef STOPWATCH11_H
#define STOPWATCH11_H
#include <chrono>
using namespace std::chrono;
class TimerBaseChrono {
public:
using tick_t = unsigned long;
// 构造函数，clears the timer
TimerBaseChrono(): m_start(system_clock::time_point::min()) {}
// clears the timer
void Clear() {
m_start = system_clock::time_point::min();
}
bool IsStarted() const {
return m_start != system_clock::time_point::min();
}
// starts the timer
void Start() {
m_start = system_clock::now();
}
unsigned long GetMs() {
if(IsStarted()) {
system_clock::duration diff;
diff = system_clock::now() - m_start;
return (unsigned)(duration_cast<milliseconds>(diff).count());
}
return 0;
}
private:
system_clock::time_point m_start;
};
#include "stopwatch.h"
using StopWatch = basic_stopwatch<TimerBaseChrono>;
// 声明 stopwatch的测试方法，在外面调用
int test_stopwatch11(int test_no, unsigned long);
# endif
kvstruct.h
#ifndef _FREDRIC_KVSTRUCT_H_
#define _FREDRIC_KVSTRUCT_H_
#include <cstring>
// simple, non-template key/value class with char[] keys, unsigned values
struct kvstruct {
char key[9];
unsigned value;
kvstruct(unsigned k): value(k) {
char buf[9];
strcpy(key, stringify(k, buf));
}
// Dec to Hex
static char const* stringify(unsigned i, char* buf) {
buf[8] = 0;
char* bufp = &buf[8];
do {
*--bufp = "0123456789ABCDEF"[i & 0xf];
i >>= 4;
} while(i!=0);
return bufp;
}
bool operator<(kvstruct const& that) const { return strcmp(this->key, that.key) < 0; }
bool operator==(kvstruct const& that) const { return strcmp(this->key, that.key) == 0; }
};
#endif
charbuf.h
#ifndef _FREDRIC_CHAR_BUF_H_
#define _FREDRIC_CHAR_BUF_H_
#include "hash.h" // hash function 用来扩展std::hash
#include "array_iterator.h" // std::begin(), std::end(), std::size()
// Simple container for a char[] text string
template <unsigned N=10, typename T=char>
struct charbuf{
charbuf();
charbuf(charbuf const& cb);
charbuf(T const* p);
charbuf& operator=(charbuf const& rhs);
charbuf& operator=(T const* rhs);
T* data();
T const* data() const;
operator size_t() const;
bool operator==(charbuf const& that) const;
bool operator<(charbuf const& that) const;
size_t capacity() const;
size_t hash1() const;
size_t hash2() const;
private:
T data_[N];
};
template <unsigned N, typename T>
inline charbuf<N, T>::charbuf() {
for(auto it=std::begin(data_); it<std::end(data_); ++it) {
*it = 0;
}
}
template <unsigned N, typename T>
inline charbuf<N, T>::charbuf(charbuf const& cb) {
T const* p = cb.data();
for(auto it=std::begin(data_); it!=std::end(data_); ++it) {
*it = *p;
if(*p) {
++p;
}
}
}
template <unsigned N, typename T>
inline charbuf<N, T>::charbuf(T const* p) {
if(p == nullptr) {
p = "";
}
for(auto it=std::begin(data_); it!=std::end(data_); ++it) {
*it = *p;
if(*p) {
++p;
}
}
}
template <unsigned N, typename T>
inline charbuf<N, T>& charbuf<N, T>::operator=(charbuf const& rhs) {
if(this != &rhs) {
T const* p= rhs.data();
for(auto it=std::begin(data_); it!=std::end(data_); ++it) {
*it = *p;
if(*p) {
++p;
}
}
}
return *this;
}
template <unsigned N, typename T>
inline charbuf<N, T>& charbuf<N, T>::operator=(T const* rhs) {
if(rhs != data_) {
if(rhs == nullptr) {
rhs = "";
}
for(auto it=std::begin(data_); it!=std::end(data_); ++it) {
*it = *rhs;
if(*rhs) {
++rhs;
}
}
}
return *this;
}
template <unsigned N, typename T>
inline T* charbuf<N, T>::data() {
return data_;
}
template <unsigned N, typename T>
inline T const* charbuf<N, T>::data() const {
return data_;
}
template <unsigned N, typename T>
inline size_t charbuf<N, T>::hash1() const {
return hash_range(std::begin(data_), std::end(data_));
}
template <unsigned N, typename T>
inline size_t charbuf<N, T>::hash2() const {
size_t hash = 5381;
for(T const* it=std::begin(data_); it!=std::end(data_); ++it) {
hash = (hash << 6) + hash + (*it);
}
return hash;
}
template <unsigned N, typename T>
inline charbuf<N,T>::operator size_t () const {
return hash1();
}
template <unsigned N, typename T>
inline bool charbuf<N, T>::operator==(charbuf const& that) const {
return strcmp(this->data_, that.data_) == 0;
}
template <unsigned N, typename T>
inline bool charbuf<N, T>::operator<(charbuf const& that) const {
return strcmp(this->data_, that.data_) < 0;
}
template <unsigned N, typename T>
inline size_t charbuf<N, T>::capacity() const {
return N;
}
#endif
hash.h
#ifndef _FREDIRC_HASH_H_
#define _FREDRIC_HASH_H_
#include <cstddef>
#include <boost/container_hash/hash.hpp>
template <typename IT>
inline size_t hash_range(IT first, IT last) {
size_t hash = 0;
for(; first!=last; ++first) {
boost::hash_combine(hash, *first);
}
return hash;
}
// Hash 一个支持迭代器的顺序容器
template <typename SEQ>
struct hash_seq {
size_t operator()(SEQ const& x) const {
return hash_range(x.begin(), x.end());
}
};
#endif
test_driver.h
#ifndef _FREDRIC_TEST_DRIVER_H_
#define _FREDRIC_TEST_DRIVER_H_
using test_func = int(*)(int, unsigned long);
// 调用多个 test_func类型的函数
void test_driver(test_func* flist, int argc=0, char** argv=0);
// 调用一个test_func类型的函数
void test_driver(test_func f, int argc=0, char** argv=0);
#endif
array_iterator.h
#ifndef _FREDRIC_ARRAY_ITERATOR_H_
#define _FREDRIC_ARRAY_ITERATOR_H_
#include <cstddef>
// 获取c style array 大小的模板方法
namespace std {
template <typename T, int N>
size_t size(T (&a) [N]) {
return N;
}
};
#endif
vector.cpp
#include "stopwatch11.h"
#include "kvstruct.h"
#include <iostream>
#include <algorithm>
#include <vector>
bool test_vector(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
bool rc = true;
std::size_t const nelts = random_vector.size();
std::cout << std::endl << "std::vector " << random_vector.size() << " entries" << std::endl << std::endl;
// std::vector 插入和删除
{
StopWatch sw("assign vector to vector + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
test_container = random_vector;
std::vector<kvstruct>().swap(test_container);
}
}
// 1000 次的插入和删除统计
{
StopWatch sw("assign vector to vector", false);
StopWatch::tick_t ticks;
StopWatch::tick_t assign_x_1000 = 0;
StopWatch::tick_t delete_x_1000 = 0;
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
sw.Start("");
test_container = random_vector;
ticks = sw.Show("");
assign_x_1000 += ticks;
std::vector<kvstruct>().swap(test_container);
delete_x_1000 += sw.Stop("") - ticks;
}
std::cout << " assign vector to vector x 1000: "
<< assign_x_1000 << "ms" << std::endl;
std::cout << " vector delete x 1000: "
<< delete_x_1000 << "ms" << std::endl;
}
// std::vector 迭代器插入加删除1000次
{
StopWatch sw("vector iterator insert(begin()) vector + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
test_container.insert(test_container.begin(), random_vector.begin(), random_vector.end());
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("same, only with reserve");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
test_container.reserve(nelts);
test_container.insert(test_container.begin(), random_vector.begin(), random_vector.end());
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("vector iterator insert(end()) vector + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("vector iterator push_back() to vector + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
for(auto it=random_vector.begin(); it != random_vector.end(); ++it) {
test_container.push_back(*it);
}
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("same, only with reserve");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
test_container.reserve(nelts);
for(auto it=random_vector.begin(); it != random_vector.end(); ++it) {
test_container.push_back(*it);
}
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("vector.at() push_back() to vector + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.push_back(random_vector.at(i));
}
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("vector[] push_back() to vector + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.push_back(random_vector[i]);
}
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("vector iterator insert at back to vector + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(test_container.end(), *it);
}
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("same, but with reserve");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
test_container.reserve(nelts);
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(test_container.end(), *it);
}
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("vector.at() insert at end + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.insert(test_container.end(), random_vector.at(i));
}
std::vector<kvstruct>().swap(test_container);
}
}
{
StopWatch sw("vector[] insert at the end + delete x 1000");
std::vector<kvstruct> test_container;
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.insert(test_container.end(), random_vector[i]);
}
std::vector<kvstruct>().swap(test_container);
}
}
// vector insert at front part
std::vector<kvstruct> test_container;
{
StopWatch sw("vector interator insert at front to vector");
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(test_container.begin(), *it);
}
}
std::vector<kvstruct>().swap(test_container);
{
StopWatch sw("same but with reserve");
test_container.reserve(nelts);
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(test_container.begin(), *it);
}
}
std::vector<kvstruct>().swap(test_container);
{
StopWatch sw("vector at() insert at front");
for(unsigned i=0; i<nelts; ++i) {
test_container.insert(test_container.begin(), random_vector.at(i));
}
}
std::vector<kvstruct>().swap(test_container);
{
StopWatch sw("vector [] insert at front");
for(unsigned i=0; i<nelts; ++i) {
test_container.insert(test_container.begin(), random_vector[i]);
}
}
// vector traversal
{
long long sum;
std::vector<kvstruct> test_container = random_vector;
sum = 0;
{
StopWatch sw("traversal vector (at) x 1000");
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<nelts; ++i) {
sum += test_container.at(i).value;
}
}
}
rc &= (sum!=0);
sum = 0;
{
StopWatch sw("traversal vector, subscript, size() x 1000");
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<test_container.size(); ++i) {
sum += test_container[i].value;
}
}
}
rc &= (sum!=0);
sum = 0;
{
StopWatch sw("traversal vector (subscript) x 1000");
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<nelts; ++i) {
sum += test_container[i].value;
}
}
}
rc &= (sum!=0);
sum = 0;
{
StopWatch sw("traversal vector (iterator) x 1000");
for(unsigned j=0; j<1000; ++j) {
for(auto it=test_container.begin(); it!=test_container.end(); ++it) {
sum += it->value;
}
}
}
rc &= (sum!=0);
}
// vector sort
{
std::vector<kvstruct> sorted_container;
sorted_container = random_vector;
{
StopWatch sw("std::sort() vector + assign + delete x 100");
for(unsigned j=0; j<100; ++j) {
sorted_container = random_vector;
std::sort(sorted_container.begin(), sorted_container.end());
}
}
{
StopWatch sw("std::sort() sorted vector x 100");
for(unsigned j=0; j<100; ++j) {
std::sort(sorted_container.begin(), sorted_container.end());
}
}
rc &= (sorted_container.size() == random_vector.size());
// std::stable_sort
sorted_container = random_vector;
{
StopWatch sw("std::stable_stort() vector assign + delete x 100");
for(unsigned j=0; j<100; ++j) {
sorted_container = random_vector;
std::stable_sort(sorted_container.begin(), sorted_container.end());
}
}
{
StopWatch sw("std::stable_sort() sorted vector x 100");
for(unsigned j=0; j<100; ++j) {
std::stable_sort(sorted_container.begin(), sorted_container.end());
}
}
rc &= (sorted_container.size() == random_vector.size());
}
// lookup
{
std::vector<kvstruct> sorted_container;
sorted_container = random_vector;
std::sort(sorted_container.begin(), sorted_container.end());
StopWatch sw("lookup in sorted vector x 100");
std::vector<kvstruct>::iterator kp;
for(unsigned j=0; j<100; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
kp = std::lower_bound(sorted_container.begin(), sorted_container.end(),
*it);
// 不可能有小于的，因为random_vector中的值都是 sorted_container中的值，都是
// *it == *kp
if(kp!= sorted_container.end() && *it < *kp) {
kp = sorted_container.end();
}
}
}
rc &= (kp != sorted_container.end());
}
return rc;
}
list.cpp
#include "stopwatch11.h"
#include "kvstruct.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
// TODO: add test_list code
bool test_list(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
bool rc = true;
std::size_t const nelts = random_vector.size();
std::cout << std::endl << "std::list " << random_vector.size() << " entries" << std::endl
<< "multiplier == " << multiplier << std::endl << std::endl;
std::list<kvstruct> random_container;
// list insert and delete
{
random_container.insert(random_container.end(), random_vector.begin(), random_vector.end());
{
StopWatch sw("assign list to list + delete x multiplier");
StopWatch::tick_t begin_ticks = 0;
StopWatch::tick_t assign_ticks = 0;
StopWatch::tick_t assign_x_1000 = 0;
StopWatch::tick_t delete_x_1000 = 0;
std::list<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
test_container = random_container;
assign_ticks = sw.Show("");
assign_x_1000 += assign_ticks - begin_ticks;
test_container.clear();
begin_ticks = sw.Show("");
delete_x_1000 += begin_ticks - assign_ticks;
}
std::cout << "assign " << assign_x_1000 << "ms"
<< " + delete "
<< delete_x_1000 << "ms"
<< " == " << (assign_x_1000 + delete_x_1000)
<< "ms" << std::endl;
}
{
StopWatch sw("vector iterator insert(end()) + delete x multiplier");
std::list<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
test_container.clear();
}
}
{
StopWatch sw("vector iterator push_back() + delete x multiplier");
std::list<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.push_back(*it);
}
test_container.clear();
}
}
{
StopWatch sw("vector at() push_back + delete x multiplier");
std::list<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.push_back(random_vector.at(i));
}
test_container.clear();
}
}
{
StopWatch sw("vector[] push_back + delete x multiplier");
std::list<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.push_back(random_vector[i]);
}
test_container.clear();
}
}
{
StopWatch sw("vector iterator push_front() + delete multiplier");
std::list<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.push_front(*it);
}
test_container.clear();
}
}
{ StopWatch sw("vector.at() push_front() + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
for (unsigned i = 0; i < nelts; ++i)
test_container.push_front(random_vector.at(i));
test_container.clear();
}
}
{ StopWatch sw("vector[] push_front() + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
for (unsigned i = 0; i < nelts; ++i)
test_container.push_front(random_vector[i]);
test_container.clear();
}
}
{ StopWatch sw("vector iterator insert at back + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
for (auto it = random_vector.begin(); it != random_vector.end(); ++it)
test_container.insert(test_container.end(), *it);
test_container.clear();
}
}
{ StopWatch sw("vector.at() insert at end + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
for (unsigned i = 0; i < nelts; ++i)
test_container.insert(test_container.end(), random_vector.at(i));
test_container.clear();
}
}
{ StopWatch sw("vector[] insert at end + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
for (unsigned i = 0; i < nelts; ++i)
test_container.insert(test_container.end(), random_vector[i]);
test_container.clear();
}
}
{ StopWatch sw("vector iterator insert at last position + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
auto place = test_container.begin();
for (auto it = random_vector.begin(); it != random_vector.end(); ++it)
place = test_container.insert(place, *it);
test_container.clear();
}
}
{ StopWatch sw("vector iterator insert at front + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
for (auto it = random_vector.begin(); it != random_vector.end(); ++it)
test_container.insert(test_container.begin(), *it);
test_container.clear();
}
}
{ StopWatch sw("vector.at() insert at front + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
for (unsigned i = 0; i < nelts; ++i)
test_container.insert(test_container.begin(), random_vector.at(i));
test_container.clear();
}
}
{ StopWatch sw("vector[] insert at frone + delete x multiplier");
std::list<kvstruct> test_container;
for (unsigned j = 0; j < multiplier; ++j) {
for (unsigned i = 0; i < nelts; ++i)
test_container.insert(test_container.begin(), random_vector[i]);
test_container.clear();
}
}
}
// traversal
{
std::list<kvstruct> test_container;
unsigned long long sum;
sum = 0;
test_container = random_container;
{ StopWatch sw("traverse list (iterator) x 1000");
for (unsigned j = 0; j < 1000; ++j)
for (auto it = test_container.begin(); it != test_container.end(); ++it)
sum += it->value;
}
rc &= (sum != 0);
}
// list sort
{
std::list<kvstruct> sorted_container;
{ StopWatch sw("std::list::sort() list + build + delete x 100");
for (unsigned j = 0; j < 100; j++) {
sorted_container = random_container;
sorted_container.sort();
}
}
{ StopWatch sw("std::list::sort() sorted list x 100");
for (unsigned j = 0; j < 100; j++) {
sorted_container.sort();
}
}
rc &= (sorted_container.size() == random_vector.size());
}
return rc;
}
deque.cpp
#include "stopwatch11.h"
#include "kvstruct.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
bool test_deque(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
bool rc = true;
std::size_t const nelts = random_vector.size();
std::cout << std::endl << "std::deque " << random_vector.size() << " entries" << std::endl << std::endl;
std::deque<kvstruct> random_container;
// deque insert and delete
{
std::cout << "multiplier == " << multiplier << std::endl;
random_container.insert(random_container.end(), random_vector.begin(), random_vector.end());
{
StopWatch sw("assign deque to deque + delete x multiplier");
StopWatch::tick_t begin_ticks = 0;
StopWatch::tick_t assign_ticks = 0;
StopWatch::tick_t assign_x_1000 = 0;
StopWatch::tick_t delete_x_1000 = 0;
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
test_container = random_container;
assign_ticks = sw.Show("");
assign_x_1000 += assign_ticks - begin_ticks;
test_container.clear();
begin_ticks = sw.Show("");
delete_x_1000 += begin_ticks - assign_ticks;
}
std::cout << " assign " << assign_x_1000 << "ms"
<< " + delete " << delete_x_1000 << "ms"
<< " == " << (assign_x_1000 + delete_x_1000) << "ms";
}
{
StopWatch sw("vector iterator insert(end()) + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
test_container.clear();
}
}
{
StopWatch sw("vector iterator push_back() + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.push_back(*it);
}
test_container.clear();
}
}
{
StopWatch sw("vector.at() push_back() + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.push_back(random_vector.at(i));
}
test_container.clear();
}
}
{
StopWatch sw("vector[] push_back() + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.push_back(random_vector[i]);
}
test_container.clear();
}
}
{
StopWatch sw("vector iterator push_front() + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.push_front(*it);
}
test_container.clear();
}
}
{
StopWatch sw("vector at() push_front() + delete multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.push_front(random_vector.at(i));
}
test_container.clear();
}
}
{
StopWatch sw("vector[] push_front() + delete multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.push_front(random_vector[i]);
}
test_container.clear();
}
}
{
StopWatch sw("vector iterator insert at back + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(test_container.end(), *it);
}
test_container.clear();
}
}
{
StopWatch sw("vector at() insert at end + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.insert(test_container.end(), random_vector.at(i));
}
test_container.clear();
}
}
{
StopWatch sw("vector[] insert at end + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.insert(test_container.end(), random_vector[i]);
}
test_container.clear();
}
}
{
StopWatch sw("vector iterator insert at front + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it = random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(test_container.begin(), *it);
}
test_container.clear();
}
}
{
StopWatch sw("vector.at() insert at front + delete x multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.insert(test_container.begin(), random_vector.at(i));
}
test_container.clear();
}
}
{
StopWatch sw("vector[] insert at front + delete multiplier");
std::deque<kvstruct> test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(unsigned i=0; i<nelts; ++i) {
test_container.insert(test_container.begin(), random_vector[i]);
}
test_container.clear();
}
}
}
// deque traversal
{
std::deque<kvstruct> test_container;
test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
long long sum;
sum = 0;
{
StopWatch sw("traverse deque (at) x 1000");
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<nelts; ++i) {
sum += test_container.at(i).value;
}
}
}
rc &= (sum != 0);
sum = 0;
{
StopWatch sw("traverse deque (subscript) x 1000");
for(unsigned j=0; j<1000; ++j) {
for(unsigned i=0; i<nelts; ++i) {
sum += test_container[i].value;
}
}
}
rc &= (sum != 0);
sum = 0;
{
StopWatch sw("traverse deque iterator x 1000");
for(unsigned j=0; j<1000; ++j) {
for(auto it=test_container.begin(); it!=test_container.end(); ++it) {
sum += it->value;
}
}
}
rc &= (sum != 0);
}
// deque sort
{
std::deque<kvstruct> sorted_container;
{
StopWatch sw("std::sort() deque build + delete x 100");
for(unsigned j=0; j<100; ++j) {
sorted_container = random_container;
std::sort(sorted_container.begin(), sorted_container.end());
}
}
{
StopWatch sw("std::sort() sorted deque x 100");
for(unsigned j=0; j<100; ++j) {
std::sort(sorted_container.begin(), sorted_container.end());
}
}
rc &= (sorted_container.size() == random_vector.size());
// std::stable_sort() deque
{
StopWatch sw("std::stable_sort() deque + build + delete x 100");
for(unsigned j=0; j<100; ++j) {
sorted_container = random_container;
std::stable_sort(sorted_container.begin(), sorted_container.end());
}
{
StopWatch sw("std::stable_sort() sorted deque x 100");
for(unsigned j=0; j<100; ++j) {
std::stable_sort(sorted_container.begin(), sorted_container.end());
}
}
rc &= (sorted_container.size() == random_vector.size());
}
// lookup
{
std::deque<kvstruct> sorted_container;
sorted_container = random_container;
std::sort(sorted_container.begin(), sorted_container.end());
StopWatch sw("lookup in sorted vector x 100");
std::deque<kvstruct>::iterator kp;
for(unsigned j=0; j<100; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
kp = std::lower_bound(
sorted_container.begin(),
sorted_container.end(),
*it
);
if(kp != sorted_container.end() && *it < *kp) {
kp = sorted_container.end();
}
}
}
rc &= (kp != sorted_container.end());
}
}
return rc;
}
map.cpp
#include "kvstruct.h"
#include "charbuf.h"
#include "stopwatch11.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
bool test_map(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
bool rc = true;
std::size_t const nelts = random_vector.size();
std::cout << std::endl << "std::map " << random_vector.size() << " entries" << std::endl
<< " multiplier=" << multiplier << std::endl << std::endl;
using ContainerT = std::map<charbuf<9>, unsigned>;
using value_type = ContainerT::value_type;
ContainerT random_container;
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
random_container.insert(random_container.end(), value_type(it->key, it->value));
}
rc &= random_container.size() == nelts;
// map insert and delete
{
StopWatch::tick_t begin_ticks = 0;
StopWatch::tick_t assign_ticks = 0;
StopWatch::tick_t assign_x_1000 = 0;
StopWatch::tick_t delete_x_1000 = 0;
{
StopWatch sw("assign map to map + delete x multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
test_container = random_container;
assign_ticks = sw.Show("");
assign_x_1000 += assign_ticks - begin_ticks;
test_container.clear();
begin_ticks = sw.Show("");
delete_x_1000 += begin_ticks - assign_ticks;
}
std::cout << " assign " << assign_x_1000 << "ms"
<< " + delete "
<< delete_x_1000 << "ms"
<< "=="
<< (assign_x_1000 + delete_x_1000)
<< "ms" << std::endl;
}
{
StopWatch sw("vector iterator insert to map + delete x multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
test_container.clear();
}
}
std::vector<kvstruct> sorted_vector = random_vector;
std::stable_sort(sorted_vector.begin(), sorted_vector.end());
{
StopWatch sw("sorted vector iterator insert into map + delete x multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=sorted_vector.begin(); it!=sorted_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
test_container.clear();
}
}
{
StopWatch sw("sorted vector iterator insert into map w/end hint + delete x multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=sorted_vector.begin(); it!=sorted_vector.end(); ++it){
test_container.insert(test_container.end(), value_type(it->key, it->value));
}
test_container.clear();
}
}
{
StopWatch sw("sorted vector iterator insert into map w/C++98 preceeder hint + delete x multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
auto hint = test_container.end();
for(auto it=sorted_vector.begin(); it!=sorted_vector.end(); ++it) {
hint = test_container.insert(hint, value_type(it->key, it->value));
}
}
test_container.clear();
}
{
StopWatch sw("sorted vector iterator insert into map w/ reverse iterator follow hint + delete x multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
auto hint = test_container.end();
for(auto it=sorted_vector.rbegin(); it!=sorted_vector.rend(); ++it) {
hint = test_container.insert(hint, value_type(it->key, it->value));
}
test_container.clear();
}
}
}
// map traversal
ContainerT test_container = random_container;
{
unsigned long long sum;
sum = 0;
{
StopWatch sw("traverse map (iterator) x multiplier");
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=test_container.begin(); it!=test_container.end(); ++it) {
sum += it->second;
}
}
}
rc &= (sum != 0);
}
// map lookup
{
StopWatch sw("map lookup x 100");
for(unsigned j=0; j<100; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
rc &= (test_container.find(it->key) != test_container.end());
if(test_container.find(it->key) == test_container.end()) {
std::cout << "error on key " << it->key << std::endl;
}
}
}
}
return rc;
}
unordered_map.cpp
#include "charbuf.h"
#include "kvstruct.h"
#include "stopwatch11.h"
#include <iostream>
#include <vector>
#include <unordered_map>
// show properties of a std::unordered_map
template <typename T>
void hash_stats(T const& table) {
unsigned zeros = 0;
unsigned ones = 0;
unsigned many = 0;
unsigned many_sigma = 0;
for(unsigned i=0; i<table.bucket_count(); ++i) {
unsigned how_many_this_bucket = 0;
for(auto it=table.begin(i); it!=table.end(i); ++it) {
how_many_this_bucket += 1;
}
switch (how_many_this_bucket) {
case 0:
zeros += 1;
break;
case 1:
ones += 1;
break;
default: {
many += 1;
many_sigma += how_many_this_bucket;
}
break;
}
}
std::cout << "unordered_map with " << table.size() << " entries" << std::endl
<< " " << table.bucket_count() << " buckets"
<< " load factor " << table.load_factor()
<< ", max load factor " << table.max_load_factor() << std::endl;
if(many > 0) {
std::cout << " average length of multi-entry chain " <<((float)many_sigma)/many
<< std::endl;
}
}
// Performance tests for std::unordered_map
bool test_unordered_map(std::vector<kvstruct> const& random_vector, unsigned long multiplier) {
bool rc = true;
std::size_t const nelts = random_vector.size();
std::cout << std::endl << "std::unordered_map " << random_vector.size() << " entries"
<< std::endl << "multiplier == " << multiplier << std::endl << std::endl;
struct hash_charbuf {
std::size_t operator()(charbuf<9> const& cb) const {
return (size_t)cb;
}
};
using ContainerT = std::unordered_map<charbuf<9>, unsigned, hash_charbuf>;
using value_type = ContainerT::value_type;
ContainerT random_container;
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it){
random_container.insert(random_container.end(), value_type(it->key, it->value));
}
rc &= (random_container.size() == nelts);
// unordered_map insert and delete
{
StopWatch::tick_t begin_ticks = 0;
StopWatch::tick_t assign_ticks = 0;
StopWatch::tick_t assign_x_1000 = 0;
StopWatch::tick_t delete_x_1000 = 0;
{
StopWatch sw("assign unordered_map to unordered_map + delete x multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
test_container = random_container;
assign_ticks = sw.Show("");
assign_x_1000 += assign_ticks - begin_ticks;
test_container.clear();
begin_ticks = sw.Show("");
delete_x_1000 += begin_ticks - assign_ticks;
}
}
std::cout << " assign " << assign_x_1000 << "ms"
<< " + delete "
<< delete_x_1000 << "ms"
<< " == " << (assign_x_1000 + delete_x_1000)
<< "ms" << std::endl;
{
ContainerT test_container;
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
std::cout << "test container, no optimization.";
hash_stats(test_container);
}
{
ContainerT test_container;
test_container.max_load_factor(2.0f);
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
std::cout << "initially set to 100k buckets.";
hash_stats(test_container);
}
{
ContainerT test_container;
test_container.rehash(random_vector.size());
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
std::cout << "initially set to 100k buckets.";
hash_stats(test_container);
}
{
StopWatch sw("vector iterator insert into unordered_map + delete multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
test_container.clear();
}
}
{
StopWatch sw("vector iterator insert into unordered_map w/ pre-allocation + delete x multiplier");
ContainerT test_container;
for(unsigned j=0; j<multiplier; ++j) {
test_container.rehash(random_vector.size()*5);
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
test_container.clear();
}
}
{
StopWatch sw("vector iterator insert into unordered_map w/ max 0.8 + delete x multiplier");
ContainerT test_container;
test_container.max_load_factor(0.5f);
for(unsigned j=0; j<multiplier; ++j) {
test_container.rehash(random_vector.size() * 5);
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
test_container.max_load_factor(1.0f);
test_container.rehash(1);
test_container.clear();
}
}
ContainerT test_container = random_container;
// unordered_map traversal
{
unsigned long long sum;
sum = 0;
{
StopWatch sw("traversal unordered_map (iterator) x multiplier");
for(unsigned j=0; j<multiplier; ++j) {
for(auto it=test_container.begin(); it!=test_container.end(); ++it) {
sum += it->second;
}
}
}
rc &= (sum != 0);
}
// unordered_map lookup
{
ContainerT test_container;
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
hash_stats(test_container);
{
StopWatch sw("unordered_map lookup x 100");
for(unsigned j=0; j<100; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++j) {
rc &= (test_container.find(it->key) != test_container.end());
if(test_container.find(it->key) == test_container.end()) {
std::cout << "error on key " << it->key << std::endl;
}
}
}
}
test_container.clear();
test_container.rehash(random_vector.size());
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
test_container.insert(value_type(it->key, it->value));
}
hash_stats(test_container);
{
StopWatch sw("unordered_map lookup, preallocated table x 100");
for(unsigned j=0; j<100; ++j) {
for(auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
rc &= (test_container.find(it->key) != test_container.end());
if(test_container.find(it->key) == test_container.end()) {
std::cout << "error on key " << it->key << std::endl;
}
}
}
}
}
}
return rc;
}
stl_list_test.cpp
#include "stopwatch11.h"
#include "kvstruct.h"
#include "test_driver.h"
#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <functional>
#include <set>
#include <list>
void build_random_vector(std::vector<kvstruct>& v, unsigned count) {
std::set<unsigned> unique;
std::default_random_engine e;
// 从count 到 10*count的均匀分布
std::uniform_int_distribution<unsigned> d(count, 10* count);
auto randomizer = std::bind(d, e);
v.clear();
while(v.size() < count) {
unsigned rv = randomizer();
// 新元素插入
if(unique.insert(rv).second == true) {
v.emplace_back(rv);
}
}
}
bool test_vector(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_deque(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_list(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_forward_list(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_map(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
bool test_unordered_map(std::vector<kvstruct> const& random_vector, unsigned long multiplier);
int test_stl(int test_no, unsigned long multiplier) {
bool rc = true;
unsigned long table_size = 100000;
switch (test_no) {
default:
return -1;
case 0:
return 2;
case 1: // 测试kvstruct的各个方法和操作符是否工作
{
// 验证10进制转16进制成功
char buf[9];
rc &= (strcmp(kvstruct::stringify(0, buf), "0") == 0);
rc &= (strcmp(kvstruct::stringify(0x123, buf), "123") == 0);
rc &= (strcmp(kvstruct::stringify(0x1000, buf), "1000") == 0);
rc &= (strcmp(kvstruct::stringify(0xffffffff, buf), "FFFFFFFF") == 0);
// 测试build_random_vector返回的值都是唯一的
std::vector<kvstruct> rnd_vector;
build_random_vector(rnd_vector, 100);
std::sort(rnd_vector.begin(), rnd_vector.end());
for(unsigned i=1; i<rnd_vector.size(); ++i) {
rc &= (rnd_vector[i-1].key < rnd_vector[i].key);
}
}
break;
case 2:
{
std::vector<kvstruct> rnd_vector;
build_random_vector(rnd_vector, table_size);
rc &= test_vector(rnd_vector, multiplier);
rc &= test_deque(rnd_vector, multiplier);
rc &= test_list(rnd_vector, multiplier);
rc &= test_forward_list(rnd_vector, multiplier);
rc &= test_map(rnd_vector, multiplier);
rc &= test_unordered_map(rnd_vector, multiplier);
}
break;
}
return rc ? 1: 0;
}
int main(int argc, char* argv[]) {
test_driver(test_stl, argc, argv);
return EXIT_SUCCESS;
}
test_driver.cpp
#include "test_driver.h"
#include "priority_thread.h"
#include <iostream>
#include <cstring>
// 运行多少 千 次
// 默认1*1000
// 参数通过 ./xxx_test -x2 传入
void test_driver(test_func* flist, int argc, char** argv) {
unsigned long multiplier = 1;
if(argc > 1) {
// 第一个参数的前面两个是 -x，例如 ./xxxx_test -x3
if(strncmp(argv[1], "-x", 2) == 0) {
// 从 -x后面的数字开始，转换成ulong
multiplier = strtoul(argv[1]+2, nullptr, 10);
}
}
// 测试函数列表为空，多个函数
if(flist == nullptr) {
std::cout << "No test function" << std::endl;
} else {
std::cout << "multiplier set to " << multiplier << std::endl;
// 进程拉到前台
PriorityThread p;
// 逐个执行flist中的函数
for(unsigned f=0; flist[f]!=0; ++f) {
if(flist[f] == nullptr) {
continue;
}
// 执行测试合集， 合集的测试号为1， 0返回所有测试个数，2-end是单个测试
if(flist[f](1, multiplier) == 1) {
std::cout << "All tests pass" << std::endl;
} else {
std::cout << "Tests failed" << std::endl;
}
for(int i=2, e=flist[f](0, multiplier); i<=e; ++i) {
if(flist[f](i, multiplier) != 1) {
std::cout << "test " << i << " failed" << std::endl;
}
}
}
}
}
void test_driver(test_func f, int argc, char** argv) {
unsigned long multiplier = 1;
if(argc > 1) {
if(strncmp(argv[1], "-x", 2) == 0) {
multiplier = strtoul(argv[1]+2, nullptr, 10);
}
}
if(f == nullptr) {
std::cout << "no test function" << std::endl;
} else {
std::cout << "multiplier set to: " << multiplier << std::endl;
PriorityThread p;
if(f(1, multiplier) == 1) {
std::cout << "all tests pass" << std::endl;
} else {
std::cout << "tests failed" << std::endl;
}
for(int i=2, e=f(0, multiplier); i<=e; ++i) {
if(f(i, multiplier) != 1) {
std::cout << "test " << i << " failed" << std::endl;
}
}
}
}
priority_thread.cpp
#include "priority_thread.h"
#include <iostream>
PriorityThread::PriorityThread() {
// 设置当前进程nice值为最低，设置为最高优先级进程
nice(-20);
// 获取当前线程优先级，并保存为老的优先级参数，后续在析构函数中好进行恢复
pthread_getschedparam(pthread_self(), &policy, ¶m);
old_priority = param.sched_priority;
// 设置当前线程优先级为最高优先级
param.sched_priority = sched_get_priority_max(policy);
pthread_setschedparam(pthread_self(), policy, ¶m);
}
PriorityThread::~PriorityThread() {
// 析构函数中恢复当前进程和线程的优先级
// 设置当前nice值为最高，降低优先级
nice(19);
// 恢复当前线程优先级为普通优先级
param.sched_priority = old_priority;
pthread_setschedparam(pthread_self(), policy, ¶m);
}
程序输出如下，如果是考虑各种方法的插入，删除,查找和相关效率来优化算法的话，这个数据还是可以参考一下的。
image.png
网友评论