C++

平时使用C++的过程中，关联容器std::map、std::set经常被用到，本文分享几个使用方面的小技巧，虽然举例时均使用std::map，但结论同样适用于std::set。

注意迭代器失效问题

void f(std::map<int, int> &m) {
    for (auto it = m.begin(); it != m.end(); ++it) {
        if (it->first % 2 == 0)
            m.erase(it);
    }
}

上述代码有什么问题吗？有！在循环中使用erase会导致迭代器失效，使用失效的迭代器再进行诸如++it的操作就会导致错误，一种正确的使用方法如下

void f(std::map<int, int> &m) {
    for (auto it = m.begin(); it != m.end();) {
        if (it->first % 2 == 0) {
            it = m.erase(it);
        } else {
            ++it;
        }
    }
}

在range based for loop中谨慎地指定类型

std::size_t test_for1(std::map<int, std::string> &m) {
    std::size_t total = 0;
    for (const auto &v : m) {
        total += v.second.size();
    }
    return total;
}

std::size_t test_for2(std::map<int, std::string> &m) {
    std::size_t total = 0;
    for (const std::pair<int, std::string> &v : m) {
        total += v.second.size();
    }
    return total;
}

上述两段遍历std::map的代码有哪里不同呢？原来进行遍历操作时指定的引用类型不同！一般情况下我们不会写成第二种方式，但在理论上第二种写法确实会比第一种慢一些，原因是std::map<int, std::string>容器中保存的是std::map<int, std::string>::value_type，即std::pair<const int, std::string>，所以当使用const std::pair<int, std::string> &类型用于遍历时，每个元素都会被复制一份，这份开销可能不大，但一定是不必要的。对标准库容器进行只读遍历时，一般使用const auto &即可，但如果你的公司编码规范要求不能使用auto，出现一个罚款100元，要记得使用正确的类型。

快速创建容器的思路

我想根据一组数据创建一个std::map，怎么插入数据性能更好呢？本文测试了将一千万条数据放入容器时，下述几种操作方式的效率，得出了耗时(Cost)和元素比较次数(Compare)的表格，测试代码放到文章最后

  • insert_range: 使用m.insert(first, last)的接口直接创建
  • insert: 使用m.insert(data)逐个放入
  • insert_back: 使用m.insert(m.end(), data)逐个放入
  • sort_and_insert: 先对数据排序，再使用m.insert(data)逐个放入
  • sort_insert_back: 先对数据排序，再使用m.insert(m.end(), data)逐个放入

结果如下，对于需要排序的方式，Cost包含排序占用的时间，但Compare不包含排序时的比较次数

Test MethodCost(ms)Compares
sort_insert_back124620000000
sort_and_insert2525430640011
insert12116242834184
insert_back12309252833970
insert_range11939252833970
sort_only9110

从表中惊奇地发现，先排序再构建std::map竟然比直接构建快十倍，这是为什么呢？

一般来说，C++标准库常用红黑树这种数据结构来实现std::map，当添加有序的新数据时，该数据恰好应当被放到最后一个位置，因此sort_insert_back可以减少很多次因查找带来的比较次数。sort_and_insert没有提示应当放到哪个位置，所以比较次数增加了约20倍，但为什么耗时只增加一倍呢？这件事应当从缓存命中的方面思考，考虑逐步向一棵树上新增有序数据时，每次查找几乎都是沿着树的右边界进行，因此其大概率可以命中高速缓存，所以虽然比较次数很多但效率尚可，当然这与具体硬件性能有关，可能换一个CPU后耗时还会增加。

对于未排序的数据，向std::map新增数据时，首先需要查找插入的位置，然后调整树的结构保持平衡，当数据量变大时，这个过程命中高速缓存的可能性就很小了，所以耗时会急剧增加。在实际应用中，需要综合考虑多种指标来确定优化方案，例如需要从文件中导入数据到某个数据结构中，瓶颈很可能在文件IO上面，与缓存未命中相比，读文件的耗时那就高太多了。

并发访问时通过延迟销毁降低锁粒度

假设你正在写一个支持多线程访问的高性能内存数据库，在处理flushdb指令时写下了下述代码

std::map<std::string, std::string> db;
std::mutex mtx;

void flushdb() {
    std::lock_guard<std::mutex> lg(mtx);
    db.clear();
}

