Carbon's Blog

以梦为马 不负韶华


  • 首页

  • 标签

  • 分类

  • 归档

  • 搜索

C++ 内存数据结构与二进制文件之间的序列化和反序列化

发表于 2018-04-10 | 更新于: 2018-04-11 | 分类于 Backend Development

应用场景

许多后端检索server启动时候需要从文件加载到内存中构建索引,这个过程往往会消耗比较多的时间,这样会造成sever启动消耗比较多的时间,在存在多台服务器的时候会更加明显。
我们可以将够构建索引的过程独立成一个单独的进程,此进程实现的功能是根据原始文件构建索引结构,并将索引结构序列化到本地二进制文件,Server在启动的时候只需要读取二进制文件就可以构造出索引结构,可以大大提高启动速度。

示例代码

io.hpp ,对std::ifstream 以及std::ofstream 的封装,提供从vector序列化到二进制文件和从二进制文件反序列化到vector等接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#ifndef IO_HPP
#define IO_HPP

#include <string>
#include <vector>
#include <fstream>

class FileReader
{
public:
FileReader(const std::string& filename)
: input_stream(filename,std::ios::binary)
{
}

/* Read count objects of type T into pointer dest */
template <typename T> void ReadInto(T *dest, const std::size_t count)
{
static_assert(std::is_trivially_copyable<T>::value,
"bytewise reading requires trivially copyable type");

if (count == 0)
return;

const auto &result = input_stream.read(reinterpret_cast<char *>(dest), count * sizeof(T));
const std::size_t bytes_read = input_stream.gcount();

if (bytes_read != count * sizeof(T) && !result)
{
return;
}
}

template <typename T> void ReadInto(std::vector<T> &target)
{
ReadInto(target.data(), target.size());
}

template <typename T> void ReadInto(T &target)
{
ReadInto(&target, 1);
}

template <typename T> T ReadOne()
{
T tmp;
ReadInto(tmp);
return tmp;
}

std::uint32_t ReadElementCount32()
{
return ReadOne<std::uint32_t>();
}
std::uint64_t ReadElementCount64()
{
return ReadOne<std::uint64_t>();
}

template <typename T> void DeserializeVector(std::vector<T> &data)
{
const auto count = ReadElementCount64();
data.resize(count);
ReadInto(data.data(), count);
}

private:
std::ifstream input_stream;
};

class FileWriter
{
public:
FileWriter(const std::string& filename)
: output_stream(filename,std::ios::binary)
{
}

/* Write count objects of type T from pointer src to output stream */
template <typename T> void WriteFrom(const T *src, const std::size_t count)
{
static_assert(std::is_trivially_copyable<T>::value,
"bytewise writing requires trivially copyable type");

if (count == 0)
return;

const auto &result =
output_stream.write(reinterpret_cast<const char *>(src), count * sizeof(T));
}

template <typename T> void WriteFrom(const T &target)
{
WriteFrom(&target, 1);
}

template <typename T> void WriteOne(const T tmp)
{
WriteFrom(tmp);
}

void WriteElementCount32(const std::uint32_t count)
{
WriteOne<std::uint32_t>(count);
}
void WriteElementCount64(const std::uint64_t count)
{
WriteOne<std::uint64_t>(count);
}

template <typename T> void SerializeVector(const std::vector<T> &data)
{
const auto count = data.size();
WriteElementCount64(count);
return WriteFrom(data.data(), count);
}

private:
std::ofstream output_stream;
};

#endif

binary_io.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "io.hpp"
#include <iostream>

struct Data
{
int a;
double b;

friend std::ostream& operator<<(std::ostream& out,const Data& data)
{
out << data.a << "," << data.b;
return out;
}
};

template<typename T>
void printData(const std::vector<T>& data_vec)
{
for (const auto data : data_vec)
{
std::cout << "{" << data << "} ";
}
std::cout << std::endl;
}
template<typename T>
void serializeVector(const std::string& filename,const std::vector<T>& data_vec)
{
FileWriter file_writer(filename);
file_writer.SerializeVector<T>(data_vec);
}

template<typename T>
void deserializeVector(const std::string& filename,std::vector<T>& data_vec)
{
FileReader file_reader(filename);
file_reader.DeserializeVector<T>(data_vec);
}

int main()
{
std::vector<Data> vec1 = {{1,1.1},{2,2.2},{3,3.3},{4,4.4}};
std::cout << "before write to binary file.\n";
printData(vec1);
const std::string filename = "vector_data";
std::cout << "serialize vector to binary file.\n";
serializeVector<Data>(filename,vec1);
std::vector<Data> vec2;
deserializeVector<Data>(filename,vec2);
std::cout << "vector read from binary file.\n";
printData(vec2);
return 0;
}

编译代码

1
g++ -std=c++11 binary_io.cpp -o binary_io

执行程序

1
./binary_io

