一、測(cè)試對(duì)象

這次測(cè)試的對(duì)象是標(biāo)準(zhǔn)庫的vector，我們將會(huì)在vs2019 16.10和Linux + GCC 11.1上進(jìn)行測(cè)試。為了代碼寫著方便，我還會(huì)啟用c++17支持。

這次的疑問來自于《A Tour of C++》這本書，最近在重新翻閱本書的時(shí)候發(fā)現(xiàn)書里第九章給出了一個(gè)很有意思的建議：盡量少用reserve方法。

我們都知道reserve會(huì)提前分配足夠大的內(nèi)存來容納元素，這樣在push_back時(shí)可以減少內(nèi)存分配和元素移動(dòng)的次數(shù)，從而提高性能。所以習(xí)慣上如果我們知道vector中存儲(chǔ)元素的大致數(shù)量，就會(huì)使用reserve提前進(jìn)行內(nèi)存分配，這是典型的“空間換時(shí)間”。

而書中給出的理由僅僅是說vector的內(nèi)存分配器性能已經(jīng)很高，預(yù)分配往往是多此一舉，收效甚微。事實(shí)到底如何呢，性能問題光靠腦補(bǔ)是不能定位的，所以我們用實(shí)驗(yàn)結(jié)果說話。

二、使用模板函數(shù)生成測(cè)試

測(cè)試用例的設(shè)計(jì)很簡(jiǎn)單，我們定義普通vector和reserve過的vector，然后分別對(duì)其添加一定數(shù)量的元素（逐步從少到多）測(cè)試性能。

同時(shí)vector本身是泛型容器，所以為了測(cè)試的全面性我們需要測(cè)試兩至三種類型參數(shù)。

如果針對(duì)每一種情況寫測(cè)試函數(shù)，顯然違反了DRY原則，因?yàn)槌藇ector的類型參數(shù)不同，其他代碼幾乎是完全一樣的。

對(duì)于上面的需求，就需要模板測(cè)試函數(shù)登場(chǎng)了：

template <typename T, std::size_t length, bool is_reserve = true>
void bench_vector_reserve(benchmark::State& state)
{
	for (auto _ : state) {
		std::vector<T> container;
		if constexpr (is_reserve) {
			container.reserve(length);
		}
		for (std::size_t i = 0; i < length; ++i) {
			container.push_back(T{});
		}
	}
}

非常的簡(jiǎn)單，我們通過length控制插入的元素個(gè)數(shù)；is_reserve則負(fù)責(zé)控制是否預(yù)分配內(nèi)存，通過if constexpr可以生成reserve和不進(jìn)行任何操作的兩種代碼。

然后我們像往常一樣定義一個(gè)測(cè)試用例：

BENCHMARK(bench_vector_reserve<std::string,100>);

可是等我們編譯的時(shí)候卻報(bào)錯(cuò)了！

$ g++ test.cpp -lpthread -lbenchmark -lbenchmark_main

test.cpp:19:48: 錯(cuò)誤：宏“BENCHMARK”傳遞了 2 個(gè)參數(shù)，但只需要 1 個(gè)

   19 | BENCHMARK(bench_vector_reserve<std::string,100>);

      |                                                ^

In file included from a.cpp:1:

/usr/local/include/benchmark/benchmark.h:1146: 附注：macro "BENCHMARK" defined here

 1146 | #define BENCHMARK(n)                                     \

      | 

test.cpp:19:1: 錯(cuò)誤：‘BENCHMARK'不是一個(gè)類型名

   19 | BENCHMARK(bench_vector_reserve<std::string,100>);

原因是這樣的，在編譯器處理宏的時(shí)候?qū)嶋H上不會(huì)考慮c++語法，所以分割模板參數(shù)的逗號(hào)被識(shí)別成了分割宏參數(shù)的逗號(hào)，因此在宏處理器的眼里我們像是傳了兩個(gè)參數(shù)。這也說明了BENCHMARK是處理不了模板的。