这份代码没有任何错误，且格式规范、逻辑清晰，但当需要清理一个数据量很大的数据库时，整个数据库服务仿佛被冻结了，数百毫秒无法提供服务！原因是清理整个std::map可能非常耗时，导致清理过程中新的读写操作都无法进行。此时若通过swap将清理操作推迟到锁外进行，则可以立刻开始处理新的请求。注意：清理操作被推迟，大量新的数据被写入后，可能有短时间内存占用超出预期的情况，请谨慎斟酌。

void flushdb_delay() {
    std::map<std::string, std::string> tmp;

    mtx.lock();
    tmp.swap(db);
    mtx.unlock();

    // 即使不调用clear也可被析构函数释放
    tmp.clear();
}

同理，删除元素也可以将销毁操作推迟，一般情况下释放一条数据不会有太多的耗时，除非数据本身非常大（比如长度1G的字符串）或者结构复杂（比如包含数万条数据的std::list，数据不多但逐个销毁时会因无法命中高速缓存而进度缓慢）等，在实际应用中应酌情考虑。

void del(const std::string &key) {
    std::lock_guard<std::mutex> lg(mtx);
    db.erase(key);
}

void del_delay(const std::string &key) {
    std::map<std::string, std::string>::node_type node;

    mtx.lock();
    auto it = db.find(key);
    if (it != db.end())
        node = db.extract(it);
    mtx.unlock();
}

结语

在学习和工作中，无需进行过早的优化，不然可能会花费过多的精力在用处不大的地方，但当问题发生时，我们应当有足够的知识储备，能快速地发现问题并提出解决方案，这是目前的我比较期待的生活状态。

附录1

#include <vector>
#include <map>
#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iomanip>
#include <string>

using namespace std;

long compare_count{0};

template<typename T>
struct CountCompare {
    bool operator()(const T &l, const T &r) const {
        ++compare_count;
        return l < r;
    }
};

using MapType = std::map<int, int, CountCompare<int>>;
using ValueType = std::pair<int, int>;

long now() {
    using namespace std::chrono;
    auto d = steady_clock::now().time_since_epoch();
    return duration_cast<milliseconds>(d).count();
}

void insert_back(std::vector<ValueType> &data, MapType &m) {
    for (const auto &d : data)
        m.insert(m.end(), d);
}

void sort_insert_back(std::vector<ValueType> &data, MapType &m) {
    std::sort(data.begin(), data.end());
    for (const auto &d : data)
        m.insert(m.end(), d);
}

void insert(std::vector<ValueType> &data, MapType &m) {
    for (const auto &d : data)
        m.insert(d);
}

void sort_and_insert(std::vector<ValueType> &data, MapType &m) {
    std::sort(data.begin(), data.end());
    for (const auto &d : data)
        m.insert(d);
}

void insert_range(std::vector<ValueType> &data, MapType &m) {
    m.insert(data.begin(), data.end());
}

void sort_only(std::vector<ValueType> &data, MapType &) {
    std::sort(data.begin(), data.end());
}

using test_func_t = void(*)(std::vector<ValueType> &, MapType &);

void do_test(const char *test_type, test_func_t func, const std::vector<ValueType> &data) {
    std::vector<ValueType> v = data;
    MapType m;
    long start = now();
    compare_count = 0;

    func(v, m);

    long cost = now() - start;
    std::cout << "| " << std::setw(18) << test_type <<
        " | " << std::setw(16) << cost << " | "
        << std::setw(16) << compare_count << " |\n";
}

void test_header() {
    std::cout << "| " << std::setw(18) << "Test Method" <<
        " | " << std::setw(16) << "Cost(ms)" << " | "
        << std::setw(16) << "Compares" << " |\n";

    std::cout << "| " << std::string(18, '-') <<
        " | " << std::string(16, '-') << " | "
        << std::string(16, '-') << " |\n";
}

#define TEST_MAP(func, data) do_test(#func, func, data)

int test_create_map() {
    constexpr int SIZE = 10000001;
    std::vector<ValueType> data;
    data.reserve(SIZE);
    for (int i = 0; i < SIZE; i++)
        data.push_back({i, i});

    std::mt19937_64 mt(12345);
    std::shuffle(data.begin(), data.end(), mt);

    test_header();

    // 第一次不计入统计，以避免page fault影响
    TEST_MAP(sort_insert_back, data);

    TEST_MAP(sort_insert_back, data);
    TEST_MAP(sort_and_insert, data);
    TEST_MAP(insert, data);
    TEST_MAP(insert_back, data);
    TEST_MAP(insert_range, data);
    TEST_MAP(sort_only, data);

    return 0;
}

int main() {
    return test_create_map();
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注