执行结果
执行结果
程序将内存中vector 数据写入二进制文件,并从二进制文件中反序列化到一个新的vector。可以看到序列化前和序列化后的结果一致。

注意

序列化到文件的数据结构需要满足 is_trivially_copyable。std::is_trivially_copyable 在c++11 引入,TriviallyCopyable类型对象有以下性质

每个拷贝构造函数是trivial 或者是deleted
每个移动构造函数是trivial 或者是deleted
每个拷贝赋值运算符是trivial 或者是deleted
每个移动赋值运算符是trivial 或者是deleted
以上至少有一个是non-deleted
析构函数是trivial 并且non-deleted

对于is_trivially_copyable 类型对象的性质,解释如下

Objects of trivially-copyable types are the only C++ objects that may be safely copied with std::memcpy or serialized to/from binary files with std::ofstream::write()/std::ifstream::read(). In general, a trivially copyable type is any type for which the underlying bytes can be copied to an array of char or unsigned char and into a new object of the same type, and the resulting object would have the same value as the original

只有满足trivially-copyable的对象才可以保证序列化到二进制文件后, 从二进制文件反序列化到内存后的值保持不变。

LRU Cache 解析及实现

发表于 2018-04-02 | 更新于: 2018-09-04 | 分类于 Backend Development

LRU Cache 原理

LRU是Least Recently Used 的缩写,是一种缓存替换算法,当系统中的缓存满时,通过删除最近最少使用的元素来填充新的内容。LRU 算法在操作系统中有广泛应用,如CPU与物理内存之间的Cache替换算法, 物理内存与硬盘之间Cache替换算法。

LRU Cache 实现

我们可以使用一个双向链表和hash map 实现LRU Cache,其中hash map 存储缓存的内容,hash map 的value 存储指向双向链表节点的指针,双向链表存储缓存的内容,当有节点被加入时,该节点放到双向列表的头部,当访问已经存在的节点时,把该节点移动到双向链表头部,当双向链表满时,删除双向链表最后一个元素。简单的讲,双向链表的作用是记录缓存内容的使用顺序。

C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/*************************************************************************
> File Name: lru_cache_template.hpp
> Author: ce39906
> Mail: ce39906@163.com
> Created Time: 2018-04-02 16:44:58
************************************************************************/
#ifndef LRU_CACHE_TEMPLATE_HPP
#define LRU_CACHE_TEMPLATE_HPP
#include <unordered_map>

template <class Key,class Value>
struct Node
{
Node(Key k,Value v) :
key(k), value(v), prev(NULL), next(NULL)
{
}

Node()
{
}

Key key;
Value value;
Node* prev;
Node* next;
};

template <class Key, class Value>
class LruCache
{
public:

LruCache(int capacity) :
size_(0), capacity_(capacity)
{
head = new Node<Key,Value>;
tail = new Node<Key,Value>;
head->next = tail;
head->prev = NULL;
tail->next = NULL;
tail->prev = head;
container_.clear();
};

~LruCache()
{
while(head)
{
Node<Key,Value>* temp = head->next;
delete head;
head = temp;
}
};

void Put(Key key ,Value value)
{
//insert
if (container_.find(key) == container_.end())
{
//not full
if (size_ != capacity_)
{
Node<Key,Value>* data = new Node<Key,Value>(key,value);
attach(data);
container_.insert(std::make_pair(key,data));
size_++;
}
else
{
Node<Key,Value>* temp = tail->prev;
container_.erase(temp->key);
detach(temp);
if (temp)
delete temp;
Node<Key,Value>* data = new Node<Key,Value>(key,value);
attach(data);
container_.insert(std::make_pair(key,data));
}
}
else //update
{
Node<Key,Value>* data = container_[key];
detach(data);
if (data)
delete data;
data = new Node<Key,Value>(key,value);
container_[key] = data;
attach(data);
}
}

Value Get(Key key)
{
//find
if (container_.find(key) != container_.end())
{
Node<Key,Value>* data = container_[key];
detach(data);
attach(data);
return data->value;
}
else // not find
{
return Value();
}
}

private:

int size_;
int capacity_;
std::unordered_map<Key,Node<Key,Value>*> container_;
Node<Key,Value>* head;
Node<Key,Value>* tail;

void attach(Node<Key,Value>* node)
{
Node<Key,Value>* temp = head->next;
head->next = node;
node->next = temp;
node->prev = head;
temp->prev = node;
}

void detach(Node<Key,Value>* node)
{
node->prev->next = node->next;
node->next->prev = node->prev;
}
};

#endif

C++ Thread Pool 使用解析

发表于 2018-03-29 | 更新于: 2018-03-29 | 分类于 Backend Development

boost::threadpool