不過別擔(dān)心，Google早就想到這種情況了，所以提供了BENCHMARK_TEMPLATE宏，我們只需要把模板名字和需要的類型參數(shù)依次傳給宏即可：

BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, 100);
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, 1000);
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, 10000);
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, 100000);
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, 100, false);
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, 1000, false);
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, 10000, false);
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, 100000, false);

現(xiàn)在就可以正常編譯運(yùn)行了：

可以看到reserve過的容器性能幾乎比默認(rèn)的快了一倍。

不過在揭曉為什么書上不推薦reserve的謎底之前，我們的代碼還有可以簡(jiǎn)化的地方。

三、定制測(cè)試參數(shù)

首當(dāng)其沖的問題其實(shí)還是違反了DRY原則——除了數(shù)字，其他內(nèi)容都是重復(fù)的。

看到這種代碼直覺就告訴我該做些改進(jìn)了。

Ranges接受start和end兩個(gè)int64_t類型的參數(shù)，默認(rèn)從start起每次累乘8，一直達(dá)到end。

通過RangeMultiplier我們可以改變乘數(shù)，比如從8改成10。

在這里我們的length參數(shù)其實(shí)是不必要的，所以代碼可以這樣改：

template <typename T, bool is_reserve = true>
void bench_vector_reserve(benchmark::State& state)
{
	for (auto _ : state) {
		std::vector<T> container;
		if constexpr (is_reserve) {
            // 通過range方法獲取傳入的參數(shù)
			container.reserve(state.range(0));
		}
		for (std::size_t i = 0; i < state.range(0); ++i) {
			container.push_back(T{});
		}
	}
}

BENCHMARK_TEMPLATE(bench_vector_reserve, std::string)->RangeMultiplier(10)->Range(10, 10000 * 10);
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, false)->RangeMultiplier(10)->Range(10, 10000 * 10);

現(xiàn)在我們測(cè)試的元素?cái)?shù)量是[10, 100, 1000, 10^4, 10^5]。

除此之外還有另一種叫“密集參數(shù)”的Ranges。google benchmark提供了DenseRange方法。

這個(gè)方法的原型如下：

DenseRange(int64_t start, int64_t end, int64_t step);

Ranges是累乘，而DenseRange是累加，因?yàn)槔鄢藭?huì)導(dǎo)致幾何級(jí)數(shù)的增長(zhǎng)，在數(shù)軸上的分布越來越稀疏，累加則看上去像是均勻分布的，因此累加的參數(shù)生成器被叫做密集參數(shù)生成器。

如果我們把測(cè)試用例這么改：

BENCHMARK_TEMPLATE(bench_vector_reserve, std::string)->DenseRange(1000, 100 * 100, 1000);

現(xiàn)在我們的length就是這樣一個(gè)序列：[1000，2000，3000， ...，9000，10000]。

關(guān)于自定義參數(shù)最后一個(gè)知識(shí)點(diǎn)是ArgsProduct?？疵志椭肋@是一個(gè)參數(shù)工廠。

ArgsProduct(const std::vector< std::vector<int64_t> >& arglists);

std::vector<int64_t>實(shí)際上就是一組參數(shù)，arglists就是多組參數(shù)的合集，他們之間會(huì)被求笛卡爾積，舉個(gè)例子：

BENCHMARK(BM_test)->ArgsProduct({ {"a", "b", "c", "d"}, {1, 2, 3, 4} });

// 等價(jià)于下面的
BENCHMARK(BM_test)->Args({"a", 1})
                  ->Args({"a", 2})
                  ->Args({"a", 3})
                  ->Args({"a", 4})
                  ->Args({"b", 1})
                  ->Args({"b", 2})
                  ->Args({"b", 3})
                  ...
                  ->Args({"d", 3})
                  ->Args({"d", 4})

我們可以看到參數(shù)工廠其實(shí)得自己手寫所有參數(shù)，那如果我想配合工廠使用Ranges呢？

沒問題，benchmark的開發(fā)者們?cè)缇拖氲搅?，所以提供了下面這些幫助函數(shù)：