按照boost标准开发的第三方库。下载地址在boost::threadpool 使用方法较为简单。例子如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include "boost/bind.hpp"
#include "boost/threapool.hpp"
using namespace std;
using namespace threadpool;
void first_task()
{
cout << "first task" << endl;
}
void second_task()
{
cout << "second task" << endl;
}
void task_with_parameter(int value,string str)
{
cout << "task with parameter,value is: " << value <<",str is: " << str;
}
int main()
{
// 声明线程池
pool thread_pool(2);
// 向线程池中添加任务
thread_pool.schedule(&first_task);
// 等待线程函数执行完成
thread_pool.wait();
thread_pool.schedule(&second_task);
thread_pool.schedule(boost::bind(task_with_parameter,8,"hello"));
thread_pool.wait();
return 0;
}

boost::threadpool 添加任务,同步方式都相对简单,在添加多参数的任务时候需要注意 boost::bind() 传递的参数是按照拷贝的方式传递的。如果想使用引用的方式传递的话,需要使用boost::ref() 或者boost::cref()。还有需要注意的是boost::bind()最多接受九个参数
boost::threadpool 是相对比较老的一个库,在2005-2008年间更新

boost::thread_group 以及io_service

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <boost/asio/io_service.hpp>
#include <boost::bind.hpp>
#include <boost::thread/thread_group.hpp>

boost::asio::io_service ioService;
boost::thread_group threadpool;
/*The work class is used to inform the io_service when
work starts and finishes. This ensures that the
io_service object's run() function will not exit
while work is underway, and that it does exit when
there is no unfinished work remaining
*/
/* 声明一个ioService work 的原因是为了保证io service
的run方法在这个work销毁之前不会退出
*/
boost::asio::io_service::work work(ioService);
// 放在for循环中,根据线程池中线程中个数创建
// ioService 可以理解为任务队列
//Run the io_service object's event processing loop.
threadpool.create_thread(boost::bind(&boost::asio::ioservice::run,&ioService));
threadpool.create_thread(boost::bind(&boost::asio::ioservice::run,&ioService));
// 向ioService 中提交任务
ioService.post(boost::bind(myTask,"hello world"));
ioService.post(boost::bind(myTask2,"clear"));
...
// ioService 在stop 之后,post到ioService中的task 都不会被执行
ioService.stop();
threadpool.join_all();

boost::ioservice 以及 boost::thread_pool 实现的thread pool没有提供wait() 方法,因此需要调用者主动判断所提交的任务有没有完成

基于c++11 实现的线程池

主要步骤如下:

  • 设定线程池中所提供的服务线程数

    1
    int threads = thread::hardware_concurrency();
  • 每个线程都应该执行一个无限循环,无限循环中等待新任务到达,并执行任务

    1
    2
    3
    4
    5
    vector<thread> pool;
    for (int i = 0; i < threads; i++)
    {
    pool.push_back(thread(Infinite_loop_function));
    }
  • 无限循环function

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    while(true)
    {
    {
    unique_lock<mutex> lock(queue_mutex);
    condition.wait(lock,[]{return !Queue.empty()});
    Task = Queue.front();
    Queue.pop();
    }
    Task();
    }
  • 向任务队列中添加任务

    1
    2
    3
    4
    5
    6
    7
    8
    void enqueue(function<void()> new_task)
    {
    {
    unique_lock<mutex> lock(queue_mutex);
    Queue.push(new_task);
    }
    condition.notify_one();
    }

具体实现例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class ThreadPool {
public:
ThreadPool(size_t threads) : stop(false)
{
for(size_t i = 0;i<threads;++i)
workers.emplace_back(
[this]
{
for(;;)
{
std::function<void()> task;
{
std::unique_lock<std::mutex> lock(this->queue_mutex);
this->condition.wait(lock,
[this]{ return this->stop || !this->tasks.empty(); });
if(this->stop && this->tasks.empty())
return;
task = std::move(this->tasks.front());
this->tasks.pop();
}
task();
}
}
);
}
// add new work item to the pool
void enqueue(std::function<void()>& task)
{
{
std::unique_lock<std::mutex> lock(queue_mutex);

// don't allow enqueueing after stopping the pool
if(stop)
throw std::runtime_error("enqueue on stopped ThreadPool");

tasks.emplace(task);
}
condition.notify_one();
}
~ThreadPool()
{
{
std::unique_lock<std::mutex> lock(queue_mutex);
stop = true;
}
condition.notify_all();
for(std::thread &worker: workers)
worker.join();
}
private:
std::vector< std::thread > workers;
// the task queue
std::queue< std::function<void()> > tasks;

// synchronization
std::mutex queue_mutex;
std::condition_variable condition;
bool stop;
};

总结

从线程池的实现可以看到,线程在任务队列中获取任务以及向任务队列中提交任务都需要抢占队列的互斥锁,会造成时间损耗,尤其在任务数多,每个任务需要的时间不是很长的情况下,抢占任务队列互斥锁的时间损耗就显得更加明显。例如,在16核机器,线程池开启14个线程,向线程池中提交2000个task(每个task耗时1ms 左右)的情况下,向线程池提交任务所需时间约20ms。
因此,线程池的方式更适合每个task消耗的时间比较长,任务数不是特别多的场景