benchmark::CreateRange(8, 128, /*multi=*/2)   // 生成：[8, 16, 32, 64, 128]
benchmark::CreateDenseRange(1, 6, /*step=*/1) // 生成：[1, 2, 3, 4, 5, 6]

如果換成我們的例子，就可以這樣寫：

BENCHMARK_TEMPLATE(bench_vector_reserve, std::string)->ArgsProduct({
    benchmark::CreateRange(10, 10000*10, 10)
});
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, false)->ArgsProduct({
    benchmark::CreateRange(10, 10000*10, 10)
});

借助僅僅兩行代碼我們就能生成數(shù)量可觀的測(cè)試用例：

當(dāng)然，這只是一個(gè)類型參數(shù)，實(shí)際上我們還有另外兩個(gè)類型需要測(cè)試。另外這是1.5.5新增的功能，如果你想嘗鮮得先升級(jí)google benchmark。

四、進(jìn)一步簡(jiǎn)化

通常做到上面那一步就足夠了，然而在這里我們還有優(yōu)化空間，因?yàn)槿绻覀儼哑渌麅蓚€(gè)測(cè)試用的類型加上，代碼是這樣的，MyClass的定義后面會(huì)給出：

BENCHMARK_TEMPLATE(bench_vector_reserve, std::string)->ArgsProduct({
    benchmark::CreateRange(10, 10000*10, 10)
});
BENCHMARK_TEMPLATE(bench_vector_reserve, std::string, false)->ArgsProduct({
    benchmark::CreateRange(10, 10000*10, 10)
});
BENCHMARK_TEMPLATE(bench_vector_reserve, std::size_t)->ArgsProduct({
    benchmark::CreateRange(10, 10000*10, 10)
});
BENCHMARK_TEMPLATE(bench_vector_reserve, std::size_t, false)->ArgsProduct({
    benchmark::CreateRange(10, 10000*10, 10)
});
BENCHMARK_TEMPLATE(bench_vector_reserve, MyClass)->ArgsProduct({
    benchmark::CreateRange(10, 10000*10, 10)
});
BENCHMARK_TEMPLATE(bench_vector_reserve, MyClass, false)->ArgsProduct({
    benchmark::CreateRange(10, 10000*10, 10)
});

你看見了什么？沒錯(cuò)，重復(fù)重復(fù)重復(fù)！我們又違背了DRY原則。

重復(fù)說不上什么十惡不赦，但能避免還是要避免的，所以我準(zhǔn)備用宏來簡(jiǎn)化這些代碼：

#define generate_test(type) \
	BENCHMARK_TEMPLATE(bench_vector_reserve, type)->ArgsProduct({benchmark::CreateRange(10, 100000, 10)}); \
	BENCHMARK_TEMPLATE(bench_vector_reserve, type, false)->ArgsProduct({benchmark::CreateRange(10, 100000, 10)});

generate_test(std::string);
generate_test(std::size_t);
generate_test(MyClass);

這下舒服多了。

接著來看我們的MyClass，我們的MyClass包含幾個(gè)虛函數(shù)，禁止移動(dòng)賦值，同時(shí)被刻意設(shè)計(jì)成了非平凡復(fù)制，這樣的類型可以說是繞過了標(biāo)準(zhǔn)庫容器設(shè)計(jì)的大部分優(yōu)化措施，算是個(gè)妥妥的反面教材，希望你的項(xiàng)目里盡量不要出現(xiàn)這種東西：

class MyClass {
public:
	long i = 2L;
    MyClass() { i = 2L; }
	virtual ~MyClass() {}
	virtual long get() { return i; }
	MyClass& operator=(MyClass&&) = delete;
	MyClass(const MyClass& obj) {
		i = obj.i;
	}
	MyClass& operator=(const MyClass& obj) {
		i = obj.i;
	}
};

這個(gè)類其實(shí)就是針對(duì)內(nèi)存分配器實(shí)現(xiàn)的，vector在重新進(jìn)行內(nèi)存分配后很可能靠移動(dòng)語義或者memmove來移動(dòng)數(shù)據(jù)，這兩者將導(dǎo)致重新分配內(nèi)存導(dǎo)致的性能損失變小，不利于我們觀察vector的行為，所以我定制了這個(gè)類。

這是Windows上的結(jié)果，Linux上也差不多，到目前為止我們看到reserve過的vector有著驚人的性能，那書里說的到底是怎么回事呢？

五、揭曉答案

實(shí)際上上面測(cè)試的都是我們明確知道vector一定會(huì)被插入N個(gè)元素不多不少的情況。

然而這種情況其實(shí)在開發(fā)中是不多見的，更多的時(shí)候我們只能得到vector里元素?cái)?shù)量的平均數(shù)、眾數(shù)，甚至是一個(gè)沒什么可靠依據(jù)的經(jīng)驗(yàn)值。

所以試想一下這種情況，reserve給的參數(shù)是1000，而我的vector總是會(huì)插入1001~1005個(gè)參數(shù)，顯然1000是不夠的，除了reserve外還會(huì)進(jìn)行一次內(nèi)存分配，而且這次分配后很可能還需要把原先的元素都轉(zhuǎn)移過去（realloc不是總能找到合適的位置擴(kuò)展已有內(nèi)存，而且像MyClass那樣的類在c++17中是不能bitwise復(fù)制的），那么這樣的開銷究竟如何呢？我們還是拿測(cè)試說話。

篇幅有限，所以我只能簡(jiǎn)單模擬一下上述情況：

template <typename T, bool is_reserve = true>
void bench_vector_reserve(benchmark::State& state)
{
	for (auto _ : state) {
		std::vector<T> container;
		if constexpr (is_reserve) {
			container.reserve(state.range(0));
		}
        // 每次多插入兩個(gè)元素，這樣多半會(huì)導(dǎo)致一次內(nèi)存分配（當(dāng)然不保證一定會(huì)）
		for (std::size_t i = 0; i < state.range(0)+2; ++i) {
			container.push_back(T{});
		}
	}
}

編譯均使用Release模式和默認(rèn)的優(yōu)化級(jí)別，這是Linux上的測(cè)試結(jié)果：

和我們預(yù)期的一樣，多出來的一次內(nèi)存分配使reserve帶來的性能優(yōu)勢(shì)蕩然無存。

有意思的是Windows上的結(jié)果：

奇怪的事情發(fā)生了，雖說多出的一次分配縮小了性能差距，但reserve任然帶來了明顯的優(yōu)勢(shì)。

這里我就不賣關(guān)子了，我們直接看vector的源碼。

首先是GCC11.1的，代碼在/usr/include/c++/11.1.0/bits目錄下，分散在vector.tcc和stl_vector.h中，其中push_back在容器內(nèi)存不夠的時(shí)候會(huì)用_M_realloc_insert重新分配足夠的內(nèi)存，這個(gè)函數(shù)在vector.tcc的432行有定義，使用_M_check_len計(jì)算重新分配的內(nèi)存大小。

_M_check_len是關(guān)鍵，定義在stl_vector.h的1756行：

// Called by _M_fill_insert, _M_insert_aux etc.
size_type
_M_check_len(size_type __n, const char* __s) const
{
	if (max_size() - size() < __n)
	  __throw_length_error(__N(__s));

	const size_type __len = size() + (std::max)(size(), __n);
	return (__len < size() || __len > max_size()) ? max_size() : __len;
}

__n在push_back的時(shí)候是1，所以不難看出GCC的vector的擴(kuò)容策略是每次擴(kuò)容一倍。

vs2019的stl實(shí)現(xiàn)開源在了github。關(guān)鍵代碼在這里，push_back在內(nèi)存不夠的時(shí)候會(huì)調(diào)用_Emplace_reallocate，里面會(huì)調(diào)用_Calculate_growth計(jì)算重新分配的內(nèi)存大小：