Boost Spirit

发表于 2018-03-28 | 更新于: 2018-08-01 | 分类于 Backend Development

What is boost spirit

boost spirit is an object-oriented,recursive-descent parser and output generation library for C++.It allows you to write grammars and format descripting using a format similar to Extended Backs Naur Form(EBNF) directly in C++.

The figure below shows the overall structure of Boost Spirit library.

image

The three components Qi,Kama and Lex are designed to be used either stand alone or together. The general methodology is to use the token sequence generated by Lex as the input for a parser generated by Qi. On the opposite side of the equation,the hierarchical data structures generated by Qi are used for the output generators created using Kama.

The place of Spirit.Qi and Spirit.Kama in a data transformation flow of a typical application.

image

Qi- Writing Parsers

Spirit.Qi is designed to be a practical parsing tool. Scanf ,boost::regex or boost::tokenizer do not scale well when we need to write more elaborate parsers.

Examples

Example #1 parsing a number

Create a parser that will parse a floating-point number.

1
double_

Example #2 parsing 2 numbers

Create a parser that will accept a line consisting of 2 floating-point numbers.

1
double_ >> double_

Example #3 parsing zero or more numbers

Create a parser that will accept zero or more floating-point numbers.

1
*double_

Example #4 parsing a comma-delimited list of numbers

This example will create a parser that accepts a comma-delimited list of numbers.

1
double_ >> *(char_(',') >> double_)

Notice char_(‘,’) is a literal charcter parser that can recognize the comma ‘,’.

Let’s Parse

We are done with defining the parser.So the next step is invoking this parser to do its work.Here we will use phrase_parse function. One overload of this function accepts four arguments.

  1. iterator pointing to the start of the input.
  2. iterator pointing to the end of the input.
  3. parser object
  4. another parser called the skip parser
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename Iterator>
bool parse_numbers(Iterator first, Iterator last)
{
using qi::double_;
using qi::phrase_parse;
using ascii::space;

bool r = pharse_parse(
first,
last,
double_ >> *(',' >> double_),
space
);
if (fisrt != last)
return false;
return r;
}

Parser Semantic Actions

The previous example was very simple.It only recognized data,but did noting with it.Now we want to extract information from what was parsed.
Semantic actions may be attached to any point in the grammar specification. These functions are C++ functions or function objects that are called whenever a part of the parser successfully recognizes a portion of the input.

Example of Semantic Actions

  • using plain function pointer
  • using simple function object
  • using boost.bind with a plain function
  • using boost.bind with a member function
  • using boost.lambda

Such as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
namespace client
{
namespace qi = boost::qi;
// A plain function
void print(const int& i)
{
std::cout << i << std::endl;
}
// A member function
struct writer
{
void print(const int& i) const
{
std::cout << i << std::endl;
}

};
// A function object
struct print_action
{
void operator()(const int& i,qi::unset_type,qi::unset_type) const
{
std::cout << i << std::endl;
}
};
}

All examples parse inputs of the form:

1
"{integer}"

These below shows the usages

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using boost::spirit::qi::int_;
using boost::spirit::qi::parse;
using client::print;
using client::writer;
using clinet::print_action;

const char* fisrt = "{43}";
const char* last = first + std::strlen(first);

// example using plain function
parse(first,last,'{'>>int_[&print]>>'}');
// example using simple function object
parse(first,last,'{'>>int_[print_action()]>>'}');
// example using boost bind with a plain function
parse(fisrt,last,'{' >> int_[boost::bind(&print,_1)]>>'}');
// example using boost bind with a member function
parse(first,last,'{'>> int_[boost::bind(&writer::print,&w,_1)]>>'}');

// example using boost lambda
namespace lambda = boost::lambda;
using lambda::_1;
parse(first,last,'{' >> int_[std::cout << _1 << '\n'] >> '}');

Phoenix

Phoenix , a companion library bundled with Spirit. is sepcifically suited for binding semantic actions. It is like Boost.lambad on sterodis, with spiecial custom featrues that make it easy to inergrate semantic action with Spirit.

Complex - Our first complex parser

A parser that parses complex numbers.This time we are using Phoenix to do the semantic actions.
Here is a simple parser expression for complex numbers.

1
2
'(' >> double_ >> -(',' >> double_) >> ')' 
| double_

This parser can parse complex numbers of the form:

1
2
3
(123.22,2121.21)
(213.33)
212.33

This below shows example of action with phoniex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
namespace client
{
template<typename Iterator>
bool parse_complex(Iterator first,Iterator last,std::complex<double>& c)
{
using boost::spirit::qi::double_;
using boost::spirit::qi::_1;
using boost::spirit::qi::phrase_parse;
using boost::spirit::ascii::space;
using boost::phoenix::ref;

double rN = 0.0;
double iN = 0.0;
bool r = phrase_parse(
first,
last,
(
'(' >> double_[ref(rN) = _1]
>> -(',' >> double_[ref(iN) = _1]) >> ')'
| double_[ref(rN) = _1]
),
space
);
if (!r || first != last)
return false;
c = std::complex<double>(rN,iN);
return r;
}
}