_CONSTEXPR20_CONTAINER size_type _Calculate_growth(const size_type _Newsize) const {
    // given _Oldcapacity and _Newsize, calculate geometric growth
    const size_type _Oldcapacity = capacity();
    const auto _Max              = max_size();

    if (_Oldcapacity > _Max - _Oldcapacity / 2) {
        return _Max; // geometric growth would overflow
    }

    const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2; // 關(guān)鍵代碼

    if (_Geometric < _Newsize) {
        return _Newsize; // geometric growth would be insufficient
    }

    return _Geometric; // geometric growth is sufficient
}

_Newsize相當(dāng)于前面GCC的__n，在push_back的時(shí)候是1，所以不難看出vs2019的vector增長(zhǎng)策略是每次擴(kuò)容0.5倍。

除此之外兩者的剩余部分大同小異，都是先分配新內(nèi)存，然后在新內(nèi)存里構(gòu)建要插入的元素，再把其他元素移動(dòng)到新內(nèi)存里，就連移動(dòng)元素的方式也差不多，都是先嘗試memmove，接著試試移動(dòng)語義，最后讓復(fù)制操作兜底。

那么兩者肉眼可見的區(qū)別就只有擴(kuò)容策略這一條了。所以這會(huì)帶來什么影響呢？看個(gè)例子：

#include <iostream>
#include <vector>

void test1(std::size_t len)
{
	std::vector<int> v1, v2;
	v2.reserve(len);
	for (std::size_t i = 0; i < len; ++i) {
		v1.push_back(1);
		v2.push_back(1);
	}
	std::cout << "v1: " << v1.capacity() << '\n';
	std::cout << "v2: " << v2.capacity() << '\n';
}

void test2(std::size_t len)
{
	std::vector<int> v1, v2;
	v2.reserve(len);
	for (std::size_t i = 0; i < len + 1; ++i) {
		v1.push_back(1);
		v2.push_back(1);
	}
	std::cout << "v1: " << v1.capacity() << '\n';
	std::cout << "v2: " << v2.capacity() << '\n';
}

int main()
{
	test1(100000);
	test2(100000);
}

/*
vs2019的運(yùn)行結(jié)果:
v1: 138255
v2: 100000
v1: 138255
v2: 150000

GCC11.1.0的結(jié)果:
v1: 131072
v2: 100000
v1: 131072
v2: 200000
*/

如果是一個(gè)有10萬個(gè)元素的vector想要擴(kuò)容，GCC就會(huì)比vs多分配50000個(gè)元素需要的內(nèi)存，分配如此多的內(nèi)存需要花費(fèi)更多的時(shí)間，即使reserve帶來了性能優(yōu)勢(shì)在這一步也都揮霍的差不多了。

激進(jìn)的擴(kuò)容策略讓GCC出現(xiàn)了明顯的性能波動(dòng)，不過這只是出現(xiàn)上面那樣測(cè)試結(jié)果的原因之一，兩個(gè)標(biāo)準(zhǔn)庫的allocator實(shí)現(xiàn)上的區(qū)別也可能是其中一個(gè)原因。不過msvc的分配器實(shí)現(xiàn)并不公開，所以最終是什么導(dǎo)致了上述的結(jié)果并不能輕易斷言。

六、總結(jié)

我們學(xué)習(xí)了如何使用模板和參數(shù)生成器創(chuàng)建大量測(cè)試用例，以提高編寫測(cè)試的效率。

我們還順便了解了vector.reserve對(duì)性能的影響，總結(jié)規(guī)律有幾條：

1.如果明確知道vector要存放元素的具體數(shù)量，推薦reserve，性能提升是有目共睹的；

2.否則你不應(yīng)該使用reserve，一來有提前優(yōu)化之嫌，二是在使用libstdc++的程序上會(huì)產(chǎn)生較大的性能波動(dòng)；

3.接上一條，reserve使用不當(dāng)還會(huì)造成內(nèi)存的浪費(fèi)。

看來《A Tour of C++》的作者只說對(duì)了一半，這也證明了性能問題不能靠臆斷，一定要靠測(cè)試來定位、解決。

以上就是淺談c++性能測(cè)試工具google benchmark的詳細(xì)內(nèi)容，更多關(guān)于c++性能測(cè)試工具google benchmark的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論