Sum - adding numbers

Here is a parser that sums a comma-separated list of numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::spirit::phoenix;

using qi::double_;
using qi::_1;
using ascii::space;
using phoenix::ref;

template<typename Iterator>
bool adder(Iterator first,Iterator last,double& n)
{
bool r = qi::phrase_parse(
first,
last,
(
double_[ref(n) = _1] >> *(',' >> double_[ref(n) += _1])
),
space
);
if (fisrt != last)
return false;
return r;
}

Number List - stuffing numbers into a std::vector

This sample demonstrates a parser for a comma separated list of numbers. The numbers are inserted in a vector using phoenix.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename Iterator>
bool parse_numbers(Iterator fisrt,Iterator last,std::vector<double>& v)
{
using qi::double_;
using qi::phrase_parse;
using qi::_1;
using ascii::space;
using phoenix::push_back;
using phoenix::ref;

bool r = phrase_parse(
first,
last,
(
double_[push_back(ref(v),_1)] >>
*(',' >> double_[push_back(ref(v),_1)])
),
space
);
if(first != last)
return false;
return r;
}

Number List Redux - list syntax

So far, we’ve been using the syntax:

1
double_ >> *(',' >> double_)

to parse a comma-delimited list of numbers.Such lists are common in parsing and Spirit provides a simpler shortcut for them

1
double_ % ','

reads as a list of doubles separted by ‘,’.
The last example could be done as this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<typename Iterator>
bool parse_numbers(Iterator first,Iterator last,std::vector<double>& v)
{
using qi::double_;
using qi::phrase_parse;
using qi::_1;
using ascii::space;
using phoenix::push_back;
using phoenix::ref;

bool r = phrase_parse(
first,
last,
(
double_[ref(v),_1] % ','
),
space
);
if (first != last)
return false;
return r;

}

Number List Attribute - one more,with style

As we know,the double_ parser has a doubel attribute. All parsers have an attribute,even complex parsers.

Our parser

1
doubel_ % ','

has an attribute of std::vector.
So we can simply pass in a std::vector to our number of list parser.the overload of phrase_parse has five arguments:

  1. iterator pointing to start of the input
  2. iterator pointing to last of the input
  3. the parser object
  4. another parser called skip parser
  5. the parse’s attribute
1
2
3
4
5
6
7
8
9
bool r = phrase_parse(
first,
last,
(
double_ % ','
),
space,
v
);

Roman Numerals

This example demonstrates:

  • symbol table
  • rule
  • grammar

Symbol table

Each entry in a symbol table has an associated mutable data solt. In this regard, one can view the symbol table as an associative container of key-value pairs where the keys are strings.

Here is a parser for roman hundreds(100..900) using the symbol table. Keep in mind that the data associated with each slot is the parser’s attribute(which is passed to attached semantic actions).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct hundreds_ : qi::symbols<char, unsigned>
{
hundreds_()
{
add
("C",100)
("CC",200)
("CCC",300)
("CD",400)
("D", 500)
("DC", 600)
("DCC",700)
("DCCC",800)
("CM",900);
}
} hundreds;

we also can define tens ones symbol table.They are all parsers.

Rules

Up until now,we have been inlining our parser expressions, passing them directly to the phrase_parse function. The expression evalutes into a temporary,unnamed parser which is passed into the phrase_parse function, used and then destroyed. This is fine for small parsers. When the expressions get complicated, you’d want to break the expressions into smaller easier-to-understand pieces, name them, and refer to them from other expressions by name.

A parser expression can be assigned to what is called a “rule”.Threr are various ways to declare rules.The simplest form is :

1
2
3
4
5
6
7
8
rule<Iterator> r;
// this rule cannot used by phrase_parse function,
// it can only be used by parse function -- a version that does not do white space skipping.
// If you want to have it skip white spaces,you need to pass in the type skip parser.
rule<Iterator,Skipper> r;
rule<string::iterator,space_type> r;
// This type of rule can be used for both
// phrase_parse and parse.

There is one more rule form you should know about.

1
rule<Iterator,Signature,Skipper> r;

The Signature specifies athe attributes of the rule. Recall that the double_ parser has an attribute of double. To be precise, these are synthesized attributes.The parser “synthesized” the attribute value.Think of them as the function return value.

There is another type of attribute called “inherited” attribute. You can think them as function arguments. And,rightly so, the rule signature is a function signature .

After having declared a rule,you can now assign any parser expression to it. Example:

1
r = double_ >> *(',' >> double_);

Grammars

A grammar encapsulates one or more rules.It has the same template parameters as the rule.You can declare a grammar by:

  1. deriving a struct from the grammar class template
  2. declare one or more rules as member variables
  3. initialize the base grammar class by giving it the start rule(its the first rule that gets called when the grammar starts parsing)
  4. initalize your rules in your constrctor.

The rommon numeral grammar is a very nice and simple example of a grammar.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename Iterator>
struct roman :qi::grammar<Iterator,unsigned()>
{
roman() : roman::base_type(start)
{
using qi::eps;
using qi::lit;
using qi::_val;
using qi::_1;
using ascii::char_;

start = eps [_val = 0] >>
(
+lit('M') [_val += 1000]
|| hundreds [_val += _1]
|| tens [_val += _1]
|| ones [_val += _1]
)
}
qi::rule<Iterator,unsigned()> start;
}

  1. the grammar and start rule sinature is unsigned() it has a synthesized attribute(return value) of type unsigned whith on inherited attributeds(argumnents).
  2. roman::base_type is a typedef for grammar<Iterator,unsigned()>
  3. _val is another Phoenix placeholder representing the rule’s synthesized attribute
  4. eps is a special spirit parser that consumes no input but is always successful. We use it to initialize _val,the rule’s synthesized attribute, to zero before anything else. Using eps this way is good for doing pre and post initializations.
  5. the example a || b reads, match a or b and in sequence.That is if both a and b match, it must be in sequence; this is equivalen to a >> -b | b,but more efficient.

Usage

1
2
3
4
5
6
bool r = parse(iter,end,roman_parser,result);
if (r && iter == end)
{
std::cout << "Parse success.\n";
std::cout << "Result = " << result << std::endl;
}

Employee - Pasing into structs

This section shows how to parse and place the reult into a C++ struct.

fisrtly, let’s create a struct representing an employee.

1
2
3
4
5
6
7
struct employee
{
int age;
std::string surname;
std::string forename;
double salary;
};

now we will write a parser for our employee. Inputs will be of the form.

1
employee{ age,"surname","forename",salary }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template<typename Iterator>
struct employee_parser : qi::grammar<Iterator,employee(),ascii::space_type>
{
employee_parser():employee_parser::base_type(start)
{
using qi::int_;
using qi::lit;
using qi::double_;
using qi::lexeme;
using ascii::char_;

quoted_string %= lexeme['"' >> +(char_ - '"') >> '"'];

start %=
lit("employee")
>> '{'
>> int_ >> ','
>> quoted_string >> ','
>> quoted_string >> ','
>> double_
>> '}'
;
}
qi::rule<Iterator,std::string(),ascii::space_type> quoted_string;
qi::rule<Iterator,employee(),ascii::space_type> start;
};

Lexeme

1
lexeme['"' >>(char_ - '"') >> '"']

lexeme inhibits sapce skipping from the open brace to the closing space.The expression parses quoted strings.

1
+(char_ - '"')

parses one or more chars,except the double quote. It stops when it sees a double quote.

+a matches one or more,its attribute is a std::vector where A is the attribute of a .

Sequence Attribute

now what’s the attribute of

1
'"' >> (char_ - '"') >>'"'

1
2
3
a >> b >> c 
fusion::vector<A,B,C>
// is a tuple

Some parser,especially those very little parsers like ‘“‘ do not have attributes.
Nodes without attributes are disregarded.
so, ‘“‘ >> (char_ - ‘“‘) >>’”‘ ‘s attribue is

1
fusion::vector<std::vector<char>>

but there is one more collpase rule.if the attribute is followed by a single element fusion::vector, The element is stripped naked from its container. so the attribute come to this

1
std::vector<char>

Auto Rules

it is typical to see rules like

1
r = p[_val = _1]

if you have a rule definiton such as the above,where the attribute of the right hand side of the rule is compitable with the left hand side.then you can rewrite is as:

1
r %= p;

so

1
quoted_string %= lexeme['"' >> +( char_ -'"') >> '"'];

is simple version of

1
quoted_string = lexeme['"' >> + (char_ - '"') >> '"'][_val = _1];

Note: r %= p and r = p are equivalent if there are no semantic actions associated with p.

In case you are wondering, lit(“employee”) is the same as “employee”. We had to wrap it inside lit because immediately after it is >> ‘{‘. You can’t right-shift a char[] and a char - you know, C++ syntax rules.

Karma - Writing Generators

Spirit.Karma - what’s that?

Spirit.Karma is the counterpart to spirit.qi.
Some people say it’s the Yin to Spirit.Qi’s Yang. Spirit.karma is generating byte sequences from internal data structures as Spirit.Qi is parsing byte sequences into those internal data structures.

Why should you use a generator library for such a simple thing as output generation? Programmers have been using printf, std::stream formatting, or boost::format for quite some time. The answer is - yes, for simple output formatting tasks those familiar tools might be a quick solution. But experience shows: as soon as the formatting requirements are becoming more complex output generation is getting more and more challenging in terms of readability, maintainability, and flexibility of the code. Last, but not least, it turns out that code using Spirit.Karma runs much faster than equivalent code using either of the ‘straight’ methods mentioned above.

In terms of development simplicity and ease in deployment, the same is true for Spirit.Karma as has been described elsewhere in this documentation for Spirit.Qi: the entire library consists of only header files, with no libraries to link against or build. Just put the spirit distribution in your include path, compile and run. Code size? Very tight, essentially comparable to hand written code.

Examples

Trivial Example Generating a number

1
double_

Generating two numbers

1
double_ << double_

Generating one or more numbers

1
*double_

Generating a comma-delimited list of numbers

1
double_ << *(lit(',')) << double_

Let’s generate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename OutputIterator>
bool generate_numbers(OutputIterator& sink,std::list<double> const& v)
{
using karma::double_;
using karma::generate_delimited;
using ascii::space;

bool r = genated_delimited(
sink,
double_ << *(',' << double_),
v
);
return r;
}

OpenMp Tutorial

发表于 2018-03-28 | 更新于: 2018-03-29 | 分类于 Backend Development

What is openmp

easy multithreading programing for c++.

it is a simple C/C++/Fortran complier extension that allows to add parallelism into existing source code without significantly having to rewrite it.

Example

example for init an array

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include<vector>
int main()
{
vector<int> arr;
arr.reserve(1000);
#pargma omp parallel for
for(int i=0;i<1000;i++)
{
arr[i] = i * 2;
}
return 0;
}

you can compile it like this

g++ tmp.cpp -fopenmp

if you remove the #pragma lines,the result is still a valid C++ program that runs and dose the expected thing.
if the compiler encounters a #pragma that it dose not support,it will ignore it.

The syntax

the parallel construct

it creates a team of N threads(where N is the number of CPU cores by default) . after the statement, the threads join back into one.

1
2
3
4
5
#pragma omp parallel
{
// code inside thie region runs in parallel
printf("Hello\n");
}

Loop construct: for

the for construct splits the for-loop so that each thread in the current team handles a different portion of the loop

1
2
3
4
5
#pragma omp for
for(int n=0;n<10;++n)
{
printf(" %d",n);
}

Note:#pragma omp for onlt delegates portions of the loop for different threads in current team. a team is the group of threads excuting the program.At program start,the team only consists the main thread.
To create a new team of threads,you need to specify the parallel keyword

1
2
3
4
5
#pragma omp parallel
{
#pragma omp for
for(int n=0;n<10;n++) printf(" %d",n)
}

or use

1
#pragma omp parallel for

you can explicitly specify the number of threads to be created in the team. using num_threads

1
#pragma omp parallel for num_threads(3)

scheduling

The scheduling algorithm for the for-loop can explicity controlled

default

1
#pargma omp for schedule(static)

in the dynamic schedule,each thread ask the omp runtime library for an iteration number,then handles it.
the chunk size can also be specified to lessen the number of calls to the runtime library

1
#pargma omp parallel for schedule(dynamic,3)

the ordered clause

it is possible to force that certain events within the loop happen in a predicted order, using ordered clause

1
2
3
4
5
6
7
#pargma omp parallel for ordered shcedule(dynamic)
for(int n = 0;i < 100;i++)
{
files[n].compress();
#pragma omp ordered
send(files[n]);
}

the collapse clause

when you have nested loops.you can use collapse

1
2
3
4
5
6
7
8
#pargma omp parallel for collapse(2)
for(int i = 0;i < 10;i++)
{
for(int j = 0;j < 10;j++)
{
doSth();
}
}

section

sometimes,it is handy to indicate that “this and this can run in parallel” the sectiongs is just for that

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#pragma omp parallel sections
{
{
work1();
}
#pragma omp section
{
work2();
work3();
}
#pragma omp section
{
work4();
}
}

This code indicates that any of tasks work1,work2+work3,work4 can run in parallel.

Thread-safety

Atomicity

1
2
#pragma omp atomic
couter += value;

the atomic keyword in OpenMP specifies that denoted action happens atomically.

atomic read expression

1
2
#pragma omp atomic read
var = x;

atomic write expression

1
2
#pragma omp atomic write
x = expr;

atomic update expression

1
2
3
#pragma omp atomic update
++x;--x;x++;x--;
+=,-= ...

atomic capture expression

capture expression combine the read and update features

1
2
#pragma omp atomic capture
var = x++;

the critical construct

the critical construct restricts the execution of the associated statement / block to a single thread at a time

1
2
3
4
#pragma omp critical
{
doSth();
}

Note:the critical section names are global to the entire program.

locks

The openmp runtime library provides a lock type,omp_lock_t in omp.h
the lock type has five manipulator functions

omp_init_lock : initializes the lock
omp_destory_lock : the lock must be unset before the call
omp_set_lock: get the lock
omp_unset_lock: release the lock
omp_test_lock: attempts to set the lock.if the lock is already set by another thread it returns 0;if it managed to set the lock,it return 1

the flush directive

Even when variables used by threads are supposed to be shared,the compiler may take liberties and optimize them as register variables. This can skew concurrent observations of variable. The flush directive can be used to forbid this.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*first thread*/
b=1;
#pragma omp flush(a,b)
if(a == 0)
{
/* critical section*/

}
/*second thread*/
a = 1;
#pragma omp flush(a,b)
if(b==0)
{
/* critical section*/
}

Controlling which data to share between threads

1
2
3
4
5
6
7
int a,b =0;
#pragma omp parallel for private(a) shared(b)
for(a=0;a<50;++a)
{
#pragma omp atomic
b += a;
}

a is private(each thread has their own copy of it) and b is shared(each thread accesses the same variable)

the difference between private and firstprivate
private does not copy the value of the variable that was in the surrounding context.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<string>
#include<iostream>
int main()
{
std::string a = "x",b="y";
#pragma omp parallel private(a,c) shared(b) num_threads(2)
{
a+="k";
c+= 7;
std::cout << "A is " << a <<", b is "<< b;
}

}
// eaquls this below
OpenMP_thread_fork(2);
{ // Start new scope
std::string a; // Note: It is a new local variable.
int c; // This too.
a += "k";
c += 7;
std::cout << "A becomes (" << a << "), b is (" << b << ")\n";
} // End of scope for the local variables
OpenMP_join();

If you actually need a copy of the original value, use the firstprivate clause instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <string>
#include <iostream>

int main()
{
std::string a = "x", b = "y";
int c = 3;

#pragma omp parallel firstprivate(a,c) shared(b) num_threads(2)
{
a += "k";
c += 7;
std::cout << "A becomes (" << a << "), b is (" << b << ")\n";
}
}

Execution synchronization

the barrier directive and the nowait clause

The barrier directive causes threads encoutering the barrier to wait until all the other threads in the same team have encountered the barrier.

1
2
3
4
5
6
7
8
#pragma omp parrllel
{
// all threads execute this
SomeCode();
#pragma omp barrier
// all threads execute this,but not before all threads have finished executing SomeCode()
SomeMoreCode();
}

Note:there is an implicit barrier at the end of each parallel block,at the end of each section for statement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#pragma omp parallel
{
#pragma omp for
for(int n=0; n<10; ++n) Work();

// This line is not reached before the for-loop is completely finished
SomeMoreCode();
}

// This line is reached only after all threads from
// the previous parallel block are finished.
CodeContinues();

#pragma omp parallel
{
#pragma omp for nowait
for(int n=0; n<10; ++n) Work();

// This line may be reached while some threads are still executing the for-loop.
SomeMoreCode();
}

// This line is reached only after all threads from
// the previous parallel block are finished.
CodeContinues();

the single and master constructs

The single construct specifies that the given statement/block is executed by only one thread. It is unspecified which thread. Other threads skip the statement/block and wait at an implicit barrier at the end of the construct.

1
2
3
4
5
6
7
8
9
#pragma omp parallel
{
Work1();
#pragma omp single
{
Work2();
}
Work3();
}

The master construct is similar, except that the statement/block is run by the master thread, and there is no implied barrier; other threads skip the construct without waiting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static const char* FindAnyNeedle(const char* haystack, size_t size, char needle)
{
const char* result = haystack+size;
#pragma omp parallel
{
unsigned num_iterations=0;
#pragma omp for
for(size_t p = 0; p < size; ++p)
{
++num_iterations;
if(haystack[p] == needle)
{
#pragma omp atomic write
result = haystack+p;
// Signal cancellation.
#pragma omp cancel for
}
// Check for cancellations signalled by other threads:
#pragma omp cancellation point for
}
// All threads reach here eventually; sooner if the cancellation was signalled.
printf("Thread %u: %u iterations completed\n", omp_get_thread_num(), num_iterations);
}
return result;
}

Loop nesting

this code will not do the excepted thing

1
2
3
4
5
6
7
8
9
#pragma omp parallel for
for(int y=0; y<25; ++y)
{
#pragma omp parallel for
for(int x=0; x<80; ++x)
{
tick(x,y);
}
}

solution

1
2
3
4
5
6
7
8
#pragma omp parallel for collapse(2)
for(int y=0; y<25; ++y)
{
for(int x=0; x<80; ++x)
{
tick(x,y);
}
}

Readmore

http://www.openmp.org/wp-content/uploads/openmp-4.5.pdf
https://en.wikipedia.org/wiki/OpenMP

1…45
carbo06@163.com

carbo06@163.com

About Linux C++ and routing algorithms.

45 日志
5 分类
18 标签
GitHub E-Mail
Friends
  • DingliYang
  • SongZhang
© 2018 carbo06@163.com
0%